Accessible blocks with whiskers
In Section 4 of the paper Cohen-Macaulay binomial edge ideals of small graphs by Davide Bolognini, Antonio Macchia, Giancarlo Rinaldo and Francesco Strazzanti, we prove
Theorem. Let \(G\) be one of the following
- A graph with \(|V(G)|\leq 15\);
- \(G=\bar{B}\) a block with whiskers where \(|V(B)|= 11\).
Then the conditions below are equivalent:
- \(R/J_G\) is Cohen-Macaulay;
- \(J_G\) is strongly unmixed;
- \(R/J_G\) satisfies Serre's \(S_2\)-condition;
- \(G\) is accessible.
A key tool for the proof of this result is the following
Algorithm
We refer to Section 4 of the article for the notation and for an in-depth description of the algorithm. Here we describe the implementation through some examples, we show how to install the software and the computational results. All the computations shown here have been performed using a laptop with a Celeron i5 CPU and Ubuntu 22.04 operating system.
Implementation of the algorithm
We choose the inputs \(n\) and \(k\), for instance \(n=5\) and \(k=4\).
Line 2: Generation of the blocks
The first tool we used is Nauty, which generates all non-isomorphic graphs with a given number of vertices and outputs them in a string format.
Nauty generates blocks with bounded vertex degree. We implemented a customized Prune function to remove the graphs having free vertices. From now on suppose we are in the bin folder generated after the installation. Running the commands
cd bin
./graphsNoFreeVertices 5 -C -d3
Nauty generates all graphs that are blocks with 5 vertices, with vertices of degree at least 3, and without free vertices. In this case the output is a single graph, the wheel graph \(W_5\), with edge set \(E(W_5) = \{\{0,1\}, \{1,2\}, \{2,3\}, \{1,3\}, \{0,4\}, \{1,4\}, \{2,4\}, \{3,4\}\}\).
Lines 4-5: Computation of the cut sets of \(B\) given \(k\)
We compute the cut sets of every block \(B\) generated in the previous step and, for each cut set \(T\) of \(B\), we compute the number \(k_T\) of whiskers to attach to the vertices of \(T\) so that the binomial edge ideal \(J_{\bar{B}}\) is unmixed. In particular, if \(k_T\leq 0\) or \(k_T>k\), where \(k\) is the number of whisker to attach to \(B\), we discard \(B\).
This computation can be rather slow for a large number of graphs, thus we implemented this step in C++.
In the example above with \(n=5\), we choose to add \(k=4\) whiskers; running the following line we obtain the cuts sets of the wheel graph \(W_5\):
./graphsNoFreeVertices -C -d3 5 | ./isBlockCandidate 4
The output is:
(set({0,1,4}),2),(set({2,3,4}),2),
D]{
where the first line is a list of pairs \((T, k_T)\) related to the graph in the second line; here the string "D]{" represents the graph \(W_5\). In this case we need to add two whiskers to the vertices of each of the cut sets \(\{0,1,4\}\) and \(\{2,3,4\}\) in order to have \(J_{\bar{B}}\) unmixed. Observe that the vertex \(4\) is the central vertex of the wheel, and by [LMRR, Example 3] we know that the binomial edge ideal of \(W_5\) with 4 whiskers attached to the vertices \(\{0,1,2,3\}\) is Cohen-Macaulay.
Lines 6-15: Adding \(k\) whiskers to a block
This routine takes as input a block \(B\) and the set of pairs \((T,k_T)\) as defined in line 4. Now we want to find the subsets of \(k\) vertices of \(B\) to which we will then add whiskers. To this aim, in line 6 we define the set \(V\) of vertices of \(B\) with at most \(\lfloor \frac{n+k}{2} \rfloor - 2\) neighbors. Then for every subset \(S \subset V\) of cardinality \(k\), we check several conditions; in particular it is important that \(S\cap T\) has exactly \(k_T\) elements. We implemented this part of the algorithm in Python and used the open-source library igraph, which is efficient in the manipulation of graphs.
The smallest values of \(n\) and \(k\) that produce a non-empty list \(\bar{\mathcal B}\) are the following
./graphsNoFreeVertices -C 9 -d3 |./isBlockCandidate 5 | ./AddWhiskers.py 9 5 > b9_w5.nty
./graphsNoFreeVertices -C 9 -d3 |./isBlockCandidate 6 | ./AddWhiskers.py 9 6 > b9_w6.nty
In \(\sim 10^2\) seconds we obtain the file b9_w5.nty, containing two blocks with 9 vertices and 5 whiskers, and the file b9_w6.nty, containing two blocks with 9 vertices and 6 whiskers. The selection process operated here is extremely efficient since the binomial edge ideal of each of the blocks with whiskers in \(\bar{\mathcal B}\) is unmixed (in Table 1 of the paper one can see that there are exactly two graphs with \(J_{\bar{B}}\) unmixed and \(9+5\) or \(9+6\) vertices).
We then test unmixedness using the following commands
cat b9_w5.nty | ./isUnmixed > b9_w5_unmixed.nty
cat b9_w6.nty | ./isUnmixed > b9_w6_unmixed.nty
As mentioned above, in both cases the output are exatly the blocks with whiskers in the files b9_w5.nty and b9_w6.nty.
Lines 16 and 20: Check if the accessible graphs have a cut vertex \(v\) such that \(J_{\bar{B}}\) is unmixed
We now test accessibility using a routine that can be found here.
To filter the accessible blocks with whiskers in \(\bar{\mathcal B}\) we use the following
cat b9_w5_unmixed.nty | ./isAccessible 1 > b9_w5_accessible.nty
cat b9_w6_unmixed.nty | ./isAccessible 1 > b9_w6_accessible.nty
The accessible blocks with 9 vertices and 5 whiskers are exactly the two graphs in b9_w5_unmixed.nty, whereas with 6 whiskers we get only one of the two graphs in b9_w6_unmixed.nty.
Finally we check if each accessible block with whiskers \(\bar{B}\) has a cut vertex \(v\) such that \(J_{\bar{B} \setminus \{v\}}\) is unmixed. This last routine has been implemented in C++.
cat b9_w5_accessible.nty | ./isGminusVUnmixed
cat b9_w6_accessible.nty | ./isGminusVUnmixed
In both cases the input coincides with the output.
Installation
In this section we describe step by step the process to install the routines that we implemented in C, C++ and Python (gcc ver.11.3.0 and Python 3.10.6) whose sources and output files can be found here.
The functions in C and C++ have been developed under Linux on Ubuntu distribution (tested on versions 22.04) and only use standard libraries and Nauty. With some effort they work on any platform. To use the code, download and extract the files with the command
tar -xzvf CMSmallBEI.tgz
move to the folder
cd CMSmallBEI
and then compile the C++ program by using
make
We need to compile another program. In fact our implementation uses a customized version of the geng routine in Nauty. This package generates graphs up to isomorphism. Download the file in tgz format from here or here into the folder CMSmallBEI, and follow the instructions.
We tested the program with Versions 2.6r12 and 2.8r6. Using the latter version, execute the following lines
tar xvzf nauty2_8_6.tar.gz cd nauty2_8_6 ./configure make
Now we have to copy the source file to create the binary in order to generate graphs without free vertices (the computation is described in line 2). Hence we execute
cp ../src/graphsNoFreeVertices.c .
and compile it
gcc -o graphsNoFreeVertices -O3 -DWORDSIZE=32 -DMAXN=32 -DPRUNE=has_no_free_vertex geng.c gtools.c nauty.c nautil.c naugraph.c schreier.c naurng.c graphsNoFreeVertices.c
We now have a new binary that needs to be stored in the binary folder
cp graphsNoFreeVertices ../bin
All the necessary binaries are in the bin folder. In the same folder there is also the Python script AddWhiskers.py. This script uses the python-igraph library, that we need for our computations.
Computational results and examples
The computation of the blocks with whiskers in \(\bar{\mathcal B}\), with blocks having \(10\) or \(11\) vertices, takes some time. Here we compute all the blocks with \(n=10\) vertices and \(k=5,6,7\) whiskers.
We show the input and the output in the console. We first generate the blocks with whiskers in \(\bar{\mathcal B}\).
time ./bin/graphsNoFreeVertices -C 10 -d3 |./bin/isBlockCandidate 5 | ./bin/AddWhiskers.py 10 5 > b10_w5.nty
time ./bin/graphsNoFreeVertices -C 10 -d3 |./bin/isBlockCandidate 6 | ./bin/AddWhiskers.py 10 6 > b10_w6.nty
time ./bin/graphsNoFreeVertices -C 10 -d3 |./bin/isBlockCandidate 7 | ./bin/AddWhiskers.py 10 7 > b10_w7.nty
The output files are b10_w5.nty, b10_w6.nty and b10_w7.nty. The time needed for the computation for the case \(n=10\) and \(k=5\) is:
real 109m53,113s
user 140m25,065s
sys 5m54,879s
The time needed for the computation for the case \(n=10\) and \(k=6\) is:
real 143m55,189s
user 191m29,097s
sys 5m45,002s
The time needed for the computation for the case \(n=10\) and \(k=7\) is:
real 115m26,396s
user 168m48,530s
sys 4m12,758s
We can see that each of the above computations needs \(\sim 2\) hours on a Celeron i5 CPU.
Now, we need to filter the graphs whose binomial edge ideal is unmixed, and among them, the ones that are accessible. These computations only take few seconds since the number of graphs in \(\bar{\mathcal B}\) produced in the previous step is quite small (less than \(30\) graphs in each case).
cat b10_w5.nty |./bin/isUnmixed > b10_w5_unmixed.nty
cat b10_w6.nty |./bin/isUnmixed > b10_w6_unmixed.nty
cat b10_w7.nty |./bin/isUnmixed > b10_w7_unmixed.nty
cat b10_w5_unmixed.nty |./bin/isAccessible 1 > b10_w5_accessible.nty
cat b10_w6_unmixed.nty |./bin/isAccessible 1 > b10_w6_accessible.nty
cat b10_w7_unmixed.nty |./bin/isAccessible 1 > b10_w7_accessible.nty
Instead of testing the conjecture we compare these files with the ones provided in the out folder:
cmp b10_w5_unmixed.nty out/b10_w5_unmixed.nty
cmp b10_w6_unmixed.nty out/b10_w6_unmixed.nty
cmp b10_w7_unmixed.nty out/b10_w7_unmixed.nty
cmp b10_w5_accessible.nty out/b10_w5_accessible.nty
cmp b10_w6_accessible.nty out/b10_w6_accessible.nty
cmp b10_w7_accessible.nty out/b10_w7_accessible.nty
The output is empty which means that the files are the same.
In the paper we present the following table summarizing all the computations we performed. The second column contains the number of the blocks \(B\) generated with the program graphsNoFreeVertices (see line 2). We observe that the number of blocks with \(11\) vertices is \(\sim 100\) times the number of blocks with \(10\) vertices. Hence, using the same Celeron i5 CPU the computation would take several days. The case of blocks with \(12\) vertices would take too long due to the combinatorial explosion in the number of graphs.
