Cohen-Macaulay and S2 of second power

In the paper Do Trong Hoang, Giancarlo Rinaldo, and Naoki Terai, Cohen-Macaulay and (\(S_2\)) properties of the second power of squarefree monomial ideals, we show that Cohen-Macaulay and (\(S_2\)) property are equivalent for the second power of an edge ideal, moreover we give an example of a Gorenstein squarefree monomial ideal I such that \(S/I^2\) satisfies Serre condition (\(S_2\)) but is not Cohen-Macaulay.

In the paper we used

Algorithm 1: In Theorem 3.5, where we classified 4-dimensional Cohen-Macaulay \(S/I(G)^2\), with \(I(G)\) edge ideal;
Algorithm 2: In the last section, where we provide an example of Gorenstein squarefree monomial ideal I such that \(S/I^2\) satisfies condition (\(S_2\)) but it is not Cohen-Macaulay.

In the following sections we describe the algorithms and show the results obtained. We refer to the article for an in-depth description of the notation and results. In this page you will find respectively descriptions of Algorithm 1 and Algorithm 2 and the implementation of them with the results of our computation. We recall the following general facts

\(S/I^2\) is Cohen-Macaulay if and only if \(S/I^{(2)}\) is Cohen-Macaulay and \(I^2=I^{(2)}\) (well known);
If \(S/I^{(2)}\) is Cohen-Macaulay then \(S/I^{(2)}\) satisfies \(S_2\) condition (well known);

and the following property related to squarefree monomial ideals

\(S_2\) Condition: \(S/I_{\Delta}^{(2)}\) satisfies \(S_2\) condition if and only if diam\((link_\Delta F))\leq 2\) for any \(F \in \Delta\) with dim \(link_\Delta F\geq 1\) (see Theorem 1.1).

Algorithm 1

Let G be a graph on the vertex set \([n]\). To obtain a classification of Cohen-Macaulay quotient rings \(S/I(G)^2\) by a given Krull dimension \(d\), are useful the following results:

\(S/I(G)^2\) is Cohen-Macaulay if and only if G is triangle-free and Gorenstein (Theorem 1.3);
\(n \leq (d^2+3d-2)/2\) (Theorem 3.1).

In particular in Theorem 3.5 we classified the case \(d=4\). That is the number of vertices is less than or equal to 13. Since we have to consider the ones that does not have isolated vertices we have to consider \(n\in \{8,\ldots,13\}\).

A very nice package that computes graphs up to isomorphism is Nauty. As an example the triangle-free graphs with 13 non-isolated vertices are 19534822. Here is the command used by Nauty for this goal:

nauty-geng -t -u 13 -d1 
>A nauty-geng -td1D12 n=13 e=7-42
>Z 19534822 graphs generated in 16.32 sec

Since \(S/I(G)\) Gorenstein implies that I(G) is unmixed, that is all minimal covers have the same cardinality, we need an algorithm that filters the Nauty output by this condition.

It is well known that if \(I(G)=(x_{i_1}x_{j_1},\ldots,x_{i_q}x_{j_q})\) then the ideal \[ I_C(G)=\cap_{k=1}^q (x_{i_k},x_{j_k}) \] is generated by monomials representing the minimal covers of G. If \(I_C(G)\) has minimal set of generators of the same degree we are done (well known).

A quite efficient method is the following. We calculate in each step for \(k\in\{1,\ldots, q\}\) the minimal set of generators of he subideal \(I_k \) where: \[ I_k = (x_{i_1}, x_{j_1} ) \cap (x_{i_2} , x_{j_2})\cap \ldots \cap (x_{i_k} , x_{j_k}). \] since \(I_k = I_{k−1}\cap (x_{i_k} , x_{j_k})\). In this way we control the growth of not minimal generators step by step.

The \(S_2\) condition is purely combinatorial, too, and can be tested by an effective and quite efficient algorithm. We describe it in detail.

We recall that diameter, diam(), is computed on the skeleton of dimension 1 of a certain simplicial complex \(\Delta\), roughly speaking on the graph whose edges are the facets of the subcomplex of dimension 1, namely \(G=skel_1(\Delta)\). As an example in the images you see \(\Delta\) that is given by the boundary of the octahedron, and its 1-skeleton.

Octahedron Octahedral skeleton

The diameter is the maximal distance between all the vertices of G, namely \(V(G)=\{1,\ldots,n\}\). Since we want diam\((G)\leq 2\) it is sufficient that in two steps it is possible to reach any vertex by any other vertex. Let \(L=\{L_1,\ldots,L_n\}\) be the adiacency set of \(G\) on the vertices \(V(G)\). That is \(L_i\) is the set of vertices adjacent to the vertex \(i\), for \(i\in\{1,\ldots,n\}\).

Let \(d(v,w)\) be the distance between two vertices of \(G\). Focus on the vertex 1, we want to test \(d(1,v)\leq 2\) for all \(v\in \{2,\ldots,n\}\). It is sufficient to consider the union

