Properties of the Toric Rings of a Chordal Bipartite Family of Graphs

Laura Ballard Mathematics Department, Syracuse University, Syracuse, NY 13244, U.S.A. [email protected]

Abstract.

This work concerns the study of properties of a group of Koszul algebras coming from the toric ideals of a chordal bipartite infinite family of graphs (alternately, these rings may be interpreted as coming from determinants of certain ladder-like structures). We determine a linear system of parameters for each ring and explicitly determine the Hilbert series for the resulting Artinian reduction. As corollaries, we obtain the multiplicity and regularity of the original rings. This work extends results easily derived from lattice theory for a subfamily coming from a two-sided ladder to a family where, as we show, lattice theory no longer applies in any obvious way and includes constructive proofs which may be useful in future study of these rings and others.

Key words and phrases:

Koszul algebra, toric ring, graph, chordal bipartite, Castelnuovo-Mumford regularity, multiplicity

2020 Mathematics Subject Classification:

05E40, 13C15, 13D02, 13F65, 13H15, 16S37

L. Ballard was partially supported by the National Science Foundation (DMS-1003384).

1. Introduction

In recent decades, there has been a growing interest in the investigation of algebraic invariants associated to combinatorial structures. Toric ideals of graphs (and the associated edge rings), a special case of the classical notion of a toric ideal, have been studied by various authors with regard to invariants such as depth, dimension, projective dimension, regularity, graded Betti numbers, Hilbert series, and multiplicity, usually for particular families of graphs (see for example [2, 3, 5, 7, 8, 9, 10, 12, 14, 16, 17, 18, 19, 22, 23, 26]). We note in Remarks 2.6 and 2.14 that the family we consider does not overlap at all or for large $n$ with those considered in [5], [8], [9], and [23]; it is more obviously distinct from other families that have been studied. We think it fitting to mention that the recent book by Herzog, Hibi, and Ohsugi ([15]) also investigates toric ideals of graphs as well as binomial ideals coming from other combinatorial structures.

In this work, we consider a family of graphs with iterated subfamilies and develop algebraic properties of the toric rings associated to the family which depend only on the number of vertices (equivalently, the number of edges) in the associated graphs. In the development of this project, we were particularly inspired by the work of Jennifer Biermann, Augustine O’Keefe, and Adam Van Tuyl in [3], where they establish a lower bound for the regularity of the toric ideal of any finite simple graph and an upper bound for the regularity of the toric ideal of a chordal bipartite graph. Our goal is to construct as “simple” a family of graphs as possible that still yields interesting toric ideals. It is our hope that our process and results will lead to further generalizations of properties of toric ideals for other (perhaps broader) families of graphs, or for graphs containing or arising from such graphs.

Herein, we introduce the infinite family $\mathcal{F}$ of chordal bipartite graphs $G_{n}^{t}$ , where $n$ determines the number of edges and vertices and $t$ determines the structure of the graph, and establish some algebraic properties of the toric rings $R(n,t)$ associated to the graphs $G_{n}^{t}$ . The use of bipartite graphs makes each $R(n,t)$ normal and Cohen-Macaulay by [25] and [15]; we use the latter in Section 3. Our main results prove to be independent of $t$ and depend only on $n$ .

In Section 2, we construct the family $\mathcal{F}$ of graphs $G_{n}^{t}$ from a family of ladder-like structures $L_{n}^{t}$ so that the toric ideals of the $G_{n}^{t}$ are generalized determinantal ideals of the $L_{n}^{t}$ . The ladder-like structures associated to a subfamily $\mathcal{F}_{1}\subset\mathcal{F}$ , introduced in Example 2.4, are in fact two-sided ladders (for large $n$ ), so that the family of rings $R(n,t)$ is a generalization of the family of ladder determinantal rings coming from $\mathcal{F}_{1}$ . While the rings arising from $\mathcal{F}_{1}$ come from a distributive lattice and have easily derived properties (see for example [15]), we show that the rings associated to $\mathcal{F}$ do not naturally arise from any lattice in general, and merit closer study.

In Section 3, we establish some algebraic properties of the $R(n,t)$ , particularly Krull dimension, projective dimension, multiplicity, and regularity. To do so, we prove that the determinantal generators of the defining ideal $I_{G_{n}^{t}}$ are a Gröbner basis (it follows immediately from [15] that $R(n,t)$ is Koszul) and work with the initial ideal $\text{in}_{>}I_{G_{n}^{t}}$ . We also develop a system of parameters $\overline{X_{n}}$ that allows us to work with Artinian reductions in part of our treatment, and their Hilbert series.

Our first result establishes the Krull dimension of the toric ring $R(n,t)=S(n)/I_{G_{n}^{t}}$ , where the ring $S(n)=k[x_{0},x_{2},x_{3},\ldots,x_{2n+3},x_{2n+4}]$ is the polynomial ring over the edges of $G_{n}^{t}$ and $I_{G_{n}^{t}}$ is the toric ideal of $G_{n}^{t}$ .

Theorem 1.1 (Theorem 3.4).

The dimension of $R(n,t)$ is

\dim R(n,t)=n+3.

As a corollary, since $R(n,t)$ comes from a bipartite graph and is hence Cohen-Macaulay (Corollary 2.16), we obtain the projective dimension of $R(n,t)$ .

Corollary 1.2 (Corollary 3.5).

The projective dimension of $R(n,t)$ over $S(n)$ is

\textnormal{pd}_{S(n)}R(n,t)=n+1.

We then develop a linear system of parameters for $R(n,t)$ , using differences of elements on antidiagonals of the ladder-like structure $L_{n}^{t}$ .

Proposition 1.3 (Proposition 3.10).

Let $R(n,t)=S(n)/I_{G_{n}^{t}}$ . Then the image of

X_{n}=x_{0},x_{2}-x_{3},x_{4}-x_{5},\ldots,x_{2n}-x_{2n+1},x_{2n+2}-x_{2n+3},x_{2n+4}

in $R(n,t)$ is a system of parameters for $R(n,t)$ .

Since $R(n,t)$ is Cohen-Macaulay, the linear system of parameters above is a regular sequence (Corollary 3.12).

With the aim of obtaining the multiplicity and regularity of $R(n,t)$ , we form an Artinian quotient of $R(n,t)$ by the regular sequence above and call it $\widehat{R(n,t)}$ . We note that $\widehat{R(n,t)}$ does not denote the completion, and explain the choice of notation in Definition 3.7.

Using a convenient vector space basis for $\widehat{R(n,t)}$ established in Lemma 3.13, we show the coefficients of the Hilbert series for $\widehat{R(n,t)}$ .

Theorem 1.4 (Theorem 3.16).

If $R(n,t)=S(n)/I_{G_{n}^{t}}$ and $\widehat{R(n,t)}\cong R(n,t)/(\overline{X_{n}})$ , we have

{\displaystyle\dim_{k}(\widehat{R(n,t)})_{i}=\begin{cases}1&i=0\\ {\displaystyle\frac{1}{i!}\prod_{j=1}^{i}(n+j-2(i-1))}&i\geq 1.\end{cases}}

In particular, $\dim_{k}(\widehat{R(n,t)})_{i}=0$ when $i>n/2+1$ .

As a corollary, we obtain the regularity of $R(n,t)$ , which is equal to the top nonzero degree of $\widehat{R(n,t)}$ .

Corollary 1.5 (Corollary 3.18).

For $G_{n}^{t}\in\mathcal{F}$ ,

\operatorname{reg}R(n,t)=\left\lfloor n/2\right\rfloor+1.

We include an alternate graph-theoretic proof of the result above at the end of this work. Beginning with an upper bound from [3] (or equivalently for our purposes, one from [14]) and then identifying the initial ideal $\text{in}_{>}I_{G_{n}^{t}}$ with the edge ideal of a graph, we use results from [4] (allowing us to use $\text{in}_{>}I_{G_{n}^{t}}$ instead of $I_{G_{n}^{t}}$ ) and then [13] for a lower bound which agrees with our upper bound.

From a recursion established in Lemma 3.15, we go on to prove a Fibonacci relationship between the lengths of the Artinian rings $\widehat{R(n,t)}$ in Proposition 3.19, and obtain the multiplicity of $R(n,t)$ as a corollary. In the following, we drop $t$ for convenience.

Corollary 1.6 (Corollary 3.21).

For $n\geq 2$ , there is an equality of multiplicities

e(R(n))=e(R(n-1))+e(R(n-2)).

In particular,

e(R(n))=F\left(n+3\right)=\frac{(1+\sqrt{5})^{n+3}-(1-\sqrt{5})^{n+3}}{2^{n+3}\sqrt{5}}.

For more background, detail, and motivation, we refer the reader to [1], but note that different notation and indexing conventions have been employed in this work. Throughout, $k$ is a field.

Acknowledgements. Macaulay2 [11] was used for computation and hypothesis formation. We would like to thank Syracuse University for its support and hospitality and Claudia Miller for her valuable input on the original project in [1] and this condensed version. We also acknowledge the partial support of an NSF grant.

2. The Family of Toric Rings

In the following, we define a family of toric rings $R(n,t)$ coming from an iterative chordal bipartite family of graphs, $\mathcal{F}$ . We show that although one subfamily of these rings comes from join-meet ideals of a (distributive) lattice and has some easily derived algebraic invariants, this is not true in general. The reader may find the definition of the toric ideal of a graph in Section 2.2, when it becomes relevant to the discussion. We recall for the reader that a chordal bipartite graph is a bipartite graph in which every cycle of length greater than or equal to six has a chord.

2.1. The Family $\mathcal{F}$ of Graphs

Below, we define the family $\mathcal{F}$ of chordal bipartite graphs iteratively from a family of ladder-like structures $L_{n}^{t}$ . We note that the quantities involved in the following definition follow patterns as follows:

$n$	$\left\lfloor{n/2}\right\rfloor+2$	$\left\lceil{n/2}\right\rceil+2$
0	2	2
1	2	3
2	3	3
3	3	4
⋮	⋮	⋮

Definition 2.1.

For each $n\geq 0$ and each $t\in\mathbb{F}_{2}^{n+1}$ , we construct a ladder-like structure $L_{n}^{t}$ with $(\left\lfloor{n/2}\right\rfloor+2)$ rows and $(\left\lceil{n/2}\right\rceil+2)$ columns and with nonzero entries in the set $\{x_{0},x_{2},x_{3},\ldots,x_{2n+4}\}$ . To do so, we use the notation $\widehat{t}\in\mathbb{F}_{2}^{n}$ for the first $n$ entries of $t$ , that is, all except the last entry. The construction is as follows, where throughout, indices of entries in $L_{n}^{t}$ are strictly increasing from left to right in each row and from top to bottom in each column. We note that $L_{n}^{t}$ does not depend on $t$ for $n<2$ , but does for $n\geq 2$ .

•

For $n=0$ , the ladder-like structure $L_{0}^{0}=L_{0}^{1}$ is

$\begin{matrix}x_{0}&x_{2}\\ x_{3}&x_{4}\end{matrix}$
•

For $n=1$ , to create $L_{1}^{t}$ (regardless of what $t$ is in $\mathbb{F}_{2}^{2}$ ), we add another column with the entries $x_{5}$ and $x_{6}$ to the right of $L_{0}^{\widehat{t}}$ to obtain

$\begin{matrix}x_{0}&x_{2}&x_{5}\\ x_{3}&x_{4}&x_{6}\end{matrix}$
•
For $2\leq n\equiv 0\mod 2(\equiv 1\mod 2)$ , to create $L_{n}^{t}$ , we add another row (column) with the entries $x_{2n+3},x_{2n+4}$ below (to the right of) $L_{n-1}^{\widehat{t}}$ in the following way:
- $\circ$
  
  The entry $x_{2n+4}$ is in the ultimate row and column, row $\left\lfloor{n/2}\right\rfloor+2$ and column $\left\lceil{n/2}\right\rceil+2$ .
- $\circ$
  The entry $x_{2n+3}$ is in the new row (column) in a position directly below (to the right of) another nonzero entry in $L_{n}^{t}$ .
  - *
    
    If the last entry of $t$ is $0$ , $x_{2n+3}$ is directly beneath (to the right of) the first nonzero entry in the previous row (column).
  - *
    
    If the last entry of $t$ is $1$ , $x_{2n+3}$ is directly beneath (to the right of) the second nonzero entry in the previous row (column).

In this way, the entries in $t$ determine the choice at each stage for the placement of $x_{2n+3}$ .

Remark 2.2.

We note a few things about this construction for $n\equiv 0\mod 2$ ( $\equiv 1\mod 2$ ), which may be examined in the examples below:

•

We note that $x_{2n+4}$ is directly beneath (to the right of) $x_{2n+2}$ .
•

We note that the only entries in row $\left\lfloor{n/2}\right\rfloor+1$ (column $\left\lceil{n/2}\right\rceil+1$ ) of $L_{n-1}^{\widehat{t}}$ are $x_{2n-1}$ , $x_{2n}$ , and $x_{2n+2}$ , so that the choices listed for placement of $x_{2n+3}$ are the only cases. In particular, $t_{n+1}=0$ if and only if $x_{2n+3}$ is directly beneath (to the right of) $x_{2n-1}$ , and $t_{n+1}=1$ if and only if $x_{2n+3}$ is directly beneath (to the right of) $x_{2n}$ .
•

Finally, we note that the only entries in column $\left\lceil{n/2}\right\rceil+2$ (row $\left\lfloor{n/2}\right\rfloor+2$ ) of $L_{n}^{t}$ are $x_{2n+1}$ , $x_{2n+2}$ , and $x_{2n+4}$ , and that the only entries in row $\left\lfloor{n/2}\right\rfloor+2$ (column $\left\lceil{n/2}\right\rceil+2$ ) of $L_{n}^{t}$ are $x_{2n+3}$ and $x_{2n+4}$ .

Example 2.3.

We have

L_{2}^{(1,1,1)}=\begin{matrix}x_{0}&x_{2}&x_{5}\\ x_{3}&x_{4}&x_{6}\\ &x_{7}&x_{8}\end{matrix}\hskip 56.9055ptL_{2}^{(0,0,0)}=\begin{matrix}x_{0}&x_{2}&x_{5}\\ x_{3}&x_{4}&x_{6}\\ x_{7}&&x_{8}\end{matrix}

In either of the cases above, we could go on to construct $L_{3}^{\widehat{t}}$ and $L_{4}^{t}$ in the following way: For $n=3$ , place $x_{10}$ to the right of $x_{8}$ and place $x_{9}$ to the right of either $x_{5}$ or $x_{6}$ , depending whether the last entry of $\widehat{t}$ is $0$ or $1$ , respectively. Then for $n=4$ , place $x_{12}$ below $x_{10}$ and place $x_{11}$ below either $x_{7}$ or $x_{8}$ , depending whether the last entry of $t$ is $0$ or $1$ , respectively.

