A lower bound for depths of powers of edge ideals

Abstract

Let $G$ be a graph, and let $I$ be the edge ideal of $G$. Our main results in this article provide lower bounds for the depth of the first three powers of $I$ in terms of the diameter of $G$. More precisely, we show that $\mathrm{{depth}}\,R/I^t \ge \left\lceil {\frac{d-4t+5}{3}} \right\rceil +p-1$, where $d$ is the diameter of $G$ and $p$ is the number of connected components of $G$ and $1 \le t \le 3$. For general powers of edge ideals we show that $\mathrm{{depth}}\,R/I^t \ge p-t$. As an application of our results we obtain the corresponding lower bounds for the Stanley depth of the first three powers of $I$.

1 Introduction

Let $R$ be either a Noetherian local ring or a standard graded $k$-algebra, where $k$ is a field. Let $I$ be an ideal of $R$, and when $R$ is graded, assume that $I$ is a graded ideal. Let $d=\dim R$. A classical result by Burch [5], which was improved by Broadmann [2], states that

$$\begin{aligned} \underset{t\rightarrow \infty }{\hbox {lim}}\,\mathrm{{depth}}\,R/I^{t} \le d-\ell (I), \end{aligned}$$

where $\ell (I)$ is the analytic spread of $I$. Eisenbud and Huneke [11] showed that the equality holds if the associated graded ring $\mathrm{gr}_{R}{(I)}= \bigoplus \limits _{i=0}^{\infty } I^i/I^{i+1}$ of $I$ is Cohen–Macaulay. Therefore, the limiting behavior of the depth is well understood. However, the initial behavior of the depth of powers is still mysterious. Thus, it is natural to investigate lower bounds for $\mathrm{{depth}}\,R/I^t$.

In the case of monomial ideals, lower bounds for the depth of the first power, $\mathrm{{depth}}\,R/I$, have been studied extensively [15, 16, 24]. Herzog and Hibi [21] determined that $\mathrm{{depth}}\,R/I^{t}$ is a nonincreasing function if all the powers of $I$ have a linear resolution. They also obtained lower bounds for $\mathrm{{depth}}\,R/I^t$ if all the powers of $I$ have linear quotients, a condition that implies that all the powers of $I$ have linear resolutions [21]. In particular, they showed that all edge ideals associated with a finite graph whose complementary graph is chordal have linear quotients. Also, if $I$ is a square-free Veronese ideal (which includes the class of complete graphs), then all powers of $I$ have linear quotients. However, in general edge ideals and their powers do not have linear resolutions. Even for monomial ideals the depth function can behave quite wildly, see [1]. For square-free monomial ideals, it is known that $\mathrm{{depth}}\,R/I^{t}$ will not necessarily be a nonincreasing function, see [23], Theorem 13], but the question is still open for edge ideals of graphs.

Another motivation for studying lower bounds for $\mathrm{{depth}}\,R/I^t$ is the fact that these lower bounds provide upper bounds for $\mathrm{projdim}_{R} R/I^t$, the projective dimension of $R/I^t$. When $I$ is the edge ideal of a graph, then an upper bound for the projective dimension of a graph’s edge ideal provides a lower bound for the first nonzero homology group of the graph’s independence complex [8], Observation 1.2]. Moreover, when $I$ is square-free monomial, its cohomological dimension and projective dimension are equal, [12], Theorem 0.2] or [33], Corollary 4.2]. Many researchers have studied the question of finding upper bounds for the projective dimension of $R/I$ and upper bounds for the cohomological dimension, see, for example, [13, 14, 19, 25, 28, 29].

We now describe our setup. Let $V=\{x_1, \ldots , x_n\}$ be a set of $n$ vertices and let $G$ be a simple graph (no multiple edges, no loops) on $V$. Let $I$ be the edge ideal of $G$ in the ring $R=k[x_1, \ldots , x_n]$, where $k$ is a field. By $\mathrm{{depth}}\,R/I^{t}$ we mean the maximum length of an $R/I^{t}$-regular sequence in $\mathfrak {m}=(x_1, \ldots , x_n)$. When $I$ is the edge ideal of a bipartite graph, then $\mathrm{{depth}}\,R/I^t \ge 1$, since $\mathfrak {m}\not \in \mathrm{Ass}(R/I^t)$, by [32], Theorem 5.9]. In a recent article, Morey gives lower bounds for the depths of all powers when $I$ is the edge ideal of a forest [27]. We focus our interest on studying lower bounds for the depths of powers of edge ideals of graphs without any restrictions on the shape of the graph.

The article is organized as follows. In Sect. 2 we give the necessary definitions and relevant background. In Sects. 3 and 4 we establish the main results of this article. More precisely, we prove in Theorem 3.1 that when $I$ is the edge ideal of a graph, then $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{d+1}{3}} \right\rceil$, where $d$ is the diameter of the graph. One can improve this bound by considering the diameters of each connected component of the graph. We show in Corollary 3.3 that when $G$ has $p$ connected components, then $\mathrm{{depth}}\,R/I \ge \sum \nolimits _{i=1}^{p}\left\lceil {\frac{d_i+1}{3}}\right\rceil$, where $d_i$ is the diameter of the $i$th connected component of $G$.

We develop a series of lemmas that leads us to prove lower bounds for the second and third powers of the edge ideal of a graph. We first prove in Proposition 4.3 that $\mathrm{{depth}}\,R/I^t \ge p-t$ for any $t$; then, in Theorems 4.4 and  4.13 we show that $\mathrm{{depth}}\,R/I^2 \ge \left\lceil {\frac{d-3}{3}}\right\rceil +p-1$ and $\mathrm{{depth}}\,R/I^3 \ge \left\lceil {\frac{d-7}{3}}\right\rceil +p-1$, where $I$ is the edge ideal of a graph $G$, $d$ is the diameter of $G$, and $p$ is the number of connected components of $G$. It is worth noting here that in order to establish the bounds for the second and third powers we need to deal with the depth of the edge ideal of a graph that potentially has loops. We provide a lower bound on the depth of the edge ideal of a graph with loops based on knowledge of the position of the loops. More precisely, we prove in Proposition 3.5 that when $I$ is the edge ideal of a graph with loops and $\ell$ is an integer such that there exists a vertex $u$ with $d(u,x) \ge \ell$ for all vertices $x$ for which there is a loop on $x$, then $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{\ell -1}{3}}\right\rceil$. This result for the depth of the edge ideal of a graph with loops is of independent interest.

We conclude the article by using [4], Proposition 2.6] or [31], Lemma 2.2] in place of the Depth Lemma, to extend our results to provide lower bounds on the Stanley depth of the powers of $I$. In particular, in Theorem 4.18 we show that $\mathrm{{sdepth}\,}{R/I^t} \ge \left\lceil {\frac{d-4t+5}{3}} \right\rceil +p-1$ for $1 \le t \le 3$, where $\mathrm{{sdepth}\,}$ denotes the Stanley depth.

2 Background

Let $V=\{x_1, \ldots , x_n\}$ be a set of $n$ vertices, and let $G$ be a graph on $V=V(G)$. Let $E=E(G)$ denote the set of edges of $G$. Unless otherwise stated we will assume that $G$ is a simple graph, that is, without loops and without multiple edges. Let $R=k[x_1, \ldots , x_n]$ be a polynomial ring, where $k$ is a field. Note that we will not distinguish between the vertices of a graph and the variables in the corresponding polynomial ring. The edge ideal $I(G)$ of a graph $G$ is defined to be the monomial ideal in the ring $R$ generated by the monomials $x_ix_j$, where $\{x_i, x_j\} \in E$. Similarly, if $I$ is a square-free monomial ideal generated in degree two, $G(I)$ is the graph associated with $I$. That is, $\{x_i, x_j\} \in E(G(I))$ if and only if $x_ix_j$ is a generator of $I$.

We now collect some useful definitions from graph theory. For algebraic definitions and background material, see [26] or [36].

Definition 2.1

Let $G$ be a graph, let $V=V(G)=\{x_1, \ldots , x_n\}$ and let $E=E(G)$. Then,

• (a) A path of length $r-1$ is a set of $r$ distinct vertices $x_{i_1}, \ldots , x_{i_r}$ together with $r-1$ edges $x_{i_j}x_{i_{j+1}}$, where $x_{i_j} \in \{ x_1, \ldots , x_n\}$ and $1 \le j \le r-1$.

• (b) The distance between two vertices $u$ and $v$ is the length of the shortest path between $u$ and $v$ and is denoted as $d(u,v)$.

• (c) The diameter of a connected graph is $d(G)=\max \{d(u,v)\mid u, v \in V\}$. Therefore, if $d=d(G)$, then there exist vertices $u,v$ of $G$ with $d(u,v)=d$. In this case we say that a path of length $d$ with endpoints $u$ and $v$ realizes the diameter of $G$. Although technically the diameter of a disconnected graph is infinite, we will find it useful to refer to the maximum of the diameters of the connected components of $G$ as the diameter of $G$ when $G$ is disconnected.

