oneStepGVD -- computes a geometric vertex decomposition

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

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