Example 2.4.

In fact, when the entries of $t$ are all ones, we see that $L_{n}^{(1,1,\ldots,1)}$ has a ladder shape (is a two-sided ladder for $n\geq 3)$ , shown below in the case when $2\leq n\equiv 0\mod 2$ :

\begin{matrix}x_{0}&x_{2}&x_{5}&\\ x_{3}&x_{4}&x_{6}&x_{9}&\\ &x_{7}&x_{8}&x_{10}&x_{13}&\\ &&x_{11}&x_{12}&x_{14}&x_{17}&\\ &&&x_{15}&x_{16}&x_{18}&x_{21}&\\ &&&&x_{19}&x_{20}&x_{22}&x_{25}&\\ &&&&&x_{23}&x_{24}&x_{26}&\ddots&\\ &&&&&&x_{27}&x_{28}&\ddots&x_{2n+1}\\ &&&&&&&\ddots&\ddots&x_{2n+2}\\ &&&&&&&&x_{2n+3}&x_{2n+4}.\end{matrix}

We denote the subfamily of graphs coming from $t=(1,1,\ldots,1)$ by $\mathcal{F}_{1}\subset\mathcal{F}$ .

When the entries of $t$ are all zeros, $L_{n}^{(0,0,\ldots,0)}$ has the following structure, shown below in the case when $2\leq n\equiv 0\mod 2$ :

\begin{matrix}x_{0}&x_{2}&x_{5}&x_{9}&x_{13}&x_{17}&x_{21}&x_{25}&\cdots&x_{2n+1}\\ x_{3}&x_{4}&x_{6}\\ x_{7}&&x_{8}&x_{10}\\ x_{11}&&&x_{12}&x_{14}\\ x_{15}&&&&x_{16}&x_{18}\\ x_{19}&&&&&x_{20}&x_{22}\\ x_{23}&&&&&&x_{24}&x_{26}\\ x_{27}&&&&&&&x_{28}&\ddots\\ \vdots&&&&&&&&\ddots&x_{2n+2}\\ x_{2n+3}&&&&&&&&&x_{2n+4}.\end{matrix}

For a more varied example, we have $L_{16}^{(1,0,1,0,1,1,0,0,1,1,1,0,0,0,1,0,0)}$ below:

\begin{matrix}x_{0}&x_{2}&x_{5}&x_{9}&&&&&&\\ x_{3}&x_{4}&x_{6}&&&&&&&\\ &x_{7}&x_{8}&x_{10}&x_{13}&x_{17}&&&&\\ &&x_{11}&x_{12}&x_{14}&&&&&\\ &&x_{15}&&x_{16}&x_{18}&x_{21}&x_{25}&x_{29}&x_{33}\\ &&&&x_{19}&x_{20}&x_{22}&&&\\ &&&&&x_{23}&x_{24}&x_{26}&&\\ &&&&&x_{27}&&x_{28}&x_{30}&\\ &&&&&&&x_{31}&x_{32}&x_{34}\\ &&&&&&&x_{35}&&x_{36}.\end{matrix}

Definition 2.5.

If we associate a vertex to each row and each column and an edge to each nonzero entry of $L_{n}^{t}$ , we have a finite simple connected bipartite graph $G_{n}^{t}$ . The set $V_{r}$ of vertices corresponding to rows and the set $V_{c}$ of vertices corresponding to columns form a bipartition of the vertices of $G_{n}^{t}$ . We say a graph $G$ is in $\mathcal{F}$ if $G=G_{n}^{t}$ for some $n\geq 0$ and some $t\in\mathbb{F}_{2}^{n+1}$ .

Remark 2.6.

We note that by construction $G_{n}^{t}$ has no vertices of degree one, since each row and each column of $L_{n}^{t}$ has more than one nonzero entry. This ensures that for large $n$ our family is distinct from that studied in [5], since a Ferrers graph with bipartitation $V_{1}$ and $V_{2}$ with no vertices of degree one must have at least two vertices in $V_{1}$ of degree $|V_{2}|$ and at least two vertices in $V_{2}$ of degree $|V_{1}|$ , impossible for our graphs when $n\geq 3$ , as the reader may verify. We also use the fact that $G_{n}^{t}$ has no vertices of degree one for an alternate proof of the regularity of $R(n,t)$ at the end of this work.

Example 2.7.

When $n=5$ , $G_{5}^{(1,1,\ldots,1)}\in\mathcal{F}_{1}$ is

We develop properties of the $L_{n}^{t}$ which allow us to show in Section 2.2 that certain minors of the $L_{n}^{t}$ are generators for the toric rings of the corresponding graphs $G_{n}^{t}$ .

Definition 2.8.

For this work, a distinguished minor of $L_{n}^{t}$ is a $2$ -minor involving only (nonzero) entries of the ladder-like structure $L_{n}^{t}$ , coming from a $2\times 2$ subarray of $L_{n}^{t}$ .

Proposition 2.9.

For each $i\geq 1$ and each $f\in\mathbb{F}_{2}^{i+1}$ , the entry $x_{2i+3}$ and the entry $x_{2i+4}$ each appear in exactly two distinguished minors of $L_{i}^{f}$ . For $i\equiv 0\mod 2(\equiv 1\mod 2)$ , these minors are of the form

s_{2i}:=x_{2i+1}x_{2i+3}-x_{j_{2i}}x_{2i+4}

coming from the subarray

\begin{bmatrix}x_{j_{2i}}&x_{2i+1}\\ x_{2i+3}&x_{2i+4}\end{bmatrix}\hskip 56.9055pt\left(\begin{bmatrix}x_{j_{2i}}&x_{2i+3}\\ x_{2i+1}&x_{2i+4}\end{bmatrix}\right)

for some $j_{2i}\in\{0,2,3,\ldots,2i-2\}$ and

s_{2i+1}:=x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4}

coming from the subarray

\begin{bmatrix}x_{j_{2i+1}}&x_{2i+2}\\ x_{2i+3}&x_{2i+4}\end{bmatrix}\hskip 56.9055pt\left(\begin{bmatrix}x_{j_{2i+1}}&x_{2i+3}\\ x_{2i+2}&x_{2i+4}\end{bmatrix}\right)

for some $j_{2i+1}\in\{2i-1,2i\}$ , and the only distinguished minor of $L_{n}^{t}$ with indices all less than $5$ is $s_{1}:=x_{2}x_{3}-x_{0}x_{4}$ .

Proof.

The last statement is clear by Definition 2.1; we prove the remaining statements by induction on $i$ . For $i=1$ , we have the distinguished minors $s_{2}=x_{3}x_{5}-x_{0}x_{6}$ and $s_{3}=x_{4}x_{5}-x_{2}x_{6}$ coming from the subarrays

\begin{bmatrix}x_{0}&x_{5}\\ x_{3}&x_{6}\end{bmatrix}

and

\begin{bmatrix}x_{2}&x_{5}\\ x_{4}&x_{6}\end{bmatrix}

where $j_{2}=0\in\{0\}$ and $j_{3}=2\in\{1,2\}$ , so we have our base case. Now suppose the statement is true for $i$ with $1\leq i<n$ , and let $n\equiv 0\mod 2(\equiv 1\mod 2)$ and $t\in\mathbb{F}_{2}^{n+1}$ .

Case 1: If $t_{n+1}=0$ , then by Remark 2.2, $x_{2n+3}$ is in the same column (row) as $x_{2n-1}$ . By induction, we have the distinguished minor $s_{2n-2}=x_{2n-1}x_{2n+1}-x_{j_{2n-2}}x_{2n+2}$ coming from the subarray

\begin{bmatrix}x_{j_{2n-2}}&x_{2n+1}\\ x_{2n-1}&x_{2n+2}\end{bmatrix}\hskip 56.9055pt\left(\begin{bmatrix}x_{j_{2n-2}}&x_{2n-1}\\ x_{2n+1}&x_{2n+2}\end{bmatrix}\right).

Then in fact we have a subarray of the form

\begin{bmatrix}x_{j_{2n-2}}&x_{2n+1}\\ x_{2n-1}&x_{2n+2}\\ x_{2n+3}&x_{2n+4}\end{bmatrix}\hskip 56.9055pt\left(\begin{bmatrix}x_{j_{2n-2}}&x_{2n-1}&x_{2n+3}\\ x_{2n+1}&x_{2n+2}&x_{2n+4}\end{bmatrix}\right),

so that we have the distinguished minors

	$\displaystyle s_{2n}$	$\displaystyle=$	$\displaystyle x_{2n+1}x_{2n+3}-x_{j_{2n-2}}x_{2n+4}$
	$\displaystyle s_{2n+1}$	$\displaystyle=$	$\displaystyle x_{2n+2}x_{2n+3}-x_{2n-1}x_{2n+4}$

with

j_{2n}=j_{2n-2}\in\{0,2,3,\ldots,2n-4\}\subset\{0,2,3,\ldots,2n-2\}

by induction and with

j_{2n+1}=2n-1\in\{2n-1,2n\}.

Since the only entries in row $\left\lfloor{n/2}\right\rfloor+2$ (column $\left\lceil{n/2}\right\rceil+2$ ) of $L_{n}^{t}$ are $x_{2n+3}$ and $x_{2n+4}$ and since the only entries in column $\left\lceil{n/2}\right\rceil+2$ (row $\left\lfloor{n/2}\right\rfloor+2$ ) of $L_{n}^{t}$ are $x_{2n+1}$ , $x_{2n+2}$ , and $x_{2n+4}$ by Remark 2.2, these are the only distinguished minors of $L_{n}^{t}$ containing either $x_{2n+3}$ or $x_{2n+4}$ , as desired.

Case 2 for $t_{n+1}=1$ is analogous and yields

j_{2n}=j_{2n-1}\in\{2n-3,2n-2\}\subset\{0,2,3,\ldots,2n-2\}

and

j_{2n+1}=2n\in\{2n-1,2n\}.

∎

Definition 2.10.

Define the integers $j_{2i}$ , $j_{2i+1}$ for $j_{2},\ldots,j_{2n+1}$ as in the statement of Proposition 2.9. We note in the remark below some properties of the $j_{k}$ .

Remark 2.11.

From the proof of Proposition 2.9, we note that $j_{2}=0$ , $j_{3}=2$ , and that for $i\geq 2$ , we have the following:

	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 0\iff j_{2i}=j_{2i-2}\iff j_{2i+1}=2i-1$
	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 1\iff j_{2i}=j_{2i-1}\iff j_{2i+1}=2i.$

For the sake of later proofs, we extend the notion of $j_{k}$ naturally to $s_{1}=x_{2}x_{3}-x_{0}x_{4}$ and say that $j_{1}=0$ , and note the following properties of the $j_{k}$ for $1\leq k\leq 2n+1$ :

•

We have $j_{2i}\in\{j_{2i-2},j_{2i-1}\}$ and $j_{2i}\leq 2i-2$ . Indeed, for $i=1$ , $j_{2}=j_{1}=0$ , and for $i\geq 2$ , this is clear from the statement above.
•

We have $j_{2i+1}\in\{2i-1,2i\}$ . Indeed, for $i=0$ , $j_{1}=0\in\{-1,0\}$ , for $i=1$ , $j_{3}=2\in\{1,2\}$ , and for $i\geq 2$ , this follows from the statement above.
•

The $j_{2i}$ form a non-decreasing sequence. Indeed, for $i\geq 2$ , either $j_{2i}=j_{2i-2}$ or $j_{2i}=j_{2i-1}\geq 2i-3>2i-4\geq j_{2i-2}$ .

Remark 2.12.

We also note from the proof above that the following is a subarray of $L_{n}^{t}$ for all $i\equiv 0\mod 2(\equiv 1\mod 2)$ such that $1\leq i\leq n$ , which we use in the proof of the proposition below:

\begin{bmatrix}x_{j_{2i}}&x_{2i+1}\\ x_{j_{2i+1}}&x_{2i+2}\\ x_{2i+3}&x_{2i+4}\end{bmatrix}\hskip 56.9055pt\left(\begin{bmatrix}x_{j_{2i}}&x_{j_{2i+1}}&x_{2i+3}\\ x_{2i+1}&x_{2i+2}&x_{2i+4}\end{bmatrix}\right)

Proposition 2.13.

For $n\geq 0$ , each graph $G_{n}^{t}\in\mathcal{F}$ is chordal bipartite with vertex bipartition $V_{r}\cup V_{c}$ of cardinalities

	$\displaystyle\|V_{r}\|=\left\lfloor\frac{n}{2}\right\rfloor+2$
	$\displaystyle\|V_{c}\|=\left\lceil\frac{n}{2}\right\rceil+2.$

Proof.

We already know by Definition 2.5 that every graph $G_{n}^{t}$ is bipartite for $n\geq 0$ , with the bipartition above coming from the rows and columns of $L_{n}^{t}$ . The cardinalities of the vertex sets follow from Definition 2.2. We prove the chordal bipartite property by induction on $n$ . It is clear for $i=0$ and $i=1$ that $G_{i}^{f}$ is chordal bipartite for $f\in\mathbb{F}_{2}^{i+1}$ , since these graphs have fewer than six vertices. Now suppose $G_{i}^{f}$ is chordal bipartite for $i$ with $1\leq i<n\equiv 0\mod 2(\equiv 1\mod 2)$ , and consider $G_{n}^{t}$ for $t\in\mathbb{F}_{2}^{n+1}$ . We know that the following array (or its transpose) is a subarray of $L_{n}^{t}$ by Remark 2.12, and we include for reference the corresponding subgraph of $G_{n}^{t}$ with vertices labeled by row and column.

\begin{bmatrix}x_{j_{2n}}&x_{2n+1}\\ x_{j_{2n+1}}&x_{2n+2}\\ x_{2n+3}&x_{2n+4}\end{bmatrix}

We know the only difference between $G_{n}^{t}$ and $G_{n-1}^{\widehat{t}}$ is one vertex $r_{3}$ corresponding to row $\left\lfloor{n/2}\right\rfloor+2$ (column $\left\lceil{n/2}\right\rceil+2$ ) and two edges $x_{2n+3}=\{r_{3},c_{1}\}$ and $x_{2n+4}=\{r_{3},c_{2}\}$ , where $c_{1}$ corresponds to the column (row) containing $x_{2n+3}$ and $c_{2}$ corresponds to column $\left\lceil{n/2}\right\rceil+2$ (row $\left\lfloor{n/2}\right\rfloor+2$ ). By Remark 2.2, $\deg r_{3}=2$ , since the only entries in row $\left\lfloor{n/2}\right\rfloor+2$ (column $\left\lceil{n/2}\right\rceil+2$ ) are $x_{2n+3}$ and $x_{2n+4}$ . Then any even cycle containing $r_{3}$ must also contain $x_{2n+3}$ and $x_{2n+4}$ . Similarly, by the same remark, the only other edges with endpoint $c_{2}$ are $x_{2n+1}$ and $x_{2n+2}$ , the entries added to make $L_{n-1}^{\widehat{t}}$ , so we know that any even cycle containing $x_{2n+4}$ and $x_{2n+3}$ must contain either $x_{2n+1}$ or $x_{2n+2}$ . We see that any even cycle containing $r_{3}$ and $x_{2n+1}$ is either a 4-cycle or has $x_{j_{2n}}$ as a chord, and any even cycle containing $r_{3}$ and $x_{2n+2}$ is either a 4-cycle or has $x_{j_{2n+1}}$ as a chord. Thus every graph $G_{n}^{t}$ is chordal bipartite for $n\geq 0$ , with the bipartition above. ∎

