Squarefree Monomial Ideals that Fail the Persistence Property and Non-increasing Depth

Abstract

In a recent work (Kaiser et al., J. Comb. Theory Ser. A 123, 239–251, 2014), Kaiser et al. provide a family of critically 3-chromatic graphs whose expansions do not result in critically 4-chromatic graphs and, thus, give counterexamples to a conjecture of Francisco et al. (Discrete Math. 310, 2176–2182, 2010). The cover ideal of the smallest member of this family also gives a counterexample to the persistence and non-increasing depth properties. In this paper, we show that the cover ideals of all members of their family of graphs indeed fail to have the persistence and non-increasing depth properties.

1 Introduction

Let k be a field and let R=k[x ₁,…,x _n ] be a polynomial ring over k. Let I⊆R be a homogeneous ideal. It is known by Brodmann [3] that the set of associated primes of I ^s stabilizes for large s, that is, Ass(R/I ^s)=Ass(R/I ^s+1) for all s≫0. However, the behavior of these sets can be very strange for small values of s. The ideal I is said to have the persistence property if

$$\text{Ass}(R/I^{s}) \subseteq \text{Ass}(R/I^{s+1}) \ \forall \ s \ge 1. $$

It is also known by Brodmann [4] that depth(R/I ^s) takes a constant value for large s. The behavior of depth(R/I ^s), for small values of s, can also be very complicated. The ideal I is said to have non-increasing depth if

$$\text{depth}(R/I^{s}) \ge \text{depth}(R/I^{s+1}) \ \forall \ s \ge 1.$$

Associated primes and depth of powers of ideals have been extensively investigated in the literature (cf. [1, 6–8, 10, 11, 13–15, 17, 19–21]). Even for monomial ideals, it is difficult to classify which ideals possess the persistence property or non-increasing depth. In this case, when I is a monomial ideal, the two properties are related by the fact that I possesses the persistence property if all monomial localizations of I have non-increasing depth. Herzog and Hibi [11] gave an example where $\mathfrak {m} = (x_{1}, \dots , x_{n}) \in \text {Ass}(R/I^{s})$ for small even integers s (whence depth(R/I ^s)=0) and $\mathfrak {m} \not \in \text {Ass}(R/I^{s})$ for small odd integers s (whence depth(R/I ^s)>0). Squarefree monomial ideals behave considerably better than monomial ideals in general, and many classes of squarefree monomial ideals were shown to have the persistence property. For instance, edge ideals of graphs ([17]), cover ideals of perfect graphs, cover ideals of cliques, odd holes and odd antiholes [7], and polymatroidal ideals [14]. A large class of squarefree monomial ideals with constant depth was constructed in [15].

In an attempt to tackle the persistence property, at least in identifying a large class of squarefree monomial ideals having the persistence property, the first author, together with Francisco and Van Tuyl in [7], made a graph theoretic conjecture about expansion of critically s-chromatic graphs and proved that this conjecture implies the persistence property for the cover ideals of graphs. The converse a priori is not known to be true. Recently, Kaiser et al. [16] gave a family of counterexamples to this graph theoretic conjecture. Computational experiment showed that the first member of their family of graphs also gave a counterexample to the persistence property and non-increasing depth for squarefree monomial ideals. In fact, this is the only graph with at most 20 vertices whose cover ideal fails the persistence property [22]. The goal of this paper is to prove that all members of this family indeed give counterexamples to the persistence property. As a consequence, they also provide counterexamples to non-increasing depth property.

Let us now describe more specifically our problem and results. Let G=(V,E) be a simple graph with vertex set V={x ₁,…,x _n } and edge set E. The expansion of G at a vertex x∈V is obtained from G by adding a new vertex y, an edge {x,y}, and edges {y,z} whenever {x,z} is an edge in G. For a subset W⊆V, the expansion of G at W, denoted by G[W], is obtained by expanding successively at the vertices in W. The first author, together with Francisco et al. in [7], made the following conjecture.

Conjecture 1.1

Let G be a critically s-chromatic graph. Then, there exists a subset W of the vertices such that G[W] is critically (s+1)-chromatic.

