Double Markovian relations

This page provides the lists of graph pairs from Challenge 2.17 in our paper The geometry of Gaussian double Markovian distributions.

In the table below, the “tasks” for ground set sizes 3, 4 and 5 are provided in separate files. There may be comment lines prefixed with a # symbol. Each record consists of three lines: R = followed by the CI structure in the canonical variable ordering, G = followed by the list of edges of the first graph and H = followed by the list of edges of the second graph. Records are separated by an empty line.

NOTE: The challenge as stated in v1 of the arXiv paper is wrong (a fault in symmetry reduction). Instead of 3+21+231 we have 4+55+2644 models up to symmetry and the decomposition theorem 2.17. The upcoming v2 will come with corrected numbers.

# Have 8 connected graph pairs to consider
# There are 4 models up to twisted symmetry
R = 001111
G = 1-3, 2-3
H = 1-3, 2-3

R = 011011
G = 1-3, 2-3
H = 1-2, 2-3


This data is computed as follows: first all connected graphs on the given number of vertices are enumerated and representatives modulo the symmetric group (isomorphic graphs yield isomorphic CI structures) are computed. For all pairs of graphs (G,H) where G is reduced modulo symmetry and H$ is arbitrary connected, the CI structures are computed and reduced modulo the twisted symmetric group (permutation isomorphy and duality). For each resulting orbit of CI structures, one graph pair is recorded in the file. Deciding smoothness for this graph pair settles the whole orbit.

Note that in these lists different CI structures may still have the same model because double Markovian relations are not complete.

tasks-3.log 4
tasks-4.log 55
tasks-5.log 2644