Remark 2.14.

We note that the previous proposition ensures that our graphs are distinct from those studied in [8], [9], and [23], which are not chordal bipartite except for the first family in [8], in which every four-cycle shares exactly one edge with every other four-cycle (also distinct from our family except for the trivial case with only one four-cycle, corresponding to $G_{0}^{t}$ ).

2.2. Toric Rings for $\mathcal{F}$

In this section, we develop the toric ring $R(n,t)$ for each of the chordal bipartite graphs $G_{n}^{t}$ in the family $\mathcal{F}$ . We first show that the toric ideal $I_{G_{n}^{t}}$ of the graph $G_{n}^{t}$ is the same as the ideal $I(n,t)$ generated by the distinguished minors of $L_{n}^{t}$ . We then demonstrate that for some $n$ and $t$ , these ideals do not arise from the join-meet ideals of lattices in a natural way, so that results in lattice theory do not apply to the general family $\mathcal{F}$ in an obvious way.

We first define the toric ideal of a graph. For any graph $G$ with vertex set $V$ and edge set $E$ , there is a natural map $\pi:k[E]\to k[V]$ taking an edge to the product of its endpoints. The polynomial subring in $k[V]$ generated by the images of the edges under the map $\pi$ is denoted $k[G]$ and is called the edge ring of $G$ . The kernel of $\pi$ is denoted $I_{G}$ and is called the toric ideal of $G$ ; the ring $k[G]$ is isomorphic to $k[E]/I_{G}$ . In this work, we consider the toric ring $k[E]/I_{G}$ and the toric ideal $I_{G}$ for our particular graphs. It is known in general that $I_{G}$ is generated by binomial expressions coming from even closed walks in $G$ [27, Prop 3.1] and that the toric ideal of a chordal bipartite graph is generated by quadratic binomials coming from the $4$ -cycles of $G$ (see [20, Th 1.2]).

Let $S(n)=k[x_{0},x_{2},x_{3},\ldots,x_{2n+4}]$ be the polynomial ring in the edges of $G_{n}^{t}$ . The edge ring for $G_{n}^{t}\in\mathcal{F}$ is denoted by $k[G_{n}^{t}]$ and is isomorphic to the toric ring

R(n,t):=\frac{S(n)}{I_{G_{n}^{t}}},

where $I_{G_{n}^{t}}$ is the toric ideal of $G_{n}^{t}$ [15, 5.3]. For the general construction of a toric ideal, we refer the reader to [24, Ch 4]. Our goal is to show that the toric ideal $I_{G_{n}^{t}}$ of $G_{n}^{t}$ is equal to

I(n,t)=(\{\text{distinguished minors of $L_{n}^{t}$}\}).

Proposition 2.15.

Let $S(n)=k[x_{0},x_{2},x_{3},\ldots,x_{2n+4}]$ . For $G_{n}^{t}\in\mathcal{F}$ , we have

R(n,t)=\frac{S(n)}{I(n,t)},

where

I(n,t)=(\{\text{distinguished minors of $L_{n}^{t}$}\}).

Proof.

To prove this, we need only show that $I(n,t)$ is the toric ideal $I_{G_{n}^{t}}$ of the graph $G_{n}^{t}$ . By Definition 2.5, it is clear that the distinguished minors of $L_{n}^{t}$ are in $I_{G_{n}^{t}}$ , corresponding to the $4$ -cycles of $G_{n}^{t}$ . Since $G$ is chordal bipartite by Proposition 2.13, these are the only generators of $I_{G_{n}^{t}}$ [15, Cor 5.15]. ∎

Corollary 2.16.

The rings $R(n,t)$ are normal Cohen-Macaulay rings.

Proof.

By Definition 2.5 and Proposition 2.15, the ring $R(n,t)$ is the toric ring of a finite simple connected bipartite graph, and hence by Corollary 5.26 in [15], $R(n,t)$ is Cohen-Macaulay for each $n$ and $t$ . The fact that each $R(n,t)$ is normal follows from [25, Th 5.9, 7.1]. ∎

Because we know the distinguished minors of $L_{n}^{t}$ , we are now able to characterize the generators for the toric ideal $R(n,t)$ of $G_{n}^{t}$ .

Remark 2.17.

By Proposition 2.9, the generators $s_{1},\ldots,s_{2n+1}$ for $I_{G_{n}^{t}}$ may be summarized as follows. For integers $i$ such that $1\leq i\leq n$ , set

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle x_{2}x_{3}-x_{j_{1}}x_{4}$
$\displaystyle s_{2i}$	$\displaystyle=$	$\displaystyle x_{2i+1}x_{2i+3}-x_{j_{2i}}x_{2i+4}$
$\displaystyle s_{2i+1}$	$\displaystyle=$	$\displaystyle x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4},$

where the nonnegative integers $j_{k}$ are as in Remark 2.11, that is, $j_{1}=j_{2}=0$ , $j_{3}=2$ , and for $i\geq 2$ , we have

	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 0\iff j_{2i}=j_{2i-2}\iff j_{2i+1}=2i-1$
	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 1\iff j_{2i}=j_{2i-1}\iff j_{2i+1}=2i.$

We note that the number of generators depends on $n$ and that the $j_{k}$ depend on $t$ , but we may ignore dependence on $t$ when working with general $j_{k}$ . We sometimes call $s_{1},\ldots,s_{2n+1}$ the standard generators of $I_{G_{n}^{t}}$ , and show in Section 2.3 that for certain $n$ and $t$ , they are not equal to the usual generators for the join-meet ideal of any lattice $D$ .

Example 2.18.

We consider the toric ideal of a graph in $\mathcal{F}_{1}$ . For $n=5$ and $t=(1,1,\ldots,1)$ , by Remark 2.11 we have $j_{1}=j_{2}=0$ , $j_{3}=2$ , $j_{2i}=j_{2i-1}$ and $j_{2i+1}=2i$ for $i\geq 2$ , so that

R(5,(1,1,\ldots,1))=\frac{k[x_{0},x_{2},\ldots,x_{14}]}{I_{G_{5}^{(1,1,\ldots,1)}}},

where $I_{G_{5}^{(1,1,\ldots,1)}}$ is generated by the distinguished minors of $L_{5}^{(1,1,\ldots,1)}$ :

$\displaystyle s_{1}$	$\displaystyle=x_{2}x_{3}-x_{0}x_{4}$	$\displaystyle s_{2}$	$\displaystyle=x_{3}x_{5}-x_{0}x_{6}$
$\displaystyle s_{3}$	$\displaystyle=x_{4}x_{5}-x_{2}x_{6}$	$\displaystyle s_{4}$	$\displaystyle=x_{5}x_{7}-x_{2}x_{8}$
$\displaystyle s_{5}$	$\displaystyle=x_{6}x_{7}-x_{4}x_{8}$	$\displaystyle s_{6}$	$\displaystyle=x_{7}x_{9}-x_{4}x_{10}$
$\displaystyle s_{7}$	$\displaystyle=x_{8}x_{9}-x_{6}x_{10}$	$\displaystyle s_{8}$	$\displaystyle=x_{9}x_{11}-x_{6}x_{12}$
$\displaystyle s_{9}$	$\displaystyle=x_{10}x_{11}-x_{8}x_{12}$	$\displaystyle s_{10}$	$\displaystyle=x_{11}x_{13}-x_{8}x_{14}$
$\displaystyle s_{11}$	$\displaystyle=x_{12}x_{13}-x_{10}x_{14}.$

2.3. Distinction From Join-Meet Ideals of Lattices

We saw in Example 2.4 and Proposition 2.15 that if $G_{n}^{t}\in\mathcal{F}_{1}\subset\mathcal{F}$ , then $I_{G_{n}^{t}}$ is a ladder determinantal ideal for $n\geq 2$ . It is known that a ladder determinantal ideal is equal to the join-meet ideal of a (distributive) lattice (indeed, with a natural partial ordering which decreases along rows and columns of $L_{n}^{t}$ we obtain such a lattice). Some algebraic information such as regularity and projective dimension may be easily derived for some join-meet ideals of distributive lattices (see, for example, Chapter 6 of [15]). We spend some time in this section establishing that not all rings $R(n,t)\in\mathcal{F}$ arise from a lattice in a natural way (see Remark 2.20), and so there does not seem to be any obvious way to obtain our results in Section 3 from the literature on join-meet ideals of distributive lattices or on ladder determinantal ideals. The results in Section 3 may be viewed as an extension of what may already be derived for the family $\mathcal{F}_{1}$ from the existing literature.

The following five lemmas serve to provide machinery to show that there is at least one ring in the family $\mathcal{F}$ , namely $R(5,(1,1,1,1,1,0))$ , whose toric ideal does not come from a lattice on the set $\{x_{0},x_{2},\ldots,x_{14}\}$ in any obvious way. That is, we show that the standard generators of $I_{G_{5}^{t}}$ , the $s_{k}$ from Remark 2.17, are not equal to the standard generators (see Definition 2.19) for any lattice $D$ on $\{x_{0},x_{2},\ldots,x_{14}\}$ .

Before we begin, we introduce some definitions and notation that we use extensively throughout.

Definition 2.19.

The join-meet ideal of a lattice is defined from the join (least upper bound) $x\vee y$ and meet (greatest lower bound) $x\wedge y$ of each pair of incomparable elements $x,y\in L$ . In this work, a standard generator of the join-meet ideal of a lattice $D$ is a nonzero element of one of the following four forms:

	$\displaystyle x_{a}x_{b}-(x_{a}\vee x_{b})(x_{a}\wedge x_{b})$	$\displaystyle=$	$\displaystyle x_{a}x_{b}-(x_{a}\wedge x_{b})(x_{a}\vee x_{b})$
	$\displaystyle(x_{a}\vee x_{b})(x_{a}\wedge x_{b})-x_{a}x_{b}$	$\displaystyle=$	$\displaystyle(x_{a}\wedge x_{b})(x_{a}\vee x_{b})-x_{a}x_{b}$

for $x_{a},x_{b}\in L$ . We sometimes refer to such an element as a standard generator of $D$ (the join-meet ideal is defined by analogous generators in the literature, though sometimes $a,b\in L$ instead of $x_{a}$ and $x_{b}$ ). We note that for a standard generator, the pair $\{x_{a},x_{b}\}$ is an incomparable pair, and the pair $\{(x_{a}\vee x_{b}),(x_{a}\wedge x_{b})\}$ is a comparable pair.

Though we are in a commutative ring, we provide all possible orderings for factors within the terms of a standard generator to emphasize that either factor of the monomial

(x_{a}\vee x_{b})(x_{a}\wedge x_{b})=(x_{a}\wedge x_{b})(x_{a}\vee x_{b})

may be the join or the meet of $x_{a}$ and $x_{b}$ .

Remark 2.20.

We give an explanation for why it makes sense to focus only on the standard generators of a join-meet ideal. We recall that the standard generators $s_{k}$ for $I_{G_{n}^{t}}$ from Remark 2.17 come from distinct $2\times 2$ arrays within the ladder-like structure $L_{n}^{t}$ and recognize that either monomial of $s_{k}$ determines its $2\times 2$ array. Then an element of the form $ab-cd$ in $I_{G_{5}^{t}}$ with $a,b,c,d\in\{x_{0},x_{2},x_{3},\ldots,x_{14}\}$ must be equal to $\pm s_{i}$ for some $i$ , since a nontrivial sum of $s_{k}$ with coefficients in $\{-1,1\}$ either has more than two terms or is equal to $s_{i}$ for some $i$ , and other coefficients would be extraneous. Then any generating set for $I_{G_{5}^{t}}$ where each element has the form $ab-cd$ in $I_{G_{5}^{t}}$ with $a,b,c,d\in\{x_{0},x_{2},x_{3},\ldots,x_{14}\}$ must consist of all the $s_{k}$ (up to sign). We conclude that it is natural to check whether the $s_{k}$ are standard generators of a lattice $D$ , instead of non-standard generators.

Definition 2.21.

Given a standard generator $s=uz-wv$ of a lattice $D$ , where $u,v,w,z\in D$ , let $F_{s}\in\mathbb{F}_{2}$ be defined as follows:

•

If $F_{s}=0$ , the elements in the first (positive) monomial of $s$ are not comparable in $D$ (so the elements in the second (negative) monomial of $s$ are comparable in $D$ ).
•

If $F_{s}=1$ , the elements in the negative monomial of $s$ are not comparable in $D$ (so the elements in the positive monomial of $s$ are comparable in $D$ ).

For a given list $s_{1},s_{2},\ldots,s_{m}$ of standard generators of a lattice $D$ , we use

F=(F_{1},\ldots,F_{m})\in\mathbb{F}_{2}^{m},

where $F_{j}=F_{s_{j}}$ , to encode the comparability of the variables in these generators.

We note that exactly one of $F_{j}=0$ or $F_{j}=1$ happens for each $j$ ; we are merely encoding which monomial in $s_{j}$ corresponds to $x_{a}x_{b}$ , and which to $(x_{a}\vee x_{b})(x_{a}\wedge x_{b})=(x_{a}\wedge x_{b})(x_{a}\vee x_{b})$ .

Notation 2.22.

We use the notation $u>\{w,v\}$ if $u>w$ and $u>v$ in a lattice $D$ , and $\{w,v\}>z$ if $w>z$ and $v>z$ in $D$ .

In the first lemma, we begin by showing what restrictions we must have on a lattice whose join-meet ideal contains the 2-minors of the following array as standard generators:

$\begin{matrix}a&b&e\\ c&d&f\end{matrix}$

Lemma 2.23.

Suppose

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle bc-ad$
$\displaystyle s_{2}$	$\displaystyle=$	$\displaystyle ce-af$
$\displaystyle s_{3}$	$\displaystyle=$	$\displaystyle de-bf$

are standard generators of a lattice $D$ . Let $F\in\mathbb{F}_{2}^{3}$ be defined for these three elements as in Definition 2.21. Then up to relabeling of variables,

F\in\{\{0,0,0\},\{0,0,1\},\{0,1,1\}\}.