The cover ideal of G=(V,E) is defined to be

$$J(G) = \bigcap\limits_{\{x,y\} \in E} (x,y).$$

It was also shown in [7] that if Conjecture 1.1 holds, then the persistence property holds for the cover ideal of any graph. The converse is not known to be true.

A family of counterexamples to Conjecture 1.1 was given by Kaiser et al. [16] as follows. Let K ₃ denote the complete graph on 3 vertices, and let P _q , for q≥4, denote a path of length q−1. The graph $H_{q} = K_{3} \boxtimes P_{q}$ is formed by taking q copies of K ₃ with vertices {x _i,0,x _i,1,x _i,2},i=1,…,q, connecting x _i,j and x _i+1,j for i=1,…,q−1 to get 3 paths of length q−1 and finally connecting x _1,j and x _q,2−j for j=0,1,2 (see Fig. 1). These graphs were originally constructed by Gallai [9]. One of the interesting properties of H _q s is that they embed in the Klein bottle as quadrangulations (see [16]).

Fig. 1

The graph $H_{q} = K_{3} \boxtimes P_{q}$

It was pointed out in [16] that when q=4, the cover ideal J=J(H ₄) fails the persistence property and non-increasing depth. In particular, if $\mathfrak {m}$ is the maximal homogeneous ideal, then $\mathfrak {m} \in \text {Ass}(R/J^{3})$ but $\mathfrak {m} \not \in \text {Ass}(R/J^{4})$. The main result of this paper is to show that this phenomenon occurs for all q≥4.

Theorem 1.2

Let H _q be the graph constructed as before. Let J=J(H _q ) and let $\mathfrak {m}$ be the maximal homogeneous ideal in the polynomial ring R=k[x _i,j | i=1,…,q,j = 0,1,2]. Then, $\mathfrak {m} \in \text {Ass}(R/J^{3})$ and $\mathfrak {m} \not \in \text {Ass}(R/J^{4})$ . As a consequence, J fails to have non-increasing depth.

2 Preliminaries

In this section, we collect notation and terminology used in the paper. We follow standard texts in the research area [2, 5, 12, 18].

Let k be a field, let R=k[x ₁,…,x _n ], and let $\mathfrak {m} = (x_{1}, \dots , x_{n})$. Throughout the paper, we shall identify the variables of R with distinct vertices V={x ₁,…,x _n }. A graph G = (V,E) consists of V and a set E of edges connecting pairs of vertices. We shall restrict our attention to simple graphs, i.e., graphs without loops nor multiple edges.

Definition 2.1

Let G be a simple graph.

• (1) The chromatic number of a graph G, denoted by χ(G), is the least number of colors to assign to the vertices so that adjacent vertices get different colors.

• (2) The graph G is said to be critically s-chromatic if χ(G)=s, and for any vertex x in G,χ(G∖x)<s.

Critically s-chromatic graphs are also known as s-vertex critical graphs. We choose to use the terminology of critically s-chromatic graphs to be consistent with [7], where Conjecture 1.1 was stated.

A collection of vertices W⊆V in G=(V,E) is called a vertex cover if for any edge e∈E,W∩e≠∅. A vertex cover is called minimal if no proper subset of it is also a vertex cover.

There are various ways to associate squarefree monomial ideals to simple graphs. In this paper, the correspondence that we explore is the cover ideal construction.

Definition 2.2

Let G=(V,E) be a simple graph. The cover ideal of G is defined to be

$$J(G) = \bigcap\limits_{\{x,y\} \in E} (x,y).$$

The term cover ideal comes from the fact that minimal generators of J(G) correspond to minimal vertex covers in G. This cover ideal construction gives a one-to-one correspondence between simple graphs and unmixed, codimension two squarefree monomial ideals (this construction extends to hypergraphs to give a one-to-one correspondence to all squarefree monomial ideals).

Definition 2.3

Let I⊆R be an ideal. A prime ideal P is said to be an associated prime of I if there exists an element c∈R such that P=I:c. The set of all associated primes of I is denoted by Ass(R/I).

Definition 2.4

Let M be a finitely generated R-module.

