Unmixed generalized binomial edge ideals
In the paper Generalized Cohen-Macaulay binomial edge ideals by Luca Amata, Marilena Crupi and Giancarlo Rinaldo, (section 3), we present the following table representing the cardinalities of generalized binomial edge ideals \(J_{G,m}\) on \(n\) vertices that are unmixed for all \(3\leq m\leq 10\) and \(4\leq n\leq 10\)
In this file we give the set of unmixed graphs in nauty format. Moreover we provide the implementation in C++ of the algorithms described in (1), downloadable from here.
We refer to the article for the notation and results. In this page you will find a description of the algorithm and an implementation with an example of computation
Description of the algorithm
The first tool 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.
In the paper we observed that if \(J_{G,m}\) is unmixed then \(G\) is \(m-1\)-connected, and in particular deg\((v)\geq m-1\) for any vertex \(v\). It is not possible in nauty to generate \(m-1\)-connected graphs. But we can generate biconnected ones (by -C) and with a lower bound on the minimum degree (-dx).
E.g. suppose that we are interested in all the unmixed graphs with 4 vertices, and \(m=3\) we can simply run:
nauty-geng -C -d2 4
If we want to filter the unmixed ones we filter the output with
nauty-geng -C -d2 4 |isGunmixed 4
Here the unmixed ones are exactly 3, that is the graphs are all unmixed. In fact these graphs induce an ideal of the type \(J_{G,n-1}\). See Proposition 1.4 of the paper.
For the unmixedness we modified the algorithm implemented in C++ in the paper \(S_2\)-condition and Cohen-Macaulay binomial edge ideals by Alberto Lerda, Carla Mascia, Giancarlo Rinaldo and Francesco Romeo, defined the first time in Algorithm 1 described in the paper Cohen-Macaulay binomial edge ideals of small deviation. Here we compute the non-empty cutsets while the property \(c(T)=\frac{|T|}{m-1}+1\) is satisfied and we stop returning false as soon as it is not satisfied.
Implementation and the case n=4, m=3
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 and 20.04). It has been tested also on
- Windows 10 (Home Edition) under Windows Subsystem for Linux WSL2 x86_64 with Ubuntu 20.04 installed;
- MacOS Monterey with MacPorts.
It uses standard library and nauty package. To use it you have to download, and extract by
tar -xzvf generalizedunmixed.tgz
move to the folder
cd generalizedunmixed
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 4 vertices and let m=3.
We show the input and the output in the console. We generate the graphs related to unmixed generalized binomial edge ideals.
scripts/generate_gunmixed.sh 3 4
The output file is outs/g4/g3_4unmixed.nty and it contains 3 graphs in nauty format. Unfortunately this ASCII format is compact but not human-readable. Hence we use the following commands that translate nauty in dot version (see DOT) and show it on the console.
scripts/nty2gv.sh outs/g4/g3_4unmixed
cat outs/g4/g3_4unmixed.dot
The corresponding output is
graph G {1--3;2--3;1--4;2--4}
graph G {1--3;2--3;1--4;2--4;3--4}
graph G {1--2;1--3;2--3;1--4;2--4;3--4}
We observe that the graphs are: the cycle \(C_4\), the diamond graph (see Diamond graph), and the complete graph \(K_4\). That are all the graphs with 4 vertices with \(\deg(v)\geq 2\), as expected.