Proof.

We first note that some of the cases we consider are equivalent. If we relabel variables according to the permutation $(ac)(bd)(ef)$ , we see that

F=\{i,j,k\}\equiv\{1-i,1-j,1-k\}.

This limits the cases we need to consider to

F\in\{\{0,0,0\},\{0,0,1\},\{0,1,0\},\{0,1,1\}\}.

That is, we only need to show that the case $F=\{0,1,0\}$ is impossible.

Let $F_{1}=0$ . Then without loss of generality, up to reversing the order in the lattice (which does not affect the join-meet ideal), we have $a>\{b,c\}>d$ . If $F_{2}=1$ , we have $e>\{a,f\}>c$ , so $e>\{b,f\}>d$ and hence $F_{3}=1$ . We conclude that the case $F=\{0,1,0\}$ is impossible. ∎

In the second lemma, we show what restrictions we must have on a lattice whose join-meet ideal contains the 2-minors of the ladder

$\begin{matrix}a&b&e\\ c&d&f\\ &g&h\\ \end{matrix}$

as standard generators, and which meets certain comparability conditions.

Lemma 2.24.

Suppose

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle bc-ad$
$\displaystyle s_{2}$	$\displaystyle=$	$\displaystyle ce-af$
$\displaystyle s_{3}$	$\displaystyle=$	$\displaystyle de-bf$
$\displaystyle s_{4}$	$\displaystyle=$	$\displaystyle eg-bh$
$\displaystyle s_{5}$	$\displaystyle=$	$\displaystyle fg-dh$

are standard generators of a lattice $D$ , and that $\{a,g\}$ , $\{a,h\}$ , $\{c,g\}$ , and $\{c,h\}$ are comparable pairs in $D$ . Let $F\in\mathbb{F}_{2}^{5}$ be defined for these five elements as in 2.21. Then up to relabeling of variables, $F=\{0,0,0,0,0\}$ .

Proof.

We first note that with natural relabeling, both $\{s_{1},s_{2},s_{3}\}$ and $\{s_{3},s_{4},s_{5}\}$ satisfy the hypotheses of Lemma 2.23, so if we let $F$ be defined as in Definition 2.21, this limits the cases we need to consider to 5-tuples whose first three elements and whose last three elements satisfy the conclusion of Lemma 2.23. We note that some of the cases we consider are equivalent. If we relabel variables according to the permutation $(ac)(bd)(ef)$ , we see that $F=\{i,j,k,l,m\}\equiv\{1-i,1-j,1-k,m,l\}$ , and if we relabel the variables according to the permutation $(be)(df)(gh)$ , we have $F=\{i,j,k,l,m\}\equiv\{j,i,1-k,1-l,1-m\}$ . The permutation $(ah)(cg)(bf)$ yields $F=\{i,j,k,l,m\}\equiv\{m,l,k,j,i\}$ . Then by Lemma 2.23 we have the eighteen cases

\{0,0,0,0,0\}\equiv\{1,1,1,0,0\}\equiv\{1,1,0,1,1\}\equiv\{0,0,1,1,1\}

$\displaystyle\{0,0,0,0,1\}\equiv\{1,1,1,1,0\}\equiv\{1,1,0,0,1\}\equiv\{0,0,1,1,0\}$	$\displaystyle\equiv$	$\displaystyle\{0,1,1,0,0\}$
	$\displaystyle\equiv$	$\displaystyle\{1,0,0,0,0\}$
	$\displaystyle\equiv$	$\displaystyle\{0,1,1,1,1\}$
	$\displaystyle\equiv$	$\displaystyle\{1,0,0,1,1\}$

\{0,0,0,1,1\}\equiv\{1,1,1,1,1\}\equiv\{1,1,0,0,0\}\equiv\{0,0,1,0,0\}

\{0,1,1,1,0\}\equiv\{1,0,0,0,1\}

Case 1: $F=\{0,0,0,0,1\}$ . Since $F_{1}=0$ , without loss of generality (reversing the order on the entire lattice if needed) we have $a>\{b,c\}>d$ . Then $F_{2}=F_{3}=F_{4}=0$ and $F_{5}=1$ , with the ordering chosen, yield

	$\displaystyle a>\{c,e\}>f$
	$\displaystyle b>\{d,e\}>f$
	$\displaystyle b>\{e,g\}>h$
	$\displaystyle g>\{d,h\}>f.$

If $c>g$ , then $a>\{b,c\}>g>d$ , but then $bc-ad$ is not a standard generator of $D$ , and this is a contradiction. If $c<g$ , then $c<g<b$ so that both $\{b,c\}$ and $\{a,d\}$ from $s_{1}$ are comparable pairs, but this is a contradiction. We conclude that the case $\{0,0,0,0,1\}$ is impossible.

Because of the comparability of the pair $\{c,g\}$ , the case $F=\{0,1,1,1,0\}$ forces comparability of $\{f,g\}$ or $\{b,c\}$ and hence yields a contradiction, as the reader may verify. In the case $F=\{0,0,0,1,1\}$ , the comparability of $\{c,g\}$ forces either the comparability of $\{b,c\}$ (a contradiction), or $d<\{b,c\}<a<g$ , up to reversing the order in the lattice, since $s_{1}$ is a standard generator. Since $\{a,h\}$ is a comparable pair, it immediately follows that either $\{b,h\}$ is comparable (a contradiction) or $e<\{b,h\}<a<g$ , which is a contradiction since $s_{4}$ is a standard generator, as the reader may verify. These cases are compatible with the given relabelings and thus conclude our proof. ∎

In the third lemma, we show what restrictions we must have on a lattice whose join-meet ideal contains the 2-minors of the ladder

$\begin{matrix}a&b&e&\\ c&d&f&i\\ &g&h&j\end{matrix}$

as standard generators and which meets certain comparability conditions.

Lemma 2.25.

Suppose

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle bc-ad$
$\displaystyle s_{2}$	$\displaystyle=$	$\displaystyle ce-af$
$\displaystyle s_{3}$	$\displaystyle=$	$\displaystyle de-bf$
$\displaystyle s_{4}$	$\displaystyle=$	$\displaystyle eg-bh$
$\displaystyle s_{5}$	$\displaystyle=$	$\displaystyle fg-dh$
$\displaystyle s_{6}$	$\displaystyle=$	$\displaystyle gi-dj$
$\displaystyle s_{7}$	$\displaystyle=$	$\displaystyle hi-fj$

are standard generators of a lattice $D$ , and that $\{a,g\}$ , $\{a,h\}$ , $\{c,g\}$ , $\{c,h\}$ , $\{b,i\}$ , $\{b,j\}$ , $\{e,i\}$ , and $\{e,j\}$ are comparable pairs in $D$ . Let $F\in\mathbb{F}_{2}^{7}$ be defined for these seven elements as in Definition 2.21. Then up to relabeling of variables, $F=\{0,0,0,0,0,0,0\}$ .

Proof.

We first note that with natural relabeling, both $\{s_{1},s_{2},s_{3},s_{4},s_{5}\}$ and $\{s_{3},s_{4},s_{5},s_{6},s_{7}\}$ satisfy the hypotheses of Lemma 2.24, so if we let $F$ be defined as in Definition 2.21, this limits the cases we need to consider to 7-tuples whose first five elements and whose last five elements satisfy the conclusion of Lemma 2.24. The only possible cases are $\{0,0,0,0,0,0,0\}$ and $\{0,0,1,1,1,0,0\}$ . If we relabel variables according to the permutation $(be)(df)(gh)$ , we see that $F=\{i,j,k,l,m,n,o\}\equiv\{j,i,1-k,1-l,1-m,o,n\}$ , so that these two cases are equivalent. Then up to relabeling of variables, $F=\{0,0,0,0,0,0,0\}$ . ∎

In the fourth lemma, we show what restrictions we must have on a lattice whose join-meet ideal contains the 2-minors of the ladder

$\begin{matrix}a&b&e&\\ c&d&f&i\\ &g&h&j\\ &&k&l\end{matrix}$

as standard generators, and which meets certain comparability conditions.

Lemma 2.26.

Suppose

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle bc-ad$
$\displaystyle s_{2}$	$\displaystyle=$	$\displaystyle ce-af$
$\displaystyle s_{3}$	$\displaystyle=$	$\displaystyle de-bf$
$\displaystyle s_{4}$	$\displaystyle=$	$\displaystyle eg-bh$
$\displaystyle s_{5}$	$\displaystyle=$	$\displaystyle fg-dh$
$\displaystyle s_{6}$	$\displaystyle=$	$\displaystyle gi-dj$
$\displaystyle s_{7}$	$\displaystyle=$	$\displaystyle hi-fj$
$\displaystyle s_{8}$	$\displaystyle=$	$\displaystyle ik-fl$
$\displaystyle s_{9}$	$\displaystyle=$	$\displaystyle jk-hl$

are standard generators of a lattice $D$ , and that $\{a,g\}$ , $\{a,h\}$ , $\{c,g\}$ , $\{c,h\}$ , $\{b,i\}$ , $\{b,j\}$ , $\{e,i\}$ , $\{e,j\}$ , $\{d,k\}$ , $\{d,l\}$ , $\{g,k\}$ , and $\{g,l\}$ are comparable pairs in $D$ . Let $F\in\mathbb{F}_{2}^{9}$ be defined for these nine elements as in Definition 2.21. Then $F=\{0,0,0,0,0,0,0,0,0\}$ .

Proof.

We first note that with natural relabeling, both $\{s_{1},s_{2},s_{3},s_{4},s_{5},s_{6},s_{7}\}$ and
$\{s_{3},s_{4},s_{5},s_{6},s_{7},s_{8},s_{9}\}$ satisfy the hypotheses of Lemma 2.25, so if we let $F$ be defined as in Definition 2.21, this limits the cases we need to consider to 9-tuples whose first seven entries and whose last seven entries satisfy the conclusion of Lemma 2.25. We see by Lemma 2.25 that $F=\{0,0,0,0,0,0,0,0,0\}$ . ∎

We now have the machinery necessary to show that for $t=(1,1,1,1,1,0)$ , $I_{G_{5}^{t}}$ does not come from a lattice. In our proof, we use the previous four lemmas and the fact that $I_{G_{5}^{t}}$ is generated by the distinguished minors of $L_{5}^{(1,1,1,1,1,0)}$ :

$\begin{matrix}x_{0}&x_{2}&x_{5}&&\\ x_{3}&x_{4}&x_{6}&x_{9}&x_{13}\\ &x_{7}&x_{8}&x_{10}&\\ &&x_{11}&x_{12}&x_{14}\end{matrix}$

Proposition 2.27.

Let $n=5$ and $t=(1,1,1,1,1,0)$ . Then the set of standard generators for $I_{G_{5}^{t}}$ is not equal to the complete set of standard generators (up to sign) of any (classical) lattice.

Proof.

By Remark 2.17 and choice of $n=5$ and $t=(1,1,1,1,1,0)$ , the generators of $I_{G_{5}^{t}}$ are

$\displaystyle s_{1}$	$\displaystyle=x_{2}x_{3}-x_{0}x_{4}$	$\displaystyle s_{2}$	$\displaystyle=x_{3}x_{5}-x_{0}x_{6}$
$\displaystyle s_{3}$	$\displaystyle=x_{4}x_{5}-x_{2}x_{6}$	$\displaystyle s_{4}$	$\displaystyle=x_{5}x_{7}-x_{2}x_{8}$
$\displaystyle s_{5}$	$\displaystyle=x_{6}x_{7}-x_{4}x_{8}$	$\displaystyle s_{6}$	$\displaystyle=x_{7}x_{9}-x_{4}x_{10}$
$\displaystyle s_{7}$	$\displaystyle=x_{8}x_{9}-x_{6}x_{10}$	$\displaystyle s_{8}$	$\displaystyle=x_{9}x_{11}-x_{6}x_{12}$
$\displaystyle s_{9}$	$\displaystyle=x_{10}x_{11}-x_{8}x_{12}$	$\displaystyle s_{10}$	$\displaystyle=x_{11}x_{13}-x_{6}x_{14}$
$\displaystyle s_{11}$	$\displaystyle=x_{12}x_{13}-x_{9}x_{14}$

Suppose a lattice $D$ exists whose complete set of standard generators (up to sign) equals { $s_{1},\ldots,s_{11}$ }. We note that if the monomial $x_{i}x_{j}$ does not appear in any of the $s_{k}$ , then $\{x_{i},x_{j}\}$ is a comparable pair, since otherwise $\pm(x_{i}x_{j}-(x_{i}\vee x_{j})(x_{i}\wedge x_{j}))$ would be in the set of standard generators of $D$ . Thus the pairs $\{x_{0},x_{7}\}$ , $\{x_{0},x_{8}\}$ , $\{x_{3},x_{7}\}$ , $\{x_{3},x_{8}\}$ , $\{x_{2},x_{9}\}$ , $\{x_{2},x_{10}\}$ , $\{x_{5},x_{9}\}$ , $\{x_{5},x_{10}\}$ , $\{x_{4},x_{11}\}$ , $\{x_{4},x_{12}\}$ , $\{x_{7},x_{11}\}$ , $\{x_{7},x_{12}\}$ , $\{x_{10},x_{13}\}$ , and $\{x_{10},x_{14}\}$ are comparable pairs in $D$ . Let $F\in\mathbb{F}_{2}^{11}$ be defined as in Definition 2.21. Then with natural relabeling of the first nine relations, this lattice satisfies the hypotheses of Lemma 2.26, so the only cases we need to consider are $F=\{0,0,0,0,0,0,0,0,0,a,b\}$ .

Since $F_{1}=0$ , without loss of generality, we have $x_{0}>\{x_{2},x_{3}\}>x_{4}$ . Then with the ordering chosen, the fact that $F_{3}=F_{5}=F_{7}=F_{9}=0$ yields

	$\displaystyle x_{2}>\{x_{4},x_{5}\}>x_{6}$
	$\displaystyle x_{4}>\{x_{6},x_{7}\}>x_{8}$
	$\displaystyle x_{6}>\{x_{8},x_{9}\}>x_{10}$
	$\displaystyle x_{8}>\{x_{10},x_{11}\}>x_{12}.$

The reader may verify that $b=0$ and $b=1$ both yield contradictions based on inspecting the standard generator $s_{11}$ in light of the comparability of the pairs $\{x_{10},x_{13}\}$ and $\{x_{10},x_{14}\}$ , respectively, using the same technique employed in Case 1 of the proof of Lemma 2.24.

We conclude that there is no lattice whose complete set of standard generators (up to sign) equals the set of standard generators of $I_{G_{5}^{(1,1,1,1,1,0)}}$ . ∎

3. Properties of the Family of Toric Rings