• (1) A sequence of elements x ₁,…,x _t ∈R is called an M-regular sequence if M ≠ (x ₁,…,x _t )M and x _i is not a zero divisor of M/(x ₁,…,x _i−1)M for all i=1,…,t.

• (2) The depth of M, denoted by depth(M), is the largest length of an M-regular sequence in R.

Remark 2.5

It is an easy exercise to see that for an ideal I⊆R, depth(R/I)>0 if and only if $\mathfrak {m} \not \in \text {Ass}(R/I)$.

Remark 2.6

The construction of the graph H _q can be generalized to a pair consisting of a path and a complete graph of any size. Indeed, let P _q be a path of length q−1 and let K _p be the complete graph of size p. We can then construct the graph $H_{p,q} = K_{p} \boxtimes P_{q}$ by taking q copies of K _p with vertices {x _i,0,…,x _i,p−1},i=1,…,q, connecting x _i,j to x _i+1,j for i=1,…,q−1 to get p paths of length q−1, and finally connecting x _1,j to x _q,p−1−j for j=0,…,p−1. In this construction, H _q =H _3,q .

3 Proof of the Main Result

This section is devoted to the proof of our main result, Theorem 1.2. This theorem will be proved as a combination of Propositions 3.1 and 3.2 and Corollary 3.8. For simplicity of terminology, we call the complete graph K ₃ on {x _i,0,x _i,1,x _i,2} the ith triangle in H _q . We shall also abuse notation in identifying vertices of H _q and corresponding variables in R.

Proposition 3.1

Let H _q be the graph constructed as in the introduction. Let J=J(H _q ) and let $\mathfrak {m}$ be the maximal homogeneous ideal in R=k[x _i,j | i=1,…,q,j=0,1,2]. Then, $\mathfrak {m} \in \text {Ass}(R/J^{3})$.

Proof

It was shown in [16, Proposition 9] that H _q is critically 4-chromatic. Thus, it follows from [6, Corollary 4.5] that $\mathfrak {m} \in \text {Ass}(R/J^{3})$. □

Proposition 3.2

Let H _q be the graph constructed as in the introduction. Let J=J(H _q ) and let $\mathfrak {m}$ be the maximal homogeneous ideal in R=k[x _i,j | i=1,…,q,j=0,1,2]. Then, $\mathfrak {m} \not \in \text {Ass}(R/J^{4})$.

Proof

Suppose, by contradiction, that $\mathfrak {m} \in \text {Ass}(R/J^{4})$. That is, there exists a monomial T in R such that T∉J ⁴ and $J^{4} : T = \mathfrak {m}$. Since the generators of J are squarefree, the powers of each variable in minimal generators of J ⁴ are at most 4. This implies that the power of each variable in T is at most 3, i.e., T divides $({\prod }_{i,j} x_{i,j})^{3}$. We shall now make a few observations to reduce the number of cases that we need to consider later.

Observation 3.3

$M = ({\prod }_{i,j} x_{i,j})^{3} \in J^{4}$. Indeed, we can write M=M ₁ M ₂ M ₃ M ₄ N as follows.

• (1) If q is odd, then choose $N = {\prod }_{i=1}^{q} x_{i,0}$ and

  $$\begin{array}{@{}rcl@{}} M_{1} & = &\left(\prod\limits_{i < q \text{ odd}} x_{i,0} x_{i,1}\right) \left(\prod\limits_{i \text{ even}} x_{i,1} x_{i,2}\right) (x_{q,0} x_{q,2}) \\ M_{2} & = &\left(\prod\limits_{i < q \text{ odd}} x_{i,0} x_{i,2}\right) \left({\prod}_{i \text{ even}} x_{i,1} x_{i,2}\right) (x_{q,0} x_{q,1}) \\ M_{3} & =& \left(\prod\limits_{i < q \text{ odd}} x_{i,1} x_{i,2}\right) \left(\prod\limits_{i \text{ even}} x_{i,0} x_{i,1}\right) (x_{q,1} x_{q,2}) \\ M_{4} & =& \left(\prod\limits_{i < q \text{ odd}} x_{i,1} x_{i,2}\right) \left(\prod\limits_{i \text{ even}} x_{i,0} x_{i,2}\right) (x_{q,1} x_{q,2}). \end{array} $$

