Set of routines to generate and analyze all the squarefree monomial ideals with 5 generators

In the paper K. Kimura, G. Rinaldo, N. Terai, Arithmetical rank of squarefree monomial ideals generated by five elements or with arithmetic degree four (section 6), the authors described an algorithm to compute squarefree monomial ideals with 5 generators satisfaying certain algebraic properties.

In this page we give an example of this computation: We calculate by an exhaustive method the class of monomial ideals with 5 generators and that have height I equal to 2, projective dimension S/I equal to 3 where the polynomial ring is S=K[x₁,...,x_n], with n=24,25,26.

We recall some key concepts, but we refer to the article for an in-depth study. The algorithm is composed mainly by three steps:

Step 1)

Compute all the squarefree monomial ideals with 5 generators;

Step 2)

Filter ideals by algebraic invariants;

Step 3)

Find maximal ideals under localization.

Note: For the reader interested to test the examples is useful a unix-like workstation (linux, mac-os, etc.) and basic knowledge about gcc and the command line of Unix.

---

Step 1) Compute all the squarefree monomial ideals with 5 generators

A possible way to represent such ideals is to consider the graphs satisfying definition 5.2 of the article. For sake of completeness we recall the following

Definition 5.2. Let X={x₁,...,x_n}, Y={y₁,...,y_m} and let G be the bipartite graph on the vertex set V=X ∪ Y. We consider the bipartite graphs G satisfying the following 3 conditions:

1. The graph is connected;
2. For all y_i, y_j∈ Y, i ≠ j, N(y_i) ⊄ N(y_j);
3. For all x_i, x_j∈ X, i ≠ j, N(x_i) ≠ N(x_j).

In this definition N(v) is the set of neighborhoods of the vertex v &isin V.

With this assumption N(y₁),…,N(y_m) represent the supports of a minimal set of generators of a squarefree monomial ideal.

A very nice package to calculate graphs up to isomorphisms is Nauty. In this case our graph is bipartite and it needs to satisfy the 3 conditions. The command within Nauty useful for our aim is genbg with the following options

genbg -c -z m n

Where

• m and n are the cardinalities of the sets Y and X;
• the option -c computes only the connected graphs (condition 1 of definition 5.2)
• the option -z satisfies condition 3 of definition 5.2.

Unfortunately genbg is not sufficient since there is no filtration for condition 2. Nevertheless a nice feature of Nauty is the internal but user-defined command "prune".

Therefore we implemented the test of condition 2 and we prune the bipartite graphs not satisfying this condition. The name of this customization of genbg is genclut (in fact in general it solves the problem of the generation of all clutters up to isomorphisms).

To install genclut, first install Nauty and then copy this file in the directory where Nauty is installed. Then insert the following command in the console

gcc -o genclut -O4 -DMAXN=32 -DPRUNE1=Prune genbg.c gtools.o nauty1.o nautil1.o naugraph1.o pruneclut.c

Now we are ready to compute the graphs with m=5 and n=26, n=25, n=24. We show the input and the output in the console.

---

./genclut -c -z 5 26 > b5.26.nty 

>A ./genclut n=5+26 e=30:130 d=1:1 D=26:5 zc
>Z 2160 graphs generated in 128.82 sec

---

./genclut -c -z 5 25 > b5.25.nty 

>A ./genclut n=5+25 e=29:125 d=1:1 D=25:5 zc
>Z 8035 graphs generated in 128.44 sec

---

./genclut -c -z 5 24 > b5.24.nty

>A ./genclut n=5+24 e=28:120 d=1:1 D=24:5 zc
>Z 26195 graphs generated in 128.00 sec

---

Step 2) Filter ideals by algebraic invariants

Once computed the graphs, we have to go back to monomial ideals and see if they satisfy the algebraic conditions. To this aim we use CoCoA and implement a library that is an interface to Nauty format (FileIo.coc) and a short routine to calculate height and projective dimension of each element in the 3 files obtainad in the previous step. The 3 corresponding output files are : b5.26.Ht2.nty, b5.25.Ht2.nty, b5.24.Ht2.nty. The source of the routines used in these computations are here. In this case since the monomial ideals are not so many we show their generators that are m1, m2, m3, m4, m5 .

---