In Section 2, we defined a family of toric rings, the rings $R(n,t)$ coming from the family $\mathcal{F}$ , and we demonstrated some context for these rings in the area of graph theory. Now we investigate some of the algebraic properties of each $R(n,t)$ . We develop proofs to establish dimension, regularity, and multiplicity.

3.1. Dimension and System of Parameters

We use the the degree reverse lexicographic monomial order with $x_{0}>x_{2}>x_{3}>\cdots$ throughout this section, and denote it by $>$ . We show that the standard generators $s_{k}$ given in Remark 2.17 are a Gröbner basis for $I_{G_{n}^{t}}$ with respect to $>$ .

Lemma 3.1.

If $s_{1},\ldots,s_{2n+1}$ are as in Remark 2.17, then $B=\{s_{1},\ldots,s_{2n+1}\}$ is a Gröbner basis for $I_{G_{n}^{t}}$ with respect to $>$ .

Proof.

This is a straightforward computation using Buchberger’s Criterion and properties of the $j_{k}$ from Remark 2.11. By Remark 2.17, for $1\leq i\leq n$ the ideal $I_{G_{n}^{t}}$ is generated by

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle x_{2}x_{3}-x_{j_{1}}x_{4}$
$\displaystyle s_{2i}$	$\displaystyle=$	$\displaystyle x_{2i+1}x_{2i+3}-x_{j_{2i}}x_{2i+4}$
$\displaystyle s_{2i+1}$	$\displaystyle=$	$\displaystyle x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4},$

where $j_{1}=j_{2}=0$ , $j_{3}=2$ , and for $i\geq 2$ , we have

	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 0\iff j_{2i}=j_{2i-2}\iff j_{2i+1}=2i-1$
	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 1\iff j_{2i}=j_{2i-1}\iff j_{2i+1}=2i.$

If we adopt $S$ -polynomial notation $S_{i,j}$ for the $S$ -polynomial of $s_{i}$ and $s_{j}$ , then the cases to consider are

S_{2i-1,2i}\text{ and }S_{2i,2i+1}\text{ for }1\leq i\leq n

S_{2i,2i+2}\text{ for }1\leq i\leq n-1.

To give a flavor of the computation involved, we show the case $S_{2i-1,2i}$ for $1\leq i\leq n$ , and leave the remaining cases to the reader. We show in each subcase that $S_{2i-1,2i}$ is equal to a sum of basis elements with coefficients in $S(n)$ , so that the reduced form of $S_{2i-1,2i}$ is zero in each subcase. We have

	$\displaystyle S_{2i-1,2i}$	$\displaystyle=$	$\displaystyle x_{2i+3}(x_{2i}x_{2i+1}-x_{j_{2i-1}}x_{2i+2})-x_{2i}(x_{2i+1}x_{2i+3}-x_{j_{2i}}x_{2i+4})$
		$\displaystyle=$	$\displaystyle-x_{j_{2i-1}}x_{2i+2}x_{2i+3}+x_{j_{2i}}x_{2i}x_{2i+4}$

Case 1: If $i\geq 2$ and $t_{i+1}=0$ , then $j_{2i}=j_{2i-2}$ and $j_{2i+1}=2i-1$ , so we have

\displaystyle S_{2i-1,2i}

\displaystyle=

\displaystyle-x_{j_{2i-1}}x_{2i+2}x_{2i+3}+x_{j_{2i-2}}x_{2i}x_{2i+4}

Case 1.1: If in addition $i\geq 3$ and $t_{i}=0$ , then $j_{2i-2}=j_{2i-4}$ and $j_{2i-1}=2i-3$ , so we have

$\displaystyle S_{2i-1,2i}$ $\displaystyle=$ $\displaystyle-x_{2i-3}x_{2i+2}x_{2i+3}+x_{j_{2i-4}}x_{2i}x_{2i+4}$

$\displaystyle=$ $\displaystyle-x_{2i-3}(x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4})+x_{2i+4}(x_{2i-3}x_{2i-1}-x_{j_{2i-4}}x_{2i})$

$\displaystyle=$ $\displaystyle-x_{2i-3}s_{2i+1}+x_{2i+4}s_{2i-4}.$

Case 1.2: If in addition $i=2$ or $i\geq 3$ and $t_{i}=1$ , then $j_{2i-2}=j_{2i-3}$ and $j_{2i-1}=2i-2$ , so we have

$\displaystyle S_{2i-1,2i}$ $\displaystyle=$ $\displaystyle-x_{2i-2}x_{2i+2}x_{2i+3}+x_{j_{2i-3}}x_{2i}x_{2i+4}$

$\displaystyle=$ $\displaystyle-x_{2i-2}(x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4})+x_{2i+4}(x_{2i-2}x_{2i-1}-x_{j_{2i-3}}x_{2i})$

$\displaystyle=$ $\displaystyle-x_{2i-2}s_{2i+1}+x_{2i+4}s_{2i-3}.$

Case 2: If $i=1$ or if $i\geq 2$ and $t_{i+1}=1$ , then $j_{2i}=j_{2i-1}$ and $j_{2i+1}=2i$ , so we have

	$\displaystyle S_{2i-1,2i}$	$\displaystyle=$	$\displaystyle-x_{j_{2i}}x_{2i+2}x_{2i+3}+x_{j_{2i}}x_{2i}x_{2i+4}$
		$\displaystyle=$	$\displaystyle-x_{j_{2i}}s_{2i+1}.$

This concludes the case $S_{2i-1,2i}$ for $1\leq i\leq n-1$ . The remaining cases are similar.

∎

Corollary 3.2.

The ring $R(n,t)$ is Koszul for all $n$ and all $t$ .

Proof.

Since $I_{G_{n}^{t}}$ has a quadratic Gröbner basis, the ring $R(n,t)$ is Koszul for all $n$ and all $t$ due to [15, Th 2.28]. ∎

Corollary 3.3.

The initial ideal for $I_{G_{n}^{t}}$ with respect to the degree reverse lexicographic monomial order $>$ is

\text{in}_{>}I_{G_{n}^{t}}=(x_{2}x_{3},\{x_{2i+1}x_{2i+3},x_{2i+2}x_{2i+3}\mid 1\leq i\leq n\}).

We note that $\text{in}_{>}I_{G_{n}^{t}}$ does not depend on $t$ , which will be useful for the following sections.

We use the initial ideal $\text{in}_{>}I_{G_{n}^{t}}$ from Corollary 3.3 and direct computation to show the Krull dimension of $R(n,t)$ . As a corollary, we obtain the projective dimension of $R(n,t)$ . We note that the Krull dimension, like the initial ideal, does not depend on $t$ . We refer the reader to Remark 2.17 for a reminder of how to think of the toric ring

R(n,t)=\frac{S(n)}{I_{G_{n}^{t}}}=\frac{k[x_{0},x_{2},x_{3},\ldots,x_{2n+4}]}{I_{G_{n}^{t}}}

in the context of this work.

Theorem 3.4.

The Krull dimension of $R(n,t)$ is

\dim R(n,t)=n+3.

Proof.

Let $>$ be the degree reverse lexicographic monomial order with

x_{0}>x_{2}>x_{3}>\cdots>x_{2n+4}.

By Corollary 3.3, the initial ideal of $I_{G_{n}^{t}}$ with respect to $>$ is

\text{in}_{>}I_{G_{n}^{t}}=(x_{2}x_{3},\{x_{2i+1}x_{2i+3},x_{2i+2}x_{2i+3}\mid 1\leq i\leq n\}).

Since $S(n)/(\text{in}_{>}I_{G_{n}^{t}})$ and $R(n,t)=S(n)/I_{G_{n}^{t}}$ are known to have the same Krull dimension (see for example [6, Props 9.3.4 and 9.3.12]), it suffices to prove that

\dim S(n)/(\text{in}_{>}I_{G_{n}^{t}})=n+3.

To see that the dimension is at least $n+3$ , we construct a chain of prime ideals in $S(n)$ containing $\text{in}_{>}I_{G_{n}^{t}}$ . Since every monomial generator of $\text{in}_{>}I_{G_{n}^{t}}$ contains a variable of odd index, we begin with $P_{n}=(\{x_{k}\mid\text{$k$ odd, $2<k<2n+4$}\})$ , a prime ideal containing $\text{in}_{>}I_{G_{n}^{t}}$ . Then we have the chain of prime ideals $P_{n}\subsetneq P_{n}+(x_{0})\subsetneq P_{n}+(x_{0},x_{2})\subsetneq P_{n}+(x_{0},x_{2},x_{4})\subsetneq\cdots\subsetneq P_{n}+(\{x_{2i}\mid 0\leq i\leq n+2\})$ , so that

\dim S(n)/(\text{in}_{>}I_{G_{n}^{t}})\geq n+3.

To see that the dimension is at most $n+3$ , we find a sequence of $n+3$ elements in $S(n)/(\text{in}_{>}I_{G_{n}^{t}})$ such that the quotient by the ideal they generate has dimension zero. Let

X_{n}=x_{0},x_{2}-x_{3},x_{4}-x_{5},\ldots,x_{2n}-x_{2n+1},x_{2n+2}-x_{2n+3},x_{2n+4}

in $S(n)$ , and take the quotient of $S(n)/(\text{in}_{>}I_{G_{n}^{t}})$ by the image of $X_{n}$ to obtain the following. In the last step, we rewrite the quotient of $S(n)$ and $(\text{in}_{>}I_{G_{n}^{t}})+(X_{n})$ by $(X_{n})$ by setting $x_{0}$ and $x_{2n+4}$ equal to zero and replacing $x_{2i}$ with $x_{2i+1}$ for $1\leq i\leq n+1$ :

$\displaystyle\frac{S(n)/(\text{in}_{>}I_{G_{n}^{t}})}{((\text{in}_{>}I_{G_{n}^{t}})+(X_{n}))/(\text{in}_{>}I_{G_{n}^{t}})}$	$\displaystyle\cong$	$\displaystyle\frac{S(n)}{((\text{in}_{>}I_{G_{n}^{t}})+(X_{n}))}$
	$\displaystyle\cong$	$\displaystyle\frac{S(n)/(X_{n})}{((\text{in}_{>}I_{G_{n}^{t}})+(X_{n}))/(X_{n})}$
	$\displaystyle\cong$	$\displaystyle\frac{k[x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}]}{(x_{3}^{2},\{x_{2i+1}x_{2i+3},x_{2i+3}^{2}\mid 1\leq i\leq n\})}.$

Since

\sqrt{(x_{3}^{2},\{x_{2i+1}x_{2i+3},x_{2i+3}^{2}\mid 1\leq i\leq n\})}=(x_{3},x_{5},\ldots,x_{2n+3}),

the above ring has dimension zero. Thus,

\dim S(n)/(\text{in}_{>}I_{G_{n}^{t}})\leq n+3.

We conclude that $\dim R(n,t)=\dim S(n)/(\text{in}_{>}I_{G_{n}^{t}})=n+3$ . ∎

Corollary 3.5.

The projective dimension of $R(n,t)$ over $S(n)$ is

\textnormal{pd}_{S(n)}R(n,t)=n+1.

Proof.

We know the Krull dimension of the polynomial ring $S(n)$ is $2n+4$ . The result follows from the fact that $R(n,t)$ is Cohen-Macaulay (Corollary 2.16) and from the graded version of the Auslander-Buchsbaum formula. ∎

Remark 3.6.

The proof of the previous theorem shows that the image of

X_{n}=x_{0},x_{2}-x_{3},x_{4}-x_{5},\ldots,x_{2n}-x_{2n+1},x_{2n+2}-x_{2n+3},x_{2n+4}

in $S(n)/(\text{in}_{>}I_{G_{n}^{t}})$ is a system of parameters for $S(n)/(\text{in}_{>}I_{G_{n}^{t}})$ . We prove in the next theorem that the image of $X_{n}$ in $R(n,t)$ (which we call $\overline{X_{n}}$ ) is also a system of parameters for $R(n,t)$ . Before doing so, we introduce some notation and a definition which allows us to better grapple with the quotient ring $R(n,t)/(\overline{X_{n}})$ .

Definition 3.7.

Consider the isomorphism

\frac{R(n,t)}{(\overline{X_{n}})}=\frac{S(n)/(I_{G_{n}^{t}})}{((I_{G_{n}^{t}})+(X_{n}))/(I_{G_{n}^{t}})}\cong\frac{S(n)/(X_{n})}{((I_{G_{n}^{t}})+(X_{n}))/(X_{n})}

We view taking the quotient by $X_{n}$ as setting $x_{0}$ and $x_{2n+4}$ equal to zero and replacing $x_{2i}$ with $x_{2i+1}$ for $1\leq i\leq n+1$ to obtain

\widehat{S(n)}:=k[x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}]\cong S(n)/(X_{n}).

By the same process (detailed below), we obtain the ideal $\widehat{I_{G_{n}^{t}}}\cong(I_{G_{n}^{t}}+(X_{n}))/(X_{n})$ . We further define the quotient

\widehat{R(n,t)}:=\widehat{S(n)}/\widehat{I_{G_{n}^{t}}}\cong R(n,t)/(\overline{X_{n}}).

We find this notation natural since it is often used for the removal of variables, and the quotient by $X_{n}$ may be viewed as identifying and removing variables. Since this work has no completions in it, there should be no conflict of notation.

Definition 3.8.

To define $\widehat{I_{G_{n}^{t}}}$ in particular, we recall the standard generators of $I_{G_{n}^{t}}$ and introduce further notation to describe the generators of $\widehat{I_{G_{n}^{t}}}\cong(I_{G_{n}^{t}}+(X_{n}))/(X_{n})$ . By Remark 2.17, the standard generators of $I_{G_{n}^{t}}$ are

$\displaystyle s_{1}$	$\displaystyle=$	$\displaystyle x_{2}x_{3}-x_{j_{1}}x_{4}$
$\displaystyle s_{2i}$	$\displaystyle=$	$\displaystyle x_{2i+1}x_{2i+3}-x_{j_{2i}}x_{2i+4}$
$\displaystyle s_{2i+1}$	$\displaystyle=$	$\displaystyle x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4},$

for $1\leq i\leq n$ , where the nonnegative integers $j_{k}$ are as in Remark 2.11.

Let $\widehat{\iota}$ be the largest index such that $j_{2\widehat{\iota}}=0$ . By Remark 2.11, we see that the $j_{2i}$ are defined recursively and form a non-decreasing sequence. Then

j_{1}=j_{2}=j_{4}=j_{6}=\cdots=j_{2\widehat{\iota}}=0,

and since we view taking the quotient by $X_{n}$ as setting $x_{0}$ and $x_{2n+4}$ equal to zero and replacing $x_{2i}$ with $x_{2i+1}$ for $1\leq i\leq n+1$ , we define $\widehat{I_{G_{n}^{t}}}$ by replacing $x_{j_{k}}$ with $x_{J_{k}}$ (defined below) for $1\leq k<2n$ to obtain