• (2) If q is even, then choose $N = {\prod }_{i=1}^{q} x_{i,1}$ and

  $$\begin{array}{@{}rcl@{}} M_{1} & =& \left(\prod\limits_{i \text{ odd}} x_{i,0} x_{i,2}\right) \left(\prod\limits_{i \text{ even}} x_{i,0} x_{i,1}\right) \\ M_{2} & =& \left(\prod\limits_{i \text{ odd}} x_{i,0} x_{i,2}\right) \left(\prod\limits_{i \text{ even}} x_{i,1} x_{i,2}\right) \\ M_{3} & =& \left(\prod\limits_{i \text{ odd}} x_{i,0} x_{i,1}\right) \left(\prod\limits_{i \text{ even}} x_{i,0} x_{i,2}\right) \\ M_{4} & = &\left(\prod\limits_{i \text{ odd}} x_{i,1} x_{i,2}\right) \left(\prod\limits_{i \text{ even}} x_{i,0} x_{i,2}\right). \end{array} $$

It is an easy exercise to verify that M ₁,…,M ₄ are vertex covers of H _q . Thus, M∈J ⁴. This observation allows us to assume that T strictly divides M.

Observation 3.4

For each i=1,…,q, the total power of x _i,0,x _i,1 and x _i,2 in T is at least 8. Indeed, take k≠i, then since $J^{4} : T = \mathfrak {m}$, we must have T x _k,0∈J ⁴. It then follows from the fact that generators of J correspond to vertex covers of H _q that T x _k,0 can be written as the product of 4 vertex covers of H _q . Notice also that to cover the triangle with vertices {x _i,0,x _i,1,x _i,2}, each vertex cover needs at least two of those 3 vertices. Thus, 4 vertex covers contain in total at least 8 copies of those vertices. This observation and the fact that T divides M allow us to conclude that for each i=1,…,q, either all three vertices {x _i,0,x _i,1,x _i,2} appear in T each with power exactly 3 or two of them appear in T with power 3 and the third one appears in T with power of exactly 2. For simplicity of language, we shall call the total power of {x _i,0,x _i,1,x _i,2} in T the power of the ith triangle in T.

Observation 3.5

Suppose that the power of the ith triangle in T is at least 8, and we already impose the conditions that 3 among the M _i s each has to contain a specific (but distinct) variable in the ith triangle. Then, we can always distribute the remaining variables of the ith triangle from T into the M _i s so that each of them indeed covers the edges of the ith triangle. To see this, without loss of generality, we may assume that the 3 imposed conditions are x _i,0 | M ₁,x _i,1 | M ₂ and x _i,2 | M ₃ and assume that x _i,1 and x _i,2 appear in T with powers at least 3. This implies that x _i,0 appears in T with power at least 2, and we can distribute the variables of the ith triangle in T into the M _i s as follows:

$$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1}\left|~M_{1}\right. \\ &&x_{i,1} x_{i,2}\left|~M_{2}\right. \\ &&x_{i,1} x_{i,2}\left|~M_{3}\right. \\ &&x_{i,0} x_{i,2}\left|~M_{4}\right. . \end{array} $$

Observation 3.6

Re-indexing the vertices of H _q as follows: label x _q,0 by x _1,2, label x _q,1 by x _1,1, label x _q,2 by x _1,0 (notice that we have switched the second indices 0 and 2 in the q triangle and bring it to be the first triangle), and then label x _i,j by x _i+1,j for all 1≤i≤q−1 and j=0,1,2 (i.e., shifting the rest of the triangles one place to the right). We then obtain an isomorphic copy of H _q where the old qth triangle becomes the first one. This process can be repeated. Thus, coupled with Observation 3.3, we can assume that the power of the first triangle in T is exactly 8. Without loss of generality, we may further assume that x _1,0 appears in T with power 2, while x _1,1 and x _1,2 appear in T with powers 3.

Observation 3.7