• (d) Let $u \in V$. The neighbor set of $u$ is the set $N(u)=\{v\in V(G) \mid \{u,v\} \in E\}$. When $N(u)=\emptyset$, then $u$ is called an isolated vertex, and when the cardinality of $N(u)$ is one, then $u$ is called a leaf.

• (e) A loop in a graph $G$ is an edge both of whose endpoints are equal, that is, an edge $\{x, x\} \in E$. A loop on $x$ corresponds to a generator $x^2$ in the edge ideal, so the edge ideal of a graph with loops is no longer square-free. Note that if loops are added to a graph, the distance between two vertices is unchanged.

When dealing with general graphs, it is helpful to consider a construction that is commonly used to produce a spanning tree. Although the spanning tree produced will not be used here, nonetheless the construction yields a partition of the vertices that we will exploit.

Notation 2.2

Suppose $G$ is a connected graph and $u \in V(G)$. Let $X^i_G(u) =\{x\in V(G) \, | \, d(u,x)=i\}$. Note that $X^0_G(u)=\{u\}$ and that $i$ runs from $0$ to $d$, where $d=\text{ max } \{d(u,x) \, | \, x \in V(G)\}$. The sets $X^i_G(u)$ form a partition of $V(G)$. Once $u$ has been fixed, we will omit $G$ and $u$ from the notation when they are clear from context. We will frequently choose $u$ to be an endpoint of a path realizing the diameter, in which case $d$ will be the diameter of $G$. When a graph $G$ is not connected, this construction can be applied to the connected component of $G$ containing $u$.

When a vertex $u$ has been fixed in $G$, we will denote the connected component of $G$ that contains $u$ by ${}_{u}G$. Thus, if $I$ is an edge ideal and $u$ has been fixed, then $d({}_{u}G(I))$ denotes the diameter of the connected component of $G(I)$ containing $u$.

There are two basic facts about these sets that will prove useful in the sequel. Fix $u$ and form $X^i=X^i_G(u)$. First note that if $x \in X^i$ for $i \ge 1$, then $N(x) \cap X^{i-1}$ is nonempty since there is a path from $u$ to $x$ of length precisely $i$ by the definition of $X^i$. Also, if $u$ and $v$ are the endpoints of a path realizing the diameter, then $v \in X^d$ and if $y \in N(v)$, then $y$ is not a leaf. If $y$ were a leaf, $d(u,y)=d+1$, a contradiction.

The next lemma is well known, see, for example, [27], Lemma 2.2].

Lemma 2.3

Let $I$ be an ideal in a polynomial ring $R$, let $x$ be an indeterminate over $R$, and let $S=R[x]$. Then $\mathrm{{depth}}\,S/IS = \mathrm{{depth}}\,R/I +1$.

If $x_1$ is an isolated vertex of a graph $G$, define $R'=k[x_2, \ldots , x_n]$. Notice that all generators of $I=I(G)$ lie in $R'$, and so by abuse of notation we can consider an ideal $I'=IR'$ in the ring $R'$ generated by the edges of the graph $G$. Then, by Lemma 2.3, $\mathrm{{depth}}\,R/I = \mathrm{{depth}}\,R'/I' +1$. Thus we will assume that graphs are initially free of isolated vertices and that all variables of $R$ divide at least one generator of $I$.

Throughout the paper we will perform operations on ideals that correspond to the graph minors of contractions and deletions. A deletion minor is formed by removing a vertex $x$ from $G$ and deleting any edge of $G$ containing $x$. This corresponds to the ideal $(I,x)$, or more precisely the quotient ring $R/(I,x)$. This process can result in isolated vertices, which will increase the depth of the quotient ring as in Lemma 2.3. To provide clarity we will count isolated vertices separately and will require connected components of a graph to have at least two vertices. A contraction minor of $G$ is formed by removing redundancies from the set $\{e\setminus \{x\} \mid e \in E(G)\}$ to obtain the edge set of the contraction. Note that if $y$ is a neighbor of $x$ in $G$, it becomes an isolated vertex of the contraction as any other edge containing $y$ was removed as a redundancy. This corresponds to forming the ideal $(I:x)$. Note that $N(x) \subseteq (I:x)$, and so such an ideal may have variables as generators. However, if $K=(J,x_1)$ is a minimal generating set of an ideal, then $R/K \cong k[x_2, \ldots , x_n]/J$. Thus, we will refer to $K$ as an edge ideal if $J$ is an edge ideal.

For clarity and ease of reference, we now state several previously known results.

Lemma 2.4

Let $I$ be a monomial ideal in a polynomial ring $R$, and let $M$ be a monomial in $R$. If $y$ is a variable such that $y$ does not divide $M$ and $K$ is the extension in $R$ of the image of $I$ in $R/y$, then $((I:M),y)=((K:M),y)$.

Proof

See the proof of [18], Theorem 3.5]. $\square$

Lemma 2.5

[27], Lemma 2.10] Suppose $G$ is a graph, $I=I(G)$, $x$ is a leaf of $G$, and $y$ is the unique neighbor of $x$. Then $(I^t:xy)=I^{t-1}$ for any $t \ge 2$.

We conclude this section with an extension of the preceding lemma that will allow us to use any edge of the graph.

Lemma 2.6

Let $G$ be a graph, $I=I(G)$ and $\{x, y\}\in E(G)$. Then $(I^2:xy)=(I,E)$, where $E=<x_iy_j | x_i\in N(x),\, y_j\in N(y)>$. More generally, if $x_1 \cdots x_{2t}\in I^{t}$, then $(I^{t+1}:x_1 \cdots x_{2t})=(I,E)$, where $E$ is the ideal generated by all degree two monomials $y_1y_2$ supported on $\bigcup \limits _{i=1}^{2t} N(x_i)$ satisfying $y_1y_2x_1 \cdots x_{2t}\in I^{t+1}$.

Proof

Suppose first that $a$ is a minimal generator of $(I,E)$. If $a \in I$, then $a \in (I^{2}:xy)$ since $xy \in I$. Else $a=x_iy_j\in E$ and $axy=x_ixy_jy \in I^2$. Thus, $(I,E) \subseteq (I^2:xy)$.

Conversely, suppose $b\in (I^2:xy)$ but $b \not \in I$. Since $(I^2:xy)$ is a monomial ideal, we may assume that $b$ is a monomial. Then $bxy \in I^2$, so $bxy=e_1e_2h$, where $e_i$ are degree two monomials corresponding to edges of $G$. Since $b \not \in I$, $e_i$ does not divide $b$ for $i=1,2$, and so without loss of generality, $x$ divides $e_1$ and $y$ divides $e_2$. Thus, $e_1=xx_i$ and $e_2=yy_j$ for some $x_i\in N(x)$ and $y_j \in N(y)$. Thus, $x_iy_j$ divides $b$, and so $b \in E \subset (I,E)$.

The proof of the generalized statement follows the same outline. Note that the $x_i$ need not all be distinct. $\square$

Note that the ideal $(I,E)$ in Lemma 2.6 is no longer guaranteed to be square-free. If $z\in N(x) \cap N(y)$, then $z^2 \in E$. However, $(I,E)$ is still a monomial ideal, and if $z^2$ and $w^2$ are both generators of $E$, then $zw \in (I,E)$. This follows easily since $z\in N(x)$ and $w \in N(y)$.

3 The first power

As a first step toward determining the depths of $R/I^t$ for arbitrary graphs, a lower bound, similar to the one given in [27] for trees, is needed for $\mathrm{{depth}}\,R/I$. This lower bound is generally far from sharp; however, it is of a form that generalizes to higher powers. Alternate bounds for this depth, or equivalently for the projective dimension of $R/I$, exist in the literature [7–9, 21]. However, the focus here is on providing a bound that will serve as the basis for bounds on the depths of higher powers, using techniques that will extend to higher powers. We first present the main result of this section. An alternate proof has been communicated to us by Russ Woodroofe.

Theorem 3.1

Let $G$ be a connected graph and let $I=I(G)$. If there exist $u, v \in V(G)$ with $d(u,v)=d$, then $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{d+1}{3}} \right\rceil$.

Proof

We proceed by induction on $n$, the number of vertices. Notice that for any fixed $d$, we have that $n\ge d+1$. Since $\mathfrak {m}\not \in \mathrm{Ass}\,(R/I)$, then $\mathrm{{depth}}\,R/I \ge 1$. Note that if $d\le 2$, then $\left\lceil {\frac{d+1}{3}}\right\rceil =1$, and so the result holds. If $n=d+1$, the graph is a path, and thus the result holds by [27], Lemma 2.8]. Hence, we may assume that $n-1>d \ge 3$.