cocoa Ideal5On26Ht2Pd3.coc

The set is empty!

---

cocoa Ideal5On25Ht2Pd3.coc

m1=x[1]x[5]x[6]x[7]x[11]x[12]x[15]x[18]x[19]x[20]x[21]x[22]x[23]x[24]
m2=x[2]x[5]x[8]x[9]x[11]x[13]x[15]x[16]x[17]x[18]x[21]x[22]x[24]x[25]
m3=x[3]x[6]x[8]x[10]x[12]x[14]x[15]x[16]x[17]x[20]x[21]x[23]x[24]x[25]
m4=x[4]x[7]x[9]x[10]x[13]x[14]x[17]x[18]x[19]x[20]x[22]x[23]x[24]x[25]
m5=x[11]x[12]x[13]x[14]x[16]x[19]x[21]x[22]x[23]x[25]

This ideal is maximal in the set of graphs with m=5 since the set of monomial ideals on the ring with 26 variable is empty.

---

cocoa Ideal5On24Ht2Pd3.coc

Ideal 1
m1=x[1]x[5]x[6]x[7]x[11]x[12]x[15]x[18]x[19]x[20]x[22]x[23]x[24]
m2=x[2]x[5]x[8]x[9]x[11]x[13]x[15]x[16]x[17]x[18]x[20]x[21]x[22]x[23]
m3=x[3]x[6]x[8]x[10]x[12]x[14]x[15]x[16]x[17]x[19]x[20]x[21]x[22]x[24]
m4=x[4]x[7]x[9]x[10]x[13]x[14]x[17]x[18]x[19]x[21]x[22]x[23]x[24]
m5=x[11]x[12]x[13]x[14]x[16]x[20]x[21]x[23]x[24]

Ideal 2
m1=x[1]x[5]x[6]x[7]x[11]x[12]x[15]x[18]x[19]x[20]x[21]x[22]x[23]x[24]
m2=x[2]x[5]x[8]x[9]x[11]x[13]x[15]x[16]x[17]x[18]x[21]x[22]x[23]
m3=x[3]x[6]x[8]x[10]x[12]x[14]x[15]x[16]x[17]x[20]x[21]x[23]x[24]
m4=x[4]x[7]x[9]x[10]x[13]x[14]x[17]x[18]x[19]x[20]x[22]x[23]x[24]
m5=x[11]x[12]x[13]x[14]x[16]x[19]x[21]x[22]x[24]

Ideal 3
m1=x[1]x[5]x[6]x[7]x[11]x[12]x[15]x[18]x[19]x[20]x[21]x[22]x[23]
m2=x[2]x[5]x[8]x[9]x[11]x[13]x[15]x[16]x[17]x[18]x[21]x[22]x[24]
m3=x[3]x[6]x[8]x[10]x[12]x[14]x[15]x[16]x[17]x[20]x[21]x[23]x[24]
m4=x[4]x[7]x[9]x[10]x[13]x[14]x[17]x[18]x[19]x[20]x[22]x[23]x[24]
m5=x[11]x[12]x[13]x[14]x[16]x[19]x[21]x[22]x[23]x[24]

Ideal 4
m1=x[1]x[5]x[6]x[7]x[11]x[12]x[15]x[18]x[19]x[20]x[21]x[23]x[24]
m2=x[2]x[5]x[8]x[9]x[11]x[13]x[15]x[16]x[17]x[18]x[20]x[21]x[22]x[23]
m3=x[3]x[6]x[8]x[10]x[12]x[14]x[15]x[16]x[17]x[20]x[22]x[23]x[24]
m4=x[4]x[7]x[9]x[10]x[13]x[14]x[17]x[18]x[19]x[21]x[22]x[23]x[24]
m5=x[11]x[12]x[13]x[14]x[16]x[19]x[20]x[21]x[22]x[24]

Ideal 5
m1=x[1]x[5]x[6]x[7]x[10]x[13]x[14]x[15]x[16]x[17]x[20]x[21]x[22]x[23]
m2=x[2]x[5]x[8]x[9]x[11]x[12]x[14]x[15]x[16]x[19]x[20]x[21]x[22]x[24]
m3=x[3]x[6]x[8]x[10]x[12]x[14]x[17]x[18]x[19]x[20]x[22]x[23]x[24]
m4=x[4]x[7]x[9]x[11]x[13]x[16]x[17]x[18]x[19]x[21]x[22]x[23]x[24]
m5=x[10]x[11]x[12]x[13]x[15]x[18]x[20]x[21]x[23]x[24]