$\displaystyle\widehat{s_{1}}$	$\displaystyle=$	$\displaystyle x_{3}^{2}-x_{J_{1}}x_{5}$
$\displaystyle\widehat{s_{2i}}$	$\displaystyle=$	$\displaystyle x_{2i+1}x_{2i+3}-x_{J_{2i}}x_{2i+5}$
$\displaystyle\widehat{s_{2i+1}}$	$\displaystyle=$	$\displaystyle x_{2i+3}^{2}-x_{J_{2i+1}}x_{2i+5}$
$\displaystyle\widehat{s_{2n}}$	$\displaystyle=$	$\displaystyle x_{2n+1}x_{2n+3}$
$\displaystyle\widehat{s_{2n+1}}$	$\displaystyle=$	$\displaystyle x_{2n+3}^{2}$

for $1\leq i<n$ , where

x_{J_{k}}=\begin{cases}0&\text{ if }k\text{ is even and }k\leq 2\widehat{\iota},\text{ or if }k=1\\ x_{j_{k}+1}&\text{ if }2\widehat{\iota}<k<2n\text{ and $j_{k}$ is even}\\ x_{j_{k}}&\text{ if }j_{k}\text{ is odd}\end{cases}

We note that $J_{k}\leq k$ for each $1\leq k<2n$ , since $j_{k}\leq k-1$ by Remark 2.11. By properties of the original $j_{k}$ from Remark 2.11, we know that $x_{J_{1}}=x_{J_{2}}=0$ , $J_{3}=3$ , and for $2\leq i<n$ ,

	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 0\iff x_{J_{2i}}=x_{J_{2i-2}}\iff J_{2i+1}=2i-1$
	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 1\iff x_{J_{2i}}=x_{J_{2i-1}}\iff J_{2i+1}=2i+1.$

Example 3.9.

We construct the ring $R(2,(0,0,0))$ . For the graph $G_{2}^{(0,0,0)}\in\mathcal{F}$ , we have the toric ring

R(2,(0,0,0))=\frac{k[x_{0},x_{2},x_{3},\ldots,x_{8}]}{(x_{2}x_{3}-x_{0}x_{4},x_{3}x_{5}-x_{0}x_{6},x_{4}x_{5}-x_{2}x_{6},x_{5}x_{7}-x_{0}x_{8},x_{6}x_{7}-x_{3}x_{8})}

coming from the ladder-like structure

L_{2}^{(0,0,0)}=\begin{matrix}x_{0}&x_{2}&x_{5}\\ x_{3}&x_{4}&x_{6}\\ x_{7}&&x_{8}\end{matrix}

from Example 2.3. We know

X_{2}=x_{0},x_{2}-x_{3},x_{4}-x_{5},\ldots,x_{4}-x_{5},x_{6}-x_{7},x_{8},

so that $R(2,(0,0,0))/(\overline{X_{2}})$ is isomorphic to

\frac{k[x_{0},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}]}{(x_{2}x_{3}-x_{0}x_{4},x_{3}x_{5}-x_{0}x_{6},x_{4}x_{5}-x_{2}x_{6},x_{5}x_{7}-x_{0}x_{8},x_{6}x_{7}-x_{3}x_{8},x_{0},x_{2}-x_{3},\ldots,x_{8})}

\cong\frac{k[x_{3},x_{5},x_{7}]}{(x_{3}^{2},x_{3}x_{5},x_{5}^{2}-x_{3}x_{7},x_{5}x_{7},x_{7}^{2})}=\widehat{R(2,(0,0,0))}.

Now we show that $X_{n}$ is also a system of parameters for $R(n,t)$ , and not just for the quotient by the initial ideal.

Proposition 3.10.

Let $R(n,t)=S(n)/I_{G_{n}^{t}}$ and let

X_{n}=x_{0},x_{2}-x_{3},x_{4}-x_{5},\ldots,x_{2n}-x_{2n+1},x_{2n+2}-x_{2n+3},x_{2n+4}

so that the image of $X_{n}$ in $S(n)/(\text{in}_{>}I_{G_{n}^{t}})$ is the system of parameters from Remark 3.6. Then the image of $X_{n}$ in $R(n,t)$ is a system of parameters for $R(n,t)$ .

Proof.

Let $X_{n}$ be defined as above. Then by Theorem 3.4 and Definition 3.7 we need only show that $\dim\widehat{R(n,t)}=0$ . We have for $n=0$ that

\widehat{R(0,t)}=\frac{k[x_{3}]}{(x_{3}^{2})},

for $n=1$

\widehat{R(1,t)}=\frac{k[x_{3},x_{5}]}{(x_{3}^{2},x_{3}x_{5},x_{5}^{2})},

and for $n>1$

\widehat{R(n,t)}=\frac{\widehat{S(n)}}{\widehat{I_{G_{n}^{t}}}}=\frac{k[x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}]}{(\{\widehat{s_{1}},\widehat{s_{2i}},\widehat{s_{2i+1}}\mid 1\leq i\leq n\})},

where

$\displaystyle\widehat{s_{1}}$	$\displaystyle=$	$\displaystyle x_{3}^{2}$
$\displaystyle\widehat{s_{2i}}$	$\displaystyle=$	$\displaystyle x_{2i+1}x_{2i+3}-x_{J_{2i}}x_{2i+5}$
$\displaystyle\widehat{s_{2i+1}}$	$\displaystyle=$	$\displaystyle x_{2i+3}^{2}-x_{J_{2i+1}}x_{2i+5}$
$\displaystyle\widehat{s_{2n}}$	$\displaystyle=$	$\displaystyle x_{2n+1}x_{2n+3}$
$\displaystyle\widehat{s_{2n+1}}$	$\displaystyle=$	$\displaystyle x_{2n+3}^{2}$

for $1\leq i<n$ from Definition 3.8. We know $\dim\widehat{R(n,t)}=\dim\widehat{S(n)}/\widehat{I_{G_{n}^{t}}}=\dim\widehat{S(n)}/\sqrt{\widehat{I_{G_{n}^{t}}}}$ . We claim that

\sqrt{\widehat{I_{G_{n}^{t}}}}=\left(x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}\right).

This is clear for $n\in\{0,1\}$ . For $n>1$ , we prove this by induction. Since $\widehat{s_{1}}=x_{3}^{2}$ and $\widehat{s_{2n+1}}=x_{2n+3}^{2}$ are in $\widehat{I_{G_{n}^{t}}}$ , we have $x_{3},x_{2n+3}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ . Since

\widehat{s_{3}}=x_{5}^{2}-x_{3}x_{7}\in\widehat{I_{G_{n}^{t}}}\subseteq\sqrt{\widehat{I_{G_{n}^{t}}}}

and $x_{3}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ , we get $x_{5}^{2}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ , so that $x_{5}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ . Now suppose $x_{2i-1},x_{2i+1}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ for $2\leq i<n$ . We have

\widehat{s_{2i+1}}=x_{2i+3}^{2}-x_{J_{2i+1}}x_{2i+5}\in\widehat{I_{G_{n}^{t}}}\subseteq\sqrt{\widehat{I_{G_{n}^{t}}}}.

But $x_{J_{2i+1}}\in\{x_{2i-1},x_{2i+1}\}$ by Definition 3.8 and $\{x_{2i-1},x_{2i+1}\}\subseteq\sqrt{\widehat{I_{G_{n}^{t}}}}$ by induction, so that $x_{2i+3}^{2}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ , and hence $x_{2i+3}\in\sqrt{\widehat{I_{G_{n}^{t}}}}$ . We conclude that

\left(x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}\right)\subseteq\sqrt{\widehat{I_{G_{n}^{t}}}}\subseteq\left(x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}\right),

so we have equality. Since $\widehat{S(n)}/\sqrt{\widehat{I_{G_{n}^{t}}}}\cong k$ has dimension zero, so does $\widehat{R(n,t)}\cong R(n,t)/(\overline{X_{n}})$ . Thus, the image of $X_{n}$ is a system of parameters for $R(n,t)$ . ∎

Remark 3.11.

We note that as a consequence of the proof of the preceding theorem, the ring $\widehat{R(n,t)}$ is Artinian, which will be relevant in Section 3.2.

Corollary 3.12.

The image of

X_{n}=x_{0},x_{2}-x_{3},x_{4}-x_{5},\ldots,x_{2n}-x_{2n+1},x_{2n+2}-x_{2n+3},x_{2n+4}

in $R(n,t)=S(n)/I_{G_{n}^{t}}$ is a regular sequence for $R(n,t)$ .

Proof.

We know by Proposition 3.10 that the image of $X_{n}$ in $R(n,t)$ is a linear system of parameters. Since the rings $R(n,t)$ are Cohen-Macaulay (Corollary 2.16), we are done. ∎

3.2. Length, Multiplicity, and Regularity

In this section, we determine the multiplicity and Castelnuovo-Mumford regularity of the toric rings $R(n,t)$ coming from the associated graphs $G_{n}^{t}\in\mathcal{F}$ by computing the length of the Artinian rings

\widehat{R(n,t)}\cong R(n,t)/(\overline{X_{n}})

from Definition 3.7. We know by Corollary 3.12 that $\overline{X_{n}}$ is a linear regular sequence for $R(n,t)$ , which allows us to compute the multiplicity of the rings $R(n,t)$ . As a corollary of Theorem 3.16, which establishes the Hilbert function for $\widehat{R(n,t)}$ , we obtain the multiplicity and regularity of $R(n,t)$ . We also develop an alternate graph-theoretic proof for the regularity of $R(n,t)$ , which is included at the end of this section.

We begin with a lemma establishing a vector space basis for $\widehat{R(n,t)}$ , which we use extensively for our results.

Lemma 3.13.

The image of all squarefree monomials with only odd indices whose indices are at least four apart, together with the image of $1_{k}$ , forms a vector space basis for $\widehat{R(n,t)}$ over $k$ .

Proof.

We recall for the reader the definition of $\widehat{R(n,t)}$ and then find the initial ideal of $\widehat{I_{G_{n}^{t}}}$ and use Macaulay’s Basis Theorem to show that the desired representatives form a basis for $\widehat{R(n,t)}$ as a vector space over $k$ .

From Definition 3.7, we have

R(n,t)/(\overline{X_{n}})\cong\widehat{R(n,t)}=\widehat{S(n)}/\widehat{I_{G_{n}^{t}}},

where

\widehat{S(n)}=k[x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}].

By Definition 3.8, for $1\leq i<n$ the ideal $\widehat{I_{G_{n}^{t}}}$ is generated by

$\displaystyle\widehat{s_{1}}$	$\displaystyle=$	$\displaystyle x_{3}^{2}-x_{J_{1}}x_{5}$
$\displaystyle\widehat{s_{2i}}$	$\displaystyle=$	$\displaystyle x_{2i+1}x_{2i+3}-x_{J_{2i}}x_{2i+5}$
$\displaystyle\widehat{s_{2i+1}}$	$\displaystyle=$	$\displaystyle x_{2i+3}^{2}-x_{J_{2i+1}}x_{2i+5}$
$\displaystyle\widehat{s_{2n}}$	$\displaystyle=$	$\displaystyle x_{2n+1}x_{2n+3}$
$\displaystyle\widehat{s_{2n+1}}$	$\displaystyle=$	$\displaystyle x_{2n+3}^{2},$

where $x_{J_{1}}=x_{J_{2}}=0$ , $J_{3}=3$ , and for $2\leq i<n$ ,

	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 0\iff x_{J_{2i}}=x_{J_{2i-2}}\iff J_{2i+1}=2i-1$
	$\displaystyle t_{i+1}$	$\displaystyle=$	$\displaystyle 1\iff x_{J_{2i}}=x_{J_{2i-1}}\iff J_{2i+1}=2i+1.$

We first show that the image of the monomials with the desired property is a basis in the quotient of $\widehat{S(n)}$ by the initial ideal $\text{in}_{>}\widehat{I_{G_{n}^{t}}}$ . By Macaulay’s Basis Theorem, which is Theorem 1.5.7 in [21], the image of these monomials in $\widehat{R(n,t)}$ is also a basis.

To find the initial ideal of $\widehat{I_{G_{n}^{t}}}$ , we establish that the given generators $\widehat{s_{k}}$ are a Gröbner basis for $\widehat{I_{G_{n}^{t}}}$ with respect to the degree reverse lexicographic order $>$ . This is a relatively straightforward computation using Buchberger’s Criterion, with separate cases for when $x_{J_{k}}=0$ .

If we adopt $S$ -polynomial notation $S_{i,j}$ for the $S$ -polynomial of $\widehat{s_{i}}$ and $\widehat{s_{j}}$ , then the cases to consider are

S_{1,2},S_{2,3},S_{2,4},S_{2n-2,2n},S_{2n-1,2n},S_{2n,2n+1}

S_{2i-1,2i}\text{ for }1<i<n

S_{2i,2i+1}\text{ for }1<i<n

S_{2i,2i+2}\text{ for }1<i<n-1.

To give a flavor of the computation involved, we show the case $S_{2i,2i+2}$ for $1<i<n-1$ , and leave the remaining cases to the reader. We show in each subcase that $S_{2i,2i+2}$ is equal to zero or to a sum of basis elements with coefficients in $\widehat{S(n)}$ , so that the reduced form of $S_{2i,2i+2}$ is zero in each subcase. We have

	$\displaystyle S_{2i,2i+2}$	$\displaystyle=$	$\displaystyle x_{2i+5}(x_{2i+1}x_{2i+3}-x_{J_{2i}}x_{2i+5})-x_{2i+1}(x_{2i+3}x_{2i+5}-x_{J_{2i+2}}x_{2i+7})$
		$\displaystyle=$	$\displaystyle-x_{J_{2i}}x_{2i+5}^{2}+x_{2i+1}x_{J_{2i+2}}x_{2i+7}$

Case 1: If $t_{i+2}=0$ , then $x_{J_{2i+2}}=x_{J_{2i}}$ and $J_{2i+3}=2i+1$ , so we have

	$\displaystyle S_{2i,2i+2}$	$\displaystyle=$	$\displaystyle-x_{J_{2i}}x_{2i+5}^{2}+x_{J_{2i}}x_{2i+1}x_{2i+7}$
		$\displaystyle=$	$\displaystyle-x_{J_{2i}}\widehat{s_{2i+3}}$

We note that if $x_{J_{2i}}=x_{J_{2i+2}}=0$ , then $S_{2i,2i+2}=0$ .

Case 2: If $t_{i+2}=1$ , then $x_{J_{2i+2}}=x_{J_{2i+1}}$ and $J_{2i+3}=2i+3$ , so we have

\displaystyle S_{2i,2i+2}

\displaystyle=

