ASYMPTOTIC GROWTH OF ASSOCIATED PRIMES
OF CERTAIN GRAPH IDEALS

arXiv:1204.3315v2 [] 5 Dec 2012

SARAH WOLFF
Abstract. We specify a class of graphs, Ht , and characterize
the irreducible decompositions of all powers of the cover ideals.
This gives insight into the structure and stabilization of the corresponding associated primes; specifically, providing an answer to
the question “For each integer t ≥ 0, does there exist a (hyper)
graph Ht such that stabilization of associated primes occurs at
n ≥ (χ(Ht ) − 1) + t?” [4]. For each t, Ht has chromatic number 3
and associated primes that stabilize at n = 2 + t.

1. Introduction
We work at the intersection of graph theory and commutative algebra
by relating powers of square-free monomial ideals in polynomial rings
to vertex covers of finite simple graphs. Ideal constructions give two
correspondences, both of which associate to each such graph a monomial ideal. These correspondences have been established and studied
in, for example, [9], [8], [3], and [4].
Motivated by the Strong Perfect Graph Theorem, Francisco, Hà,
and Van Tuyl [3] expand the link between graph theory and algebra in
order to provide an algorithm for determining if a graph is perfect—
neither it nor its complementary graph has an induced odd cycle of
length five or greater. Their algorithm results from relating odd cycles
to the associated primes of powers of monomial ideals. Francisco, Hà,
and Van Tuyl continue to investigate this connection in [4], establishing
a lower bound on the stabilization of these associated primes that is
derived from the chromatic number of the corresponding graphs. They
find that stabilization does not occur when n < χ(G) − 1, for χ(G)
the chromatic number of the graph and n the power of the ideal [4,
Corollary 4.9]. They further show that this bound is not optimal,
leading to the question: “For each integer t ≥ 0, does there exist a
(hyper)graph Ht such that the stabilization of associated primes occurs
Date: March 24, 2018.
2000 Mathematics Subject Classification. 05C25, 05E40, 05C38, 13F20.
1

2

SARAH WOLFF

at n ≥ (χ(Ht ) − 1) + t?” [4, Question 4.10]. In this paper we answer
this question in the affirmative.
More precisely, let G be a graph with vertex set VG = {v1 , . . . , vm }
and edge set EG consisting of unordered pairs of distinct vertices of
G. Let K be a field. We identify the vertices of G with the variables in the polynomial ring RG = K[v1 , . . . , vm ]. Further, we associate two square-free monomial ideals to G: the edge ideal, IG , generated by {vi vj | {vi , vj } ∈ EG }, and the cover ideal, JG , generated
by {vi1 · · · vij | {vi1 , . . . , vij } a vertex cover of G}. These ideal constructions were first introduced in [9] and give the correspondences
mentioned above.
Francisco, Hà, and Van Tuyl study the associated primes of RG /(JG )2 ,
denoted Ass(RG /(JG )2 ), and find that P is in Ass(RG /(JG )2 ) if and
only if either P = (vi , vj ) where {vi , vj } is an edge of G, or P =
(vi1 , . . . , vis ) where the subgraph induced by {vi1 , . . . , vis } is an odd cycle of G [3, Corollary 3.4]. These results are derived by determining the
irreducible decomposition of (JG )2 , i.e., writing (JG )2 as an intersection
of irreducible monomial ideals.
They then extend these ideas in [4] by studying Ass(RG /(JG )n ) for
n ≥ 2. Brodmann [2] in 1979 proved that the set of associated primes
of powers of ideals stabilizes, i.e., for a ring R and an ideal I of R,
there exists some positive integer s such that Ass(R/I s ) = Ass(R/I n )
for all n ≥ s. Francisco, Hà, and Van Tuyl [4] find a lower bound on the
stabilization of Ass(RG /(JG )n ), proving for a graph G that stabilization
does not occur when n < χ(G) − 1 [4, Corollary 4.9]. They then pose
the question mentioned above [4, Question 4.10], which we answer in
the affirmative by providing a family of graphs, Ht , each with chromatic
number three such that for each t, Ass(RHt /(JHt )n ) stabilizes at n =
(χ(Ht ) − 1) + t = 2 + t.
The main result of this paper is:
Theorem 4.1. For t ∈ Z+ , let Rt := RHt be the polynomial ring
associated to Ht and let Jt := JHt denote the cover ideal of Ht . Then
the associated primes of Rt /(Jt )n stabilize at n = (χ(Ht )−1)+t = 2+t.
As in [3], we characterize the associated primes of Rt /(Jt )n by studying the monomial ideal powers (Jt )n . Just as the cover ideal is generated
by vertex covers of the graph, we find that the generators of the ideals
in the irreducible decompositions of (Jt )n are closely related to vertex
covers. In Section 2 we develop the necessary tools from algebra and
graph theory for our results. In Section 3 we introduce the family of
graphs and explore the structure of these graphs with several key lemmas. In Section 4 we use these lemmas to characterize the irreducible