\[U= L_1 \cup_{i\in L_1} L_i \]

If \(U=\{1,\ldots,n\}\) then \(d(1,v)\leq 2\), otherwise there exists a v such that \(d(1,v)>2\).

Hence if \(d(1,v)\leq 2\) we can continue with \(d(2,v)\) and so on, otherwise we stop returning that diameter is greater than 2. If the algorithm terminates without interruption then the diameter is \(\leq 2\).

As an example if we focus on a vertex of the graph induced by octahedron, namely 1, we see that \(L_1\) is a set of 4 vertices, namely, 2,3,4,5, and \(L_2=L_3=L_4=L_5=\{1,6\}\). Hence \(U=\{1,\ldots,6\}\). The same happens for all the vertices of \(\Delta\) that is its diameter is 2. Now, focus on a vertex of \(\Delta\), namely 1. Its link is given by the cycle C of length 4, whose vertices are, 2,3,4 and 5. Applying the same algorithm to the graph C we easily obtain that its diameter is 2. Hence the octahedron satisfies the \(S_2\) condition (see also Proposition 2.3(4)).

We observe that if we focus on a n-gonal bypiramid with \(n\geq 6\) the algorithm gives a negative answer. In fact even if \(diam(\Delta)\) is 2 again, if we consider the link of one of the apex we obtain a n-gon that has diameter \(n/2\).

Now we are ready to describe Algorithm 1 in the following 4 Steps

Compute the graphs that are triangle-free and with \(n\in\{8,\ldots,13\}\) non-isolated vertices;
Filter the unmixed ones of Step 1.;
Filter the ones that satisfy \(S_2\) condition of Step 2.;
Filter the ones that are Gorenstein of Step 3.

The condition in Step 4 can be computed by any computer algebra system like CoCoA (we decided to use it).

Algorithm 2

To obtain the example shown in the article it was fundamental the classification of Frank H. Lutz in the paper F. H .Lutz Combinatorial 3-manifolds with 10 vertices, Beitr. Algebra. Geom. 49(2008), 97-106, whose database is here.

The database provided by Frank H. Lutz for the case \(n=10\) contains 247882 triangulations. Hence we needed a good filtration. The condition \(S_2\), whose algorithm has been described in the previous section, is very nice since it provides only 18 elements.

Now we are ready to describe Algorithm 2 in the following 3 Steps

Filter the file v10.txt of Lutz by \(S_2\) condition
Filter the ones that satisfy \(I^{(2)}=I^2\) of Step 1.
Filter the ones that satisfy \(S/I^2\) not Cohen-Macaulay of Step 2.

The condition in Steps 2. and 3. can be computed by any computer algebra system like CoCoA (we decided to use it).

Implementation of Algorithms 1 and 2 and results

In this section we give the results of our computation by Nauty, the routines that we implemented in c++ (using g++ of gcc ver. 4.8) and CoCoA 4.7 whose sources are downloadable from here.

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

tar -zxvf CMAndS2SecondPower.tgz

move to the folder

cd CMAndS2SecondPower

and then compile the c++ programs by

make all

Now we are ready for the computation of Algorithm 1. We show the input and the output in the console. To generate the the unmixed triangle-free graphs that satisfy \(S_2\) condition we use the following command

 
./TriangleFreeGraphUnmixedDiam2

This command generates the files g8.nty, g8.nty, g9.nty, g10.nty, g11.nty, g12.nty, g13.nty. The computation will take more or less 5 hours with an Intel Core i5. In any case the files are already part of the compressed archive you downloaded, so you don't have to compute them.

To filter the Gorenstein ones se the following commands

 
cocoa IsGorenstein8.coc

Whose result is


The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[3]x[7], x[4]x[8])
And it is Gorenstein
0 --> S(-8) --> S^4(-6) --> S^6(-4) --> S^4(-2) --> S

 
cocoa IsGorenstein9.coc

Whose result is


The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[3]x[7], x[1]x[8], x[4]x[8], x[4]x[9], x[5]x[9])
And it is Gorenstein
0 --> S(-9) --> S^7(-7) --> S^11(-5)(+)S^5(-6) --> S^5(-3)(+)S^11(-4) --> S^7(-2) --> S

 
cocoa IsGorenstein10.coc

Whose result is


The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[3]x[7], x[1]x[8], x[4]x[8], x[2]x[9], x[4]x[9], x[5]x[9], x[4]x[10], x[5]x[10], x[6]x[10])
And it is Gorenstein
0 --> S(-10) --> S^11(-8) --> S^15(-6)(+)S^16(-7) --> S^5(-4)(+)S^32(-5)(+)S^5(-6) --> S^16(-3)(+)S^15(-4) --> S^11(-2) --> S