\displaystyle-x_{J_{2i}}x_{2i+5}^{2}+x_{2i+1}x_{J_{2i+1}}x_{2i+7}.

Case 2.1: If in addition $t_{i+1}=0$ , then $x_{J_{2i}}=x_{J_{2i-2}}$ and $J_{2i+1}=2i-1$ , so we have

$\displaystyle S_{2i,2i+2}$ $\displaystyle=$ $\displaystyle-x_{J_{2i-2}}x_{2i+5}^{2}+x_{2i+1}x_{2i-1}x_{2i+7}$

$\displaystyle=$ $\displaystyle-x_{J_{2i-2}}(x_{2i+5}^{2}-x_{J_{2i+3}}x_{2i+7})+x_{2i+7}(x_{2i-1}x_{2i+1}-x_{J_{2i-2}}x_{2i+3})$

$\displaystyle=$ $\displaystyle-x_{J_{2i-2}}\widehat{s_{2i+3}}+x_{2i+7}\widehat{s_{2i-2}}.$

We note that if $x_{J_{2i}}=x_{J_{2i-2}}=0$ , then $S_{2i,2i+2}=x_{2i+7}\widehat{s_{2i-2}}$ .

Case 2.2: If in addition $t_{i+1}=1$ , then $x_{J_{2i}}=x_{J_{2i-1}}$ and $J_{2i+1}=2i+1$ , so we have

$\displaystyle S_{2i,2i+2}$ $\displaystyle=$ $\displaystyle-x_{J_{2i-1}}x_{2i+5}^{2}+x_{2i+1}^{2}x_{2i+7}$

$\displaystyle=$ $\displaystyle-x_{J_{2i-1}}(x_{2i+5}^{2}-x_{J_{2i+3}}x_{2i+7})+x_{2i+7}(x_{2i+1}^{2}-x_{J_{2i-1}}x_{2i+3})$

$\displaystyle=$ $\displaystyle-x_{J_{2i-1}}\widehat{s_{2i+3}}+x_{2i+7}\widehat{s_{2i-1}}.$

This concludes the case $S_{2i,2i+2}$ for $1<i<n-1$ . The remaining cases are similar.

Then the given generators $\widehat{s_{k}}$ are a Gröbner Basis for $\widehat{I_{G_{n}^{t}}}$ , so that the initial ideal is

\text{in}_{>}(\widehat{I_{G_{n}^{t}}})=(x_{3}^{2},\{x_{2i+1}x_{2i+3},x_{2i+3}^{2}\mid 1\leq i\leq n\})

in the ring $\widehat{S(n)}=k[x_{3},x_{5},\ldots,x_{2n+1},x_{2n+3}]$ . Since $\text{in}_{>}(\widehat{I_{G_{n}^{t}}})$ consists precisely of all squares of variables in $\widehat{S(n)}$ and all degree two products of variables whose indices differ by exactly two, it follows that the image of the squarefree monomials whose indices are at least four apart, together with the image of $1_{k}$ , forms a basis for $\frac{\widehat{S(n)}}{\text{in}_{>}\widehat{I_{G_{n}^{t}}}}$ . By Macaulay’s Basis Theorem, the image of these monomials in $\widehat{R(n,t)}=\frac{\widehat{S(n)}}{\widehat{I_{G_{n}^{t}}}}$ is also a basis.

∎

We use the lemma above to establish facts about the vector space dimensions of degree $i$ pieces of $\widehat{R(n,t)}$ , which are applied further below to establish length and multiplicity.

Notation 3.14.

Throughout this section, we use $d_{n,i}:=\dim_{k}(\widehat{R(n,t)})_{i}$ for the vector space dimension of the degree $i$ piece of $\widehat{R(n,t)}$ , that is, for the $i$ th coefficient in the Hilbert series of $\widehat{R(n,t)}$ . By Lemma 3.13, these are independent of $t$ .

We establish a recursive relationship between these dimensions by introducing a short exact sequence of vector spaces.

Lemma 3.15.

For $n\geq 2$ and $i\geq 1$ , the vector space dimension $d_{n,i}=\dim_{k}(\widehat{R(n,t)})_{i}$ satisfies the recursive relationship

d_{n,i}=d_{n-1,i}+d_{n-2,i-1}.

Proof.

We use the vector space basis defined in Lemma 3.13. We note that the basis elements described are actually monomial representatives (which do not depend on $t$ ) of equivalence classes (which do depend on $t$ ), but we suppress this and speak as if they are monomials, not depending on $t$ . We then take the liberty of suppressing $t$ in what follows, for convenience. We recall for the reader that

$\displaystyle\widehat{S(n)}$	$\displaystyle=$	$\displaystyle k[x_{3},x_{5},\ldots,x_{2n-3},x_{2n-1},x_{2n+1},x_{2n+3}]$
$\displaystyle\widehat{S(n-1)}$	$\displaystyle=$	$\displaystyle k[x_{3},x_{5},\ldots,x_{2n-3},x_{2n-1},x_{2n+1}]$
$\displaystyle\widehat{S(n-2)}$	$\displaystyle=$	$\displaystyle k[x_{3},x_{5},\ldots,x_{2n-3},x_{2n-1}]$

Let $x_{2n+3}:(\widehat{R(n-2)})_{i-1}\to(\widehat{R(n)})_{i}$ be multiplication by $x_{2n+3}$ , and let
$\widehat{x_{2n+3}}:(\widehat{R(n)})_{i}\to(\widehat{R(n-1)})_{i}$ be defined for a basis element $b$ by

\widehat{x_{2n+3}}(b)=\begin{cases}b&\text{if }x_{2n+3}\nmid b\\ 0&\text{if }x_{2n+3}\mid b.\end{cases}

We note that these vector space maps are well-defined, since $1_{k}$ or a squarefree monomial with odd indices at least four apart has an output of 0, $1$ , or a monomial with the same properties. The following sequence of vector spaces is exact

so that

d_{n,i}=d_{n-1,i}+d_{n-2,i-1}.

∎

Applying Lemma 3.15 and induction, we achieve the following closed formula for the coefficients of the Hilbert series of $\widehat{R(n,t)}$ .

Theorem 3.16.

If $R(n,t)=S(n)/I_{G_{n}^{t}}$ and $\widehat{R(n,t)}\cong R(n,t)/(\overline{X_{n}})$ , we have

{\displaystyle\dim_{k}(\widehat{R(n,t)})_{i}=\begin{cases}1&i=0\\ {\displaystyle\frac{1}{i!}\prod_{j=1}^{i}(n+j-2(i-1))}&i\geq 1.\end{cases}}

In particular, $\dim_{k}(\widehat{R(n,t)})_{i}=0$ when $i>n/2+1$ .

Proof.

We begin with the proof of the last statement, and note that throughout the following proof we use Notation 3.14. When $n\geq 0$ is even, $i=n/2+2$ , and $j=2(\leq i)$ , we have a factor of zero, and when $n\geq 1$ is odd, $i=n/2+3/2$ , and $j=1(<i)$ , we have a factor of zero. Thus $d_{n,i}=0$ when $i>n/2+1$ .

Now we establish the base cases $i,n\in\{0,1\}$ , then proceed by induction. It is clear that $d_{n,0}=1$ , generated by $1_{k}$ . By Lemma 3.13 and by the fact that $\widehat{R(n,t)}$ is a graded quotient, every nonzero element of positive degree $i$ can be represented uniquely as a sum of degree $i$ squarefree monomials with odd indices whose indices are at least four apart. Then $(\widehat{R(n,t)})_{1}$ is generated by the images of all the odd variables

x_{3},x_{2(1)+3},\ldots,x_{2n+3}

in $S(n)$ , so that

d_{n,1}=n+1=\frac{1}{1!}\prod_{j=1}^{1}(n+j-2(1-1))

matches the given formula.

Now we establish the base cases $n=0$ and $n=1$ for all $i$ . We recognize that the first monomial of degree two with odd indices at least four apart is $x_{3}x_{7}$ , which does not exist until $n=2$ , so we have

d_{0,i}=\begin{cases}1&i=0\\ 1&i=1\\ 0&\text{else}\end{cases}=\begin{cases}1&i=0\\ {\displaystyle\frac{1}{i!}\prod_{j=1}^{i}(j-2(i-1))}&i\geq 1\end{cases}

and

d_{1,i}=\begin{cases}1&i=0\\ 2&i=1\\ 0&\text{else}\end{cases}=\begin{cases}1&i=0\\ {\displaystyle\frac{1}{i!}\prod_{j=1}^{i}(1+j-2(i-1))}&i\geq 1,\end{cases}

which match the given formula.

This gives us the following table of base cases for $d_{n,i}$ , which match the given formula:

$n\setminus i$	0	1	2	3	4	5	6	7	$\cdots$
0	1	1	0	0	0	0	0	0	$\cdots$
1	1	2	0	0	0	0	0	0	$\cdots$
2	1	3
3	1	4
4	1	5
$\vdots$	$\vdots$	$\vdots$

We recall by Lemma 3.15 that we have the recursive relationship

d_{n,i}=d_{n-1,i}+d_{n-2,i-1}

for $n\geq 2$ and $i\geq 1$ . We proceed by induction. Suppose $N,I\geq 2$ and that the dimension formula holds for all $i$ when $n<N$ . By our recursion and by induction, we have

$\displaystyle d_{N,I}$	$\displaystyle=$	$\displaystyle d_{N-1,I}+d_{N-2,I-1}$
	$\displaystyle=$	$\displaystyle\frac{1}{I!}\prod_{j=1}^{I}(N-1+j-2(I-1))+\frac{1}{(I-1)!}\prod_{j=1}^{I-1}(N-2+j-2(I-2))$
	$\displaystyle=$	$\displaystyle\frac{1}{I!}(N-2(I-1))\prod_{j=1}^{I-1}(N+j-2(I-1))+\frac{1}{I!}(I)\prod_{j=1}^{I-1}(N+j-2(I-1))$
	$\displaystyle=$	$\displaystyle\frac{1}{I!}\prod_{j=1}^{I}(N+j-2(I-1)),$

as desired. ∎

Remark 3.17.

We note from the proof of the theorem above a few facts for future reference. By our base cases, we have $\ell(\widehat{R(0,t)})=1+1=2$ and $\ell(\widehat{R(1,t)})=1+2=3$ . Taking the Fibonacci sequence $F(n)$ with $F(0)=0$ and $F(1)=1$ , we have $F(2)=1$ , $F(3)=2$ , and $F(4)=3$ , so that

	$\displaystyle\ell(\widehat{R(0,t)})$	$\displaystyle=$	$\displaystyle F(3)$
	$\displaystyle\ell(\widehat{R(1,t)})$	$\displaystyle=$	$\displaystyle F(4).$

These facts become useful in Proposition 3.19.

We see in the following corollary that the regularity of $R(n,t)$ is $\left\lfloor n/2\right\rfloor+1$ . For an alternate proof of the regularity of $R(n,t)$ which uses different machinery and more graph-theoretic properties, see the end of this section.

Corollary 3.18.

For $G_{n}^{t}\in\mathcal{F}$ ,

\operatorname{reg}R(n,t)=\left\lfloor n/2\right\rfloor+1.

Proof.

We show that $\operatorname{reg}R(n,t)$ is equal to the top nonzero degree of $\widehat{R(n,t)}$ and that this value agrees with the above. Since $\widehat{R(n,t)}$ is Artinian by Remark 3.11, it is clear that $\operatorname{reg}\widehat{R(n,t)}$ is the top nonzero degree of $\widehat{R(n,t)}$ . By Theorem 3.16, we know the top nonzero degree is $N$ for some $N\leq n/2+1$ , so that $N\leq\left\lfloor n/2\right\rfloor+1$ . In fact, the top nonzero degree is $\left\lfloor n/2\right\rfloor+1$ , provided $d_{n,\left\lfloor n/2\right\rfloor+1}\neq 0$ . The only way we have a factor of zero in

d_{n,\lfloor n/2\rfloor+1}={\displaystyle\frac{1}{(\lfloor n/2\rfloor+1)!}\prod_{j=1}^{\lfloor n/2\rfloor+1}(n+j-2(\lfloor n/2\rfloor))}

is if $n+j-2(\lfloor n/2\rfloor)=0$ , which means $j/2=\lfloor n/2\rfloor-n/2$ . This can only happen when $j<1$ , but $j\geq 1$ , so we conclude that $d_{n,\left\lfloor n/2\right\rfloor+1}\neq 0$ . Since $\widehat{R(n,t)}$ is an Artinian quotient of $R(n,t)$ by a linear regular sequence, we conclude that

\operatorname{reg}R(n,t)=\operatorname{reg}\widehat{R(n,t)}=\left\lfloor n/2\right\rfloor+1.

∎

In the following, we first compute the lengths of the dimension zero rings $\widehat{R(n,t)}$ , and then show a closed form for the multiplicity of our original rings $R(n,t)$ by using a Fibonacci relationship between the lengths of the rings $\widehat{R(n,t)}$ and applying Binet’s formula for $F(n)$ , the $n$ th number in the Fibonacci sequence:

F(n)=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}\sqrt{5}}.

In the theorem and corollaries which follow, we suppress $t$ for convenience, since the statements are independent of $t$ .

Proposition 3.19.

The lengths of the rings $\widehat{R(n)}$ satisfy the recursive formula

\ell(\widehat{R(n)})=\ell(\widehat{R(n-1)})+\ell(\widehat{R(n-2)})

for $n\geq 2$ . Consequently, if $F(n)$ is the Fibonacci sequence, with $F(0)=0$ and $F(1)=1$ , then

\ell(\widehat{R(n)})=F\left(n+3\right)=\frac{(1+\sqrt{5})^{n+3}-(1-\sqrt{5})^{n+3}}{2^{n+3}\sqrt{5}}.

Proof.

Again, we use Notation 3.14. By the recursive relationship from Lemma 3.15, since $d_{n,0}=1$ in general, and since $d_{n,i}=0$ in general for $i>n/2+1$ by Theorem 3.16, we have for $n\geq 2$ that

$\displaystyle\ell(\widehat{R(n)})=\sum_{i=0}^{\left\lfloor n/2\right\rfloor+1}d_{n,i}$	$\displaystyle=$	$\displaystyle 1+\sum_{i=1}^{\left\lfloor n/2\right\rfloor+1}\left(d_{n-1,i}+d_{n-2,i-1}\right)$
	$\displaystyle=$	$\displaystyle\sum_{i=0}^{\left\lfloor n/2\right\rfloor+1}d_{n-1,i}+\sum_{i=0}^{\left\lfloor(n-2)/2\right\rfloor+1}d_{n-2,i}$
	$\displaystyle=$	$\displaystyle\ell(\widehat{R(n-1)})+\ell(\widehat{R(n-2)}).$

