Macaulay2 » Documentation
Packages » Chordal :: chordal networks examples
next | previous | forward | backward | up | index | toc

chordal networks examples -- a new representation of polynomial ideals

A chordal network is a data structure that represents polynomial ideals in terms of the paths of a certain directed graph. Remarkably, several polynomial ideals with exponentially many components admit compact chordal network representations. Moreover, chordal networks can be efficiently post-processed to compute several properties of the underlying variety, such as cardinality, dimension, components, elimination ideals, and radical ideal membership.

We now present some examples.

Ideal of adjacent minors: Consider the ideal of adjacent minors of a $2\times n$ matrix . This ideal decomposes into $F_n$ components, where $F_n$ is the Fibonacci number. These (exponentially many) components can be represented compactly with a chordal network.

i1 : I = adjacentMinorsIdeal(QQ,2,10);

o1 : Ideal of QQ[a..t]
 
i2 : N = chordalNet I;
 
i3 : chordalTria N;
 
i4 : topComponents N;
 
i5 : N

o5 = ChordalNet{ a => { , a*d - b*c}                  }
                 b => { ,  }
                 c => {c,  , c*f - d*e}
                 d => {d,  ,  }
                 e => { , e*h - f*g, e,  , e*h - f*g}
                 f => { ,  , f,  ,  }
                 g => {g,  , g*j - h*i,  , g*j - h*i}
                 h => {h,  ,  ,  ,  }
                 i => { , i*l - j*k, i,  , i*l - j*k}
                 j => { ,  , j,  ,  }
                 k => {k,  , k*n - l*m,  , k*n - l*m}
                 l => {l,  ,  ,  ,  }
                 m => { , m*p - n*o, m,  , m*p - n*o}
                 n => { ,  , n,  ,  }
                 o => {o,  , o*r - p*q,  , o*r - p*q}
                 p => {p,  ,  ,  ,  }
                 q => {q*t - r*s, q, q*t - r*s}
                 r => { , r,  }
                 s => { ,  }
                 t => { ,  }

o5 : ChordalNet

Once we have the chordal network, one may verify that the variety has codimension 9, and that it has $F_{10}=55$ components.

i6 : codimCount N

        9
o6 = 55t

o6 : ZZ[t]

Edge ideals: The edge ideal of a graph $G=(V,E)$ is generated by the monomials $x_ix_j$ for $ij\in E$. Edge ideals have a very nice combinatorial structure, but they often have an exponential number of components. Chordal networks might be used to efficiently describe these large decompositions. The following code computes a chordal network representation for edge ideal of the product graph $C_3\times P_n$.

i7 : G = cartesianProduct(cycleGraph 3, pathGraph 5);
 
i8 : I = edgeIdeal G;

o8 : MonomialIdeal of QQ[x ..x  ]
                          1   15
 
i9 : N = chordalNet(I,"SuggestOrder");
 
i10 : chordalTria N;
 
i11 : topComponents N;
 
i12 : N

o12 = ChordalNet{ x  => {x ,  }                }
                   1      1
                  x  => {x , x ,  }
                   2      2   2
                  x  => {x ,  , x , x }
                   6      6      6   6
                  x  => {x , x ,  }
                   3      3   3
                  x  => {x , x ,  }
                   5      5   5
                  x  => {x ,  , x , x }
                   9      9      9   9
                  x  => {x , x ,  }
                   4      4   4
                  x  => {x , x ,  }
                   8      8   8
                  x   => {x  ,  , x  , x  }
                   10      10      10   10
                  x  => {x , x ,  }
                   7      7   7
                  x   => {x  , x  ,  }
                   12      12   12
                  x   => {x  , x  ,  , x  ,  }
                   11      11   11      11
                  x   => {x  ,  ,  , x  , x  }
                   13      13         13   13
                  x   => {x  ,  , x  }
                   14      14      14
                  x   => { , x  }
                   15         15

o12 : ChordalNet

This variety has codimension 10, and has $48=3\times 2^{5-1}$ components.

i13 : codimCount N

         10
o13 = 48t

o13 : ZZ[t]

Chromatic ideal of a cycle: Coloring graphs is a classical NP-hard problem, but it is tractable for certain families of graphs. In particular, coloring the cycle graph $C_n$ is trivial. However, solving the problem algebraically (see chromaticIdeal) can be quite challenging using Gr\"obner bases. On the other hand, this chromatic ideal has a chordal network representation with less than $3n$ nodes [CP2017]. This network can be found with the command chordalTria(N), but the calculation requires Maple (see TriangularDecompAlgorithm).

See also