Fix an index i<q−1 where the power of the ith triangle in T is exactly 8 and assume that x _i,0 appears in T with power 2 (and so, x _i,1 and x _i,2 appear in T both with power 3). Since $J^{4} : T = \mathfrak {m}$, in particular, we have T x _q,0∈J ⁴. That is, we can write T x _q,0=M ₁ M ₂ M ₃ M ₄ as the product of 4 elements in J, i.e., 4 vertex covers of H _q . To distribute $x_{i,0}^{2}x_{i,1}^{3}x_{i,2}^{3}$ into 4 vertex covers, there is only one possibility (up to permutation of the indices of the vertex covers), which is:

$$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2}\left|\right.~ M_{4}. \end{array} $$

This distribution of the vertices of the ith triangle will impose specific conditions on how the vertices of the (i+1)st triangle can be distributed into the 4 vertex covers. Particularly, we must have that x _i+1,2 | M ₁,x _i+1,1 | M ₂, and x _i+1,0 divides both M ₃ and M ₄.

If the power of the (i+1)st triangle in T is 9, then we can distribute vertices in the (i+1)st triangle into the M _i s as follows:

$$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{4}, \end{array} $$

where the extra copy of x _i+1,0 could be assigned to either M ₁ or M ₂. Now, the only conditions imposed on the (i+2)nd triangle are x _i+2,2 | M ₃,x _i+2,1 | M ₄ and either x _i+2,0 | M ₂ or x _i+2,0 | M ₁. It follows from Observation 3.5 that the variables of the (i+2)nd triangle in T can be distributed into the M _i s, and we can think of the (i+2)nd triangle as our new starting point (if i+2<q).

If, on the other hand, the power of the (i+1)st triangle in T is 8, then we obtain the following possibilities depending on which variable in the (i+1)st triangle appears in T with power 2.

• (1) If the power of x _i+1,0 in T is 2 then (up to permuting M ₃ and M ₄), we have

  $$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{4}. \end{array} $$

• (2) If the power of x _i+1,1 in T is 2, then we must be in either of the following cases:

  $$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{4}; \end{array} $$

  or

  $$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,3}\left|\right.~ M_{4}. \end{array} $$

• (3) If the power of x _i+1,2 in T is 2, then we must be in either of the following cases:

  $$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{4}; \end{array} $$

  or

  $$\begin{array}{@{}rcl@{}} &&x_{i,0} x_{i,1} \quad x_{i+1,1} x_{i+1,2}\left|\right.~ M_{1} \\ &&x_{i,0} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{2} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,1}\left|\right.~ M_{3} \\ &&x_{i,1} x_{i,2} \quad x_{i+1,0} x_{i+1,2}\left|\right.~ M_{4}. \end{array} $$

The upshot of this observation is that we can successively distribute T and T x _q,0 (without the use of the extra variable x _q,0) into 4 vertex covers up to the (q−1)st triangle in the same way. At each step, moving from the ith triangle to the (i+1)st triangle, we might end up with a number of different choices. Moreover, if the power of the (i+1)st triangle in T is 9, then we can distribute the vertices in the ith and the (i+1)st triangles and consider the (i+2)nd triangle as our new starting point to repeat the process. The difference, and what makes T∉J ⁴ but T x _q,0∈J ⁴, occurs when we need to cover the qth triangle and edges connecting the qth and the 1st triangles (i.e., moving from the (q−1)st triangle to the last triangle).

By making use of Observation 3.7, we can successively distribute the variables appearing in T into the M _i s in the same way as that of T x _q,0 such that along the process, M _i s cover edges in the first (q−1) triangles. It remains to consider how the variables in the qth triangle are distributed. We shall show that a contradiction, either that T∈J ⁴ or that $J^{4} : T \not = \mathfrak {m}$, is always resulted in.

Notice that when the power of the (q−1)st triangle in T is 9, in our distribution process, a power 8 of this triangle is distributed to the M _i s, and there is possibly an extra copy of a variable left. This possible extra variable can then be assigned to one of the M _i s. Our argument will complete by exhausting cases depending on how the vertices in the (q−1)st triangle are distributed among the M _i s and which vertex is possibly treated as the extra one.

