The Cohen-Macaulay binomial edge ideals of graphs with n ≤ 12

In the paper \(S_2\)-condition and Cohen-Macaulay binomial edge ideals by Alberto Lerda, Carla Mascia, Giancarlo Rinaldo and Francesco Romeo, (section 5), we present the following

Theorem

Let \(G\) be a graph on \([n]\), with \(n\leq 12\). The following conditions are equivalent:

\(S/J_G\) is Cohen-Macaulay;
\(S/J_G\) satisfies \(S_2\)-condition;
\(G\) is accessible;
\(G\) is Strongly unmixed.

In this file we give the set of graphs satisfying the equivalent conditions of the Theorem in nauty format. Moreover we provide the implementation in C++ of the algorithms computing conditions (2), (3) and (4) downloadable from here.

We refer to the article for an in-depth description of the notation and results. In this page you will find a description of the algorithm and an implementation with an example of computation. In this section we also provide an example of computation necessary for the proof of Proposition 2.9.

Proof and description of the algorithm

Proof

Fixed the number of vertices \(n\), the proof can be synthesized in 5 steps:

compute all non isomorphic graphs on \([n]\);
keep only the graphs which are indecomposable and unmixed;
keep only the ones that are accessible;
keep only the ones that are strongly unmixed;
verify that the graphs obtained from step 3 and 4 are the same.

In the next sections we will discuss the main structure of the algorithms we implemented:

Some details on the tools
Unmixedness
Accessibility
Strongly unmixedness
\(S_2\)

Some details on the tools

The first tools we used is nauty, which generates all non isomorphic graphs with a fixed number of vertices and outputs them in a text format that we can read in our own tools.

We build a collection of utilities which follows the Unix philosophy

Make each program do one thing well
Expect the output of every program to become the input to another, as yet unknown, program
(The Art of Unix Programming)

There are multiple tools isS2, isAccessible, isUnmixed, etc each of which expect input and generate output in the format of nauty, this way we improve composability, we can combine those tools in any order (using Unix pipelines).

E.g. suppose that we are interested in all the unmixed graphs with 9 vertices, we can simply run:

nauty-geng 9 -c | isUnmixed

Altough the previous command works, nowadays it would be interesting to be able to use multiple cores to solve the problem. GNU parallel lets us run a program in parallel without having to deal with pthread,fork,C++ threads or similar explicitly. Using parallel the previous code becomes

nauty-geng 9 -c | parallel --pipe -j8 --N50000 isUnmixed

Let’s analyze the options of parallel

--pipe means that the input is read from the pipe (and not from a file)
-j8 means that 8 is the maximum number of jobs that will run in parallel
--N50000 means that 50000 graphs will be sent to each process
isUnmixed is the command we want to run

Unmixedness

For the unmixedness we implemented Algorithm 1 described in the paper Cohen-Macaulay binomial edge ideals of small deviation. This is the most critical part of the sequence of tools, it is rather slow and it gets a lot of graphs as input (from all the non isomorphic connected graphs we have only filtered away the undecomposable one).

In particular, the main problem is that we have to visit the graph for each subset of vertices to find the cutsets. Obviously, we visit the graph only one time for a fixed subset of vertices, we memorize the result and reuse it every time we need it. Moreover, we don’t compute all the cutset at the begininng, every time we find a cutset we verify the property \(c(T)=|T|+1\) and we stop as soon as possibile.

Accessibility

To verify the accessibility, again, we have to iterate over each subset to find the cutsets. As well as the unmixedness, we implemented the accessibility using memoization, we keep a vector where each index correspond to a subset of vertices (in C++ this can be implemented easily thanks to bitwise operations) and iterate over them in inclusion order (which is the usual ordering between numbers, removing a vertex from a subset of vertices means removing a 1 in the bitmask, which gives a smaller number). We use the fact that the property of being an accessible system is defined in an inductive way.

Strongly unmixedness

The implementation of strongly unmixedness, thank to recursion, follows exactly the definition. It could have been optimized more, but for what we need it is enough.

First of all, we verify whether the connected components are complete graphs. To do this we look at the number of edges in each connected component and we compare it with the number of edges of the complete graph (\(q=p(p-1)/2\)). If this is true we return true.

Then, we verify whether \(J_G\) is unmixed, if this is not true we return false

Finally we have to look for a cutvertex such that \(G\setminus\{v\}\), \(G_\bar{v}\setminus\{v\}\) and \(G_\bar{v}\) are strongly unmixed. And in this step we use recursion.

\(S_2\)

We can summarize the algorithm in the following steps

Iterate over the dimension of the faces from \(-1\) (the empty set face) to the dimension of the complex-1
For each size we generate all faces which belong to the complex
For each face we generate the link
Finally, we check if the link is connected looking at the 1-skeleton

