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