# isGVD -- checks whether an ideal is geometrically vertex decomposable

## Synopsis

• Usage:
isGVD I
• Inputs:
• Optional inputs:
• CheckCM => ..., default value "always", when to perform a Cohen-Macaulay check on the ideal
• CheckUnmixed => ..., default value true, check whether ideals encountered are unmixed
• IsIdealHomogeneous => ..., default value false, specify whether an ideal is homogeneous
• IsIdealUnmixed => ..., default value false, specify whether an ideal is unmixed
• UniversalGB => ..., default value false, whether the generators for an ideal form a universal Gröbner basis
• Verbose => ..., default value false
• Outputs:

## Description

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

## References

[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.

• CheckCM -- when to perform a Cohen-Macaulay check on the ideal
• CheckUnmixed -- check whether ideals encountered are unmixed
• isGeneratedByIndeterminates -- checks whether the ideal is generated by indeterminates
• IsIdealHomogeneous -- specify whether an ideal is homogeneous
• IsIdealUnmixed -- specify whether an ideal is unmixed
• isLexCompatiblyGVD -- checks whether an ideal is <-compatibly geometrically vertex decomposable for a given order
• isUnmixed -- checks whether an ideal is unmixed
• isWeaklyGVD -- checks whether an ideal is weakly geometrically vertex decomposable
• oneStepGVD -- computes a geometric vertex decomposition
• UniversalGB -- whether the generators for an ideal form a universal Gröbner basis
• Verbose -- request verbose feedback

• isGVD(Ideal)

## For the programmer

The object isGVD is .