isGVD -- checks whether an ideal is geometrically vertex decomposable

This function tests whether a given ideal is geometrically vertex decomposable. Geometrically vertex decomposable ideals are based upon the geometric vertex decomposition defined by Knutson, Miller, and Yong [KMY]. Using geometric vertex decomposition, Klein and Rajchgot gave a recursive definition for geometrically vertex decomposable ideals in [KR, Definition 2.7]. This definition generalizes the properties of a square-free monomial ideal whose associated simplicial complex is vertex decomposable.

We include the definition here. Let $y$ be a variable of the polynomial ring $R = k[x_1,\ldots,x_n]$. A monomial ordering $<$ on $R$ is said to be $y$-compatible if the initial term of $f$ satisfies ${\rm in}_<(f) = {\rm in}_<({\rm in}_y(f))$ for all $f \in R$. Here, ${\rm in}_y(f)$ is the initial $y$-form of $f$, that is, if $f = \sum_i \alpha_iy^i$ and $\alpha_d \neq 0$ but $\alpha_t = 0$ for all $t >d$, then ${\rm in}_y(f) = \alpha_d y^d$. We set ${\rm in}_y(I) = \langle {\rm in}_y(f) ~|~ f \in I \rangle$ to be the ideal generated by all the initial $y$-forms in $I$.

Given an ideal $I$ and a $y$-compatible monomial ordering $<$, let $G(I) = \{ g_1,\ldots,g_m\}$ be a Gröbner basis of $I$ with respect to this ordering. For $i=1,\ldots,m$, write $g_i$ as $g_i = y^{d_i}q_i + r_i$, where $y$ does not divide any term of $q_i$; that is, ${\rm in}_y(g_i) = y^{d_i}q_i$. Given this setup, we define two ideals: $$C_{y,I} = \langle q_1,\ldots,q_m\rangle$$ and $$N_{y,I} = \langle q_i ~|~ d_i = 0 \rangle.$$ Recall that an ideal $I$ is unmixed if all of the associated primes of $I$ have the same height.

An ideal $I$ of $R =k[x_1,\ldots,x_n]$ is geometrically vertex decomposable if $I$ is unmixed and

(1) $I = \langle 1 \rangle$, or $I$ is generated by a (possibly empty) subset of variables of $R$, or

(2) there is a variable $y = x_i$ in $R$ and a $y$-compatible monomial ordering $<$ such that $${\rm in}_y(I) = C_{y,I} \cap (N_{y,I} + \langle y \rangle),$$ and the contractions of the ideals $C_{y,I}$ and $N_{y,I}$ to the ring $k[x_1,\ldots,\hat{y},\ldots,x_n]$ are geometrically vertex decomposable.

NOTE: The ideals $C_{y,I}$ and $N_{y,I}$ do not depend upon the choice of the Gröbner basis or a particular $y$-compatible order (see comment after [KR, Definition 2.3]). When computing $C_{y,I}$ and $N_{y,I}$ we use a lexicographical ordering on $R$ where $y > x_j$ for all $i \neq j$ if $y = x_i$ since this gives us a $y$-compatible order.

i1 : R = QQ[a,b,c,d]

o1 = R

o1 : PolynomialRing

i2 : f = 3*a*b + 4*b*c+ 16*a*c + 18*d

o2 = 3a*b + 16a*c + 4b*c + 18d

o2 : R

i3 : i = ideal f

o3 = ideal(3a*b + 16a*c + 4b*c + 18d)

o3 : Ideal of R

i4 : isGVD i

o4 = true

Square-free monomial ideals that are geometrically vertex decomposable are precisely those square-free monomial ideals whose associated simplicial complex are vertex decomposable [KR, Proposition 2.9]. The edge ideal of a chordal graph corresponds to a simplicial complex that is vertex decomposable (for more, see the EdgeIdeals package). The option Verbose shows the intermediate steps; in particular, Verbose displays what variable is being used to test a decomposition, as well as the ideals $C_{y,I}$ and $N_{y,I}$.

