The Regularity of Edge Rings and Matching Numbers

Abstract

Let $K[G]$ denote the edge ring of a finite connected simple graph G on $[d]$ and $\mathrm{mat}(G)$ the matching number of G. It is shown that $\mathrm{reg}(K[G])\le \mathrm{mat}(G)$ if G is non-bipartite and $K[G]$ is normal, and that $\mathrm{reg}(K[G])\le \mathrm{mat}(G)-1$ if G is bipartite.

Let G be a finite connected simple graph on the vertex set $[d]=\{1,\dots ,d\}$ and let $E(G)$ be its edge set. Let $S=K[x_1,\dots ,x_d]$ denote the polynomial ring in d variables over a field K. The edge ring of G is the toric ring $K[G]\subset S$ which is generated by those monomials $x_i{x}_j$ with $\{i,j\}\in E(G)$. The systematic study of edge rings originated in [1]. It has been shown that $K[G]$ is normal if and only if G satisfies the odd cycle condition ([2], p. 131). Thus, particularly if G is bipartite, $K[G]$ is normal.

Let ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_d$ denote the canonical unit coordinate vectors of ${\mathbb{R}}^d$. The edge polytope is the lattice polytope ${\mathcal{P}}_G\subset {\mathbb{R}}^d$ which is the convex hull of the finite set $\{ {\mathbf{e}}_i+{\mathbf{e}}_j : \{i,j\}\in E(G) \}$. One has $\dim {\mathcal{P}}_G=d-1$ if G is non-bipartite and $\dim {\mathcal{P}}_G=d-2$ if G is bipartite. We refer the reader to ([2], Chapter 5) for the fundamental materials on edge rings and edge polytopes.

A matching of G is a subset $M\subset E(G)$ for which $e\cap e^{\prime }=\varnothing$ for $e\ne e^{\prime }$ belonging to M. The matching number is the maximal cardinality of matchings of G. Let $\mathrm{mat}(G)$ denote the matching number of G.

When $K[G]$ is normal, the upper bound of regularity of $K[G]$ can be explicitly described in terms of $\mathrm{mat}(G)$. Our main result in the present paper is as follows:

Theorem 1.

Let G be a finite connected simple graph. Then

(a) 

If G is non-bipartite and$K[G]$is normal, then$\mathrm{reg}K[G]\le \mathrm{mat}(G)$;

(b) 

If G is bipartite, then$\mathrm{reg}K[G]\le \mathrm{mat}(G)-1$.

Lemma 1 stated below, which provides information on lattice points belonging to the interiors of dilations of edge polytopes, is indispensable for the proof of Theorem 1.

Lemma 1.

Suppose that$(a_1,\dots ,a_d)\in {\mathbb{Z}}^d$belongs to the interior$q({\mathcal{P}}_G\backslash \partial {\mathcal{P}}_G)$of the dilation$q{\mathcal{P}}_G=\{q\alpha :\alpha \in {\mathcal{P}}_G\}$, where$q\ge 1$, of${\mathcal{P}}_G$. Then$a_i\ge 1$for each$1\le i\le d$.

Proof. 

The facets of ${\mathcal{P}}_G$ are described in ([1], Theorem 1.7). When $W\subset [d]$, we write $G_W$ for the induced subgraph of G on W. Since $K[G]$ is normal, it follows that ${\mathcal{P}}_G$ possesses the integer decomposition property ([2], p. 91). In other words, each $\mathbf{a}\in q{\mathcal{P}}_G\cap {\mathbb{Z}}^d$ is of the form

$$\mathbf{a}=({\mathbf{e}}_{i_1}+{\mathbf{e}}_{j_1})+\cdots +({\mathbf{e}}_{i_q}+{\mathbf{e}}_{j_q}),$$

where $\{i_1,j_1\},\dots ,\{i_q,j_q\}$ are edges of G.

(First Step) Let G be non-bipartite. Let $i\in [d]$. Let $H_1,\dots ,H_s$ and $H_1^{\prime },\dots ,H_{s^{\prime }}^{\prime }$ denote the connected components of $G_{[d]\backslash \{i\}}$, where each $H_j$ is bipartite and where each $H_{j^{\prime }}^{\prime }$ is non-bipartite. If $s=0$, then $i\in [d]$ is regular ([1], p. 414) and the hyperplane of ${\mathbb{R}}^d$ defined by the equation $x_i=0$ is a facet of $q{\mathcal{P}}_G$. Hence $a_i>0$.