Let $X^{i}=X^i_G(u)$ be as in Notation 2.2 and let $w \in N(v) \cap X^{d-1}$. Consider first $(I:w)=(J,N(w))$, where $J$ is the ideal corresponding to the minor $G'$ of $G$ formed by deleting the variables in $N(w)$. Since $d\ge 3$, then $X_{G'}^{d-3}(u) \ne \emptyset$. Let $z\in X_{G'}^{d-3}(u)$, and notice that $d(u,z)=d-3$. Moreover, $w$ does not divide any generator of $(J,N(w))$. Thus, $(J,N(w)) \subset R'[N(w)]$, where $R'$ is the polynomial ring formed by deleting $w\cup N(w)$. Then we have

$$\begin{aligned} \mathrm{{depth}}\,R/(I:w)= & {} \mathrm{{depth}}\,R'[w,N(w)]/(J,N(w))\\= & {} \mathrm{{depth}}\,R'[w]/J =\mathrm{{depth}}\,R'/J+1 \\\ge & {} \left\lceil {\frac{d-3+1}{3}}\right\rceil +1 = \left\lceil {\frac{d+1}{3}}\right\rceil \end{aligned}$$

by induction on $n$.

Next we consider $(I,w)=(K,w)$, where $K$ is the ideal of the minor $G''$ of $G$ formed by deleting $w$. If $G''$ is connected, then $d(u,v)=d$ in $G''$, and therefore $\mathrm{{depth}}\,R/(I,w)=\mathrm{{depth}}\,R/(K,w) \ge \left\lceil {\frac{d+1}{3}}\right\rceil$ by induction on $n$. If $G''$ is not connected, then there is a vertex $z \in {}_{u}G''$ with $d(u,z) \ge d-2$ and $v \not \in {}_{u}G''$. If $v$ is an isolated vertex, then by Lemma 2.3 we obtain $\mathrm{{depth}}\,R/(K,w) \ge \left\lceil {\frac{d-2+1}{3}}\right\rceil +1 \ge \left\lceil {\frac{d+1}{3}}\right\rceil$. Otherwise, $v$ is in a connected component of $G''$ that has depth at least one, so by [36], Lemma 6.2.7], we have $\mathrm{{depth}}\,R/(K,w) \ge \left\lceil {\frac{d-2+1}{3}}\right\rceil +1 \ge \left\lceil {\frac{d+1}{3}}\right\rceil$. In either case, $\mathrm{{depth}}\,R/(I,w) \ge \left\lceil {\frac{d+1}{3}}\right\rceil$.

Applying the Depth Lemma [3], Proposition 1.2.9] to the short exact sequence

$$\begin{aligned} 0 \rightarrow R/(I:w) \rightarrow R/I \rightarrow R/(I,w) \rightarrow 0 \end{aligned}$$

yields $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{d+1}{3}}\right\rceil$, as desired. $\square$

By selecting a pair of vertices $u$ and $v$ whose distance is maximal, we immediately obtain the following corollary.

Corollary 3.2

Let $G$ be a connected graph of diameter $d\ge 1$ and let $I=I(G)$. Then $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{d+1}{3}} \right\rceil$.

As an immediate corollary we extend Theorem 3.1 to graphs that are not necessarily connected.

Corollary 3.3

Let $G$ be a graph with $p$ connected components, $I=I(G)$, and let $d_i$ be the diameter of the $i$th connected component. Then $\mathrm{{depth}}\,R/I\ge \sum \nolimits _{i=1}^{p}\left\lceil {\frac{d_i+1}{3}}\right\rceil$. In particular, $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{d+1}{3}}\right\rceil +p-1$.

Proof

This follows directly from Theorem 3.1 and [36], Lemma 6.2.7]. $\square$

The next corollary is an interesting result that follows from the proof of Theorem 3.1. Although the result could be used to prove the theorem above, it is difficult to obtain independently. However, it can be useful in bounding the depths of higher powers.

Corollary 3.4

Let $G$ be a graph, let $I=I(G)$, and fix $u \in V(G)$. Let $w\in X^{\ell }=X^{\ell }_G(u)$ for some $0\le \ell$. Then $\mathrm{{depth}}\,R/(I:w) \ge \left\lceil {\frac{\ell +2}{3}}\right\rceil$.

Proof

Let $w\in X^\ell$. Notice that $(I:w)=(J, N(w))$, where $J$ is the ideal corresponding to the minor $G'$ of $G$ formed by deleting the variables in $N(w)$. Let $R'$ be the polynomial ring formed by deleting $w$ and the variables in $N(w)$. As before we have

$$\begin{aligned} \mathrm{{depth}}\,R/(I:w)= & {} \mathrm{{depth}}\,R'[w,N(w)]/(J,N(w))\\= & {} \mathrm{{depth}}\,R'[w]/J =\mathrm{{depth}}\,R'/J+1. \end{aligned}$$

If $\ell <2$ the result holds since $\mathrm{{depth}}\,R/(I:w) \ge 1$. Hence, we may assume that $\ell \ge 2$. Since the diameter of $G'$ is at least $\ell -2$, applying Theorem 3.1 yields

$$\begin{aligned} \mathrm{{depth}}\,R'/J+1\ge \left\lceil {\frac{\ell -2+1}{3}}\right\rceil +1 =\left\lceil {\frac{\ell +2}{3}}\right\rceil \end{aligned}$$

and the result follows. $\square$

We conclude this section with an extension of Theorem 3.1 that gives a bound for the depth of the first power of the edge ideal of a graph with loops. This result is of independent interest.

Proposition 3.5

Let $G$ be a connected graph with loops and let $I=I(G)$. If there exists $u\in V(G)$ with $d(u,x) \ge \ell$ for all $x$ such that $\{x,x\} \in E(G)$, then $\mathrm{{depth}}\,R/I \ge \left\lceil {\frac{\ell -1}{3}} \right\rceil$.

Proof

Notice that if $\ell <2$ the result is trivial. Thus we assume that $\ell \ge 2$. We induct on the number of loops. Let $x$ be a variable corresponding to a vertex with a loop. Notice that $(I:x)=(I,N(x))=(J,N(x))$, where $J$ is the minor formed by deleting all vertices in $N(x)$. Since $x \in N(x)$, the number of loops of $G(J)$ is less than the number of loops of $G$. Notice that since all deleted vertices are at least distance $\ell -1$ from $u$, $d({}_{u}G(J)) \ge \ell -2$ and $d(u,z) \ge \ell$ for all loops $z$. If ${}_{u}G(J)$ has no loops, then $\mathrm{{depth}}\,R/(I:x) \ge \left\lceil {\frac{\ell -1}{3}} \right\rceil$, by Theorem 3.1 since $\left\lceil {\frac{d(G(J))+1}{3}} \right\rceil \ge \left\lceil {\frac{\ell -2+1}{3}} \right\rceil$. If ${}_{u}G(J)$ contains a loop $y$, then $d(u,y) \ge \ell$, and hence $\mathrm{{depth}}\,R/(I:x) \ge \left\lceil {\frac{\ell -1}{3}} \right\rceil$, by induction.

Now consider $(I,x)=(K,x)$, where $K$ is the minor formed by deleting $x$. Then, $d({}_{u}G(K)) \ge \ell -1$ and $G(K)$ has fewer loops than $G$, so $\mathrm{{depth}}\,R/(I,x) \ge \left\lceil {\frac{\ell -1}{3}} \right\rceil$, by either Theorem 3.1 or induction as above.

Applying the Depth Lemma [3], Proposition 1.2.9] to the short exact sequence

$$\begin{aligned} 0 \rightarrow R/(I:x) \rightarrow R/I \rightarrow R/(I,x) \rightarrow 0 \end{aligned}$$

completes the proof. $\square$

4 Depths of higher powers of edge ideals

Our main results in this section focus primarily on $I^2$ and $I^3$. Selected results are stated for all powers since our methods can extend to higher powers, particularly when one has some control over the structure of the underlying graph. The central idea of the proofs will be to apply the Depth Lemma [3], Proposition 1.2.9] to families of short exact sequences. We begin the section by introducing some notation.

We will frequently use deletion minors in the proofs, and often the minors will be formed using a collection of vertices. Let $G$ be a graph and let $I=I(G)$. For $a \in V(G)$ we let $I_a$ represent the edge ideal of the minor of $G$ formed by deleting $a$. We will refer to $I_a$ as a minor of $I$. Given a collection of vertices $y_1, \ldots , y_s$, define $I_0=I$ and for $1 \le i \le s$ define $I_i$ to be the minor of $I$ formed by deleting $y_1, \ldots , y_i$. Define $R_i$ to be the corresponding polynomial ring, namely $R_i=R/(y_1, \ldots , y_i)$.

Recall that an induced graph on a subset $\{x_1, \ldots , x_r\}$ of vertices of a graph $G$ is a graph $G'$ with $V(G')=\{x_1, \ldots , x_r\}$ and $E(G')=\{ \{x_{i},x_{j}\} \in E(G) \mid x_i, x_j \in V(G')\}$.

Lemma 4.1

