next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Chordal :: chordalElim

chordalElim -- performs elimination on the chordal network

Synopsis

Description

This method performs successive elimination on a given chordal network. Under suitable conditions this procedure computes the elimination ideals.

Let I⊆k[x0,…,xn-1] be the input ideal. The "approximate" j-th elimination ideal Ij consists of the polynomials in the output network with main variable at most xj. The containment Ij ⊆I∩k[xj,…,xn-1] always holds. If guaranteed=true, then Ij provably agrees with I∩k[xj,…,xn-1] (up to radical).

Example 3.1 of [CP’16]

(chordalElim succeds 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 succeds)

i13 : I = chromaticIdeal(QQ, cycleGraph 10, 3);

o13 : Ideal of QQ[a, b, c, d, e, f, g, h, i, 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

      

Ways to use chordalElim :