Ideal 6
m1=x[1]x[4]x[7]x[8]x[10]x[12]x[15]x[16]x[17]x[19]x[20]x[21]x[23]x[24]
m2=x[2]x[5]x[7]x[9]x[11]x[12]x[13]x[16]x[18]x[19]x[20]x[22]x[23]x[24]
m3=x[3]x[6]x[8]x[9]x[11]x[14]x[15]x[17]x[18]x[19]x[21]x[22]x[23]x[24]
m4=x[4]x[5]x[6]x[10]x[11]x[12]x[13]x[14]x[15]x[20]x[21]x[22]x[23]
m5=x[10]x[13]x[14]x[16]x[17]x[18]x[20]x[21]x[22]x[24]

Ideal 7
m1=x[1]x[4]x[7]x[9]x[10]x[12]x[15]x[16]x[18]x[19]x[20]x[22]x[23]x[24]
m2=x[2]x[5]x[8]x[9]x[11]x[14]x[15]x[17]x[18]x[19]x[21]x[22]x[23]x[24]
m3=x[3]x[6]x[7]x[8]x[11]x[12]x[13]x[16]x[17]x[19]x[20]x[21]x[23]x[24]
m4=x[4]x[5]x[10]x[11]x[12]x[13]x[14]x[15]x[20]x[21]x[22]x[23]
m5=x[6]x[10]x[13]x[14]x[16]x[17]x[18]x[20]x[21]x[22]x[24]

---

Step 3) Find maximal ideals under localization

We know that the graph in the file b5.25.Ht2.nty is maximal. Hence we have to delete all the graphs that are not maximal in the file b5.24.Ht2.nty. To reach this goal we have to localize with respect to any of the 25 indeterminates the graph in b5.25.Ht2.nty. The source of the routine written in c++ is this.

---

cat b5.25.Ht2.nty | ./localize n 5 25 > l5.24.Ht2.nty

---

We obtain 25 graphs that we merge with the graphs in b5.24.Ht2.nty.

---

cat l5.24.Ht2.nty b5.24.Ht2.nty > lb5.24.Ht2.nty

---

The graphs that are unique up to isomorphism are the maximal ones in this set. By Nauty we calculate the ones that are isomorphic to other ones in the same file. The command is shortg

---

./shortg -v -u lb5.24.Ht2.nty 

>Z     32 graphs read from lb5.24.Ht2.nty

  1 :  21  22  23  25  27
  2 :  15  17  18  20  29
  3 :  11  12  13  14  16  19  26
  4 :  24  28
  5 :   1   2   3   4  31
  6 :   5   6   7   8   9  10  30
  7 :  32
>Z      7 graphs produced

---

The output shows in the first column the set of graphs up to isomorphisms (7 in this example). For example the first line

  1 :  21  22  23  25  27

means that graph 1 (in the output file) is isomorphic to the graphs 21, 22, 23, 25 and 27 of the input file lb5.24.Ht2.nty. Hence graph 1 comes from different localizations of the graph in b5.25.Ht2.nty. The only one that is unique, therefore does not come from a localization, is the graph 7 that is in position 32 in the file b5.25.Ht2.nty. This ideal is

Ideal 32
m1=x[1]x[4]x[7]x[9]x[10]x[12]x[15]x[16]x[18]x[19]x[20]x[22]x[23]x[24]
m2=x[2]x[5]x[8]x[9]x[11]x[14]x[15]x[17]x[18]x[19]x[21]x[22]x[23]x[24]
m3=x[3]x[6]x[7]x[8]x[11]x[12]x[13]x[16]x[17]x[19]x[20]x[21]x[23]x[24]
m4=x[4]x[5]x[10]x[11]x[12]x[13]x[14]x[15]x[20]x[21]x[22]x[23]
m5=x[6]x[10]x[13]x[14]x[16]x[17]x[18]x[20]x[21]x[22]x[24]

as shown in the article.

---