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.