The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[1]x[7], x[3]x[7], x[3]x[8], x[5]x[8], x[2]x[9], x[4]x[9], x[4]x[10], x[6]x[10])
And it is Gorenstein
0 --> S(-10) --> S^10(-8) --> S^25(-6)(+)S^10(-7) --> S^52(-5) --> S^10(-3)(+)S^25(-4) --> S^10(-2) --> S

 
cocoa IsGorenstein11.coc

Whose result is


The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[3]x[7], x[1]x[8], x[4]x[8], x[2]x[9], x[4]x[9], x[5]x[9], x[3]x[10], x[4]x[10], x[5]x[10], x[6]x[10], x[4]x[11], x[5]x[11], x[6]x[11], x[7]x[11])
And it is Gorenstein
0 --> S(-11) --> S^16(-9) --> S^17(-7)(+)S^35(-8) --> S^6(-5)(+)S^62(-6)(+)S^23(-7) --> S^23(-4)(+)S^62(-5)(+)S^6(-6) --> S^35(-3)(+)S^17(-4) --> S^16(-2) --> S

The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[1]x[7], x[3]x[7], x[3]x[8], x[5]x[8], x[2]x[9], x[4]x[9], x[1]x[10], x[4]x[10], x[6]x[10], x[4]x[11], x[5]x[11], x[6]x[11], x[7]x[11])
And it is Gorenstein
0 --> S(-11) --> S^15(-9) --> S^27(-7)(+)S^28(-8) --> S(-5)(+)S^92(-6)(+)S^12(-7) --> S^12(-4)(+)S^92(-5)(+)S(-6) --> S^28(-3)(+)S^27(-4) --> S^15(-2) --> S

 
cocoa IsGorenstein12.coc

Whose result is


The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[1]x[7], x[3]x[7], x[2]x[8], x[4]x[8], x[2]x[9], x[3]x[9], x[5]x[9], x[1]x[10], x[4]x[10], x[6]x[10], x[4]x[11], x[5]x[11], x[6]x[11], x[7]x[11], x[3]x[12], x[5]x[12], x[6]x[12], x[8]x[12])
And it is Gorenstein
0 --> S(-12) --> S^20(-10) --> S^36(-8)(+)S^48(-9) --> S^180(-7)(+)S^29(-8) --> S^4(-5)(+)S^280(-6)(+)S^4(-7) --> S^29(-4)(+)S^180(-5) --> S^48(-3)(+)S^36(-4) --> S^20(-2) --> S

 
cocoa IsGorenstein13.coc

Whose result is


The Ideal is
Ideal(x[1]x[5], x[2]x[6], x[1]x[7], x[3]x[7], x[1]x[8], x[2]x[8], x[4]x[8], x[2]x[9], x[3]x[9], x[5]x[9], x[1]x[10], x[3]x[10], x[4]x[10], x[6]x[10], x[3]x[11], x[5]x[11], x[6]x[11], x[8]x[11], x[2]x[12], x[4]x[12], x[5]x[12], x[7]x[12], x[4]x[13], x[6]x[13], x[7]x[13], x[9]x[13])
And it is Gorenstein
0 --> S(-13) --> S^26(-11) --> S^39(-9)(+)S^78(-10) --> S^286(-8)(+)S^65(-9) --> S^624(-7)(+)S^13(-8) --> S^13(-5)(+)S^624(-6) --> S^65(-4)(+)S^286(-5) --> S^78(-3)(+)S^39(-4) --> S^26(-2) --> S

Now we are ready for the computation of Algorithm 2. We first filter the file v10.txt of Lutz by the \(S_2\) condition.

 
./ThreeFoldsDiam2

The output file v10d2.txt contains a list of 18 triangulations of \(S^3\). Nine satisfy the condition \(I^2=I^{(2)}\). Moreover one satisfies the above condition but is not Cohen-Macaulay. To check it use the following command

 
cocoa ExampleGorensteinSecondPowerNotCM.coc

Whose output is

 
The Ideal is:
I=Ideal(x[2]x[9], x[2]x[8], x[4]x[7], x[4]x[5], x[7]x[8], x[5]x[6], x[3]x[6], x[3]x[9], x[1]x[10], x[1]x[3]x[7], x[6]x[8]x[10], x[2]x[5]x[10], x[1]x[4]x[9])
Resolution of S/I is 
0 --> S(-10) --> S^4(-7)(+)S^9(-8) --> S^40(-6)(+)S^8(-7) --> S^72(-5) --> S^8(-3)(+)S^40(-4) --> S^9(-2)(+)S^4(-3) --> S
Hence it is Gorenstein. But S/I^2 is not Cohen-Macaulay.
In fact the resolution of S/I^2 is 
0 --> S(-12) --> S^24(-10)(+)S^24(-11) --> S^228(-9)(+)S^66(-10) --> S^595(-8)(+)S^88(-9) --> S^28(-6)(+)S^656(-7)(+)S^70(-8) --> S^72(-5)(+)S^300(-6)(+)S^32(-7) --> S^45(-4)(+)S^36(-5)(+)S^6(-6) --> S