There are three choices for the possible extra vertex. For each choice of the possible extra vertex, the cases are considered depending on how the other two copies of this vertex are distributed among four vertex covers M _i s. Observe that if the possible extra vertex is x _q−1,t (where t=0,1 or 2, and we identify x _i,t with x _i,t+3), then there are six cases to consider by assigning x _q−1,t to two out of the four vertex covers M _i s. For example, if x _q−1,t is assigned to M ₁ and M ₂, then there would be two possibilities depending on how x _q−1,t+1 and x _q−1,t+2 are distributed. These possibilities are described by conditions:

$$\begin{array}{@{}rcl@{}} x_{1,0} x_{1,1} {\dots} {\dots} x_{q-1,t} x_{q-1,t+1}&\left|\right.&M_{1} \\ x_{1,0} x_{1,2} {\dots} {\dots} x_{q-1,t} x_{q-1,t+2}&\left|\right.&M_{2} \\ x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,t+1} x_{q-1,t+2}&\left|\right.&M_{3} \\ x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,t+1} x_{q-1,t+2}&\left|\right.& M_{4}, \end{array} $$

or

$$\begin{array}{@{}rcl@{}} x_{1,0} x_{1,1} {\dots} {\dots} x_{q-1,t} x_{q-1,t+2}&\left|\right.&M_{1} \\ x_{1,0} x_{1,2} {\dots} {\dots} x_{q-1,t} x_{q-1,t+1}&\left|\right.&M_{2} \\ x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,t+1} x_{q-1,t+2}&\left|\right.&M_{3} \\ x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,t+1} x_{q-1,t+2}&\left|\right.&M_{4}. \end{array} $$

This case-by-case analysis is quite tedious, but the 18 cases are mostly similar. Thus, we will go through the argument carefully for one case and leave it to the interested reader to check the details of the remaining cases.

Consider the case where x _q−1,0 is the possible extra vertex, and the other two copies of x _q−1,0 are in M ₁ and M ₂. There are two possibilities depending on how x _q−1,1 and x _q−1,2 were distributed:

$$\begin{array}{@{}rcl@{}} &&x_{1,0} x_{1,1} {\dots} {\dots} x_{q-1,0} x_{q-1,1}\left|~M_{1}\right. \\ &&x_{1,0} x_{1,2} {\dots} {\dots} x_{q-1,0} x_{q-1,2}\left|~M_{2}\right. \\ &&x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,1} x_{q-1,2}\left|~M_{3}\right. \\ &&x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,1} x_{q-1,2}\left|~M_{4}\right., \end{array} $$

or

$$\begin{array}{@{}rcl@{}} &&x_{1,0} x_{1,1} {\dots} {\dots} x_{q-1,0} x_{q-1,2}\left|\right.~ M_{1} \\ &&x_{1,0} x_{1,2} {\dots} {\dots} x_{q-1,0} x_{q-1,1}\left|\right.~ M_{2} \\ &&x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,1} x_{q-1,2}\left|\right.~ M_{3} \\ &&x_{1,1} x_{1,2} {\dots} {\dots} x_{q-1,1} x_{q-1,2}\left|\right.~ M_{4}. \end{array} $$

If it is the first possibility that occurs, and there is in fact no extra copy of x _q−1,0 (i.e., the power of the (q−1)st triangle in T was exactly 8), then this impose the following conditions on the qth triangle: x _q,0 x _q,2 | M ₁,M ₃,M ₄ and x _q,1 | M ₂. This implies that the product of the M _i s will use four copies of either x _q,0 or x _q,2. Thus, T x _q,1∉J ⁴. If it is the first possibility, but there is an extra copy of x _q,0 left, then we can distribute this extra copy of x _q,0 to either M ₃ or M ₄, say M ₄. In this case, the conditions imposed on the qth triangle are: x _q,0 x _q,2 | M ₁ and M ₃,x _q,1 | M ₂, and x _q,2 | M ₄. Thus, to cover the edges of the qth triangle, we must have

$$\begin{array}{@{}rcl@{}} &&x_{q,0} x_{q,2}\left|\right.~ M_{1} \\ &&x_{q,0} x_{q,1}\left|\right.~ M_{2} \\ &&x_{q,0} x_{q,2}\left|\right.~ M_{3} \\ &&x_{q,1} x_{q,2}\left|\right.~ M_{4}. \end{array} $$

