next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Chordal :: chordal networks examples

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×n matrix . This ideal decomposes into Fn components, where Fn 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, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, 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 F10=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 xixj for ij∈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 C3×Pn.

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

o8 : MonomialIdeal of QQ[x , x , x , x , x , x , x , x , x , x  , x  , x  , x  , x  , x  ]
                          1   2   3   4   5   6   7   8   9   10   11   12   13   14   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×25-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 Cn is trivial. However, solving the problem algebraically (see chromaticIdeal) can be quite challenging using Gröbner 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