Let $G$ be a graph, $V=V(G)$ and $I=I(G)$. Let $x_1,\ldots , x_r \in V$ be such that the induced graph on $x_1, \ldots , x_r$ is connected and fix a vertex $u$ in the connected component of $G$ containing $x_1, \ldots , x_r$. Let $\{y_1, \ldots ,y_s\} \subset \bigcup \limits _{i=1}^{r} N(x_i) \setminus \{x_1, \ldots ,x_r\}$. Then there exists an ordering of the vertices $y_1, \ldots ,y_s$ such that for all $i <s$, $x_1, \ldots , x_r \in {}_{u}G(I_i)$, where $I_i$ is obtained by deleting $y_1, \ldots , y_i$.

Proof

Using the fixed vertex $u$, form $X^i=X^i_G(u)$. Notice that $u$ may be one of the $y_i$. Since $x_1, \ldots ,x_r \in {}_{u}G$, then for each $i$, $x_i \in X^t$ for some $t$. Let $k$ be the least positive integer for which $x_i \in X^k$ for some $i$. Fix $x_q\in X^k$. Then there is a path from $u$ to $x_q$ containing precisely one vertex in $X^j$ for each $j \le k$. Since for every $i$, $y_i \in N(x_{\ell })$ for some $\ell$, then $y_i \in \bigcup \limits _{j=k-1}^d X^j$ for all $i$. Thus, at most one $y_i$ lies on the chosen path. We may reorder the variables so that $y_s$ is this vertex (if any). Then, for all $i<s$, there is a path in $I_i$ from $u$ to $x_q$ and there is a path from $x_q$ to $x_i$ for all other $i$, since the induced graph on $x_1, \ldots , x_r$ is connected. $\square$

Once we have ordered a collection of neighboring vertices as in Lemma 4.1, deleting the vertices in order will result in a series of graphs for which $u$ and $x_1 , \ldots , x_r$ are in the same connected component, followed by a graph for which $u$ and $x_i$ might be disconnected. When $r=1$ and $\{y_1, \ldots , y_s\} = N(x_1)$, deleting all vertices except $y_s$ will result in a graph for which $x_1$ is a leaf. The next lemma formalizes how this can be used to estimate depths. Although it will generally be used when $M=x_1$ is a single vertex or $M=x_1\cdots x_r$ is the product of connected vertices and $\{y_1, \ldots , y_s\}=N(x_r)\setminus \{x_1, \ldots ,x_{r-1}\}$, the result holds in the more general situation described here.

Lemma 4.2

Let $R$ be a polynomial ring over a field, $I$ an ideal, and let $M$ be a monomial in $R$. Let $\{y_1, \ldots , y_s\}$ be variables such that for all $i$, $y_i$ does not divide $M$. Let $a, b$ be two nonnegative integers. If $\mathrm{{depth}}\,R_{i-1}/(I_{i-1}^t:My_{i}) \ge a$ for all $i\ge 1$ and $\mathrm{{depth}}\,R_s/(I_s^t:M) \ge b$, then $\mathrm{{depth}}\,R_i/(I_i^t:M) \ge \min \{a,b\}$ for each $i\ge 0$. In particular, $\mathrm{{depth}}\,R/(I^t:M) \ge \min \{a, b\}$.

Proof

Consider the family of short exact sequences

$$\begin{aligned} 0\rightarrow & {} R/\left( I^t:My_1\right) \rightarrow R/\left( I^t:M\right) \rightarrow R/\left( \left( I^t:M\right) ,y_1\right) \rightarrow 0 \\ 0\rightarrow & {} R_1/\left( I_1^t:My_2\right) \rightarrow R_1/\left( I_1^t:M\right) \rightarrow R_1/\left( \left( I_1^t:M\right) ,y_2\right) \rightarrow 0 \\ 0\rightarrow & {} R_2/\left( I_2^t:My_3\right) \rightarrow R_2/\left( I_2^t:M\right) \rightarrow R_2/\left( \left( I_2^t:M\right) ,y_3\right) \rightarrow 0 \\&\vdots&\\ 0\rightarrow & {} R_{s-1}/\left( I_{s-1}^t:My_s\right) \rightarrow R_{s-1}/\left( I_{s-1}^t:M\right) \rightarrow R_{s-1}/\left( \left( I_{s-1}^t:M\right) ,y_s\right) \rightarrow 0. \end{aligned}$$

Notice that by Lemma 2.4 the right hand term of sequence $i$ is isomorphic to $R_i/(I_i^t:M)$, which is the center term of sequence $i+1$. Now $\mathrm{{depth}}\,R_i/(I_i^t:My_i) \ge a$ by hypothesis and $R_{s-1}/((I_{s-1}^t:M),y_s) \cong R_s/(I_s^t :M)$, so by hypothesis, $\mathrm{{depth}}\,R_{s-1}/((I_{s-1}^t:M),y_s) \ge b$. By applying the Depth Lemma [3], Proposition 1.2.9] repeatedly starting with the final sequence and working our way up we see that $\mathrm{{depth}}\,R_i/(I_i^t:M) \ge \min \{a,b\}$ for each $i$ from $i=s-1$ to $i=0$. Since $\mathrm{{depth}}\,R_s/(I_s^t:M) \ge b$, the result holds for all $i$. $\square$

We now give a first estimate on the depth of any power of an edge ideal in terms of the number of connected components of the graph. Recall that we have defined connected components to have at least two vertices. In Corollary 3.3 we were able to achieve a better bound for the first power and later in this section we will improve this bound for the second and third powers; however, the advantage of considering this bound is that it is a bound for all the powers even though it might not be sharp.

Proposition 4.3

Let $G$ be a graph with $p$ connected components and let $I=I(G)$. Then, for every $t\ge 1$

$$\begin{aligned} \mathrm{{depth}}\,R/I^t \ge p-t. \end{aligned}$$

Proof

We prove this by induction on $p$, the case of $p=1$ being clear. Suppose that $p\ge 2$ and $I=(J,K)$, where $J \subset A=k[x_1, \ldots , x_r]$ is the edge ideal of the graph consisting of all but one of the connected components of $G$ and $K \subset B=k[x_{r+1}, \ldots , x_n]$ is the edge ideal of the remaining connected component of $G$. Then, $\mathrm{{depth}}\,A/J \ge p-1$ and $\mathrm{{depth}}\,B/K \ge 1$ by Corollary 3.3. By induction on $p$ we have $\mathrm{{depth}}\,A/J^s \ge p-1-s$ for all $s\ge 1$. In particular, $\mathrm{{depth}}\,A/J^{t-i} \ge p-1-(t-i)=p-t+i-1$ for $1 \le i \le t-2$ and $\mathrm{{depth}}\,A/J^{t-j+1} \ge p-1-(t-j+1)=p-t+j-2$ for all $1\le j \le t$. Then, by [22], Theorem 2.4] we have

$$\begin{aligned} \mathrm{{depth}}\,R/I^t\ge & {} \min _{\begin{array}{l}{i \in [1,t-1]}\\ {j\in [1,t]}\end{array}} \{ \mathrm{{depth}}\,A/J^{t-i}+\mathrm{{depth}}\,B/K^i+1,\\&\mathrm{{depth}}\,A/J^{t-j+1} +\,\mathrm{{depth}}\,B/K^{j}\}\\= & {} \min _{\begin{array}{l}{i \in [1,t-2]}\\ {j\in [2,t]}\end{array}}\{ \mathrm{{depth}}\,A/J^{t-i}+\mathrm{{depth}}\,B/K^i+1, \\&\mathrm{{depth}}\,A/J +\,\mathrm{{depth}}\,B/K^{t-1}+1, \mathrm{{depth}}\,A/J^{t}+\mathrm{{depth}}\,B/K,\\&\mathrm{{depth}}\,A/J^{t-j+1} +\,\mathrm{{depth}}\,B/K^{j}\} \\= & {} \min _{\begin{array}{l}{i \in [1,t-2]}\\ {j\in [2,t]}\end{array}} \{p-t+i-1+0+1, p-1+0+1,\\&p-t-1+1, p-t+j-2+0 \}\\= & {} \min _{\begin{array}{l}{i \in [1,t-2]}\\ {j\in [2,t]}\end{array}} \{p-t+i, p, p-t, p-t+j-2 \}=p-t. \end{aligned}$$

$\square$

The next theorem establishes a sharper lower bound for the depth of the second power of an edge ideal.

Theorem 4.4

Let $G$ be a graph with $p$ connected components, $I=I(G)$, and let $d=d(G)$ be the diameter of $G$. Then

$$\begin{aligned} \mathrm{{depth}}\,R/I^2 \ge \left\lceil {\frac{d-3}{3}}\right\rceil +p-1. \end{aligned}$$

Proof

We proceed by induction on $n$, the number of vertices in $G$. Suppose $n\le 4$. Then $d \le 3$ and $p \le 2$ since the number of connected components does not include isolated vertices. If $p=1$ the bound is trivial. If $p=2$, for $n\le 4$ the graph must be a forest consisting of two disconnected edges and the result follows from [27], Theorem 3.4]. Note that in general, if $p \ge 2$, then $\mathrm{{depth}}\,R/I^2 \ge 1$ by [6], Lemma 2.1].

