next | previous | forward | backward | up | index | toc

# chordalElim -- performs elimination on the chordal network

## Synopsis

• Usage:
chordalElim N
• Inputs:
• Optional inputs:
• Algorithm (missing documentation) => ..., default value Inhomogeneous,
• DegreeLimit (missing documentation) => ..., default value {},
• Outputs:
• guaranteed, , 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 .