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

- ChordalNet -- a chordal network
- displayNet -- displays a chordal network using Graphivz

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Chordal/ChordalDoc.m2:280:0.