ASSOCIATED PRIMES OF CERTAIN GRAPH IDEALS

3

decompositions of (Jt )n (Theorem 4.11). Theorem 4.1 is then a direct
consequence of Theorem 4.11.
2. Graph Theory and Associated Primes
In this section we briefly introduce the important definitions from
graph theory and algebra needed for our results. We use the basic
conventions, notation, and definitions from [1], [3], and [7].
For a graph G we enumerate its vertex set VG = {v1 , . . . , vm }. We
assume that G is a simple graph so that its edge set, EG , consists of
unordered pairs {vi , vj } of distinct vertices. Two vertices are adjacent
if they are joined by an edge.
A coloring of G is an assignment of colors to the vertices of G such
that no two adjacent vertices are assigned the same color. The chromatic number of G is the minimal number of colors in a coloring of
G.
A subset A of VG is a vertex cover if every edge of G is incident to at
least one vertex of A. The subset is a minimum vertex cover if it is a
vertex cover of smallest cardinality. In this paper we consider minimum
vertex covers rather than minimal vertex covers as this distinction is
necessary for the proof of Theorem 4.11.
For a subset A of VG , the neighbors of A, denoted N (A), are the
vertices of G that are adjacent to vertices of A, but do not lie in A.
The subgraph of G induced by A is the subgraph with vertex set A and
edge set consisting of those edges of G with both vertices in A.
A graph with vertex set {w1 , . . . , wk } is a k-cycle if its edge set
consists precisely of edges connecting wk to w1 and wi to wi+1 , 1 ≤ i <
k. We call the cycle odd (respectively, even), if k is odd (respectively,
even).
Let K be a field. We identify the vertices of G with variables in
the polynomial ring RG = K[v1 , . . . , vm ]. Let IG denote the edge
ideal of G, and let JG denote the cover ideal of G, generated by
{vi1 · · · vij | {vi1 , . . . , vij } a vertex cover of G}. We note that JG is
often equivalently defined as the Alexander dual of IG (see, e.g., [3],
[4]). For an explanation of Alexander duality, see [7].
A typical monomial element of the cover ideal JG is of the form
a1 a2
am
v1 v2 · · · vm
for nonnegative integers ai . Just as the variables v1 , . . . , vm
correspond to vertices of the graph G, the vector (a1 , . . . , am ) also has
a graph theoretic interpretation. We refer to any such a = (a1 , . . . , am )
(corresponding to the vertices v1 , . . . , vm of G) as a degree vector and
say a nonzero degree vector a is a k-cover if ai + aj ≥ k whenever
{vi , vj } ∈ EG .

4

SARAH WOLFF