We didin’t need \(S_2\) for the purpose of the proof, it will be useful for the research. It is rather difficult to understand why a given ideal is not \(S_2\), for this reason a computer program is useful.

Implementation and the case n=7

In this section we give the results of our computation by the routines that we implemented in C++ (using g++ of gcc ver. 7.5) whose sources are downloadable from here.

The program in C++ has been developed under Linux on Ubuntu distribution (tested on versions 18.04). It uses standard library and nauty package and with some effort can work on any platforms. To use it you have to download, and extract by

tar -xzvf s2binomials.tgz

move to the folder

cd s2binomials

and then compile the c++ program by

make

Moreover the program use an external one that is nauty-geng (that generates graphs up to isomorphisms). So it expects to have the binary file with this name in the system.

As an example we focus on the set of connected graphs with 7 vertices. We verify

The equivalence between accessible, \(S_2\) and strongly unmixed ones
A minimal face with respect to the dimension of an unmixed graph foe which the corresponding link is not connected (Proposition 2.9).

We show the input and the output in the console. We first generate the graphs related to unmixed binomial edge ideals.


scripts/generate_unmixed.sh 7

The output file is outs/g7/g7unmixed.nty and it contains 23 graphs in nauty format.

Now we filter graphs in the file with respect to the 3 conditions: accessible, \(S_2\) and strongly unmixed. The 3 files obtained are:outs/g7/g7accessible.nty, outs/g7/g7s2.nty and outs/g7/g7stronglyUnmixed.nty. Then we compare the 3 files and we observe that are identical. Here is the input


scripts/compare_accessible_s2_stronglyunmixed.sh 7

and the corresponding output

 
For each class of graphs the first line contains the time needed to complete the computation while the second one shows the number of graphs which have been found.

Accessible:
0:00.03 real,0.01 user,0.00 sys
15
S2:
0:00.09 real,0.09 user,0.00 sys
15
Strongly unmixed:
0:00.01 real,0.00 user,0.00 sys
15
File differences (there should be no differences)

We observe that there are 15 accessible/S2/strongly unmixed graphs and the 3 files obtained are identical since thre is no extra output.

Now, for all graphs that are in g7unmixed.nty that are not \(S_2\) we compute a minimal face with respect to the dimension whose corresponding link is not connected. The input is


scripts/checkS2.sh 7

and the corresponding output is

 
--------------
The face
x:    3 4 5     
y:    3 4 5     
of dimension 5 has a disconnected link with facets
x:              
y:1 2           

x:          6 7 
y:              

with graph G {1--5;2--5;1--6;2--6;3--6;1--7;2--7;4--7}
--------------
The face
x:          6   
y:1 2 3 4   6   
of dimension 5 has a disconnected link with facets
x:1 2           
y:              

x:            7 
y:        5     

with graph G {1--5;2--5;3--6;4--6;5--6;1--7;2--7;3--7;5--7;6--7}
--------------
The face
x:        5     
y:1 2 3 4 5     
of dimension 5 has a disconnected link with facets
x:    3 4       
y:              

x:          6 7 
y:              

with graph G {1--5;2--5;3--6;4--6;5--6;1--7;2--7;3--7;4--7;5--7;6--7}
--------------
The face
x:        5     
y:1 2 3 4 5     
of dimension 5 has a disconnected link with facets
x:    3 4       
y:              

x:          6 7 
y:              

with graph G {1--5;2--5;1--6;2--6;3--6;4--6;5--6;1--7;2--7;3--7;4--7;5--7;6--7}
--------------
The face
x:    3 4       
y:1 2 3 4       
of dimension 5 has a disconnected link with facets
x:1 2           
y:              

x:        5 6   
y:              

with graph G {1--5;2--5;3--5;1--6;2--6;3--6;5--6;1--7;2--7;3--7;4--7;5--7;6--7}
--------------
The face
x:      4       
y:1 2 3 4       
of dimension 4 has a disconnected link with facets
x:1 2 3         
y:              

x:        5 6 7 
y:              

with graph G {1--5;2--5;3--5;4--5;1--6;2--6;3--6;4--6;5--6;1--7;2--7;3--7;4--7;5--7;6--7}
--------------
The face
x:        5     
y:1 2 3 4 5     
of dimension 5 has a disconnected link with facets
x:    3 4       
y:              

x:          6 7 
y:              

with graph G {1--4;2--5;1--6;2--6;3--6;4--6;5--6;1--7;2--7;3--7;4--7;5--7;6--7}
--------------
The face
x:        5     
y:1 2 3 4 5     
of dimension 5 has a disconnected link with facets
x:  2 3         
y:              

x:          6 7 
y:              

with graph G {1--4;1--5;4--5;1--6;2--6;3--6;4--6;5--6;1--7;2--7;3--7;4--7;5--7;6--7}

As expected the graphs are \(23-15=8\). Morever the 6th is (See Example 2.10 and Figure 1):