Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones

Let G be a simple graph and let Ic(G) be its ideal of vertex covers. We give a graph theoretical description of the irreducible b-vertex covers of G, i.e., we describe the minimal generators of the symbolic Rees algebra of Ic(G). Then we study the irreducible b-vertex covers of the blocker of G, i.e...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
Hauptverfasser:	Dupont, L.D., Villarreal, R.H.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2010
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/154873
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones / L.A. Dupont, R.H. Villarreal // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 2. — С. 64–86. — Бібліогр.: 30 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-154873
record_format	dspace
spelling	irk-123456789-1548732019-06-17T01:31:23Z Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones Dupont, L.D. Villarreal, R.H. Let G be a simple graph and let Ic(G) be its ideal of vertex covers. We give a graph theoretical description of the irreducible b-vertex covers of G, i.e., we describe the minimal generators of the symbolic Rees algebra of Ic(G). Then we study the irreducible b-vertex covers of the blocker of G, i.e., we study the minimal generators of the symbolic Rees algebra of the edge ideal of G. We give a graph theoretical description of the irreducible binary b-vertex covers of the blocker of G. It is shown that they correspond to irreducible induced subgraphs of G. As a byproduct we obtain a method, using Hilbert bases, to obtain all irreducible induced subgraphs of G. In particular we obtain all odd holes and antiholes. We study irreducible graphs and give a method to construct irreducible b-vertex covers of the blocker of G with high degree relative to the number of vertices of G. 2010 Article Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones / L.A. Dupont, R.H. Villarreal // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 2. — С. 64–86. — Бібліогр.: 30 назв. — англ. 2000 Mathematics Subject Classification:13F20, 05C75, 05C65, 52B20. http://dspace.nbuv.gov.ua/handle/123456789/154873 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	Let G be a simple graph and let Ic(G) be its ideal of vertex covers. We give a graph theoretical description of the irreducible b-vertex covers of G, i.e., we describe the minimal generators of the symbolic Rees algebra of Ic(G). Then we study the irreducible b-vertex covers of the blocker of G, i.e., we study the minimal generators of the symbolic Rees algebra of the edge ideal of G. We give a graph theoretical description of the irreducible binary b-vertex covers of the blocker of G. It is shown that they correspond to irreducible induced subgraphs of G. As a byproduct we obtain a method, using Hilbert bases, to obtain all irreducible induced subgraphs of G. In particular we obtain all odd holes and antiholes. We study irreducible graphs and give a method to construct irreducible b-vertex covers of the blocker of G with high degree relative to the number of vertices of G.
format	Article
author	Dupont, L.D. Villarreal, R.H.
spellingShingle	Dupont, L.D. Villarreal, R.H. Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones Algebra and Discrete Mathematics
author_facet	Dupont, L.D. Villarreal, R.H.
author_sort	Dupont, L.D.
title	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
title_short	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
title_full	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
title_fullStr	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
title_full_unstemmed	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
title_sort	symbolic rees algebras, vertex covers and irreducible representations of rees cones
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2010
url	http://dspace.nbuv.gov.ua/handle/123456789/154873
citation_txt	Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones / L.A. Dupont, R.H. Villarreal // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 2. — С. 64–86. — Бібліогр.: 30 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT dupontld symbolicreesalgebrasvertexcoversandirreduciblerepresentationsofreescones AT villarrealrh symbolicreesalgebrasvertexcoversandirreduciblerepresentationsofreescones
first_indexed	2025-07-14T06:56:26Z
last_indexed	2025-07-14T06:56:26Z
_version_	1837604470088794112
fulltext	Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 10 (2010). Number 2. pp. 64 – 86 c© Journal “Algebra and Discrete Mathematics” Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones Luis A. Dupont and Rafael H. Villarreal Communicated by B. V. Novikov Abstract. Let G be a simple graph and let Ic(G) be its ideal of vertex covers. We give a graph theoretical description of the irreducible b-vertex covers of G, i.e., we describe the minimal generators of the symbolic Rees algebra of Ic(G). Then we study the irreducible b-vertex covers of the blocker of G, i.e., we study the minimal generators of the symbolic Rees algebra of the edge ideal of G. We give a graph theoretical description of the irreducible binary b-vertex covers of the blocker of G. It is shown that they correspond to irreducible induced subgraphs of G. As a byproduct we obtain a method, using Hilbert bases, to obtain all irreducible induced subgraphs of G. In particular we obtain all odd holes and antiholes. We study irreducible graphs and give a method to construct irreducible b-vertex covers of the blocker of G with high degree relative to the number of vertices of G. Introduction A clutter C with vertex set X = {x1, . . . , xn} is a family of subsets of X, called edges, none of which is included in another. The set of vertices and edges of C are denoted by V (C) and E(C) respectively. A basic example of a clutter is a graph. Let R = K[x1, . . . , xn] be a polynomial ring over a field K. The edge ideal of C, denoted by I(C), is the ideal of R generated Partially supported by CONACyT grant 49251-F and SNI, México. 2000 Mathematics Subject Classification: 13F20, 05C75, 05C65, 52B20. Key words and phrases: edge ideal, symbolic Rees algebras, perfect graph, irre- ducible vertex covers, irreducible graph, Alexander dual, blocker, clutter. L. A. Dupont, R. H. Villarreal 65 by all monomials ∏ xi∈e xi such that e ∈ E(C). The assignment C 7→ I(C) establishes a natural one to one correspondence between the family of clutters and the family of square-free monomial ideals. Let C be a clutter and let F = {xv1 , . . . , xvq} be the minimal set of generators of its edge ideal I = I(C). As usual we use xa as an abbreviation for xa11 · · ·xann , where a = (a1, . . . , an) ∈ Nn. The n× q matrix with column vectors v1, . . . , vq will be denoted by A, it is called the incidence matrix of C. The blowup algebra studied here is the symbolic Rees algebra: Rs(I) = R⊕ I(1)t⊕ · · · ⊕ I(i)ti ⊕ · · · ⊂ R[t], where t is a new variable and I(i) is the ith symbolic power of I. Closely related to Rs(I) is the Rees algebra of I: R[It] := R⊕ It⊕ · · · ⊕ Iiti ⊕ · · · ⊂ R[t]. The study of symbolic powers of edge ideals was initiated in [21] and further elaborated on in [1, 9, 12, 13, 14, 22, 28]. By a result of Lyubeznik [17], Rs(I) is a K-algebra of finite type. In general the minimal set of generators of Rs(I) as a K-algebra is very hard to describe in terms of C (see [1]). There are two exceptional cases. If the clutter C has the max-flow min-cut property, then by a result of [13] we have Ii = I(i) for all i ≥ 1, i.e., Rs(I) = R[It]. If G is a perfect graph, then the minimal generators of Rs(I(G)) are in one to one correspondence with the cliques (complete subgraphs) of G [28]. We shall be interested in studying the minimal set of generators of Rs(I) using polyhedral geometry. Let G be a graph and let Ic(G) be the Alexander dual of I(G), see definition below. Some of the main results of this paper are graph theoretical descriptions of the minimal generators of Rs(I(G)) and Rs(Ic(G)). In Sections 1 and 2 we show that both algebras encode combinatorial information of the graph which can be decoded using integral Hilbert bases. The Rees cone of I, denoted by R+(I), is the polyhedral cone consisting of the non-negative linear combinations of the set A′ = {e1, . . . , en, (v1, 1), . . . , (vq, 1)} ⊂ Rn+1, where ei is the ith unit vector. A subset C ⊂ X is called a vertex cover of the clutter C if every edge of C contains at least one vertex of C. A subset C ⊂ X is called a minimal vertex cover of the clutter C if C is a vertex cover of C and no proper subset of C is a vertex cover of C. Let p1, . . . , ps be the minimal primes of the edge ideal I = I(C) and let Ck = {xi\|xi ∈ pk} (k = 1, . . . , s) 66 Symbolic Rees algebras be the corresponding minimal vertex covers of C, see [27, Proposition 6.1.16]. Recall that the primary decomposition of the edge ideal of C is given by I(C) = (C1) ∩ (C2) ∩ · · · ∩ (Cs), where (Ck) denotes the ideal of R generated by Ck. In particular observe that the height of I(C) equals the number of vertices in a minimum vertex cover of C. This number is called the vertex covering number of C and is denoted by α0(C). The ith symbolic power of I is given by I(i) = S−1Ii ∩R for i ≥ 1, where S = R \ ∪sk=1pi and S−1Ii is the localization of Ii at S. In our situation the ith symbolic power of I has a simple expression: I(i) = p i 1 ∩ · · · ∩ p i s, see [27]. The Rees cone of I is a finitely generated rational cone of dimension n + 1. Hence by the finite basis theorem [30, Theorem 4.11] there is a unique irreducible representation R+(I) = H+ e1 ∩H + e2 ∩ · · · ∩H+ en+1 ∩H+ ℓ1 ∩H+ ℓ2 ∩ · · · ∩H+ ℓr (1) such that each ℓk is in Zn+1, the non-zero entries of each ℓk are relatively prime, and none of the closed halfspaces H+ e1 , . . . , H + en+1 , H+ ℓ1 , . . . , H+ ℓr can be omitted from the intersection. Here H+ a denotes the closed halfspace H+ a = {x\| 〈x, a〉 ≥ 0} and Ha stands for the hyperplane through the origin with normal vector a, where 〈 , 〉 denotes the standard inner product. The facets (i.e., the proper faces of maximum dimension or equivalently the faces of dimension n) of the Rees cone are exactly: Fi = Hei ∩ R+(I), i = 1, . . . , n+ 1, Hℓ1 ∩ R+(I), . . . , Hℓr ∩ R+(I). According to [9, Lemma 3.1] we may always assume that ℓk = −en+1 + ∑ xi∈Ck ei for 1 ≤ k ≤ s, i.e., each minimal vertex cover of C determines a facet of the Rees cone and every facet of the Rees cone satisfying 〈ℓk, en+1〉 = −1 must be of the form ℓk = −en+1 + ∑ xi∈Ck ei for some minimal vertex cover Ck of C. This is quite interesting because this is saying that the Rees cone of I(C) is a carrier of combinatorial information of the clutter C. Thus we can extract the primary decomposition of I(C) from the irreducible representation of R+(I(C)). Rees cones have been used to study algebraic and combinatorial prop- erties of blowup algebras of square-free monomial ideals and clutters [9, 12, 29]. Blowup algebras are interesting objects of study in algebra and geometry [25]. L. A. Dupont, R. H. Villarreal 67 The ideal of vertex covers of C is the square-free monomial ideal Ic(C) = (xu1 , . . . , xus) ⊂ R, where xuk = ∏ xi∈Ck xi. Often the ideal Ic(C) is called the Alexander dual of I(C). The clutter Υ(C) associated to Ic(C) is called the blocker of C, see [5]. Notice that the edges of Υ(C) are precisely the minimal vertex covers of C. If G is a graph, then Rs(Ic(G)) is generated as a K-algebra by elements of degree in t at most two [14, Theorem 5.1]. One of the main result of Section 1 is a graph theoretical description of the minimal generators of Rs(Ic(G)) (see Theorem 1.7). As an application we recover an explicit description [24], in terms of closed halfspaces, of the edge cone of a graph (Corollary 1.10). The symbolic Rees algebra of the ideal Ic(C) can be interpreted in terms of “k-vertex covers” [14] as we now explain. Let a = (a1, . . . , an) 6= 0 be a vector in Nn and let b ∈ N. We say that a is a b-vertex cover of I (or C) if 〈vi, a〉 ≥ b for i = 1, . . . , q. Often we will call a b-vertex cover simply a b-cover . This notion plays a role in combinatorial optimization [20, Chapter 77, p. 1378] and algebraic combinatorics [14, 15]. The algebra of covers of I (or C), denoted by Rc(I), is the K-subalgebra of K[t] generated by all monomials xatb such that a is a b-cover of I. We say that a b-cover a of I is reducible if there exists an i-cover c and a j-cover d of I such that a = c+ d and b = i+ j. If a is not reducible, we call a irreducible. The irreducible 0 and 1 covers of C are the unit vector e1, . . . , en and the incidence vectors u1, . . . , us of the minimal vertex covers of C, respectively. The minimal generators of Rc(I) as a K-algebra correspond to the irreducible covers of I. Notice the following dual descriptions: I(b) = ({xa\| 〈a, ui〉 ≥ b for i = 1, . . . , s}), J (b) = ({xa\| 〈a, vi〉 ≥ b for i = 1, . . . , q}), where J = Ic(C). Hence Rc(I) = Rs(J) and Rc(J) = Rs(I). In general each ℓi occurring in Eq. (1) determines a minimal generator of Rs(Ic(C)). Indeed if we write ℓi = (ai,−di), where ai ∈ Nn, di ∈ N, then ai is an irreducible di-cover of I (Lemma 1.8). Let Fn+1 be the facet of R+(I) determined by the hyperplane Hen+1 . Thus we have a map ψ: {Facets of R+(I(C))} \ {Fn+1} ψ −→ Rs(Ic(C)) Hℓk ∩ R+(I) ψ −→ xaktdk , where ℓk = (ak,−dk) Hei ∩ R+(I) ψ −→ xi whose image provides a good approximation for the minimal set of gener- ators of Rs(Ic(C)) as a K-algebra. Likewise the facets of R+(Ic(C)) give 68 Symbolic Rees algebras an approximation for the minimal set of generators of Rs(I(C)). In Ex- ample 1.9 we show a connected graph G for which the image of the map ψ does not generates Rs(Ic(G)). For balanced clutters, i.e., for clutters without odd cycles, the image of the map ψ generates Rs(Ic(C)). This follows from [12, Propositions 4.10 and 4.11]. In particular the image of the map ψ generates Rs(Ic(C)) when C is a bipartite graph. It would be interesting to characterize when the irreducible representation of the Rees cone determine the irreducible covers. The Simis cone of I is the rational polyhedral cone: Cn(I) = H+ e1 ∩ · · · ∩H+ en+1 ∩H+ (u1,−1) ∩ · · · ∩H+ (us,−1), Simis cones were introduced in [9] to study symbolic Rees algebras of square-free monomial ideals. If H is an integral Hilbert basis of Cn(I), then Rs(I(C)) equals K[NH], the semigroup ring of NH (see [9, Theorem 3.5]). This result is interesting because it allows us to compute the minimal generators of Rs(I(C)) using Hilbert bases. The program Normaliz [3] is suitable for computing Hilbert bases. There is a description of H valid for perfect graphs [28]. Perfect graphs are defined in Section 2. If G is a perfect graph, the irreducible b-covers of Υ(G) correspond to cliques of G [28] (cf. Corollary 2.5). In this case, setting C = Υ(G), it turns out that the image of ψ generates Rs(Ic(Υ(G))). Notice that Ic(Υ(G)) is equal to I(G). In Section 2 we introduce and study the concept of an irreducible graph. A b-cover a = (a1, . . . , an) is called binary if ai ∈ {0, 1} for all i. We present a graph theoretical description of the irreducible binary b-vertex covers of the blocker of G (see Theorem 2.9). It is shown that they are in one to one correspondence with the irreducible induced subgraphs of G. As a byproduct we obtain a method, using Hilbert bases, to obtain all irreducible induced subgraphs of G (see Corollary 2.12). In particular we obtain all induced odd cycles and all induced complements of odd cycles. These cycles are called the odd holes and odd antiholes of the graph. It was shown recently [10] that p is an associated prime of Ic(G)2 if and only if p is generated by the vertices of an edge of G or p is generated by the vertices of an odd hole of G. The proof of this remarkable result makes use of Theorem 1.7. Odd holes and antiholes play a major role in graph theory. In [4] it is shown that a graph G is perfect if and only if G has no odd holes or antiholes of length at least five. We give a procedure to build irreducible graphs (Proposition 2.18) and a method to construct irreducible b-vertex covers of the blocker of G with high degree relative to the number of vertices of G (see Corollaries 2.24 and 2.25). Along the paper we introduce most of the notions that are relevant for our purposes. For unexplained terminology we refer to [6, 18, 25]. L. A. Dupont, R. H. Villarreal 69 1. Blowup algebras of ideals of vertex covers Let G be a simple graph with vertex set X = {x1, . . . , xn}. In what follows we shall always assume that G has no isolated vertices. Here we will give a graph theoretical description of the irreducible b-covers of G, i.e., we will describe the symbolic Rees algebra of Ic(G). Let S be a set of vertices of G. The neighbor set of S, denoted by NG(S), is the set of vertices of G that are adjacent with at least one vertex of S. The set S is called independent if no two vertices of S are adjacent. The empty set is regarded as an independent set whose incidence vector is the zero vector. Notice the following duality: S is a maximal independent set of G (with respect to inclusion) if and only if X \S is a minimal vertex cover of G. Lemma 1.1. If a = (ai) ∈ Nn is an irreducible k-cover of G, then 0 ≤ k ≤ 2 and 0 ≤ ai ≤ 2 for i = 1, . . . , n. Proof. Recall that a is a k-cover of G if and only if ai + aj ≥ k for each edge {xi, xj} of G. If k = 0 or k = 1, then by the irreducibility of a it is seen that either a = ei for some i or a = ei1 + · · ·+ eir for some minimal vertex cover {xi1 , . . . , xir} of G. Thus we may assume that k ≥ 2. Case (I): ai ≥ 1 for all i. Clearly 1 = (1, . . . , 1) is a 2-cover. If a−1 6= 0, then a− 1 is a k− 2 cover and a = 1+ (a− 1), a contradiction to a being an irreducible k-cover. Hence a = 1. Pick any edge {xi, xj} of G. Since a is a k-cover, we get 2 = ai + aj ≥ k and k must be equal to 2. Case (II): ai = 0 for some i. We may assume ai = 0 for 1 ≤ i ≤ r and ai ≥ 1 for i > r. Notice that the set S = {x1, . . . , xr} is independent because if {xi, xj} is an edge and 1 ≤ i < j ≤ r, then 0 = ai + aj ≥ k, a contradiction. Consider the neighbor set NG(S) of S. We may assume that NG(S) = {xr+1, . . . , xs}. Observe that ai ≥ k ≥ 2 for i = r+1, . . . , s, because a is a k-cover. Write a = (0, . . . , 0, ar+1 − 2, . . . , as − 2, as+1 − 1, . . . , an − 1)+ (0, . . . , 0 ︸︷︷︸ r , 2, . . . , 2 ︸︷︷︸ s−r , 1, . . . , 1 ︸︷︷︸ n−s ) = c+ d. Clearly d is a 2-cover. If c 6= 0, using that ai ≥ k ≥ 2 for r + 1 ≤ i ≤ s and ai ≥ 1 for i > s it is not hard to see that c is a (k − 2)-cover. This gives a contradiction, because a = c+ d. Hence c = 0. Therefore ai = 2 for r < i ≤ s, ai = 1 for i > s, and k = 2. The next result complements the fact that the symbolic Rees alge- bra of Ic(G) is generated by monomials of degree in t at most two [14, Theorem 5.1]. 70 Symbolic Rees algebras Corollary 1.2. Rs(Ic(G)) is generated as a K-algebra by monomials of degree in t at most two and total degree at most 2n. Proof. Let xatk be a minimal generator of Rs(Ic(G)) as a K-algebra. Then a = (a1, . . . , an) is an irreducible k-cover of G. By Lemma 1.1 we obtain that 0 ≤ k ≤ 2 and 0 ≤ ai ≤ 2 for all i. If k = 0 or k = 1, we get that the degree of xatk is at most n. Indeed when k = 0 or k = 1, one has a = ei or a = ∑ xi∈C ei for some minimal vertex cover C of G, respectively. If k = 2, by the proof of Lemma 1.1 either a = 1 or ai = 0 for some i. Thus deg(xa) ≤ 2(n− 1). Let I = I(G) be the edge ideal of G. For use below consider the vectors ℓ1, . . . , ℓr that occur in the irreducible representation of R+(I) given in Eq. (1). Corollary 1.3. If ℓi = (ℓi1, . . . , ℓin,−ℓi(n+1)), then 0 ≤ ℓij ≤ 2 for j = 1, . . . , n and 1 ≤ ℓi(n+1) ≤ 2. Proof. It suffices to observe that (ℓi1, . . . , ℓin) is an irreducible ℓi(n+1)-cover of G and to apply Lemma 1.1. Lemma 1.4. a = (1, . . . , 1) is an irreducible 2-cover of G if and only if G is non bipartite. Proof. ⇒) We proceed by contradiction assuming that G is a bipar- tite graph. Then G has a bipartition (V1, V2). Set a′ = ∑ xi∈V1 ei and a′′ = ∑ xi∈V2 ei. Since V1 and V2 are minimal vertex covers of G, we can decompose a as a = a′ + a′′, where a′ and a′′ are 1-covers, which is impossible. ⇐) Notice that a cannot be the sum of a 0-cover and a 2-cover. Indeed if a = a′ + a′′, where a′ is a 0-cover and a′′ is a 2-cover, then a′′ has an entry ai equal to zero. Pick an edge {xi, xj} incident with xi, then 〈a′′, ei + ej〉 ≤ 1, a contradiction. Thus we may assume that a = c + d, where c, d are 1-covers. Let Cr be an odd cycle of G of length r. Notice that any vertex cover of Cr must contain a pair of adjacent vertices because r is odd. Clearly a vertex cover of G is also a vertex cover of the subgraph Cr. Hence the vertex covers of G corresponding to c and d must contain a pair of adjacent vertices, a contradiction because c and d are complementary vectors and the complement of a vertex cover is an independent set. Definition 1.5. Let A be the incidence matrix of a clutter C. A clutter C has a cycle of length r if there is a square sub-matrix of A of order r ≥ 3 with exactly two 1’s in each row and column. A clutter without odd cycles is called balanced. L. A. Dupont, R. H. Villarreal 71 Proposition 1.6 ([12, Proposition 4.11]). If C is a balanced clutter, then Rs(Ic(C)) = R[Ic(C)t]. This result was first shown for bipartite graphs in [11, Corollary 2.6] and later generalized to balanced clutters [12] using an algebro combinatorial description of clutters with the max-flow min-cut property [13]. Let S be a set of vertices of a graph G, the induced subgraph on S, denoted by 〈S〉, is the maximal subgraph of G with vertex set S. The next result has been used in [10] to show that any associated prime of Ic(G) 2 is generated by the vertices of an edge of G or it is generated by the vertices of an odd hole of G. We come to the main result of this section. Theorem 1.7. Let 0 6= a = (ai) ∈ Nn and let Υ(G) be the family of minimal vertex covers of a graph G. (i) If G is bipartite, then a is an irreducible b-cover of G if and only if b = 0 and a = ei for some 1 ≤ i ≤ n or b = 1 and a = ∑ xi∈C ei for some C ∈ Υ(G). (ii) If G is non-bipartite, then a is an irreducible b-cover if and only if a has one of the following forms: (a) (0-covers) b = 0 and a = ei for some 1 ≤ i ≤ n, (b) (1-covers) b = 1 and a = ∑ xi∈C ei for some C ∈ Υ(G), (c) (2-covers) b = 2 and a = (1, . . . , 1), (d) (2-covers) b = 2 and up to permutation of vertices a = (0, . . . , 0 ︸︷︷︸ \|A\| , 2, . . . , 2 ︸︷︷︸ \|NG(A)\| , 1, . . . , 1) for some independent set of vertices A 6= ∅ of G such that (d1) NG(A) is not a vertex cover of G and V 6= A ∪NG(A), (d2) the induced subgraph 〈V \ (A ∪NG(A))〉 has no isolated vertices and is not bipartite. Proof. (i) ⇒) Since G is bipartite, by Proposition 1.6, we have the equality Rs(J) = R[Jt], where J = Ic(G) is the ideal of vertex covers of G. Thus the minimal set of generator of Rs(J) as a K-algebra is the set {x1, . . . , xn, x u1t, . . . , xust}, 72 Symbolic Rees algebras where u1, . . . , us are the incidence vectors of the minimal vertex covers of G. By hypothesis a is an irreducible b-cover of G, i.e., xatb is a minimal generator of Rs(Ic(C)). Therefore either a = ei for some i and b = 0 or a = ui for some i and b = 1. The converse follows readily and is valid for any graph or clutter. (ii) ⇒) By Lemma 1.1 we have 0 ≤ b ≤ 2 and 0 ≤ ai ≤ 2 for all i. If b = 0 or b = 1, then clearly a has the form indicated in (a) or (b) respectively. Assume b = 2. If ai ≥ 1 for all i, the ai = 1 for all i, otherwise if ai = 2 for some i, then a− ei is a 2-cover and a = ei + (a− ei), a contradiction. Hence a = 1. Thus we may assume that a has the form a = (0, . . . , 0, 2, . . . , 2, 1, . . . , 1). We set A = {xi\| ai = 0} 6= ∅, B = {xi\| ai = 2}, and C = V \ (A ∪ B). Observe thatA is an independent set because a is a 2-cover andB = NG(A) because a is irreducible. Hence it is seen that conditions (d1) and (d2) are satisfied. Using Lemma 1.4, the proof of the converse is direct. Lemma 1.8. Let C be a clutter and let I = I(C) be its edge ideal. If ℓk = (ak,−dk) is any of the vectors that occur in Eq. (1), where ak ∈ Nn, dk ∈ N, then ak is an irreducible dk-cover of C. Proof. We proceed by contradiction assume there is a d′k-cover a′k and a d′′k- cover a′′k such that ak = a′k+a ′′ k and dk = d′k+d ′′ k. Set F ′ = H(a′ k ,−d′ k )∩R+(I) and F ′′ = H(a′′ k ,−d′′ k )∩R+(I). Clearly F ′, F ′′ are proper faces of R+(I) and F = R+(I) ∩Hℓk = F ′ ∩ F ′′. Recall that any proper face of R+(I) is the intersection of those facets that contain it (see [30, Theorem 3.2.1(vii)]). Applying this fact to F ′ and F ′′ it is seen that F ′ ⊂ F or F ′′ ⊂ F , i.e., F = F ′ or F = F ′′. We may assume F = F ′. Hence H(a′ k ,−d′ k ) = Hℓk . Taking orthogonal complements we get that (a′k,−d ′ k) = λ(ak,−dk) for some λ ∈ Q+, because the orthogonal complement of Hℓk is one dimensional and it is generated by ℓk. Since the non-zero entries of ℓk are relatively prime, we may assume that λ ∈ N. Thus d′k = λdk ≥ dk ≥ d′k and λ must be equal to 1. Hence ak = a′k and a′′k must be zero, a contradiction. Example 1.9. Consider the following graph G: s s s ssx2 x4 x6 x8 s� �� s s s x1 x3 x5 x7 x9 @ @@ � �� @ @@ @ @@ @ @@ L. A. Dupont, R. H. Villarreal 73 Using Normaliz [3] it is seen that the vector a = (1, 1, 2, 0, 2, 1, 1, 1, 1) is an irreducible 2-cover of G such that the supporting hyperplane H(a,−2) does not define a facet of the Rees cone of I(G). Thus, in general, the image of ψ described in the introduction does not determine Rs(Ic(G)). We may use Lemma 1.4 to construct non-connected graphs with this property. Edge cones of graphs. Let G be a connected simple graph and let A = {v1, . . . , vq} be the set of all vectors ei + ej such that {xi, xj} is an edge of G. The edge cone of G, denoted by R+A, is defined as the cone generated by A. Below we give an explicit combinatorial description of the edge cone. Let A be an independent set of vertices of G. The supporting hyper- plane of the edge cone of G defined by ∑ xi∈NG(A) xi − ∑ xi∈A xi = 0 will be denoted by HA. Edge cones and their representations by closed halfspaces are a useful tool to study a-invariants of edge subrings [23, 26]. The following result is a prototype of these representations. As an application we give a direct proof of the next result using Rees cones. Corollary 1.10 ([24, Corollary 2.8]). A vector a = (a1, . . . , an) ∈ Rn is in R+A if and only if a satisfies the following system of linear inequalities ai ≥ 0, i = 1, . . . , n; ∑ xi∈NG(A) ai − ∑ xi∈A ai ≥ 0, for all independent sets A ⊂ V (G). Proof. Set B = {(v1, 1), . . . , (vq, 1)} and I = I(G). Notice the equality R+(I) ∩ RB = R+B, (2) where RB is R-vector space spanned by B. Consider the irreducible rep- resentation of R+(I) given in Eq. (1) and write ℓi = (ai,−di), where 0 6= ai ∈ Nn, 0 6= di ∈ N. Next we show the equality: R+A = RA ∩ Rn+ ∩H+ (2a1/d1−1) ∩ · · · ∩H+ (2ar/dr−1), (3) where 1 = (1, . . . , 1). Take α ∈ R+A. Clearly α ∈ RA∩Rn+. We can write α = λ1v1 + · · ·+ λqvq ⇒ \|α\| = 2(λ1 + · · ·+ λq) = 2b. 74 Symbolic Rees algebras Thus (α, b) = λ1(v1, 1) + · · · + λq(vq, 1), i.e., (α, b) ∈ R+B. Hence from Eq. (2) we get (α, b) ∈ R+(I) and 〈(α, b), (ai,−di)〉 ≥ 0 ⇒ 〈α, ai〉 ≥ bdi = (\|α\|/2)di = \|α\|(di/2). Writing α = (α1, . . . , αn) and ai = (ai1, . . . , ain), the last inequality gives: α1ai1 + · · ·+ αnain ≥ (α1 + · · ·+ αn)(di/2) ⇒ 〈α, ai − (di/2)1〉 ≥ 0. Then 〈α, 2ai/di − 1〉 ≥ 0 and α ∈ H+ (2ai/di−1) for all i, as required. This proves that R+A is contained in the right hand side of Eq. (3). The other inclusion follows similarly. Now by Lemma 1.8 we obtain that ai is an irreducible di-cover of G. Therefore, using the explicit description of the irreducible b-covers of G given in Theorem 1.7, we get the equality R+A = ( ⋂ A∈F H+ A ) ⋂ ( n⋂ i=1 H+ ei ) , where F is the collection of all the independent sets of vertices of G. From this equality the assertion follows at once. The edge cone of G encodes information about both the Hilbert function of the edge subring K[G] (see [23]) and the graph G itself. As a simple illustration, we recover the following version of the marriage theorem for bipartite graphs, see [2]. Recall that a pairing by an independent set of edges of all the vertices of a graph G is called a perfect matching or a 1-factor. Corollary 1.11. If G is a bipartite connected graph, then G has a perfect matching if and only if \|A\| ≤ \|NG(A)\| for every independent set of vertices A of G. Proof. Notice that the graph G has a perfect matching if and only if the vector β = (1, 1, . . . , 1) is in NA. By [23, Lemma 2.9] we have the equality Zn ∩ R+A = NA. Hence β is in NA if and only if β ∈ R+A. Thus the result follows from Corollary 1.10. 2. Symbolic Rees algebras of edge ideals Let G be a graph with vertex set X = {x1, . . . , xn} and let I = I(G) be its edge ideal. As before we denote the clutter of minimal vertex covers of G by Υ(G). The clutter Υ(G) is called the blocker of G. Recall that the symbolic Rees algebra of I(G) is given by Rs(I(G)) = K[xatb\| a is an irreducible b-cover of Υ(G)], (4) L. A. Dupont, R. H. Villarreal 75 where the set {xatb\| a is an irreducible b-cover of Υ(G)} is the minimal set of generators of Rs(I(G)) as a K-algebra. The main purpose of this section is to study the symbolic Rees algebra of I(G) via graph theory. We are interested in finding combinatorial representations for the minimal set of generators of this algebra. Lemma 2.1. Let 0 6= a = (a1, . . . , am, 0, . . . , 0) ∈ Nn and let a′ = (a1, . . . , am). If 0 6= b ∈ N, then a is an irreducible b-cover of Υ(G) if and only if a′ is an irreducible b-cover of Υ(〈S〉), where S = {x1, . . . , xm}. Proof. It suffices to prove that a is a b-cover of the blocker of G if and only if a′ is a b-cover of the blocker of 〈S〉. ⇒) The induced subgraph 〈S〉 is not a discrete graph. Take a minimal vertex cover C ′ of 〈S〉. Set C = C ′ ∪ (V (G) \S). Since C is a vertex cover of G such that C \ {xi} is not a vertex cover of G for every xi ∈ C ′, there is a minimal vertex cover Cℓ of G such that C ′ ⊂ Cℓ ⊂ C and C ′ = Cℓ∩S. Notice that ∑ xi∈C′ ai = ∑ xi∈Cℓ∩S ai = 〈a, uℓ〉 ≥ b, where uℓ is the incidence vector of Cℓ. Hence ∑ xi∈C′ ai ≥ b, as required. ⇐) Take a minimal vertex cover Cℓ of G. Then Cℓ ∩ S contains a minimal vertex cover C ′ ℓ of 〈S〉. Let uℓ (resp. u′ℓ) be the incidence vector of Cℓ (resp. C ′ ℓ). Notice that 〈a, uℓ〉 = ∑ xi∈Cℓ∩S ai ≥ ∑ xi∈C′ ℓ ai = 〈a′, u′ℓ〉 ≥ b. Hence 〈a, uℓ〉 ≥ b, as required. We denote a complete subgraph of G with r vertices by Kr. If v is a vertex of G, we denote its neighbor set by NG(v). Lemma 2.2. Let G be a graph and let a = (a1, . . . , an) be an irreducible b-cover of Υ(G) such that ai ≥ 1 for all i. If 〈NG(xn)〉 = Kr, then ai = 1 for all i, b = r, n = r + 1, and G = Kn. Proof. We may assume that NG(xn) = {x1, . . . , xr}. We set c = e1 + · · ·+ er + en; d = (a1 − 1, . . . , ar − 1, ar+1, . . . , an−1, an − 1). Notice that 〈x1, . . . , xr, xn〉 = Kr+1. Thus c is an r-cover of Υ(G) because any minimal vertex cover of G must intersect all edges of Kr+1. By the irreducibility of a, there exists a minimal vertex cover Cℓ of G such that 76 Symbolic Rees algebras ∑ xi∈Cℓ ai = b. Clearly we have b ≥ g ≥ r, where g is the height of I(G). Let Ck be an arbitrary minimal vertex cover of G. Since Ck contains exactly r vertices of Kr+1, from the inequality ∑ xi∈Ck ai ≥ b we get ∑ xi∈Ck di ≥ b− r, where d1, . . . , dn are the entries of d. Therefore d = 0; otherwise if d 6= 0, then d is a (b − r)-cover of Υ(G) and a = c + d, a contradiction to the irreducibility of a. It follows that g = r, n = r + 1, ai = 1 for 1 ≤ i ≤ r, an = 1, and G = Kn. Notation We regard K0 as the empty set with zero elements. A sum over an empty set is defined to be 0. Proposition 2.3. Let G be a graph and let J = Ic(G) be its ideal of vertex covers. Then the set F = {(ai) ∈ Rn+1\| ∑ xi∈Kr ai = (r − 1)an+1} ∩ R+(J) is a facet of the Rees cone R+(J). Proof. If Kr = ∅, then r = 0 and F = Hen+1 ∩ R+(J), which is clearly a facet because e1, . . . , en ∈ F . If r = 1, then F = Hei ∩ R+(J) for some 1 ≤ i ≤ n, which is a facet because ej ∈ F for j /∈ {i, n + 1} and there is at least one minimal vertex cover of G not containing xi. We may assume that X ′ = {x1, . . . , xr} is the vertex set of Kr and r ≥ 2. For each 1 ≤ i ≤ r there is a minimal vertex cover Ci of G not containing xi. Notice that Ci contains X ′ \ {xi}. Let ui be the incidence vector of Ci. Since the rank of u1, . . . , ur is r, it follows that the set {(u1, 1), . . . , (ur, 1), er+1, . . . , en} is a linearly independent set contained in F , i.e., dim(F ) = n. Hence F is a facet of R+(J) because the hyperplane that defines F is a supporting hyperplane. Proposition 2.4. Let G be a graph and let 0 6= a = (ai) ∈ Nn. If (a) ai ∈ {0, 1} for all i, and (b) 〈{xi\| ai > 0}〉 = Kr+1, then a is an irreducible r-cover of Υ(G). Proof. By Proposition 2.3, the closed halfspace H+ (a,−r) occurs in the irreducible representation of the Rees cone R+(J), where J = Ic(G). Hence a is an irreducible r-cover by Lemma 1.8. L. A. Dupont, R. H. Villarreal 77 A clique of a graph G is a set of vertices that induces a complete subgraph. We will also call a complete subgraph of G a clique. Symbolic Rees algebras are related to perfect graphs as is seen below. Let us recall the notion of perfect graph. A colouring of the vertices of G is an assignment of colours to the vertices of G in such a way that adjacent vertices have distinct colours. The chromatic number of G is the minimal number of colours in a colouring of G. A graph is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H. We refer to [5, 6, 20] and the references there for the theory of perfect graphs. Notation The support of xa = xa11 · · ·xann is supp(xa) = {xi \| ai > 0}. Corollary 2.5 ([28]). If G is a graph, then K[xatr\|xa square-free ; 〈supp(xa)〉 = Kr+1; 0 ≤ r < n] ⊂ Rs(I(G)) with equality if and only if G is a perfect graph. Proof. The inclusion follows from Proposition 2.4. If G is a perfect graph, then by [28, Corollary 3.3] the equality holds. Conversely if the equality holds, then by Lemma 1.8 and Proposition 2.3 we have R+(Ic(G)) = { (ai) ∈ Rn+1\| ∑ xi∈Kr ai ≥ (r − 1)an+1; ∀Kr ⊂ G } . (5) Hence a direct application of [28, Proposition 2.2] gives that G is a perfect graph. The vertex covering number of G, denoted by α0(G), is the number of vertices in a minimum vertex cover of G (the cardinality of any smallest vertex cover in G). Notice that α0(G) equals the height of I(G). If H is a discrete graph, i.e., all the vertices of H are isolated, we set I(H) = 0 and α0(H) = 0. Lemma 2.6. Let G be a graph. If a = e1 + · · · + er is an irreducible b-cover of Υ(G), then b = α0(H), where H = 〈x1, . . . , xr〉. Proof. The case b = 0 is clear. Assume b ≥ 1. Let C1, . . . , Cs be the minimal vertex covers of G and let u1, . . . , us be their incidence vectors. Notice that 〈a, ui〉 = b for some i. Indeed if 〈a, ui〉 > b for all i, then a− e1 is a b-cover of Υ(G) and a = (a− e1) + e1, a contradiction. Hence b = 〈a, ui〉 = \|{x1, . . . , xr} ∩ Ci\| ≥ α0(H). 78 Symbolic Rees algebras This proves that b ≥ α0(H). Notice that H is not a discrete graph. Then we can pick a minimal vertex cover A of H such that \|A\| = α0(H). The set C = A ∪ (V (G) \ {x1, . . . , xr}) is a vertex cover of G. Hence there is a minimal vertex cover Cℓ of G such that A ⊂ Cℓ ⊂ C. Observe that Cℓ ∩ {x1, . . . , xr} = A. Thus we get 〈a, uℓ〉 = \|A\| ≥ b, i.e., α0(H) ≥ b. Altogether we have b = α0(H). This result has been recently extended to clutters using the notion of parallelization [7]. Let C be a clutter on the vertex set X = {x1, . . . , xn} and let xi ∈ X. Then duplicating xi means extending X by a new vertex x′i and replacing E(C) by E(C) ∪ {(e \ {xi}) ∪ {x′i}\|xi ∈ e ∈ E(C)}. The deletion of xi, denoted by C \ {xi}, is the clutter formed from C by deleting the vertex xi and all edges containing xi. A clutter obtained from C by a sequence of deletions and duplications of vertices is called a parallelization. If w = (wi) is a vector in Nn, we denote by Cw the clutter obtained from C by deleting any vertex xi with wi = 0 and duplicating wi − 1 times any vertex xi if wi ≥ 1. The map w 7→ Cw gives a one to one correspondence between Nn and the parallelizations of C. Example 2.7. Let G be the graph whose only edge is {x1, x2} and let w = (3, 3). Then Gw = K3,3 is the complete bipartite graph with bipartition V1 = {x1, x 2 1, x 3 1} and V2 = {x2, x 2 2, x 3 2}. Notice that xki is a vertex, i.e., k is an index not an exponent. Proposition 2.8 ([7]). Let C be a clutter and let Υ(C) be the blocker of C. If w = (wi) is an irreducible b-cover of Υ(C), then b = min    ∑ xi∈C wi ∣ ∣ ∣ ∣ ∣ ∣ C ∈ Υ(C)    = α0(C w). The next result gives a nice graph theoretical description for the irreducible binary b-vertex covers of the blocker of G. Theorem 2.9. Let G be a graph and let a = (1, . . . , 1). Then a is a reducible α0(G)-cover of Υ(G) if and only if there are H1 and H2 induced subgraphs of G such that (i) V (G) is the disjoint union of V (H1) and V (H2), and L. A. Dupont, R. H. Villarreal 79 (ii) α0(G) = α0(H1) + α0(H2). Proof. ⇒) We may assume that a1 = e1 + · · · + er, a2 = a − a1, ai is a bi-cover of Υ(G), bi ≥ 1 for i = 1, 2, and α0(G) = b1 + b2. Consider the subgraphs H1 = 〈x1, . . . , xr〉 and H2 = 〈xr+1, . . . , xn〉. Let A be a minimal vertex cover of H1 with α0(H1) vertices. Since C = A ∪ (V (G) \ {x1, . . . , xr}) is a vertex cover G, there is a minimal vertex cover Ck of G such that A ⊂ Ck ⊂ C. Hence \|A\| = \|Ck ∩ {x1, . . . , xr}\| = 〈a1, uk〉 ≥ b1, and α0(H1) ≥ b1. Using a similar argument we get that α0(H2) ≥ b2. If Cℓ is a minimal vertex cover of G with α0(G) vertices, then Cℓ ∩ V (Hi) is a vertex cover of Hi. Therefore b1 + b2 = α0(G) = \|Cℓ\| = 2∑ i=1 \|Cℓ ∩ V (Hi)\| ≥ 2∑ i=1 α0(Hi) ≥ b1 + b2, and consequently α0(G) = α0(H1) + α0(H2). ⇐) We may assume that V (H1) = {x1, . . . , xr} and V (H2) = V (G) \ V (H1). Set a1 = e1 + · · ·+ er and a2 = a− a1. For any minimal vertex cover Ck of G, we have that Ck ∩ V (Hi) is a vertex cover of Hi. Hence 〈a1, uk〉 = \|Ck ∩ {x1, . . . , xr}\| ≥ α0(H1), where uk is the incidence vector of Ck. Consequently a1 is an α0(H1)- cover of Υ(G). Similarly we obtain that a2 is an α0(H2)-cover of Υ(G). Therefore a is a reducible α0(G)-cover of Υ(G). Definition 2.10. A graph satisfying conditions (i) and (ii) is called a reducible graph. If G is not reducible, it is called irreducible. These notions appear in [8]. As far as we know there is no structure theorem for irreducible graphs. Examples of irreducible graphs include complete graphs, odd cycles, and complements of odd cycles. Below we give a method, using Hilbert bases, to obtain all irreducible induced subgraphs of G. By [16, Lemma 5.4] there exists a finite set H ⊂ Nn+1 such that (a) Cn(I(G)) = R+H, and 80 Symbolic Rees algebras (b) Zn+1 ∩ R+H = NH, where NH is the additive subsemigroup of Nn+1 generated by H. Definition 2.11. The set H is called a Hilbert basis of Cn(I(G)). If we require H to be minimal (with respect inclusion), then H is unique [19]. Corollary 2.12. Let G be a graph and let α = (a1, . . . , an, b) be a vector in {0, 1}n ×N. Then α is an element of the minimal integral Hilbert basis of Cn(I(G)) if and only if the induced subgraph H = 〈{xi\| ai = 1}〉 is irreducible with b = α0(H). Proof. The map (a1, . . . , an, b) 7→ xa11 · · ·xann t b establishes a one to one correspondence between the minimal integral Hilbert basis of Cn(I(G)) and the minimal generators of Rs(I(G)) as a K-algebra. Thus the result follows from Lemma 2.1 and Theorem 2.9. The next result shows that irreducible graphs occur naturally in the theory of perfect graphs. Proposition 2.13. A graph G is perfect if and only if the only irreducible induced subgraphs of G are the complete subgraphs. Proof. ⇒) LetH be an irreducible induced subgraph ofG. We may assume that V (H) = {x1, . . . , xr}. Set a′ = (1, . . . , 1) ∈ Nr and a = (a′, 0 . . . , 0) ∈ Nn. By Theorem 2.9, a′ is an irreducible α0(H) cover of Υ(H). Then by Lemma 2.1, a′ is an irreducible α0(H) cover of Υ(G). Since x1 · · ·xrt α0(H) is a minimal generator of Rs(I(G)), using Corollary 2.5 we obtain that α0(H) = r − 1 and that H is a complete subgraph of G on r vertices. ⇐) In [4] it is shown that G is a perfect graph if and only if no induced subgraph of G is an odd cycle of length at least five or the complement of one. Since odd cycles and their complements are irreducible subgraphs. It follows that G is perfect. Definition 2.14. A graph G is called vertex critical if α0(G \ {xi}) < α0(G) for all xi ∈ V (G). Remark 2.15. If xi is any vertex of a graph G and α0(G \ {xi}) < α0(G), then α0(G \ {xi}) = α0(G)− 1 Lemma 2.16. If the graph G is irreducible, then it is connected and vertex critical L. A. Dupont, R. H. Villarreal 81 Proof. Let G1, . . . , Gr be the connected components of G. Since α0(G) is equal to ∑ i α0(Gi), we get r = 1. Thus G is connected. To complete the proof it suffices to prove that α0(G \ {xi}) < α0(G) for all i (see Remark 2.15). If α0(G \ {xi}) = α0(G), then G = H1 ∪H2, where H1 = G \ {xi} and V (H2) = {xi}, a contradiction. Definition 2.17. The cone C(G), over a graph G, is obtained by adding a new vertex v to G and joining every vertex of G to v. The next result can be used to build irreducible graphs. In particular it follows that cones over irreducible graphs are irreducible. Proposition 2.18. Let G be a graph with n vertices and let H be a graph obtained from G by adding a new vertex v and some new edges joining v with V (G). If a = (1, . . . , 1) ∈ Nn is an irreducible α0(G)-cover of Υ(G) such that α0(H) = α0(G) + 1, then a′ = (a, 1) is an irreducible α0(H)-cover of Υ(H). Proof. Clearly a′ is an α0(H)-cover of Υ(H). Assume that a′ = a′1 + a′2, where 0 6= a′i is a b′i-cover of Υ(H) and b′1 + b′2 = α0(H). We may assume that a′1 = (1, . . . , 1, 0, . . . , 0) and a′2 = (0, . . . , 0, 1, . . . , 1). Let ai be the vector in Nn obtained from a′i by removing its last entry. Set v = xn+1. Take a minimal vertex cover Ck of G and consider C ′ k = Ck ∪ {xn+1}. Let u′k (resp. uk) be the incidence vector of C ′ k (resp. Ck). Then 〈a1, uk〉 = 〈a′1, u ′ k〉 ≥ b′1 and 〈a2, uk〉+ 1 = 〈a′2, u ′ k〉 ≥ b′2, consequently a1 is a b′1-cover of Υ(G). If b′2 = 0, then a1 is an α0(H)- cover of Υ(G), a contradiction; because if u is the incidence vector of a minimal vertex cover of G with α0(G) elements, then we would obtain α0(G) ≥ 〈u, a1〉 ≥ α0(H), which is impossible. Thus b′2 ≥ 1, and a2 is a (b′2 − 1)-cover of Υ(G) if a2 6= 0. Hence a2 = 0, because a = a1 + a2 and a is irreducible. This means that a′2 = en+1 is a b′2-cover of Υ(H), a contradiction. Therefore a′ is an irreducible α0(H)-cover of Υ(H), as required. Definition 2.19. A graph G is called edge critical if α0(G \ e) < α0(G) for all e ∈ E(G). Proposition 2.20. If G is a connected edge critical graph, then G is irreducible. 82 Symbolic Rees algebras Proof. Assume that G is reducible. Then there are induced subgraphs H1, H2 of G such that V (H1), V (H2) is a partition of V (G) and α0(G) = α0(H1) + α0(H2). Since G is connected there is an edge e = {xi, xj} with xi a vertex of H1 and xj a vertex of H2. Pick a minimal vertex cover C of G\e with α0(G)−1 vertices. As E(Hi) is a subset of E(G\e) = E(G)\{e} for i = 1, 2, we get that C covers all edges of Hi for i = 1, 2. Hence C must have at least α0(G) elements, a contradiction. Corollary 2.21. The following hold for any connected graph: edge critical =⇒ irreducible =⇒ vertex critical. Finding generators of symbolic Rees algebras using cones The cone C(G), over the graph G, is obtained by adding a new vertex t to G and joining every vertex of G to t. Example 2.22. A pentagon and its cone: s s s s s G � �� Q QQ A A � � s s s s s s t C(G) Q QQ � �� A A � � � � �� S S SS � � � � �� B B B B BB In [1] Bahiano showed that if H = C(G) is the graph obtained by taking a cone over a pentagon G with vertices x1, . . . , x5, then Rs(I(H)) = R[I(H)t][x1 · · ·x5t 3, x1 · · ·x6t 4, x1 · · ·x5x 2 6t 5]. This simple example shows that taking a cone over an irreducible graph tends to increase the degree in t of the generators of the symbolic Rees algebra. Other examples using this “cone process” have been shown in [14, Example 5.5]. Let G be a graph with vertex set V (G) = {x1, . . . , xn}. The aim here is to give a general procedure—based on the irreducible representation of the Rees cone of Ic(G)—to construct generators of Rs(I(H)) of high degree in t, where H is a graph constructed from G by recursively taking cones over graphs already constructed. By the finite basis theorem [30, Theorem 4.11] there is a unique irreducible representation R+(Ic(G)) = H+ e1 ∩H + e2 ∩ · · · ∩H+ en+1 ∩H+ α1 ∩H+ α2 ∩ · · · ∩H+ αp (6) L. A. Dupont, R. H. Villarreal 83 such that each αk is in Zn+1, the non-zero entries of each αk are relatively prime, and none of the closed halfspaces H+ e1 , . . . , H + en+1 , H+ α1 , . . . , H+ αp can be omitted from the intersection. For use below we assume that α is any of the vectors α1, . . . , αp that occur in the irreducible representation. Thus we can write α = (a1, . . . , an,−b) for some ai ∈ N and for some b ∈ N. Lemma 2.23. Let H be the cone over G. If β = (a1, . . . , an, ( ∑n i=1 ai)− b,− ∑n i=1 ai) = (β1, . . . , βn+1,−βn+2) and ai ≥ 1 for all i, then F = Hβ ∩ R+(Ic(H)) is a facet of R+(Ic(H)). Proof. First we prove that R+(Ic(H)) ⊂ H+ β , i.e., Hβ is a supporting hyperplane of the Rees cone. By Lemma 1.8, (a1, . . . , an) is an irreducible b-cover of Υ(G). Hence there is C ∈ Υ(G) such that ∑ xi∈C ai = b. Therefore βn+1 is greater or equal than 1. This proves that e1, . . . , en+1 are in H+ β . Let C be any minimal vertex cover of H and let u = ∑ xi∈C ei be its characteristic vector. Case (i): If xn+1 /∈ C, then C = {x1, . . . , xn} and ∑ xi∈C βi = n∑ i=1 ai = βn+2, that is, (u, 1) ∈ H+ β . Case (ii): If xn+1 ∈ C, then C1 = C \ {xn+1} is a minimal vertex cover of G. Hence ∑ xi∈C βi = ∑ xi∈C1 βi + βn+1 ≥ b+ βn+1 = βn+2, that is, (u, 1) ∈ H+ β . Therefore R+(Ic(H)) ⊂ H+ β . To prove that F is a facet we must show it has dimension n+1 because the dimension of R+(Ic(H)) is n+ 2. We denote the characteristic vector of a minimal vertex cover Ck of G by uk. By hypothesis there are minimal vertex covers C1, . . . , Cn of G such that the vectors (u1, 1), . . . , (un, 1) are linearly independent and 〈(a,−b), (uk, 1)〉 = 0 ⇐⇒ 〈a, uk〉 = b, (7) for k = 1, . . . , n. Therefore 〈(β1, . . . , βn+1), (uk, 1)〉 = βn+2 and 〈(β1, . . . , βn+1), (1, . . . , 1, 0)〉 = βn+2, i.e., the set B = {(u1, 1), . . . , (un, 1), (1, . . . , 1, 0} is contained in Hβ . Since C1 ∪ {xn+1}, . . . , Cn ∪ {xn+1}, {x1, . . . , xn} 84 Symbolic Rees algebras are minimal vertex covers of H, the set B is also contained in R+(Ic(H)) and consequently in F . Thus its suffices to prove that B is linearly inde- pendent. If (1, . . . , 1, 0) is a linear combination of (u1, 1), . . . , (un, 1), then we can write (1, . . . , 1) = λ1u1 + · · ·+ λnun for some scalars λ1, . . . , λn such that ∑n i=1 λi = 0. Hence from Eq. (7) we get \|a\| = 〈(1, . . . , 1), a〉 = λ1〈u1, a〉+ · · ·+ λn〈un, a〉 = (λ1 + · · ·+ λn)b = 0, a contradiction. Corollary 2.24. If ai ≥ 1 for all i, then xβ11 · · ·x βn+1 n+1 t βn+2 is a minimal generator of Rs(I(H)). Proof. By Lemma 2.23, F = Hβ ∩ R+(Ic(H)) is a facet of R+(Ic(H)). Therefore using Lemma 1.8, the vector (β1, . . . , βn+1) is an irreducible βn+2-cover of Υ(H), i.e., xβ11 · · ·x βn+1 n+1 t βn+2 is a minimal generator of Rs(I(H)). Corollary 2.25. Let G0 = G and let Gr be the cone over Gr−1 for r ≥ 1. If α = (1, . . . , 1,−g), then (1, . . . , 1 ︸︷︷︸ n , n− g, . . . , n− g ︸︷︷︸ r ) is an irreducible n+ (r − 1)(n− g) cover of Gr. In particular Rs(I(Gr)) has a generator of degree in t equal to n+ (r − 1)(n− g). As a very particular example of our construction consider: Example 2.26. Let G = Cs be an odd cycle of length s = 2k + 1. Note that α0(Cs) = (s+ 1)/2 = k + 1. Then by Corollary 2.25 x1 · · ·xsx k s+1 · · ·x k s+rt rk+k+1 is a minimal generator of Rs(I(Gr)). This illustrates that the degree in t of the minimal generators of Rs(I(Gr)) is much larger than the number of vertices of the graph Gr [14]. References [1] C. Bahiano, Symbolic powers of edge ideals, J. Algebra 273 (2) (2004), 517-537. [2] B. Bollobás, Modern Graph Theory , Graduate Texts in Mathematics 184 Springer- Verlag, New York, 1998. L. A. Dupont, R. H. Villarreal 85 [3] W. Bruns and B. Ichim, Normaliz 2.0, Computing normalizations of affine semigroups 2008. Available from http://www.math.uos.de/normaliz. [4] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006), no. 1, 51–229. [5] G. Cornuéjols, Combinatorial optimization: Packing and covering, CBMS-NSF Regional Conference Series in Applied Mathematics 74, SIAM (2001). [6] R. Diestel, Graph Theory , Graduate Texts in Mathematics 173, Springer-Verlag, New York, 2nd ed., 2000. [7] L. A. Dupont, E. Reyes and R. H. Villarreal, Cohen-Macaulay clutters with combinatorial optimization properties and parallelizations of normal edge ideals, São Paulo J. Math. Sci. 3 (2009), no. 1, 61–75. [8] P. Erdös and T. Gallai, On the minimal number of vertices representing the edges of a graph, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 181–203. [9] C. Escobar, R. H. Villarreal and Y. Yoshino, Torsion freeness and normality of blowup rings of monomial ideals, Commutative Algebra, Lect. Notes Pure Appl. Math. 244, Chapman & Hall/CRC, Boca Raton, FL, 2006, pp. 69-84. [10] C. A. Francisco, H. T. Hà and A. Van Tuyl, Associated primes of monomial ideals and odd holes in graphs, J. Algebraic Combin. 32 (2010), no. 2, 287-301. [11] I. Gitler, E. Reyes and R. H. Villarreal, Blowup algebras of ideals of vertex covers of bipartite graphs, Contemp. Math. 376 (2005), 273–279. [12] I. Gitler, E. Reyes and R. H. Villarreal, Blowup algebras of square–free monomial ideals and some links to combinatorial optimization problems, Rocky Mountain J. Math. 39 (2009), no. 1, 71–102. [13] I. Gitler, C. Valencia and R. H. Villarreal, A note on Rees algebras and the MFMC property, Beiträge Algebra Geom. 48 (2007), No. 1, 141-150. [14] J. Herzog, T. Hibi and N. V. Trung, Symbolic powers of monomial ideals and vertex cover algebras, Adv. Math. 210 (2007), 304–322. [15] J. Herzog, T. Hibi and N. V. Trung, Vertex cover algebras of unimodular hyper- graphs, Proc. Amer. Math. Soc. 137 (2009), 409-414. [16] B. Korte and J. Vygen, Combinatorial Optimization Theory and Algorithms, Springer-Verlag, 2000. [17] G. Lyubeznik, On the arithmetical rank of monomial ideals, J. Algebra 112 (1988), 86–89. [18] H. Matsumura, Commutative Ring Theory , Cambridge Studies in Advanced Mathematics 8, Cambridge University Press, 1986. [19] A. Schrijver, On total dual integrality, Linear Algebra Appl. 38 (1981), 27–32. [20] A. Schrijver,Combinatorial Optimization, Algorithms and Combinatorics 24, Springer-Verlag, Berlin, 2003. [21] A. Simis, W. V. Vasconcelos and R. H. Villarreal, On the ideal theory of graphs, J. Algebra, 167 (1994), 389–416. [22] S. Sullivant, Combinatorial symbolic powers, J. Algebra 319(1) (2008), 115-142. [23] C. Valencia and R. H. Villarreal, Canonical modules of certain edge subrings, European J. Combin. 24(5) (2003), 471–487. 86 Symbolic Rees algebras [24] C. Valencia and R. H. Villarreal, Explicit representations of the edge cone of a graph, Int. Journal of Contemp. Math. Sciences 1 (2006), no. 1–4, 53–66. [25] W. V. Vasconcelos, Arithmetic of Blowup Algebras, London Math. Soc., Lecture Note Series 195, Cambridge University Press, Cambridge, 1994. [26] R. H. Villarreal, On the equations of the edge cone of a graph and some applica- tions, Manuscripta Math. 97 (1998), 309–317. [27] R. H. Villarreal, Monomial Algebras, Dekker, New York, N.Y., 2001. [28] R. H. Villarreal, Rees algebras and polyhedral cones of ideals of vertex covers of perfect graphs, J. Algebraic Combin. 27(3) (2008), 293-305. [29] R. H. Villarreal, Rees cones and monomial rings of matroids, Linear Algebra Appl. 428 (2008), 2933-2940. [30] R. Webster, Convexity , Oxford University Press, Oxford, 1994. Contact information L. A. Dupont Departamento de Matemáticas Centro de Investigación y de Estudios Avanzados del IPN Apartado Postal 14–740 07000 Mexico City, D.F. E-Mail: ldupont@math.cinvestav.mx URL: www.math.cinvestav.mx R. H. Villarreal Departamento de Matemáticas Centro de Investigación y de Estudios Avanzados del IPN Apartado Postal 14–740 07000 Mexico City, D.F. E-Mail: vila@math.cinvestav.mx URL: www.math.cinvestav.mx Received by the editors: 01.03.2009 and in final form 26.02.2011.

Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones

Institution

Ähnliche Einträge