Let $s\ge 1$ and $s^{\prime }\ge 0$. For each $1\le j\le s$, we write $W_j\cup U_j$ for the vertex set of the bipartite graph $H_j$ for which there is $a\in W_j$ with $\{a,i\}\in E(G)$, where $U_j=\varnothing$ if $H_j$ is a graph consisting of a single vertex. Then $T=W_1\cup \cdots \cup W_s$ is independent ([1], p. 414). In other words, no edge $e\in E(G)$ satisfies $e\subset T$. Let $G^{\prime }$ denote the bipartite graph induced by T. Thus the edges of $G^{\prime }$ are $\{b,c\}\in E(G)$ with $b\in T$ and $c\in T^{\prime }=U_1\cup \cdots \cup U_s\cup \{i\}$. Since each induced subgraph $G_{W_j\cup U_j\cup \{i\}}$ is connected, it follows that $G^{\prime }$ is connected with $V(G^{\prime })=T\cup T^{\prime }$ as its vertex set. Since the connected components of $G_{[d]\backslash V(G^{\prime })}$ are $H_1^{\prime },\dots ,H_{s^{\prime }}^{\prime }$, it follows that T is fundamental ([1], p. 415) and the hyperplane of ${\mathbb{R}}^d$ defined by ${\sum }_{\xi \in T}{x}_{\xi }={\sum }_{{\xi }^{\prime }\in T^{\prime }}{x}_{{\xi }^{\prime }}$ is a facet of $q{\mathcal{P}}_G$. Now, suppose that $a_i=0$. Since ${\mathcal{P}}_G$ possesses the integer decomposition property, one has ${\sum }_{\xi \in T}{a}_{\xi }={\sum }_{{\xi }^{\prime }\in T^{\prime }}{a}_{{\xi }^{\prime }}$. Hence $(a_1,\dots ,a_d)\in {\mathbb{Z}}^d$ cannot belong to $q({\mathcal{P}}_G\backslash \partial {\mathcal{P}}_G)$. Thus $a_i>0$, as desired.

(Second Step) Let G be bipartite. If G is a star graph with, say, $E(G)=\{\{1,2\},\{1,3\},\dots ,\{1,d\}\}$, then ${\mathcal{P}}_G$ can be regarded to be the $(d-2)$ simplex of ${\mathbb{R}}^{d-1}$ with the vertices $(1,0,\dots ,0),(0,1,0,\dots ,0),\dots ,(0,\dots ,0,1)$. Thus, since each $(a_1,\dots ,a_d)\in q{\mathcal{P}}_G\cap {\mathbb{Z}}^d$ satisfies $a_1=q$, the assertion follows immediately. In the argument below, one will assume that G is not a star graph.

Let $i\in [d]$ and $H_1,\dots ,H_s$ be the connected components of $G_{[d]\backslash \{i\}}$. If $s=1$, then $i\in [d]$ is ordinary ([1], p. 414) and the hyperplane of ${\mathbb{R}}^d$ defined by the equation $x_i=0$ is a facet of $q{\mathcal{P}}_G$. Hence $a_i>0$.

Let $s\ge 2$. Let $W_j\cup U_j$ denote the vertex set of $H_j$ for which there is $a\in W_j$ with $\{a,i\}\in E(G)$. Since G is not a star graph, one can assume that $U_1\ne \varnothing$. Then $T=W_2\cup \cdots \cup W_s$ is independent and the bipartite graph induced by T is $G_{[d]\backslash (W_1\cup U_1)}$. Hence T is acceptable ([1], p. 415) and the hyperplane of ${\mathbb{R}}^d$ defined by ${\sum }_{\xi \in W_1}{x}_{\xi }={\sum }_{{\xi }^{\prime }\in U_1}{x}_{{\xi }^{\prime }}$ is a facet of $q{\mathcal{P}}_G$. Now, suppose that $a_i=0$. Since ${\mathcal{P}}_G$ possesses the integer decomposition property, one has ${\sum }_{\xi \in W_1}{a}_{\xi }={\sum }_{{\xi }^{\prime }\in U_1}{a}_{{\xi }^{\prime }}$. Hence $(a_1,\dots ,a_d)\in {\mathbb{Z}}^d$ cannot belong to $q({\mathcal{P}}_G\backslash \partial {\mathcal{P}}_G)$. Thus $a_i>0$, as required. □