We may now assume that $n\ge 5$. Let $u,v$ be the endpoints of a path that realizes the diameter and let $X^i=X^i_G(u)$. Let $w \in N(v)$ and let $\{y_1, \ldots , y_s\}=N(w)$ be ordered as in Lemma 4.1 so that $d(u,w)$ is finite in $I_i$ for $i<s$. Recall that $I_0=I$. Then, for each $1 \le i \le s$ we have $(I_{i-1}^2:wy_i)=(I_{i-1},E_{i-1})$, where $E_{i-1}$ is as in Lemma 2.6. Now $(I_{i-1},E_{i-1})$ is the edge ideal of a graph $G'$, possibly with loops, of diameter at least $d-1$ since $d(u,w) \ge d-1$ even with the additional edges. Thus, if $(I_{i-1},E_{i-1})$ is square-free, $\mathrm{{depth}}\,R_{i-1}/(I_{i-1},E_{i-1})\ge \lceil {\frac{d(G')+1}{3}}\rceil +p-1\ge \lceil {\frac{d-1+1}{3}}\rceil +p-1$ by Corollary 3.3. If $(I_{i-1},E_{i-1})$ is not square-free, then there exists $x\in V(G)$ such that $x^2 \in E_{i-1}$. Now $x\in N(w)$, and so $d(u,x) \ge d-2$. Note that each connected component of $G((I_{i-1},E_{i-1}))$ other than ${}_{u}G((I_{i-1},E_{i-1}))$ will be square-free and so have depth at least one. Thus, combining [36], Lemma 6.2.7] with Proposition 3.5 yields $\mathrm{{depth}}\,R_{i-1}/(I_{i-1},E_{i-1}) \ge \lceil {\frac{d-2-1}{3}}\rceil +p-1$ for $i \le s$.

Now $w$ is isolated in $I_s$, so $(I_s^2:w)=I_s^2$ and $w$ is a free variable in $R_s/I_s^2$. Since $d({}_{u}G(I_s)) \ge d-3$, then by induction and Lemma 2.3 we have $\mathrm{{depth}}\,R_s/(I_s^2:w) \ge \lceil {\frac{d({}_{u}G(I_s))-3}{3}}\rceil +p-1+1\ge \lceil {\frac{d-3}{3}}\rceil +p-1$. Hence, by Lemma 4.2 we obtain $\mathrm{{depth}}\,R/(I^2:w) \ge \lceil {\frac{d-3}{3}}\rceil +p-1$.

Finally, consider $(I^2,w)=(I_w^2,w)$. If $v \in {}_{u}G(I_w)$, then $d({}_{u}G(I_w)) \ge d$ and $\mathrm{{depth}}\,R/(I^2,w) =\mathrm{{depth}}\,R_w/I_w^2 \ge \lceil {\frac{d-3}{3}}\rceil +p-1$ by induction on $n$. Otherwise, $d( {}_{u}G(I_w)) \ge d-2$ and $G(I_w)$ contains an additional connected component or an isolated vertex, so

$$\begin{aligned} \mathrm{{depth}}\,R/\left( I^2,w\right)= & {} \mathrm{{depth}}\,R/\left( I_w^2,w\right) \\\ge & {} \left\lceil {\frac{d-2-3}{3}}\right\rceil +(p+1)-1 = \left\lceil {\frac{d-2}{3}}\right\rceil +p-1. \end{aligned}$$

By applying the Depth Lemma [3], Proposition 1.2.9] to the following exact sequence

$$\begin{aligned} 0 \rightarrow R/\left( I^2:w\right) \rightarrow R/I^2 \rightarrow R/\left( I^2,w\right) \rightarrow 0 \end{aligned}$$

we see that $\mathrm{{depth}}\,R/I^2\ge \left\lceil {\frac{d-3}{3}}\right\rceil +p-1$ as desired. $\square$

Remark 4.5

Notice that in the proof of Theorem 4.4 we required that $u$ and $v$ be endpoints of a path that realizes the diameter. This was done in order to obtain the best possible lower bound for the depth of $R/I^2$. However, one may take $u$ and $v$ to be endpoints of any path of length $\ell =d(u,v)$. Then, continuing as in the proof of Theorem 4.4, we would obtain that $\mathrm{{depth}}\,R/I^2\ge \left\lceil {\frac{\ell -3}{3}}\right\rceil +p-1$. Although this is a weaker lower bound, it can be useful in a more general setting.

As with the proof of Theorem 3.1 the proof of Theorem 4.4 yields the following interesting corollary.

Corollary 4.6

Let $G$ be a graph and let $I=I(G)$. Fix $u \in V(G)$ and let $w \in X^{\ell }=X_G^{\ell }(u)$ for some $0 \le \ell$. Then $\mathrm{{depth}}\,R/(I^2:w) \ge \left\lceil {\frac{\ell -2}{3}} \right\rceil$.

Proof

First notice that when $\ell <2$ there is nothing to show. Hence, we may assume that $\ell \ge 2$. Let $\{y_1, \ldots , y_s \}= N(w)$ be ordered as in Lemma 4.1. As in the proof of Theorem 4.4, for each $1 \le i \le s$ we have $(I_{i-1}^2:wy_i)=(I_{i-1},E_{i-1})$ as in Lemma 2.6 and $(I_{i-1},E_{i-1})$ is the edge ideal of a graph of diameter at least $\ell$ since $d(u,w) =\ell$. Thus, if $(I_{i-1},E_{i-1})$ is square-free, $\mathrm{{depth}}\,R_{i-1}/(I_{i-1},E_{i-1})\ge \lceil {\frac{\ell +1}{3}}\rceil +p-1$ by Corollary 3.3. If $x^2 \in E_{i-1}$, then $d(u,x) \ge \ell -1$ so combining [36], Lemma 6.2.7] with Proposition 3.5 yields $\mathrm{{depth}}\,R_{i-1}/(I_{i-1},E_{i-1}) \ge \lceil {\frac{\ell -2}{3}}\rceil$ for $i \le s$.

Now $w$ is isolated in $I_s$, and $d({}_{u}G(I_s)) \ge \ell -2$, so by Lemma 2.3 and Theorem 4.4

$$\begin{aligned} \mathrm{{depth}}\,R_s/(I_s^2:w) = \mathrm{{depth}}\,R_s/I_s^2+1 \ge \left\lceil {\frac{\ell -2-3}{3}}\right\rceil +1 = \left\lceil {\frac{\ell -2}{3}}\right\rceil . \end{aligned}$$

Hence, by Lemma 4.2 we have $\mathrm{{depth}}\,R/(I^2:w) \ge \left\lceil {\frac{\ell -2}{3}}\right\rceil$. $\square$

When exhausting the neighbors as in Lemma 4.2, we might end up with disconnected graphs. If the vertex $w$ is not in the connected component containing $u$ and thus is not in $X^i$ for any $i$, the bound above needs to be modified, but can still be found using only the diameter of ${}_{u}G(I)$.

Lemma 4.7

Let $G$ be a graph and let $I=I(G)$. Fix $u \in V(G)$ and let $w \in V(G)$ be such that $w\not \in {}_{u}G$. Then $\mathrm{{depth}}\,R/(I^2:w) \ge \left\lceil {\frac{\ell }{3}} \right\rceil$, where $\ell =d({}_{u}G)$.

Proof

Suppose $I=(J,K)$, where $K=I(_wG)$. Let $\{z_1, \ldots ,z_s\}$ be the neighbors of $w$ ordered as in Lemma 4.1. Note that $I_{i}=(J_i,K_i)$ and $J_i=J$ for all $i$. As in Lemma 2.6, we have $(I_{i-1}^2:wz_i)=(I_{i-1},E_{i-1})$, where all the edges in $E_{i-1}$ have endpoints in $V(_wG)$. Recall that $R_{i-1}$ is the polynomial ring corresponding to $I_{i-1}$ and let $R_{i-1}'$ be the polynomial ring with variables corresponding to $V(G(J_{i-1}))$. Then $\mathrm{{depth}}\,R_{i-1}/(I_{i-1},E_{i-1}) \ge \mathrm{{depth}}\,R'_{i-1}/J_{i-1} \ge \left\lceil {\frac{\ell +1}{3}} \right\rceil$, by [36], Lemma 6.2.7] and Theorem 3.1. Finally, $w$ is an isolated vertex in $I_s$, so $(I_s^2:w)=I_s^2$ and $w$ is a free variable. Thus, $\mathrm{{depth}}\,R_s/(I_s^2:w)\ge \mathrm{{depth}}\,R_s/I_s^2+1\ge \left\lceil {\frac{\ell -3}{3}} \right\rceil +1 = \left\lceil {\frac{\ell }{3}} \right\rceil$. The result then follows from Lemma 4.2. $\square$