i5 : R = QQ[a,b,c,d]

o5 = R

o5 : PolynomialRing

i6 : i = ideal(a*b, a*c, a*d, b*c, b*d, c*d) -- edge ideal of a complete graph K_4, a chordal graph

o6 = ideal (a*b, a*c, a*d, b*c, b*d, c*d)

o6 : Ideal of R

i7 : isGVD(i, Verbose=>true)
I = ideal(a*b,a*c,a*d,b*c,b*d,c*d)
-- decomposing with respect to a
-- C = ideal(c*d,b*d,b*c,d,c,b)
-- N = ideal(c*d,b*d,b*c)
I = ideal(c*d,b*d,b*c)
-- decomposing with respect to b
-- C = ideal(c*d,d,c)
-- N = ideal(c*d)
I = ideal(c*d)
-- decomposing with respect to c
-- C = ideal d
-- N = ideal()
I = ideal()
-- zero ideal
I = ideal d
-- generated by indeterminates
I = ideal(c*d,d,c)
-- decomposing with respect to c
-- C = ideal(d,1)
-- N = ideal d
I = ideal d
-- generated by indeterminates
I = ideal(d,1)
-- unit ideal
I = ideal(c*d,b*d,b*c,d,c,b)
-- decomposing with respect to b
-- C = ideal(d,c,1)
-- N = ideal(d,c)
I = ideal(d,c)
-- generated by indeterminates
I = ideal(d,c,1)
-- unit ideal

o7 = true

The following is an example of a toric ideal of graph that is geometrically vertex decomposable, and another example of a toric ideal of a graph that is not geometrically vertex decomposable. The second ideal is not Cohen-Macaulay, so it cannot be geometrically vertex decomposable [KR, Corollary 4.5]. For background on toric ideals of graphs, see [CDSRVT, Section 3].

i8 : R = QQ[e_1..e_7]

o8 = R

o8 : PolynomialRing

i9 : i = ideal(e_2*e_7-e_5*e_6, e_1*e_4-e_2*e_3) -- the toric ideal of a graph

o9 = ideal (- e e  + e e , - e e  + e e )
               5 6    2 7     2 3    1 4

o9 : Ideal of R

i10 : isGVD i

o10 = true

i11 : R = QQ[e_1..e_10]

o11 = R

o11 : PolynomialRing

i12 : i = ideal(e_1*e_4-e_2*e_3, e_2^2*e_7*e_8*e_9-e_4^2*e_5*e_6*e_10, e_1*e_2*e_7*e_8*e_9-e_3*e_4*e_5*e_6*e_10, e_1^2*e_7*e_8*e_9-e_3^2*e_5*e_6*e_10)

                             2          2                                  
o12 = ideal (- e e  + e e , e e e e  - e e e e  , e e e e e  - e e e e e  ,
                2 3    1 4   2 7 8 9    4 5 6 10   1 2 7 8 9    3 4 5 6 10 
      -----------------------------------------------------------------------
       2          2
      e e e e  - e e e e  )
       1 7 8 9    3 5 6 10

o12 : Ideal of R

i13 : isGVD i

o13 = false

[CDSRVT] Mike Cummings, Sergio Da Silva, Jenna Rajchgot, and Adam Van Tuyl. Geometric vertex decomposition and liaison for toric ideals of graphs. To appear in Algebraic Combinatorics, preprint available at arXiv:2207.06391 (2022).

[KMY] Allen Knutson, Ezra Miller, and Alexander Yong. Gröbner geometry of vertex decompositions and of flagged tableaux. J. Reine Angew. Math. 630 (2009) 1–31.

[KR] Patricia Klein and Jenna Rajchgot. Geometric vertex decomposition and liaison. Forum Math. Sigma, 9 (2021) e70:1-23.