chordalElim -- performs elimination on the chordal network

Synopsis

Usage:

chordalElim N
Inputs:
- N, an instance of the type ChordalNet,
Optional inputs:
- Algorithm (missing documentation) => ..., default value Inhomogeneous,
- DegreeLimit (missing documentation) => ..., default value {},
Outputs:
- guaranteed, a Boolean value, whether the output is guaranteed to be the elimination ideals
Consequences:
- the input chordal network is modified

Description

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

Ways to use chordalElim :

chordalElim(ChordalNet)

For the programmer

The object chordalElim is a method function with options.