We say that a finite subset $L\subset E(G)$ is an edge cover of G if ${\cup }_{e\in L}e=[d]$. Let $\mu (G)$ denote the minimal cardinality of edge covers of G.

Corollary 1.

When$K[G]$is normal, one has$q\ge \mu (G)$if$q({\mathcal{P}}_G\backslash \partial {\mathcal{P}}_G)\cap {\mathbb{Z}}^d\ne \varnothing$.

Proof. 

Since ${\mathcal{P}}_G$ possesses the integer decomposition property, Lemma 1 guarantees that, if $\mathbf{a}\in q({\mathcal{P}}_G\backslash \partial {\mathcal{P}}_G)\cap {\mathbb{Z}}^d$, one has $q\ge \mu (G)$. □

Once Corollary 1 is established, to complete the proof of Theorem 1 is a routine job on computing the regularity of normal toric rings.

Proof of Theorem 1.

In each of the cases (a) and (b), since the edge ring $K[G]$ is normal, it follows that the Hilbert function of $K[G]$ coincides the Ehrhart function ([2], p. 100) of the edge polytope ${\mathcal{P}}_G$, which says that the Hilbert series of $K[G]$ is of the form

$$(h_0+h_1\lambda +\cdots +h_s{\lambda }^s)/{(1-\lambda )}^{(\dim {\mathcal{P}}_G)+1}$$

with each $h_i\in \mathbb{Z}$ and $h_s\ne 0$. One has

$$s=(\dim {\mathcal{P}}_G+1)-\min \{ q\ge 1 : q({\mathcal{P}}_G\backslash \partial {\mathcal{P}}_G)\cap {\mathbb{Z}}^d\ne \varnothing \}.$$

Now, Corollary 1 guarantees that

$$s\le (\dim {\mathcal{P}}_G+1)-\mu (G).$$

Finally, since $\mu (G)=d-\mathrm{mat}(G)$ ([3], Lemma 2.1), one has

$$\mathrm{reg}K[G]=s\le \dim {\mathcal{P}}_G-(d-1)+\mathrm{mat}(G),$$

as required. □

Rafael H. Villarreal informed us that part (b) of Theorem 1 can also be deduced from ([4], Theorem 14.4.19).

When $K[G]$ is non-normal, the behavior of regularity is curious.

Proposition 1.

For given integers$0\le r\le m$, there exists a finite connected simple graph G such that$\mathrm{reg}K[G]=r$, and

$$\mathrm{mat}(G)=\left\{\begin{array}{l}m, \mathrm{if} G \mathrm{is} \mathrm{non}-\mathrm{bipartite},\\ m+1, \mathrm{if} G \mathrm{is} \mathrm{bipartite}.\end{array}\right.$$

Proof. 

In the non-bipartite case, let H be the complete graph with $2r$ vertices. Its matching number is r. We know from ([5], Corollary 2.12) that $\mathrm{reg}K[H]=r$. At one vertex of H we attach a path graph of length $2(m-r)$ and call this new graph G. Then $\mathrm{mat}(G)=m$ and $\mathrm{reg}K[G]=\mathrm{reg}K[H]=r$, as $K[G]$ is just a polynomial extension of $K[H]$.

In the bipartite case, let H be the bipartite graph of type $(r+1,r+1)$. The matching number is $r+1$. Indeed, $K[H]$ may be viewed as a Hibi ring whose regularity is well-known, see for example ([6], Theorem 1.1). At one vertex of H we attach a path graph of length $2(m-r)$ and call this new graph G. Then $\mathrm{mat}(G)=m+1$ and $\mathrm{reg}K[G]=\mathrm{reg}K[H]=r$, for the same reason as before. □

These bounds for the regularity of $K[G]$ are generally only valid if $K[G]$ is normal. Consider, for example, the graph G which consists of two disjoint triangles combined as a path of length ℓ. Then the defining ideal of $K[G]$ is generated by a binomial of degree $\ell +3$, and hence $\mathrm{reg}K[G]=\ell +2$, while the matching number of G is $2+\lceil \ell /2\rceil$.

Question 1.

Let m be a positive integer, and consider the set ${\mathcal{S}}_m$ of finite connected simple graphs with matching number m.

• Is there a bound for $\mathrm{reg}K[G]$ with $G\in {\mathcal{S}}_m$?
• If such a bound exists, is it a linear function of m?