The lower bound for the depth of the first power of edge ideals that we obtained in Theorem 3.1 is realized by edge ideals of paths, as was shown in [27], Lemma 2.8]. Therefore, one cannot hope for any improvement of this bound for a general graph in terms of the invariants used. However, the lower bound for the depth of higher powers of edge ideals of paths given in [27], Proposition 3.2] is too high for general graphs. The next example shows that the bound we established in Theorem 4.4 is indeed attained, thus establishing that one cannot improve this bound in terms of the invariants used.

Example 4.8

Let $R=k[x_1, \ldots , x_{5}]$ and let $I$ be the edge ideal of the graph $G$ below

Then $d(G)=3$ and using Macaulay 2 [17] we have that $\mathrm{{depth}}\,R/I^2 =\lceil {\frac{d-3}{3}}\rceil =0$, which also follows from [6], Theorem 3.3]. Therefore, the bound in Theorem 4.4 is sharp.

We now prove a series of lemmas that will allow us to establish a bound for the depth of the third power. Where possible, we give a general statement that holds for all powers. The first lemma is an extension of Lemma 2.6.

Lemma 4.9

Let $G$ be a graph and let $I=I(G)$. Let $t \ge 1$ be an integer and let $u, x_1, \ldots , x_{2t} \in V(G)$ with $x_1\cdots x_{2t} \in I^t$. If for some $0 \le \ell \le d$ we have $x_i \in \bigcup \limits _{j=\ell }^d X^j$ for all $i$, where $X^j=X^j_G(u)$, then $\mathrm{{depth}}\,R/(I^{t+1}:x_1\cdots x_{2t}) \ge \left\lceil {\frac{\ell -2}{3}} \right\rceil$.

Proof

Notice that $(I^{t+1}:x_1\cdots x_{2t})=(I,E)$, where $E$ is the ideal generated by all degree two monomials $y_1y_2$ supported on $\bigcup \limits _{i=1}^{2t} N(x_i)$ satisfying $y_1y_2x_1\cdots x_{2t}\in I^{t+1}$ by Lemma 2.6. Let $G'$ be the graph, possibly with loops, associated with $(I,E)$. Notice that $X^i_G(u)=X^i_{G'}(u)$ for $i \le \ell -2$ since both endpoints of any generator of $E$ lie in $\bigcup \limits _{i=\ell -1}^d X^i_G$. This also implies that all loops of $G'$ are contained in $\bigcup \limits _{i=\ell -1}^d X^i_G$. So by Proposition 3.5 we have $\mathrm{{depth}}\,R/(I,E) \ge \left\lceil {\frac{\ell -2}{3}} \right\rceil$. $\square$

The general outline of the following lemmas is at each stage to reduce by one the number of variables with which a colon ideal is formed. In general, this is accomplished using Lemma 4.2; however, one must first deal with the situation where there are no neighbors to exhaust. This occurs when the graph is disconnected and one component consists of the induced graph on the variables used to form the colon ideal. In examining the later proofs in which the result is used, one sees that the goal is to create a path of vertices. The difficult case will be when the induced graph on the vertices of the path does not contain a leaf. Thus, we assume in the next lemma that the graph contains a Hamiltonian cycle, that is, a cycle that passes through each vertex precisely once. To simplify notation, we will at times use ${\underline{x}}$ in place of $x_1, \ldots ,x_n$ when the number of variables used is clear.

Lemma 4.10

Let $G$ be a disconnected graph and let $I=I(G)$. Suppose $I=(J,K)$, where $J\subset k[x_1, \ldots ,x_n]$, $K \subset k[y_1, \ldots , y_{2t-1}]$, and $G(K)$ contains a Hamiltonian cycle. Then $\mathrm{{depth}}\,R/(I^{t+1}:y_1y_2\cdots y_{2t-1}) \ge \left\lceil {\frac{d(J)-3}{3}} \right\rceil$, where $d(J)=d(G(J))$ and $R=k[{\underline{x}},{\underline{y}}]$.

Proof

Let $M=\prod _{i=1}^{2t-1}y_i$ and consider the family of short exact sequences

$$\begin{aligned} 0\rightarrow & {} R/(I^{t+1}:My_1) \rightarrow R/(I^{t+1}:M) \rightarrow R/((I^{t+1}:M),y_1) \rightarrow 0 \\ 0\rightarrow & {} R/(((I^{t+1}:M),y_1):y_2) \rightarrow R/((I^{t+1}:M),y_1) \rightarrow R/((I^{t+1}:M),y_1,y_2) \rightarrow 0 \\&\vdots&\\ 0\rightarrow & {} R/(((I^{t+1}:M),{\underline{y}}'):y_{2t-1}) \rightarrow R/((I^{t+1}:M),{\underline{y}}') \rightarrow R/((I^{t+1}:M),{\underline{y}}) \rightarrow 0, \end{aligned}$$

where ${\underline{y}}'=\{y_1, \ldots , y_{2t-2}\}$.

We first handle the left hand term of each sequence by showing that for each $0 \le i \le 2t-2$, $(((I^{t+1}:M),y_1,\ldots , y_{i}):y_{i+1})=(J,K_i)$ for some ideal $K_i$ of $k[y_1, \ldots , y_{2t-1}]$. Here, we define $(((I^{t+1}:M),y_0):y_{1})=(I^{t+1}:My_1)$ since there is no element $y_0$. By Lemma 2.4 and some straight forward computations we have $(((I^{t+1}:M),y_1, \ldots , y_i):y_{i+1})=((I^{t+1}:My_{i+1}),y_1, \ldots , y_i)$. Now since $M$ is a product of $2t-1$ variables that form a cycle and $y_{i+1}$ is an element of the cycle, $My_{i+1} \in I^t$ for each $i$. Thus, by Lemma 2.6, $((I^{t+1}:My_{i+1}),y_1, \ldots , y_i)=(I,E_i, y_1, \ldots , y_i)$, where $E_i$ is the ideal generated by all degree two monomials $y_{i_1}y_{i_2}$ supported on $\bigcup \limits _{i=1}^{2t-1} N(y_i)$ satisfying $y_{i_1}y_{i_2}My_{i+1}\in I^{t+1}$. Now $M=\prod _{i=1}^{2t-1}y_i$ and $N(y_i) \subset k[y_1, \ldots , y_{2t-1}]$ for each $i$, so $(I,E_i,y_1, \ldots , y_i)=(J,K_i)$ where $K_i \subset k[y_1, \ldots , y_{2t-1}]$. Thus, by [36], Lemma 6.2.7] and Theorem 3.1,

$$\begin{aligned} \mathrm{{depth}}\,R/((I^{t+1}:M),y_1,\ldots , y_{i}):y_{i+1})= & {} \mathrm{{depth}}\,k[{\underline{x}}]/J + \mathrm{{depth}}\,k[{\underline{y}}]/K_i \\\ge & {} \mathrm{{depth}}\,k[{\underline{x}}]/J \ge \left\lceil {\frac{d(J)-3}{3}} \right\rceil . \end{aligned}$$

Now we claim $((I^{t+1}:M),y_1,\ldots , y_{2t-1})=(J^2,y_1 \ldots , y_{2t-1})$. Since $M\in I^{t-1}$, one inclusion is clear. Suppose $aM\in I^{t+1}$ for some monomial $a \not \in J^2$. Then, $aM= e_1 \cdots e_{2t+1} h$ for some monomial $h$ and some edges $e_i$. Note that if $e_i \in k[{\underline{x}}]$, then $e_i \mid a$ since $M \in k[{\underline{y}}]$. Since $a\not \in J^2$, at most one edge $e_i$ is in $k[{\underline{x}}]$. Thus, the ${\underline{y}}$-degree of $e_1 \cdots e_{2t+1} h$ is at least $2t$, but the degree of $M$ is $2t-1$, and hence, $y_i \mid a$ for some $i$. Thus, $(I^{t+1}:M) \subseteq (J^2, y_1, \ldots , y_{2t-1})$ and the second inclusion follows. Thus,

$$\begin{aligned} \mathrm{{depth}}\,R/((I^{t+1}:M),y_1,\ldots , y_{2t-1})= & {} \mathrm{{depth}}\,R(J^2, y_1, \ldots , y_{2t-1}) \\= & {} \mathrm{{depth}}\,k[{\underline{x}}]/J^2 \ge \left\lceil {\frac{d(J)-3}{3}} \right\rceil \end{aligned}$$

by Theorem 4.4. The result now follows from repeated applications of the Depth Lemma [3], Proposition 1.2.9]. $\square$

We now return to our computations concerning the depths of various ideals involving the third power of an edge ideal.

Lemma 4.11

Let $G$ be a graph and let $I=I(G)$. Let $u, x_1,x_2,x_3 \in V(G)$ and suppose that that $x_1,x_3 \in N(x_2)$ and $x_1,x_2,x_3 \in \bigcup \limits _{i=\ell }^dX^i$, where $X^i=X^i_G(u)$ for some $0\le \ell \le d$. Then $\mathrm{{depth}}\,R/(I^3:x_1x_2x_3)\ge \left\lceil {\frac{\ell -5}{3}}\right\rceil$.