It follows that if T contains three copies of x _q,0 and x _q,2, then this distribution shows that T∈J ⁴. Otherwise, if T contains, for instance, only two copies of x _q,0, then since the product of four vertex covers, as shown, must contain at least three copies of x _q,0, we have T x _q,1∉J ⁴.

If it is the second possibility and there is no extra copy of x _q−1,0, then conditions imposed on the qth triangle are: x _q,0 x _q,1 | M ₁,x _q,1 x _q,2 | M ₂,x _q,0 x _q,2 | M ₃ and M ₄. Thus, the product of the four vertex covers contains at least three copies of x _q,0 and x _q,2. If T has at least three copies of x _q,0 and x _q,2, then T∈J ⁴. Otherwise, T x _q,1∉J ⁴. If it is the second possibility and there is an extra copy of x _q−1,0, then we can distribute this extra copy of x _q,0 to either M ₃ or M ₄, say M ₄. In this case, the conditions imposed on the qth triangle are: x _q,0 x _q,1 | M ₁,x _q,1 x _q,2 | M ₂,x _q,0 x _q,2 | M ₃, and x _q,2 | M ₄. Thus, if T contains at least three copies of x _q,2, then by distributing either x _q,0 or x _q,1 to M ₄, we get that T∈J ⁴. Otherwise, T x _q,0∉J ⁴.

For the remaining cases, it can be seen that covering the edges of the qth triangle and edges connecting to the first and the (q−1)st triangles will impose a number of conditions on how vertices of the qth triangle in T can be distributed to the four vertex covers M _i s. These conditions will fall into one of the following situations:

• (1) The conditions do not require ${\prod }_{i=1}^{4} M_{i}$ to contain any vertex of the qth triangle with power more than 2. In this case, we can always distribute the vertices of the qth powers in T into the four vertex covers M _i s in a way to satisfy these conditions. We thus have T∈J ⁴.

• (2) The conditions require ${\prod }_{i=1}^{4} M_{i}$ to contain one or two vertices of the qth triangle with powers at least 3. If T indeed does contain those vertices with powers at least 3, then we can also distribute the vertices of the qth triangle in T into the four vertex covers M _i to comply with those condition; we then have T∈J ⁴. If, otherwise, T does not contain those one or two vertices with powers at least 3, then the product of T with the third vertex will not be in J ⁴.

• (3) The conditions require ${\prod }_{i=1}^{4} M_{i}$ to contain a vertex of the qth triangle with power at least 4. In this case, the product of T and another vertex of the qth triangle will not be in J ⁴. □

Corollary 3.8

Let H _q be the graph constructed as in the introduction. Let J=J(H _q ) ⊆ R = k[x _i,j | i=1,…,q,j=0,1,2]. Then, J fails to have non-increasing depth.

Proof

The conclusion is a direct consequence of Remark 2.5 and Propositions 3.1 and 3.2. □

4 Other Constructions

Natural generalizations of the graphs H _q s are those of H _p,q s as constructed in Remark 2.6. We end the paper by showing that those graphs H _p,q do not give counterexamples to Conjecture 1.1. In fact, we shall show that H _p,q for p>3 are not critical graphs.

Theorem 4.1

Let p,q≥4 and let H _p,q be constructed as in Remark 2.6. Then, χ(H _p,q ) = p, but H _p,q is not critical p-chromatic.

Proof

Clearly, any graph containing a complete subgraph of size p has the chromatic number at least p. Thus, it suffices to show that H _p,q can be colored using p colors (and since H _p,q contains more than one copies of K _p , this will also imply that H _p,q is not critical p-chromatic). Indeed, we can assign p colors to the vertices of H _p,q as follows. We shall identify colors congruent modulo p. □

Case 1

p is even and q is odd.

