# 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).