Proof

We may assume that $\ell \ge 6$ since otherwise the bound is trivial. First suppose $x_3$ is a leaf. Then, $(I^3:x_1x_2x_3)=(I^2:x_1)$ and by Corollary 4.6 we have $\mathrm{{depth}}\,R/(I^3:x_1x_2x_3)=\mathrm{{depth}}\,R/(I^2:x_1) \ge \left\lceil {\frac{\ell -2}{3}}\right\rceil$.

Suppose $x_3$ is not a leaf. We consider two cases. If $x_1x_3$ is a generator of $I$, let $\{z_1, \ldots , z_s\}=N(x_1)\cup N(x_2) \cup N(x_3) \setminus \{x_1,x_2,x_3\}$. If $x_1x_3$ is not a generator of $I$, let $\{z_1, \ldots , z_s\}=N(x_3)\setminus \{x_2\}$. In either case, order the vertices $z_1, \ldots , z_s$ as in Lemma 4.1. Then, by considering ${}_{u}G(I_{i-1})$, we have $\mathrm{{depth}}\,R_{i-1}/(I_{i-1}^3:x_1x_2x_3z_i) \ge \left\lceil {\frac{\ell -3}{3}}\right\rceil$ by Lemma 4.9 since $z_i \in \bigcup \limits _{i=\ell -1}^dX^i$. If $x_1x_3 \in I$, then $x_1,x_2,x_3$ forms a Hamiltonian cycle of a component that is disconnected from ${}_{u}G(I_s)$, so by Lemma 4.10 we have that $\mathrm{{depth}}\,R_s/(I_s^3:x_1x_2x_3) \ge \left\lceil {\frac{d(I_s)-3}{3}}\right\rceil \ge \left\lceil {\frac{\ell -5}{3}}\right\rceil$, since $d({}_{u}G(I_s)) \ge \ell -2$. When $x_1x_3 \not \in I$, then $x_3$ is a leaf in $I_s$, so as above, $(I_s^3:x_1x_2x_3)=(I_s^2:x_1)$. If $I_s$ is disconnected, then $d({}_{u}G(I_s))\ge \ell -2$. Thus, by Lemma 4.7, or Corollary 4.6, when ${}_{u}G(I_{s})$ is connected, we obtain $\mathrm{{depth}}\,R_s/(I_s^3:x_1x_2x_3)\ge \left\lceil {\frac{\ell -2}{3}}\right\rceil$. In either case, applying Lemma 4.2 yields $\mathrm{{depth}}\,R/(I^3:x_1x_2x_3)\ge \left\lceil {\frac{\ell -5}{3}}\right\rceil$. $\square$

Lemma 4.12

Let $G$ be a graph and let $I=I(G)$. Fix $u \in V(G)$ and suppose that $xy \in E(G)$ with $x \in X^{\ell }$, where $X^{\ell }=X_G^{\ell }(u)$ for some $0 \le \ell \le d$. Then $\mathrm{{depth}}\,R/(I^3:xy) \ge \left\lceil {\frac{\ell -6}{3}}\right\rceil$.

Proof

We may assume that $\ell \ge 7$ since otherwise the bound is trivial. First suppose either $x$ or $y$ is a leaf of $G$. Then, by Lemma 2.5 we have that $(I^3:xy)=I^2$ and by Theorem 4.4, we obtain $\mathrm{{depth}}\,R/(I^3:xy)\ge \left\lceil {\frac{d(I)-3}{3}}\right\rceil +p(I)-1$. Since $d(I) \ge \ell$, the result follows.

Next we assume that neither $x$ nor $y$ is a leaf of $G$. Let $\{z_1, \ldots ,z_s\}=N(x)\setminus \{y\}$ be ordered as in Lemma 4.1. Then $\mathrm{{depth}}\,R_{i-1}/(I_{i-1}^3:xyz_i)\ge \left\lceil {\frac{\ell -6}{3}}\right\rceil$, by Lemma 4.11 since $x,y,z_i \in \bigcup \limits _{j=\ell -1}^d X^j$. Now $x$ is a leaf of $I_s$, so $I_s^3:xy=I_s^2$, by Lemma 2.5. Let $d(I_s)=d({}_{u}G(I_s))$. Then, since $z_i \in \bigcup \limits _{j=\ell -1}^dX^{j}$, we have $d(I_s) \ge \ell -2$. Thus $\mathrm{{depth}}\,R_{s}/(I_s^3:xy) = \mathrm{{depth}}\,R_s/I_s^2 \ge \left\lceil {\frac{\ell -5}{3}}\right\rceil$ by Theorem 4.4. Hence, by Lemma 4.2 we have $\mathrm{{depth}}\,R/(I^3:xy) \ge \left\lceil {\frac{\ell -6}{3}}\right\rceil$. $\square$

We are now ready to establish a bound for the depth of the third power of any edge ideal.

Theorem 4.13

Let $G$ be a graph with $p$ connected components, $I=I(G)$, and let $d=d(G)$ be the diameter of $G$. Then $\mathrm{{depth}}\,R/I^3 \ge \left\lceil {\frac{d-7}{3}} \right\rceil +p-1$.

Proof

We proceed by induction on $n$, the number of vertices. We first handle the case when $n\le 8$, in which case $d\le 7$ and $p\le 4$. When $p=4$, the result follows from Proposition 4.3 or from [27], Theorem 3.4]. By [6], Lemma 2.1] we know $\mathrm{{depth}}\,(R/I^t) \ge 1$ for all $t\le p$, so the result holds for $p=3$. If $p=1$, or $p=2$ and $d \le 4$, the bound is trivial. If $p=2$ and $d=5$, then the graph must consist of two disconnected paths, so the result follows from [27], Theorem 3.4]. Thus, we may assume that $n \ge 9$.

Let $u,v$ be the endpoints of a path that realizes the diameter of $G$ and let $X^i$ be as in Notation 2.2. Let $w \in N(v) \cap X^{d-1}$.

Notice that $(I^3,w)=(J^3,w)$, where $J$ is the minor of $I$ formed by deleting $w$. We have two cases to consider. If $u$ and $v$ are in the same connected component of $J$, then $d(J) \ge d$ and $p(J)\ge p$, where $p(J)$ is the number of connected components of the graph associated with $J$. Hence, by induction on $n$ we have

$$\begin{aligned} \mathrm{{depth}}\,R/(I^3,w) \ge \left\lceil {\frac{d(J)-7}{3}} \right\rceil +p(J)-1 \ge \left\lceil {\frac{d-7}{3}} \right\rceil +p-1. \end{aligned}$$

If $u$ and $v$ are not connected in $J$, then $d(J) \ge d({}_{u}G(J)) \ge d-2$ and $p(J) \ge p+1$, or if $v$ is isolated, Lemma 2.3 applies. Hence, again by induction on $n$ we have

$$\begin{aligned} \mathrm{{depth}}\,R/(I^3,w)\ge & {} \left\lceil {\frac{d(J)-7}{3}}\right\rceil +p+1-1\ge \left\lceil {\frac{d-9}{3}}\right\rceil +p+1-1 \\\ge & {} \left\lceil {\frac{d-7}{3}}\right\rceil +p-1. \end{aligned}$$

Let $\{z_1, \ldots ,z_s\}=N(w)$ be ordered as in Lemma 4.1. Since $w \in X^{d-1}$, then $\mathrm{{depth}}\,R_{i-1}/(I_{i-1}^3:wz_i)\ge \left\lceil {\frac{d-7}{3}}\right\rceil$, by Lemma 4.12.

Now $w$ is isolated in $I_{s}$, and thus, $(I_s^3:w)=I_s^3$. Therefore, by induction on $n$ we have that

$$\begin{aligned} \mathrm{{depth}}\,R_s/(I_s^3:w)= & {} \mathrm{{depth}}\,R_s/I_s^3 \ge \left\lceil {\frac{d(I_s)-7}{3}}\right\rceil +p(I_s)-1+1\\\ge & {} \left\lceil {\frac{d-3-7}{3}}\right\rceil +p-1+1 = \left\lceil {\frac{d-7}{3}}\right\rceil +p-1,\\ \end{aligned}$$

since $d(I_s) \ge d({}_{u}G(I_s)) \ge d-3$ and $w$ is an isolated vertex. Hence, by Lemma 4.2 we have that $\mathrm{{depth}}\,R/(I^3:w) \ge \left\lceil {\frac{d-7}{3}}\right\rceil +p-1$.

By applying the Depth Lemma [3], Proposition 1.2.9] to the following exact sequence

$$\begin{aligned} 0 \rightarrow R/(I^3:w) \rightarrow R/I^3 \rightarrow R/(I^3, w) \rightarrow 0 \end{aligned}$$

we have that $\mathrm{{depth}}\,R/I^3 \ge \left\lceil {\frac{d-7}{3}} \right\rceil +p-1$. $\square$

