This method performs successive elimination on a given chordal network. Under suitable conditions this procedure computes the elimination ideals.
Let $I\subseteq k[x_0,\dots,x_{n-1}]$ be the input ideal. The "approximate" $j$-th elimination ideal $I_j$ consists of the polynomials in the output network with main variable at most $x_j$. The containment $I_j \subseteq I\cap k[x_{j},\dots,x_{n-1}]$ always holds. If guaranteed=true, then $I_j$ provably agrees with $I\cap k[x_j,\dots,x_{n-1}]$ (up to radical).
Example 3.1 of [CP'16]
(chordalElim succeeds in computing the elimination ideals)
i1 : R = QQ[x_0..x_3, MonomialOrder=>Lex]; |
i2 : I = ideal {x_0^4-1, x_0^2+x_2, x_1^2+x_2, x_2^2+x_3};
o2 : Ideal of R
|
i3 : N = chordalNet I; |
i4 : chordalElim N o4 = true |
i5 : N
2
o5 = ChordalNet{ x => {x + x } }
0 0 2
2
x => {x + x }
1 1 2
2
x => {x - 1}
2 2
x => {x + 1}
3 3
o5 : ChordalNet
|
i6 : gbList I
2 2 2
o6 = {x + 1, x - 1, x + x , x + x }
3 2 1 2 0 2
o6 : List
|
Example 3.2 of [CP'16]
(chordalElim does not compute the elimination ideals)
i7 : R = QQ[x_0..x_2, MonomialOrder=>Lex]; |
i8 : I = ideal {x_0*x_1+1, x_1+x_2, x_1*x_2};
o8 : Ideal of R
|
i9 : N = chordalNet I; |
i10 : chordalElim N o10 = false |
i11 : N
o11 = ChordalNet{ x => {x x + 1} }
0 0 1
x => {x + x }
1 1 2
2
x => {x }
2 2
o11 : ChordalNet
|
i12 : gbList I
o12 = {1}
o12 : List
|
Example: 3-chromatic ideal of the cycle graph
(chordalElim succeeds)
i13 : I = chromaticIdeal(QQ, cycleGraph 10, 3); o13 : Ideal of QQ[a..j] |
i14 : N = chordalNet I; |
i15 : chordalElim N o15 = true |
i16 : N
2 2 2 2
o16 = ChordalNet{ a => {{a*b - a*j + b - j , a + a*j + j }} }
2 2
b => {b + b*c + c }
2 2
c => {c + c*d + d }
2 2
d => {d + d*e + e }
2 2
e => {e + e*f + f }
2 2
f => {f + f*g + g }
2 2
g => {g + g*h + h }
2 2
h => {h + h*i - i*j - j }
2 2
i => {i + i*j + j }
3
j => {j - 1}
o16 : ChordalNet
|
The object chordalElim is a method function with options.