# oneStepGVD -- computes a geometric vertex decomposition

## Synopsis

• Usage:
oneStepGVD(I, y)
• Inputs:
• I, an ideal,
• y, , an indeterminate in the ring
• Optional inputs:
• CheckDegenerate => ..., default value false, check whether the geometric vertex decomposition is degenerate
• CheckUnmixed => ..., default value true, check whether ideals encountered are unmixed
• Verbose => ..., default value false, print additional output
• Outputs:
• , containing whether the $C_{y,I}$ and $N_{y,I}$ ideals form a valid geometric vertex decomposition, these ideals $C_{y,I}$ and $N_{y,I}$, and if CheckDegenerate=>true, whether the one-step decomposition is degenerate or nondegenerate

## Description

This function computes a geometric vertex decomposition of an ideal based upon work of Knutson, Miller, and Yong [KMY, Theorem 2.1]. Geometric vertex decomposition is the key step in the recursive definition of geometrically vertex decomposable ideals. The function oneStepGVD is repeatedly used by isGVD to determine if an ideal is a geometrically vertex decomposable ideal.

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

If ${\rm in}_y(I) = C_{y,I} \cap (N_{y,I} + \langle y \rangle),$ then we call this decomposition a geometric vertex decomposition of $I$.

Furthermore, we say that a geometric vertex decomposition is degenerate if $C_{y,I} = \langle 1 \rangle$ or if $\sqrt{C_{y,I}} = \sqrt{N_{y,I}}$. The geometric vertex decomposition is nondegenerate otherwise.

For a given variable $y$, the function oneStepGVD returns a sequence, where the first element in the sequence is true or false depending if the given variable $y$ gives a geometric vertex decomposition of $I$, while the second element is the ideal $C_{y,I}$ and the third element in the sequence is the ideal $N_{y,I}$. If CheckDegenerate=>true, then there is a fourth element in the output, either "degenerate" or "nondegenerate", corresponding to whether the geometric vertex decomposition is degenerate.

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 Definition 2.3 of [KR]). 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 : oneStepGVD(i, a) o4 = (true, ideal(3b + 16c), ideal ()) o4 : Sequence

In the example below, the ideal $I$ is the edge ideal of the complete graph $K_4$. We also check if the decomposition is degenerate (see CheckDegenerate). For more on edge ideals, see the EdgeIdeals package.

 i5 : R = QQ[a,b,c,d]; i6 : i = ideal(a*b, a*c, a*d, b*c, b*d, c*d); -- edge ideal of complete graph K_4, a chordal graph o6 : Ideal of R i7 : oneStepGVD(i, c, CheckDegenerate=>true) o7 = (true, ideal (a*d, b*d, a*b, d, a, b), ideal (a*d, b*d, a*b), ------------------------------------------------------------------------ nondegenerate) o7 : Sequence

The example below is the toric ideal of a graph such that the quotient ring is not Cohen-Macaulay. By [KR, Lemma 2.6], for an ideal $I$ to have a geometric vertex decomposition with respect to the variable $y$, no term of the Gröbner bases can be divided by $y^2$. In this example, the Gröbner basis of $I$ contains an element with a term divisible by $e_1^2$. So $I$ does not have a geometric vertex decomposition with respect to $y = e_1$. For background on toric ideals of graphs, see [CDSRVT, Section 3].

 i8 : R = QQ[e_1..e_10]; i9 : 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); o9 : Ideal of R i10 : mingens gb i o10 = | e_2e_3-e_1e_4 e_2^2e_7e_8e_9-e_4^2e_5e_6e_10 ----------------------------------------------------------------------- e_1e_2e_7e_8e_9-e_3e_4e_5e_6e_10 e_1^2e_7e_8e_9-e_3^2e_5e_6e_10 | 1 4 o10 : Matrix R <--- R i11 : oneStepGVD(i, e_1) 2 2 o11 = (false, ideal (e e e e - e e e e , e , e e e e , e e e ), 2 7 8 9 4 5 6 10 4 2 7 8 9 7 8 9 ----------------------------------------------------------------------- 2 2 ideal(e e e e - e e e e )) 2 7 8 9 4 5 6 10 o11 : Sequence

## References

[CDSRVT] M. Cummings, S. Da Silva, J. Rajchgot, and A. Van Tuyl. Geometric Vertex Decomposition and Liaison for Toric Ideals of Graphs. Preprint, arXiv:2207.06391 (2022).

[KMY] A. Knutson, E. Miller, and A. Yong. Gröbner Geometry of Vertex Decompositions and of Flagged Tableaux. J. Reine Angew. Math. 630 (2009) 1–31.

[KR] P. Klein and J. Rajchgot. Geometric Vertex Decomposition and Liaison. Forum of Math, Sigma, 9 (2021) e70:1-23.

• CheckDegenerate -- check whether the geometric vertex decomposition is degenerate
• CheckUnmixed -- check whether ideals encountered are unmixed
• CyI -- computes the ideal $C_{y,I}$ for a given ideal and indeterminate
• getGVDIdeal -- computes the $C_{y,I}$ or $N_{y,I}$ ideal at any point in the GVD recursion tree
• isGVD -- checks whether an ideal is geometrically vertex decomposable
• isLexCompatiblyGVD -- checks whether an ideal is <-compatibly geometrically vertex decomposable for a given order
• isWeaklyGVD -- checks whether an ideal is weakly geometrically vertex decomposable
• NyI -- computes the ideal $N_{y,I}$ for a given ideal and indeterminate
• Verbose -- print additional output

## Ways to use oneStepGVD :

• "oneStepGVD(Ideal,RingElement)"

## For the programmer

The object oneStepGVD is .