Now we show the second statement. For our base cases, we see from Remark 3.17 that $\ell(\widehat{R(0)})=F(3)=F(0+3)$ and that $\ell(\widehat{R(1)})=F(4)=F(1+3)$ .

Now suppose that ${\displaystyle\ell(\widehat{R(n-1)})=F\left(n+2\right)}$ and ${\displaystyle\ell(\widehat{R(n-2)})=F\left(n+1\right)}$ .
Then we have

\ell(\widehat{R(n)})=\ell(\widehat{R(n-1)})+\ell(\widehat{R(n-2)})\\ =F\left(n+3\right),

as desired. The closed form for $\ell(\widehat{R(n)})$ follows directly from Binet’s formula for the Fibonacci sequence. ∎

Corollary 3.20.

For $n\geq 2$ , there is an equality of multiplicities

e(\widehat{R(n)})=e(\widehat{R(n-1)})+e(\widehat{R(n-2)}).

Proof.

We have established the length of the Artinian rings $\widehat{R(n)}$ , and hence the multiplicity $e(\widehat{R(n)})$ . ∎

Corollary 3.21.

For $n\geq 2$ , there is an equality of multiplicities

e(R(n))=e(R(n-1))+e(R(n-2)).

In particular,

e(R(n))=F\left(n+3\right)=\frac{(1+\sqrt{5})^{n+3}-(1-\sqrt{5})^{n+3}}{2^{n+3}\sqrt{5}}.

Proof.

To obtain the multiplicity of $R(n)$ , we look at $\widehat{R(n)}=R(n)/(\overline{X_{n}})$ , which by Remark 3.11 and Corollary 3.12 is the Artinian quotient of $R(n)$ by a linear regular sequence. By a standard result, we may calculate length along the obvious short exact sequences coming from multiplication by elements of our regular sequence to obtain the equality

\text{Hilb}_{R(n)}(t)(1-t)^{d}=\text{Hilb}_{\widehat{R(n)}}(t),

where $d$ is the Krull dimension of $R(n)$ . Defining multiplicity as in and preceding [24, Thm 16.7], it follows immediately that

e(R(n))=\text{Hilb}_{R(n)}(t)(1-t)^{d}\big{\rvert}_{t=1}=\text{Hilb}_{\widehat{R(n)}}(1)=\ell(\widehat{R(n)}).

We are done by Proposition 3.19. ∎

We reintroduce $t$ and spend the remainder of this section providing an alternate
graph-theoretic proof for the regularity of $R(n,t)$ .

Alternate proof of Corollary 3.18.

We show that $\operatorname{reg}R(n,t)=\left\lfloor n/2\right\rfloor+1$ by proving that $\operatorname{reg}I_{G_{n}^{t}}=\left\lfloor n/2\right\rfloor+2$ . We first show that

\operatorname{reg}I_{G_{n}^{t}}\leq\left\lfloor n/2\right\rfloor+2.

We recall by Proposition 2.13 that the graph $G_{n}^{t}$ is chordal bipartite with vertex bipartition $V_{1}\cup V_{2}$ of cardinalities

	$\displaystyle\|V_{1}\|$	$\displaystyle=$	$\displaystyle\left\lfloor\frac{n}{2}\right\rfloor+2$
	$\displaystyle\|V_{2}\|$	$\displaystyle=$	$\displaystyle\left\lceil\frac{n}{2}\right\rceil+2,$

and that $G_{n}^{t}$ does not have any vertices of degree one by Remark 2.6. Then by Theorem 4.9 of [3], we have

\operatorname{reg}I_{G_{n}^{t}}\leq\min\left\{\left\lfloor\frac{n}{2}\right\rfloor+2,\left\lceil\frac{n}{2}\right\rceil+2\right\}=\left\lfloor\frac{n}{2}\right\rfloor+2.

We note that we may equivalently prove $\operatorname{reg}R(n,t)\leq\left\lfloor\frac{n}{2}\right\rfloor+1$ by choosing the $\left\lfloor\frac{n}{2}\right\rfloor+2$ edges whose indices are equivalent to zero modulo $4$ , one from each row of $L_{n}^{t}$ , to obtain an edge matching (different from an induced matching, below) and then applying [14, Th 1].

We now show that $\operatorname{reg}I_{G_{n}^{t}}\geq\left\lfloor n/2\right\rfloor+2$ . Since $I_{G_{n}^{t}}$ is homogeneous and $\text{in}_{>}I_{G_{n}^{t}}$ consists of squarefree monomials by Corollary 3.3, we have by Corollary 2.7 of [4] that $\operatorname{reg}\text{in}_{>}I_{G_{n}^{t}}=\operatorname{reg}I_{G_{n}^{t}}$ , so it suffices to prove that $\operatorname{reg}\text{in}_{>}I_{G_{n}^{t}}\geq\left\lfloor n/2\right\rfloor+2$ . The ideal $\text{in}_{>}I_{G_{n}^{t}}$ can be viewed as the edge ideal of a simple graph, a “comb” with $n+1$ tines, with consecutive odd variables corresponding to vertices along the spine, as pictured below:

We know from Theorem 6.5 of [13] that the regularity of an edge ideal is bounded below by the number of edges in any induced matching plus one, so we choose $\left\lfloor{n/2}\right\rfloor+1$ edges (tines) corresponding to certain odd variables that create an induced matching. By beginning with the $x_{3}$ -tine and choosing every other tine corresponding to the variables

x_{3},x_{3+4(1)},\ldots,x_{3+4(\left\lfloor{n/2}\right\rfloor)},

we obtain $\left\lfloor{n/2}\right\rfloor+1$ edges that are an induced matching, so we have

\operatorname{reg}\text{in}_{>}I_{G_{n}^{t}}\geq\left\lfloor{n/2}\right\rfloor+2,

as desired.

We conclude that $\operatorname{reg}I_{G_{n}^{t}}=\left\lfloor n/2\right\rfloor+2$ , and hence that $\operatorname{reg}R(n,t)=\left\lfloor n/2\right\rfloor+1.$ ∎

References

[1] L. Ballard. Properties of the Toric Rings of a Chordal Bipartite Family of Graphs. PhD thesis, Syracuse University, 2020.
[2] S. K. Beyarslan, H. T. Hà, and A. O’Keefe. Algebraic properties of toric rings of graphs. Communications in Algebra, 47(1):1–16, 2019.
[3] J. Biermann, A. O’Keefe, and A. Van Tuyl. Bounds on the regularity of toric ideals of graphs. Advances in Applied Mathematics, 85:84–102, 2017.
[4] A. Conca and M. Varbaro. Square-free Gröbner degenerations. Inventiones Mathematicae, 221(3):713–730, 2020.
[5] A. Corso and U. Nagel. Monomial and toric ideals associated to Ferrers graphs. Transactions of the American Mathematical Society, 361(3):1371–1395, 2009.
[6] D. Cox, J. Little, and D. O’Shea. Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, New York, third edition, 2007. An introduction to computational algebraic geometry and commutative algebra.
[7] A. D’Alì. Toric ideals associated with gap-free graphs. Journal of Pure and Applied Algebra, 219(9):3862–3872, 2015.
[8] G. Favacchio, G. Keiper, and A. Van Tuyl. Regularity and h-polynomials of toric ideals of graphs. Proceedings of the American Mathematical Society, 148:4665–4677, 2020.
[9] F. Galetto, J. Hofscheier, G. Keiper, C. Kohne, M. E. Uribe Paczka, and A. Van Tuyl. Betti numbers of toric ideals of graphs: a case study. Journal of Algebra and its Applications, 18(12):1950226, 2019.
[10] I. Gitler and C. E. Valencia. Multiplicities of edge subrings. Discrete Mathematics, 302(1):107–123, 2005.
[11] D. R. Grayson and M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/.
[12] Z. Greif and J. McCullough. Green-Lazarsfeld condition for toric edge ideals of bipartite graphs. Journal of Algebra, 562:1–27, 2020.
[13] H. T. Hà and A. Van Tuyl. Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. Journal of Algebraic Combinatorics, 27(2):215–245, 2008.
[14] J. Herzog and T. Hibi. The regularity of edge rings and matching numbers. Mathematics, 8(1):39, 2020.
[15] J. Herzog, T. Hibi, and H. Ohsugi. Binomial ideals, volume 279 of Graduate Texts in Mathematics. Springer, Cham, 2018.
[16] T. Hibi, A. Higashitani, K. Kimura, and A. O’Keefe. Depth of edge rings arising from finite graphs. Proceedings of the American Mathematical Society, 139(11):3807–3813, 2011.
[17] T. Hibi and L. Katthän. Edge rings satisfying Serre’s condition ( ${R}_{1}$ ). Proceedings of the American Mathematical Society, 142(7):2537–2541, 2014.
[18] T. Hibi, K. Matsuda, and H. Ohsugi. Strongly Koszul edge rings. Acta Mathematica Vietnamica, 41(1):69–76, 2016.
[19] T. Hibi, K. Matsuda, and A. Tsuchiya. Edge rings with 3-linear resolutions. Proceedings of the American Mathematical Society, 147(8):3225–3232, 2019.
[20] T. Hibi and H. Ohsugi. Toric ideals generated by quadratic binomials. Journal of Algebra, 218(2):509–527, 1999.
[21] M. Kreuzer and L. Robbiano. Computational Commutative Algebra 1. Springer, Berlin, Heidelberg, 2000.
[22] K. Mori, H. Ohsugi, and A. Tsuchiya. Edge rings with $q$ -linear resolutions. Preprint, arxiv.org/abs/2010.02854.
[23] R. Nandi and R. Nanduri. On Betti numbers of toric algebras of certain bipartite graphs. Journal of Algebra and Its Applications, 18(12):1950231, 2019.
[24] I. Peeva. Graded Syzygies. Springer London, London, 2011.
[25] A. Simis, W. V. Vasconcelos, and R. H. Villarreal. On the ideal theory of graphs. Journal of Algebra, 167(2):389–416, 1994.
[26] C. Tatakis and A. Thoma. On the universal Gröbner bases of toric ideals of graphs. Journal of Combinatorial Theory, Series A, 118(5):1540–1548, 2011.
[27] R. H. Villarreal. Rees algebras of edge ideals. Communications in Algebra, 23(9):3513–3524, 1995.

$\displaystyle S_{2i-1,2i}$	$\displaystyle=$	$\displaystyle-x_{2i-3}x_{2i+2}x_{2i+3}+x_{j_{2i-4}}x_{2i}x_{2i+4}$
	$\displaystyle=$	$\displaystyle-x_{2i-3}(x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4})+x_{2i+4}(x_{2i-3}x_{2i-1}-x_{j_{2i-4}}x_{2i})$
	$\displaystyle=$	$\displaystyle-x_{2i-3}s_{2i+1}+x_{2i+4}s_{2i-4}.$

$\displaystyle S_{2i-1,2i}$	$\displaystyle=$	$\displaystyle-x_{2i-2}x_{2i+2}x_{2i+3}+x_{j_{2i-3}}x_{2i}x_{2i+4}$
	$\displaystyle=$	$\displaystyle-x_{2i-2}(x_{2i+2}x_{2i+3}-x_{j_{2i+1}}x_{2i+4})+x_{2i+4}(x_{2i-2}x_{2i-1}-x_{j_{2i-3}}x_{2i})$
	$\displaystyle=$	$\displaystyle-x_{2i-2}s_{2i+1}+x_{2i+4}s_{2i-3}.$

$\displaystyle S_{2i,2i+2}$	$\displaystyle=$	$\displaystyle-x_{J_{2i-2}}x_{2i+5}^{2}+x_{2i+1}x_{2i-1}x_{2i+7}$
	$\displaystyle=$	$\displaystyle-x_{J_{2i-2}}(x_{2i+5}^{2}-x_{J_{2i+3}}x_{2i+7})+x_{2i+7}(x_{2i-1}x_{2i+1}-x_{J_{2i-2}}x_{2i+3})$
	$\displaystyle=$	$\displaystyle-x_{J_{2i-2}}\widehat{s_{2i+3}}+x_{2i+7}\widehat{s_{2i-2}}.$

$\displaystyle S_{2i,2i+2}$	$\displaystyle=$	$\displaystyle-x_{J_{2i-1}}x_{2i+5}^{2}+x_{2i+1}^{2}x_{2i+7}$
	$\displaystyle=$	$\displaystyle-x_{J_{2i-1}}(x_{2i+5}^{2}-x_{J_{2i+3}}x_{2i+7})+x_{2i+7}(x_{2i+1}^{2}-x_{J_{2i-1}}x_{2i+3})$
	$\displaystyle=$	$\displaystyle-x_{J_{2i-1}}\widehat{s_{2i+3}}+x_{2i+7}\widehat{s_{2i-1}}.$

Properties of the Toric Rings of a Chordal Bipartite Family of Graphs

Abstract.

Key words and phrases:

2020 Mathematics Subject Classification:

1. Introduction

Theorem 1.1 (Theorem 3.4).

Corollary 1.2 (Corollary 3.5).

Proposition 1.3 (Proposition 3.10).

Theorem 1.4 (Theorem 3.16).

Corollary 1.5 (Corollary 3.18).

Corollary 1.6 (Corollary 3.21).

2. The Family of Toric Rings

2.1. The Family ℱ\mathcal{F} of Graphs

Definition 2.1.

Remark 2.2.

Example 2.3.

Example 2.4.

Definition 2.5.

Remark 2.6.

Example 2.7.

Definition 2.8.

Proposition 2.9.

Proof.

Definition 2.10.

Remark 2.11.

Remark 2.12.

Proposition 2.13.

Proof.

Remark 2.14.

2.2. Toric Rings for ℱ\mathcal{F}

Proposition 2.15.

Proof.

Corollary 2.16.

Proof.

Remark 2.17.

Example 2.18.

2.3. Distinction From Join-Meet Ideals of Lattices

Definition 2.19.

Remark 2.20.

Definition 2.21.

Notation 2.22.

Lemma 2.23.

Proof.

Lemma 2.24.

Proof.

Lemma 2.25.

Proof.

Lemma 2.26.

Proof.

Proposition 2.27.

Proof.

3. Properties of the Family of Toric Rings

3.1. Dimension and System of Parameters

Lemma 3.1.

Proof.

Corollary 3.2.

Proof.

Corollary 3.3.

Theorem 3.4.

Proof.

Corollary 3.5.

Proof.

Remark 3.6.

Definition 3.7.

Definition 3.8.

Example 3.9.

Proposition 3.10.

Proof.

Remark 3.11.

Corollary 3.12.

Proof.

3.2. Length, Multiplicity, and Regularity

Lemma 3.13.

Proof.

Notation 3.14.

Lemma 3.15.

Proof.

Theorem 3.16.

Proof.

Remark 3.17.

2.1. The Family $\mathcal{F}$ of Graphs

2.2. Toric Rings for $\mathcal{F}$