As in Remark 4.5 one may take $u$ and $v$ in the proof of Theorem 4.13 to be endpoints of a path of length $\ell =d(u,v)$ and obtain $\mathrm{{depth}}\,R/I^3 \ge \left\lceil {\frac{\ell -7}{3}} \right\rceil +p-1$. The next corollary follows from the proof of Theorem 4.13.

Corollary 4.14

Let $G$ be a graph and let $I=I(G)$. Fix $u \in V(G)$ and let $w \in X^{\ell }$ for some $0 \le \ell$, where $X^i=X^i_G(u)$. Then $\mathrm{{depth}}\,R/(I^3:w) \ge \left\lceil {\frac{\ell -6}{3}}\right\rceil$.

Proof

We may assume that $\ell \ge 7$ since otherwise the bound is trivial. Let $\{z_1, \ldots ,z_s\}=N(w)$ be ordered as in Lemma 4.1. By Lemma 4.12 we have $\mathrm{{depth}}\,R_{i-1}/(I_{i-1}^3:wz_i)\ge \left\lceil {\frac{\ell -6}{3}}\right\rceil$.

Now $w$ is isolated in $I_{s}$, and thus $(I_s^3:w)=I_s^3$ and $d(I_s) \ge \ell -2$. Therefore, by Theorem 4.13, we obtain

$$\begin{aligned} \mathrm{{depth}}\,R_s/(I_s^3:w)\ge \left\lceil {\frac{d(I_s) -7}{3}}\right\rceil +1 \ge \left\lceil {\frac{\ell -9}{3}}\right\rceil +1 = \left\lceil {\frac{\ell -6}{3}}\right\rceil . \end{aligned}$$

Hence, by Lemma 4.2, the result follows. $\square$

The next example shows that the bound for the depth of the third power of an edge ideal given in Theorem 4.13 is attained. This example extends naturally, which suggests a lower bound for the depth of any power.

Example 4.15

Let $R=k[x_1, \ldots , x_{10}]$ and let $I$ be the edge ideal of the graph $G$ below

Then $d(G)=7$ and using Macaulay 2 [17] we have that $\mathrm{{depth}}\,R/I= \lceil {\frac{d+1}{3}}\rceil =2$, $\mathrm{{depth}}\,R/I^2= \lceil {\frac{d-3}{3}}\rceil =1$, and $\mathrm{{depth}}\,R/I^3= \lceil {\frac{d-7}{3}}\rceil =0$. Therefore, the bound in Theorem 4.13 is sharp.

Notice this is a graph with two copies of the graph in Example 4.8 attached by an additional edge. One may attach more copies of the graph in Example 4.8 to obtain examples of graphs where $\mathrm{{depth}}\,{R/I^t}=\left\lceil {\frac{d-4t+5}{3}} \right\rceil +p-1$ for any $t \ge 1$.

Example 4.15 and Theorem 4.13 lead to the following natural question.

Question 4.16

Let $G$ be a graph with $p$ connected components, $I=I(G)$, and let $d=d(G) \ge 1$ be the diameter of $G$. Then, is it true that for all $t\ge 1$ we have that $\mathrm{{depth}}\,{R/I^t} \ge \left\lceil {\frac{d-4t+5}{3}} \right\rceil +p-1$ or equivalently $\mathrm{{projdim}}_{R} R/I^t \le n-\left\lceil {\frac{d-4t+5}{3}}\right\rceil -p+1$?

Clearly Theorems 3.1, 4.4 and 4.13 show that Question 4.16 has a positive answer for $t \le 3$. If $t=4$ and $d\le 2$, the bound in Question 4.16 reduces to $\mathrm{{depth}}\,R/I^t \ge p-4$, and so the result holds by Proposition 4.3. Indeed, if $d \le 2$, Proposition 4.3 gives a positive answer to the question for all values of $t$ and $p$. If $d=3$ and $t=4$, the bound reduces to $p-3$ and so is trivially true for $p \le 3$. However, for any ideal $J$, $\mathrm{{depth}}\,(R/J) \ge 1$ if and only if $\mathfrak {m}\not \in \mathrm{Ass}\,(R/J)$. By [6], Lemma 2.1] we know $\mathrm{{depth}}\,(R/I^t) \ge 1$ for all $t\le p$, and so the question again has an affirmative answer for $p=4$. Thus, the first case for which an answer to Question 4.16 is not known is when $d=3, t=4$, and $p=5$.

An answer to this question would provide higher power analogs for Theorems 4.4 and 4.13. The difficulty in extending the outline of the proofs of those theorems to higher powers lies in generalizing the technical lemmas. For small powers, bounding the depth of $R/(I^t:x_1\cdots x_i)$ when the induced graph on $x_1, \ldots , x_i$ is connected is manageable because the small number of $x_i$ needed restricts the possible forms the induced graph can take. However, for higher powers of $t$, the products produced by repeatedly exhausting neighbor sets can induce graphs with poor behavior, including graphs for which $x_1 \cdots x_i \not \in I^s$ for $s= \left\lfloor {\frac{i}{2}} \right\rfloor$.

We conclude this article by considering a few brief applications of our results. When $I$ is a square-free monomial ideal, then $\mathrm{projdim}R/I=\mathrm{reg}(I^{\vee })$, where $I^{\vee }$ is the Alexander dual of $I$, [35], Corollary 0.3]. Since $I^{\vee \vee }=I$, then $\mathrm{reg}(I)=\mathrm{projdim}(R/I^{\vee })=n-\mathrm{{depth}}\,R/I^{\vee }$, where $n=\dim R$. Using our result for the depth of the first power of edge ideals we may obtain bounds on these invariants as well. Another interesting invariant is Stanley depth. As a final application of our results we obtain lower bounds on the Stanley depth of the first three powers of edge ideals.

Let $R=k[x_1, \ldots , x_n]$ be a polynomial ring over a field $k$. Let $M$ be a nonzero finitely generated $\mathbb {Z}^n$-graded $R$-module, let $u \in M$ be a homogeneous element and let $Z \subset \{x_1, \ldots , x_n\}$. Then, $uk[Z]$ is the $k$-subspace generated by all monomials $uv$, where $v$ is a monomial in $k[Z]$. A presentation of $M$ as a finite direct sum of such spaces $\mathcal {D}$: $M=\bigoplus \limits _{i=1}^{r}u_ik[Z_i]$ is called a Stanley decomposition of $M$. Let $\mathrm{{sdepth}\,}{\mathcal {D}}=\min \{|Z_i|: i=1, \ldots , r\}$ and let $\mathrm{{sdepth}\,}M=\max \{ \mathrm{{sdepth}\,}{\mathcal {D}}: \mathcal {D} \text{ is } \text{ a } \text{ Stanley } \text{ decomposition } \text{ of } M\}$. Then, $\mathrm{{sdepth}\,}{M}$ is called Stanley depth of $M$. It was conjectured by Stanley in [34] that $\mathrm{{sdepth}\,}{M} \ge \mathrm{{depth}}\,M$ for all $\mathbb {Z}^n$-graded modules $M$. There has been considerable interest concerning this conjecture, see, for instance, [20], and recently Duval et al. [10] found a counterexample to Stanley’s conjecture. However, finding classes for which the conjecture holds is still an interesting endeavor.

For the case of edge ideals of graphs and their powers, we are able to obtain lower bounds for the Stanley depth using our results from the previous sections as well as the following version of the Depth Lemma for Stanley depth.

Lemma 4.17

[4], Proposition 2.6], [31], Lemma 2.2] Let $R=k[x_1, \ldots , x_n]$ be a polynomial ring over a field $k$. Let $0 \rightarrow M \rightarrow N \rightarrow L \rightarrow 0$ be a short exact sequence of finitely generated $\mathbb {Z}^n$-graded $R$-modules. Then $\mathrm{{sdepth}\,}{N} \ge \min \{\mathrm{{sdepth}\,}{M}, \mathrm{{sdepth}\,}{N}\}$.

Theorem 4.18

Let $G$ be a graph with $p$ connected components, $I=I(G)$, and let $d=d(G)$ be the diameter of $G$. Then, for $1 \le t \le 3$ we have

$$\begin{aligned} \mathrm{{sdepth}\,}{R/I^t} \ge \left\lceil {\frac{d-4t+5}{3}} \right\rceil +p-1. \end{aligned}$$

Proof

The proof follows by induction on $n$, the number of vertices of $G$. Given Lemma 4.17, we can proceed the same way as in the proofs of Theorems 3.1, 4.4, 4.13 as long as we can establish the bounds for the base case of the induction, that is, when $n=d+1$ and $G$ is the graph of a path. The required bounds are known to hold for the Stanley depth, see, for example, [30], Theorem 2.7]. $\square$

One consequence of Theorem 4.18 is that any class of ideals for which at least one of the bounds in Theorems  3.1, 4.4, 4.13 is an equality will correspond to a class of modules that satisfy the Stanley conjecture. Thus, discovering when the bounds are achieved is an area of further interest.