The concept of k-cover was first introduced in [6] as a generalization
of a vertex cover. Note that if a subset A of VG is a minimum vertex
cover then a degree vector a with ai = 1 if vi ∈ A and ai = 0 otherwise
is a one-cover of G. We call such a one-cover a minimum one-cover.
am
)
An irreducible monomial ideal is an ideal of the form V a = (v1a1 , . . . , vm
ai
n
for a ∈ N , where if ai = 0, we omit vi from the set of generators.
Every monomial ideal I can be written as the finite intersection of irreducible monomial ideals: I = V a1 ∩ · · · ∩ V as , called an irreducible
decomposition of I [7]. The decomposition is called irredundant if no
V ai can be omitted.
Let R be a commutative ring and M an R-module. The set of
associated primes of M , denoted Ass(M ), consists of prime ideals P
such that P annihilates some m in M .
T For a graph G, the cover ideal JG has irreducible decomposition JG =
{vi ,vj }∈EG (vi , vj ) (see e.g., [3]); hence, Ass(R/JG ) = {(vi , vj ) | {vi , vj } ∈
EG }. Generalizing to (JG )n , we compute the irreducible decompositions of (JG )n for our family of graphs in order to deduce the set of
associated primes of R/(JG )n . We refer to this set as the associated
primes of G.
3. A Family of Graphs
We proceed to define a family of graphs, Ht , to give an affirmative
answer to the question posed in [4, Question 4.10]: “For each integer
t ≥ 0, does there exist a (hyper)graph Ht such that the stabilization of
associated primes occurs at n ≥ (χ(Ht ) − 1) + t?” Note by [3, Remark
3.3, Corollary 3.4] that the associated primes of an odd cycle, G, stabilize at n = χ(G) − 1 + 0 = 2. We thus answer the above question for
t ≥ 1.
Definition 3.1. The graph H1 has vertex set {x1 , . . . , x5 , y1 } and edge
set such that the subgraph induced by {x1 , . . . , x5 } is a 5-cycle and the
neighbors of y1 are precisely {x1 , x2 , x3 }.
For t > 1, Ht has vertex set {x1 , . . . , x4t−1 , y1 , . . . , yt } and edge set
such that the subgraph induced by {x1 , . . . , x4t−1 } is a (4t − 1)-cycle,
the neighbors of y1 are precisely {x1 , x2 , x3 }, and for 1 < i ≤ t the
neighbors of yi are precisely {x4i−4 , x4i−3 , x4i−2 , x4i−1 } (Figure 1).
We first note that the graphs Ht have chromatic number three for all
t ≥ 1. To see this, assign color 1 to the vertices {x1 , x3 } ∪ {yi | i > 1},
color 2 to the vertices {x2 } ∪ {x2k+1 | k > 1}, and color 3 to the
remaining vertices. Each Ht has at least one odd cycle; thus, this
3-coloring is a minimum coloring.

ASSOCIATED PRIMES OF CERTAIN GRAPH IDEALS

H1

H2

x2

H3
x1

x1

x1
y1

x2

y1

x2

x3

x3

x3

x4

x4

x4

x5

x5
x6
x7

5

y2

x5
x6

y1

y2

...

x7
x8
x9
x10

y3

x11

Figure 1. Ht
Let Jt := JHt be the cover ideal of Ht for each t ≥ 1 and let Rt := RHt
be the polynomial ring associated to Ht . We show that Ass(Rt /(Jt )n )
stabilizes at n = 2 + t. This result will follow from a characterization
of the irreducible decompositions of (Jt )n for all t ≥ 1 and n ≥ 1.
For this characterization, we use the structure of the graphs together
with the following technical lemmas, all of which follow easily from the
definitions:
Lemma 3.2. Let G be a graph with vertex set {v1 , . . . , vm }. Let RG be
the polynomial ring associated to G, and let JG be the cover ideal of G.
If M is a minimal generator of (JG )n , then
\
M∈
(vin , vj ) ∩ (vin−1 , vj2 ) ∩ · · · ∩ (vi2 , vjn−1 ) ∩ (vi , vjn ).
{vi ,vj }∈EG

Lemma 3.3. Let G be a graph with vertex set {v1 , . . . , vm } and cover
am
ideal JG . Then the mononomial v1a1 · · · vm
is an element of (JG )n if
and only if a = (a1 , . . . , am ) is an n-cover of G that can be written as
the sum of n one-covers, ai , of G: a = a1 + · · · + an .
We note that a degree vector, a, for a graph G can also be interpreted as a degree vector for a subgraph of G induced by A ⊆ VG by
considering only the ai corresponding to the vertices of A. We denote
this subgraph degree vector by a|A .
Lemma 3.4. For a graph G, let a be a degree vector for G. Let
G1 , . . . , Gl be induced subgraphs of G such that EG ⊆ EG1 ∪ · · · ∪ EGl .

6

SARAH WOLFF

Then a is a one-cover of G iff a|Gi is a one-cover of Gi for all i,
1 ≤ i ≤ l.
Our interest is in studying (Jt )n . By Lemma 3.3, elements of (Jt )n
correspond to n-covers of Ht . These n-covers can be written as the sum
of n one-covers of Ht , which in turn arise from one-covers of induced
subgraphs, by Lemma 3.4. Since minimum vertex covers give rise to
one-covers, it will be informative to look at the structure of minimum
vertex covers of induced subgraphs of our family Ht .
Lemma 3.5. A minimum vertex cover of an odd k-cycle consists of
k+1
vertices.
2
Lemma 3.6. For the graph Ht , a minimum vertex cover of the induced
subgraph on {y1 } ∪ N (y1 ) consists of the vertices {x2 , y1 }. For i > 1, a
minimum vertex cover of the induced subgraph on {yi } ∪ N (yi ) consists
of exactly 3 vertices, one of which is yi .
4. Stability of Associated Primes
We restate our main theorem. Recall that Jt is the cover ideal of Ht
and Rt the polynomial ring associated to Ht .
Theorem 4.1. Let t ∈ Z+ . The associated primes of Rt /(Jt )n stabilize
at n = (χ(Ht ) − 1) + t = 2 + t.
This result will follow from the determination of the irreducible decompositions of (Jt )n in Theorem 4.11. Each component of the irreducible decomposition of (Jt )n is an irreducible monomial ideal of the
form (via11 , . . . , viakk ), for vij vertices of Ht (either x or y vertices). The
powers of the variables are in fact determined by the structure of the
subgraph induced by {vi1 , . . . , vik }. Thus, we abuse terminology in the
following way: for an ideal (via11 , . . . , viakk ) ⊆ Rt , we refer to each variable vij as a vertex, each power aj as a degree, and a = (a1 , . . . , ak ) as
a degree vector.
For any simple graph G with vertex set {v1 , . . . , vm }, let JG be the
cover ideal. Then by [3, Theorem 3.2], the irredundant irreducible
decomposition of (JG )2 is:
\
\
\
(JG )2 =
[(vi2 , vj ) ∩ (vi , vj2 )]
(vi21 , . . . , vi2k ),
{vi ,vj }∈EG

{vi1 ,...,vik }
an odd cycle

where the last intersection is over all subsets {vi1 , . . . , vik } such that
the subgraph induced by {vi1 , . . . , vik } is an odd cycle.
For our family of graphs, we generalize the above irreducible decomposition of (Jt )2 to one for (Jt )n , n > 2, by inductively adding

ASSOCIATED PRIMES OF CERTAIN GRAPH IDEALS

7

a minimum one-cover’s worth of degrees to each degree vector appearing in the irreducible decomposition of (Jt )n−1 . In other words,
if V c = (vic11 , . . . , vickk ) is an ideal in the irreducible decomposition of
(Jt )n−1 , and b is a minimum one-cover of the subgraph induced by
{vi1 , . . . , vik }, we show that V c+b is an ideal in the irreducible decomposition of (Jt )n .
To be more explicit, if the induced subgraph on {vi1 , vi2 , vi3 } ⊆ VHt is
a 3-cycle, then by [3, Theorem 3.2], (vi21 , vi22 , vi23 ) is a component of the
irreducible decomposition of (Jt )2 . We lift this to (Jt )n by showing that
(via11 , via22 , via33 ) is a component of the irreducible decomposition of (Jt )n
whenever a = (a1 , a2 , a3 ) is a degree vector for the induced subgraph
on {vi1 , vi2 , vi3 } obtained by adding (n − 2) minimum one-covers of
this subgraph to the degree vector c = (2, 2, 2). This results in many
different possibilities for a: by Lemma 3.5, a minimum one-cover of the
subgraph is of form (0, 1, 1),(1, 0, 1), or (1, 1, 0). Thus, adding (n − 2)
minimum one-covers to c leads to n2 possibilities for a.
Rather than writing out all these possibilities, we introduce below
the terminology n-admissible and n̂-admissible to distinguish degree
vectors of specific induced subgraphs of Ht . As the irreducible decompositions of (Jt )n are known for n ≤ 2, we work with n > 2 in the
following definitions.
Consider an arbitrary subset of vertices, V = {vi1 , . . . , vik } ⊆ VHt . If
the subgraph induced by V is an odd cycle, we call V an induced odd
cycle. Consider the corresponding degree vector a = (a1 , . . . , ak ).
Definition 4.2. A degree vector a corresponding to an induced odd
cycle V is n-admissible if a = (2, . . . , 2) + b1 + · · · + bn−2 where each
bi is a minimum one-cover of the cycle.
Remark 4.3. Note by Lemma 3.5 that for V an induced odd k-cycle,
if the corresponding degree vector a is n-admissible, then
k
X
i=1

ai = 2k + (n − 2)

k + 1
.
2

Now fix a positive integer r ≤ t and consider a subgraph induced by
vertices V ∪Yr = {vi1 , . . . , vik , yj1 , . . . , yjr } where V ⊆ VHt is an induced
odd cycle, Yr ⊆ {y1 , . . . , yt } (the specified y-vertices in Definition 3.1),
and N (Yr ) ⊆ V . We call such a subgraph an r-cluster, or an r-cluster
induced by V ∪ Yr , when we want to specify the vertices. Note that in
the definition of r-cluster, V can be an induced odd cycle of any length
on any of the vertices of Ht , so long as N (Yr ) ⊆ V . On the other hand,
Yr must contain exactly r vertices, and they must be y-vertices.

8

SARAH WOLFF

Recall that we assume n > 2 for the following definition.
Definition 4.4. A degree vector c corresponding to an r-cluster induced by V ∪ Yr , is n̂-admissible if c = d + e + f1 + · · · + fn−3 , where:

2 vji ∈ V \ N (Yr )
(1) di =
,
3
otherwise
(2) e|Yr ∪N (Yr ) = (0, . . . , 0),
(3) e|V \N (Yr ) is a minimum one-cover of the subgraph induced by
V \ N (Yr ),
(4) for all 1 ≤ i ≤ n − 3, fi |V \N (Yr ) is a minimum one-cover of the
subgraph induced by V \ N (Yr ),
(5) for all 1 ≤ i ≤ n − 3 and yjl ∈ Yr , fi |{yjl }∪N (yjl ) is a minimum
one-cover of the subgraph induced by {yjl } ∪ N (yjl ).
Example 4.5. Let n = 5. Consider the following 2-cluster of H4 : the
subgraph induced by
V ∪ Y2 = {x1 , x2 , x3 , x4 , y2 , x7 , x8 , y3 , x11 , x12 , x13 , x14 , x15 , y1 , y4 }.
Then d = (3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3), one of the two possibilities for e is (0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0) and two of the six possibilities for each fi , i ∈ {1, 2}, are (0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1)
and (0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1). Thus, the degree vector
c = (3, 5, 3, 3, 4, 3, 4, 3, 4, 4, 4, 5, 3, 5, 5)
is 5̂-admissible.
Remark 4.6. Consider the subgraph induced by {x1 , x2 , x3 , y1 }. By
Lemma 3.6, the minimum vertex cover of this subgraph is {x2 , y1 }.
Thus, for an arbitrary r-cluster, induced by V ∪ Yr , if y1 ∈ Yr , the
corresponding degrees for x2 and y1 would be 1 in each fj . By the same
lemma, for i > 1, a minimum vertex cover of the subgraph induced by
{yi } ∪ N (yi ) consists of yi and two vertices in N (yi ); thus, if yi ∈ Yr ,
then in each fj the corresponding degrees for yi and two vertices in
N (yi ) would be 1.
The following lemma is key to the proof of Theorem 4.11.
Lemma 4.7. Let r ≥ 1 and n > r + 1. Consider an arbitrary r-cluster
of Ht , induced by V ∪ Yr . Let c = (c1 , . . . , ck+r ) be a degree vector for

Pk+r
the r-cluster. If c is n̂-admissible then i=1
ci < r + k + n k+1
+r .
2
Proof. Consider an arbitrary r-cluster of Ht , induced by V ∪ Yr , and
suppose the corresponding degree vector, c, is n̂-admissible. We compute the degree sum imposed by the definition of n̂-admissible. This
degree sum depends on whether y1 ∈ Yr , or not.

ASSOCIATED PRIMES OF CERTAIN GRAPH IDEALS

9

First suppose y1 ∈ Yr . If c is n̂-admissible, then c = d + e + f1 +
· · · + fn−3 , with each degree vector as specified in Definition 4.4. We
first note that
k+r
X
di = 12 + 15(r − 1) + 2(k − 4r + 1).
i=1

Next, we claim
k+r
X

ei ≤

i=1

k − 4r + 1
.
2

To see this, we find a bound on the number of vertices in a minimum
vertex cover of the subgraph induced by V \ N (Yr ). First note that
k − 4r + 1 vertices comprise V \ N (Yr ). Further, the subgraph of Ht
induced by V \ N (Yr ) consists of disjoint subgraphs of V induced by
one or more subsets V1 , . . . , Vl ⊂ V . Let vα be the number of vertices
in Vα , 1 ≤ α ≤ l. If vα is even, a minimum vertex cover of the subgaph
induced by Vα consists of v2α vertices, while if vα is odd, a minimum
vertex cover consists of vα2−1 vertices. Hence,
k+r
X
i=1

l
X vα − 1
X vα
1X
k − 4r + 1
ei =
+
≤
vα =
,
2
2
2
2
v
even
α=1
v odd
α

α

as claimed.
Finally, by Lemma 3.6 and the above claim we see that for each fj ,
1 ≤ j ≤ n − 3,
k+r
X

fji ≤ 2 + 3(r − 1) +

i=1

Since the degree sum of fj ,
k+r
X
i=1

ci =

k+r
X

Pk+r
i=1

di +

i=1

k − 4r + 1
.
2

fji , is independent of j, we have:

k+r
X

ei + (n − 3)

i=1

k+r
X

f ji ,

i=1

for any j ∈ {1, . . . , n − 3}. The inequality of the lemma then reduces
to showing that r + 1 < n, which is true by assumption.
Next suppose y1 ∈
/ Yr . Here,
k+r
X

di = 15r + 2(k − 4r),

i=1

and we claim
k+r
X
i=1

ei ≤

k − 4r − 1
.
2

10

SARAH WOLFF

To see this, note that in this case k − 4r vertices comprise V \ N (Yr ).
As above, the subgraph of Ht induced by V \ N (Yr ) consists of disjoint
subgraphs of V induced by subsets V1 , . . . , Vl ⊂ V . Further, because V
is an induced odd cycle, k − 4r is odd, so at least one of the subsets,
without loss V1 , has an odd number of vertices, v1 . Hence, as above,
k+r
X
i=1

l
X vα − 1
X vα
X
 k − 4r − 1
1
ei =
+
≤ v1 − 1 +
vα =
,
2
2
2
2
v even
α=2
v odd
α

α

as claimed.
Finally, by Lemma 3.6 and the above claim we see that for each fj ,
1 ≤ j ≤ n − 3,
k+r
X
k − 4r − 1
fji ≤ 3r +
.
2
i=1
Pk+r
Again, the degree sum of fj ,
i=1 fji , is independent of j, and the
inequality of the lemma reduces to showing r + 1 < n.

We now define several ideals to simplify the statement of Theorem
4.11. Fix a graph Ht and a positive integer n. For an arbitrary set
of vertices V = {vi1 , . . . , vik } of Ht with corresponding degree vector
a = (a1 , . . . , ak ), let V a denote the ideal (via11 , . . . , viakk ). Again, we
a
remind the reader of our convention to omit vijj when aj = 0.
Definition 4.8.
\
At,n =

(vin , vj ) ∩ (vin−1 , vj2 ) ∩ · · · ∩ (vi2 , vjn−1 ) ∩ (vi , vjn ).

{vi ,vj }∈EHt

\

Definition 4.9. Bt,n =

V a.

subgraph of Ht induced
by V an odd cycle,
a n-admissible
r
Definition 4.10. Dt,n
=

\

(V ∪ Yr )c .

subgraph of Ht induced
by V ∪Yr an r-cluster,
c n̂-admissible

We now give the irreducible decompositions of (Jt )n :
Theorem 4.11. Let t ∈ Z+ and let Jt be the cover ideal of Ht . For
n > 2, (Jt )n has the following irredundant irreducible decomposition:
n

(Jt ) = At,n ∩ Bt,n ∩

n−2
\
r=1

r
Dt,n

ASSOCIATED PRIMES OF CERTAIN GRAPH IDEALS

11

T
r
Proof. For t ∈ N and n > 2, let L be the ideal At,n ∩ Bt,n ∩ n−2
r=1 Dt,n .
Let M be a minimal generator of (Jt )n . We
show M is in L by showing
Tn−2
r
separately.
it is in each of the ideals At,n , Bt,n , and r=1 Dt,n
First suppose M ∈
/ Bt,n . Since M is a minimal generator of the
am
, for {v1 , . . . , vm } the vertices of
monomial ideal (Jt )n , M = v1a1 · · · vm
Ht . By Lemma 3.3 the powers, a = (a1 , . . . , am ), when viewed as a
degree vector of Ht form an n-cover that can be written as the sum of
n one-covers, bi , of Ht : a = b1 + · · · + bn . Let V = {vj1 , . . . , vjk } be an
arbitrary induced odd cycle of Ht . Since a is an n-cover of Ht , a|V is an
n-cover of the odd cycle. Further, for 1 ≤ i ≤ n, since bi is a one-cover
of Ht , bi |V is a one-cover of the cycle. Then a|V = b1 |V + · · · + bn |V
with each bi |V a one-cover of the subgraph induced by V . Thus, a|V =
(aj1 , . . . , ajk ) is an n-cover of the cycle that can be written as the sum

P
of n one-covers. Then by Lemma 3.5, ki=1 aji ≥ n k+1
. However,
2
M ∈
/ Bt,n , so M ∈
/ V u for some n-admissible u. Thus, in M each
variable vij ∈ V has degree less than uj , so
k
X
i=1

aj i ≤

k
X

(ui − 1) = k + (n − 2)

i=1

k + 1
,
2



k+1
by Remark 4.3. But k + (n − 2) k+1
<
n
, so a|V is not an n2
2
cover of the cycle that can be written as the sum of n one-covers, a
contradiction. Thus, M ∈ Bt,n .
T
a1
r
am
Now suppose M ∈
/ n−2
r=1 Dt,n . Again, M = v1 · · · vm is a minimal
generator of (Jt )n so the powers, a = (a1 , . . . , am ), when viewed as a
degree vector of Ht form an n-cover that can be written as the sum of
n one-covers, bi , of Ht : a = b1 + · · · + bn . For r ≤ n − 2, consider
an arbitrary r-cluster of Ht , induced by V ∪ Yr . As above, a|V ∪Yr is
an n-cover of the r-cluster and for 1 ≤ i ≤ n, bi |V ∪Yr is a one-cover of
the r-cluster, so a|V ∪Yr = (al1 , . . . , alk+r ) is an n-cover of the r-cluster
that
as the sum of n one-covers.
Tn−2 r Then by Lemma 3.6,
Pk+rcan be written
k+1
+ r . However, M ∈
/ r=1 Dt,n , so M ∈
/ (V ∪ Yr )c ,
i=1 ali ≥ n
2
for some n̂-admissible c. Thus, as in the previous case,
k+r
X
i=1

ali ≤

k+r
X

(ci − 1).

i=1

But since n ≥ r + 2, Lemma 4.7 shows
k+r
X
i=1

(ci − 1) < n


k+1
+r ,
2

12

SARAH WOLFF

so a|V ∪Yr is not an n-cover of the r-cluster that can
be written as the
Tn−2
r
sum of n one-covers, a contradiction. Thus, M ∈ r=1 Dt,n
.
We finally note by Lemma 3.2 that M ∈ At,n . Hence, (Jt )n ⊆ L.
Now let P be a minimal generator of L. The ideal L is an intersection
of monomial ideals, so P = via11 · · · viamm . By definition, P ∈ At,n ; therefore, the powers a = (a1 , . . . , am ), of the variables of P when viewed
as a degree vector of Ht form an n-cover. By Lemma 3.3, it suffices to
show a can be written as the sum of n one-covers of Ht .
Consider an arbitrary one-cluster of Ht , induced by V ∪ Y1 . Note
that Ht can be written as a union of one-clusters. Thus, by Lemma 3.4,
it suffices to show that a|V ∪Y1 can be written as a sum of n one-covers
of the one-cluster. Applying Lemma 3.4 again to the subgraph induced
by V ∪ Y1 = {vi1 , . . . , vik , yj1 }, it suffices to show a|V and a|{yj1 }∪N (yj1 )
can be written as a sum of n one-covers of the subgraphs induced by
V and {yj1 } ∪ N (yj1 ), respectively.
Let V be an induced odd k-cycle of Ht . Since P ∈ Bt,n , P ∈ V u
for some n-admissible u = (u1 , . . . , uk ). Thus, we need to show that
u can be written as the sum of n one-covers of V . By Definition 4.2,
u = (2, . . . , 2) + b1 + · · · + bn−2 with each bi a one-cover of V . Thus,
we need only show that (2, . . . , 2) can be written as a sum of two onecovers of V , but this is clear because (2, . . . , 2) = (1, . . . , 1) + (1, . . . , 1),
which are trivially one-covers of V .
Now consider the subgraph induced by {yj1 } ∪ N (yj1 ). Since P ∈
Tn−2 r
c
r=1 Dt,n , P ∈ (V ∪ Y1 ) , for some n̂-admissible c. Thus, we need
to show c|{yj1 }∪N (yj1 ) can be written as a sum of n one-covers of the
subgraph induced by {yj1 } ∪ N (yj1 ). By Definition 4.4, c = d + e +
f1 + · · · + fn−3 with each fi a one-cover of the subgraph induced by
{yj1 } ∪ N (yj1 ). Further, di = 3 for each vertex in {yj1 } ∪ N (yj1 ), so we
need only show that (3, . . . , 3) can be written as a sum of 3 one-covers
of the subgraph induced by {yj1 } ∪ N (yj1 ), but this is clear by Lemma
3.6.
Thus, for an arbitrary one-cluster, induced by V ∪ Y1 , a|V ∪Y1 can be
written as the sum of n one-covers of the subgraph induced by V ∪ Y1 .
This proves that a can be written as the sum of n one-covers of Ht .
Hence, L ⊆ (Jt )n .

Our main theorem now follows as a corollary to Theorem 4.11:
Proof of Theorem 4.1. For t ∈ Z+ consider the graph Ht and label
the vertices VHt = {v1 , . . . , vm } = X ∪ Y , where X (respectively, Y )
represents the set of x-vertices (respectively, y-vertices) as in Definition

ASSOCIATED PRIMES OF CERTAIN GRAPH IDEALS

13

3.1 . By Theorem 4.11, for n > 2 it follows that a prime P is in
Ass(Rt /(Jt )n ) if and only if:
(a) P = (vi , vj ) where {vi , vj } ∈ EHt ,
(b) P = (vi1 , . . . , vik ), where the subgraph induced by {vi1 , . . . , vik }
is an odd cycle,
or,
(c) For 1 ≤ r ≤ n − 2, P = (vi1 , . . . , vik , yj1 , . . . , yjr ), where the
subgraph induced by {vi1 , . . . , vik , yj1 , . . . , yjr } is an r-cluster.
By definition, Ht has exactly t y-vertices, so Ht has a t-cluster, namely
the graph Ht itself. Thus, by (c) above, the ideal (v1 , . . . , vm ) is an
element of Ass(Rt /(Jt )n ) for n ≥ t + 2, but not for n < t + 2. Thus, the
associated primes do not stabilize until at least t+2. Further, note that
the ideals of (a) and (b) are elements of Ass(Rt /(Jt )n ) for all n ≥ 2,
so the only prime ideals not in Ass(Rt /(Jt )2+t ) that could appear in
Ass(Rt /(Jt )n ) for n > 2 + t would be ideals that fall into category (c).
However, for 1 ≤ r ≤ t, ideals whose generators correspond to the
vertices of r-clusters are elements of Ass(Rt /(Jt )2+t ), so the only new
ideals in Ass(Rt /(Jt )n ) for n > 2 + t would be those whose generators
correspond to the vertices of r-clusters for r > t. The largest r for
which Ht has an r-cluster is r = t; thus, no such new ideals exist in
Ass(Rt /(Jt )n ) for n > 2 + t. Thus, the associated primes of Ht stabilize
at 2 + t.

Remark 4.12. We note that our family of graphs can be generalized
slightly. The proof of Theorem 4.11 used the definition n̂-admissible in
two ways— to show that the degree vectors can be written as n onecovers, and to use the degree argument of Lemma 4.7. Both facts remain unchanged if the induced (4t − 1)-cycle is instead an odd cycle of
any length greater than 4t − 1 (or in the case of H1 , if the 5-cycle is
any odd cycle of length greater than 5). Further, for i > 1, yi could
have more than 4 neighbors, as long as these neighbors are distinct from
N (yj ), j 6= i, and the degree argument of Lemma 4.7 is still satisfied.
5. Acknowledgements
Many of the results of this paper started as computer experiments
using the program Macaulay 2 [5]. The author would like to thank
Amelia Taylor for introducing her to the subject and for her invaluable
support and guidance throughout the research and writing processes,
Thomas Shemanske for his help in the editing process, and Adam Van
Tuyl for a helpful discussion of Lemma 3.3. We also thank an anonymous referee for their insights and suggestions for improvement.

14

SARAH WOLFF

References
1. Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184,
Springer-Verlag, New York, 1998. MR 1633290 (99h:05001)
2. M. Brodmann, Asymptotic stability of Ass(M/I n M ), Proc. Amer. Math. Soc.
74 (1979), no. 1, 16–18. MR 521865 (80c:13012)
3. Christopher A. Francisco, Huy Tài Hà, and Adam Van Tuyl, Associated primes
of monomial ideals and odd holes in graphs, J. Algebraic Combin. 32 (2010),
no. 2, 287–301. MR 2661419 (2011e:05133)
, Colorings of hypergraphs, perfect graphs, and associated primes of
4.
powers of monomial ideals, J. Algebra 331 (2011), 224–242. MR 2774655
(2012b:13054)
5. Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in algebraic geometry,
Available at
http://www.math.uiuc.edu/Macaulay2/.
6. Jürgen Herzog, Takayuki Hibi, and Ngô Viêt Trung, Symbolic powers of monomial ideals and vertex cover algebras, Adv. Math. 210 (2007), no. 1, 304–322.
MR 2298826 (2007m:13005)
7. Ezra Miller and Bernd Sturmfels, Combinatorial commutative algebra, Graduate
Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005. MR 2110098
(2006d:13001)
8. Aron Simis, Wolmer V. Vasconcelos, and Rafael H. Villarreal, On the ideal theory
of graphs, J. Algebra 167 (1994), no. 2, 389–416. MR 1283294 (95e:13002)
9. Rafael H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66 (1990),
no. 3, 277–293. MR 1031197 (91b:13031)