For 1≤i≤q and i is odd, assign to x _i,j color j for all j=0,…,p−1. For 1≤i≤q and i is even, assign to x _i,j color j+1 for j=0,…,p−1. It is easy to see that the vertices on each copy of K _p get different colors. Also, on the ith and (i+1)st copies of K _p , since the parity of i and i+1 are different, adjacent vertices x _i,j and x _i+1,j get different colors. Finally, on the first and the last copies of K _p , adjacent vertices are x _1,j of color j and x _q,p−1−j of color p−1−j. Since p is even j≠p−1−j for any j. Figure 2 gives the assigned 4-coloring for H _4,q in this case.

Fig. 2

A 4-coloring for H _4,q when q is odd

Case 2

p and q are both even.

For 1≤i≤q and i is odd, assign to x _i,j color j for all j=0,…,p−1. For 1≤i≤q and i is even, assign to x _i,j the color p+1−j. Again, the vertices on each copy of K _p get different colors. Also, since p is even j≠p+1−j, adjacent vertices on consecutive copies of K _p also get different colors. On the first and the last copies of K _p , adjacent vertices are x _1,j of color j and x _q,p−1−j of color j+2, and we have j≢j+2 (mod p). Figure 3 gives the assigned 4-coloring for H _4,q in this case.

Fig. 3

A 4-coloring for H _4,q when q is even

Case 3

p is odd and q is even.

For 1≤i≤q and i is odd, assign to x _i,j color j for all j=0,…,p−1. For 1≤i≤q and i is even, we assign the colors to x _i,j s as follows: first, we assign to x _i,j color p−j for j=0,…,p−1 and then we switch the colors of x _i,0 and $x_{i,\frac {p+1}{2}}$ (i.e., the vertex x _i,0 now has color $\frac {p-1}{2}$ and the vertex $x_{i, \frac {p+1}{2}}$ now has color 0). Again, the vertices on each copy of K _p get different colors. On consecutive copies of K _p , since j≢p−j (mod p) unless j=0, together with the color switching between x _i,0 and $x_{i,\frac {p+1}{2}}$, it can be seen that adjacent vertices get different colors. On the first and the last copies of K _p , adjacent vertices are x _1,j of color j and x _q,p−1−j of colors j+1≢j, except when j=p−1 or $j = \frac {p-3}{2}$. Finally, x _1,p−1 and x _q,0 are adjacent and of colors $p-1 \not \equiv \frac {p-1}{2}$, while $x_{1,\frac {p-3}{2}}$ and $x_{q, \frac {p+1}{2}}$ are adjacent and of colors $\frac {p-3}{2} \not \equiv 0$ (this is where we make use of the hypothesis that p≥4). Figure 4 gives the assigned 5-coloring for H _5,q in this case.

Fig. 4

A 5-coloring for H _5,q when q is even

Case 4

p and q are both odd.

For 1≤i<q−1 and i is odd, assign to x _i,j color j for all j=0,…,p−1. For 1≤i≤q−1 and i is even, assign to x _i,j color j−1 for all j=0,…,p−1. Finally, we assign the colors to x _q,j s as follows: first, we assign to x _q,j color p−j, for j=0,…,p−1 and then we switch the colors of x _q,0 and $x_{q,\frac {p+1}{2}}$ (i.e., the vertex x _q,0 now has color $\frac {p-1}{2}$ and the vertex $x_{q,\frac {p+1}{2}}$ now has color 0). Clearly, vertices on each copy of K _p get different colors, and adjacent vertices on consecutive copies of K _p (except the last one) get different colors. On the (q−1)st and the qth copies of K _p , adjacent vertices are x _q−1,j of color j−1 and x _q,j of color p−j, except exactly when j=0 or $j=\frac {p+1}{2}$ due to the color switch. It can be seen that j−1≢p−j for all $j \not = \frac {p+1}{2}$. When $j = \frac {p+1}{2}$, the colors of $x_{q-1,\frac {p+1}{2}}$ and $x_{q,\frac {p+1}{2}}$ are $\frac {p-1}{2} \not \equiv 0$. For adjacent vertices between the qth and the first copies of K _p , the argument follows from the last part of that of case 3 (and again, we shall need the condition that p≥4). Figure 5 gives the assigned 5-coloring for H _5,q in this case.

Fig. 5

A 5-coloring for H _5,q when q is odd