Unmixed bipartite graphs and sublattices of the Boolean lattices

DOI 10.1007/s10801-009-0168-1

Unmixed bipartite graphs and sublattices of the Boolean lattices

Jürgen Herzog·Takayuki Hibi·Hidefumi Ohsugi

Received: 6 June 2008 / Accepted: 19 January 2009 / Published online: 4 February 2009

© Springer Science+Business Media, LLC 2009

Abstract The correspondence between unmixed bipartite graphs and sublattices of the Boolean lattice is discussed. By using this correspondence, we show existence of squarefree quadratic initial ideals of toric ideals arising from minimal vertex covers of unmixed bipartite graphs.

Keywords Toric ideal·Gröbner basis·Bipartite graph·Vertex cover· Cohen–Macaulay ring

Introduction

LetGbe a finite graph on the vertex set[N] = {1, . . . , N}with no loops, no multiple edges and no isolated vertices. LetE(G)denote the edge set ofG. A vertex cover of Gis a subsetC⊂ [N]such that, for each edge{i, j}ofG, one has eitheri∈C or j∈C. Such a vertex coverCis called minimal if no subsetCCis a vertex cover ofG. We say that a finite graphGis unmixed if all minimal vertex covers ofGhave the same cardinality. LetA=K[z1, . . . , zN]be the polynomial ring inN variables over a fieldK. The edge ideal ofGis the monomial idealI (G)ofAgenerated by

J. Herzog

Fachbereich Mathematik und Informatik, Universität Duisburg–Essen, Campus Essen, 45117 Essen, Germany

e-mail:[email protected]

T. Hibi

Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan

e-mail:[email protected]

H. Ohsugi (

Department of Mathematics, College of Science, Rikkyo University, Tokyo 171-8501, Japan e-mail:[email protected]

those quadratic monomialsz_iz_j such that{i, j}is an edge ofG. It is well-known that the primary decomposition of the edge ideal ofGis

I (G)=

C∈M(G)

z_i |i∈C

where M(G) is the set of all minimal vertex covers of G. We say that G is Cohen–Macaulay (overK) if the quotient ringA/I (G)is Cohen–Macaulay. Every Cohen–Macaulay graph is unmixed. A graph-theoretical characterization of Cohen–

Macaulay bipartite graphs was given in [1] and that of unmixed bipartite graphs was given in [5].

By relabeling the vertices, every unmixed bipartite graph G has the vertex set {x₁, . . . , x_n} ∪ {y₁, . . . , y_n}and satisfies that{x_i, y_i} ∈E(G)for alli(See Section1).

In Sections1and2, we study the correspondence between unmixed bipartite graphs and sublattices of the Boolean latticeLnon{x₁, . . . , x_n}:

• There exists a one-to-one correspondence between unmixed bipartite graphs on {x₁, . . . , x_n} ∪ {y₁, . . . , y_n}where{x_i, y_i} ∈E(G)for alliand sublatticesLofLn

with∅ ∈Land{x1, . . . , xn} ∈L. (Theorem1.2.)

• There exists a one-to-one correspondence between Cohen–Macaulay bipartite graphs on{x1, . . . , x_n} ∪ {y1, . . . , y_n}where{x_i, y_i} ∈E(G)for alliand full sub- lattices ofLn. (Theorem2.2.)

In Section3, we study toric ideals arising from the set of minimal vertex cov- ers of unmixed bipartite graphs. LetGbe an unmixed bipartite graph on the vertex set{x₁, . . . , x_n} ∪ {y₁, . . . , y_n}and letK[x₁, . . . , x_n, y₁, . . . , y_n] be the polynomial ring in 2n variables over a field K with each degx_i =degy_i =1. We associate each minimal vertex coverC of Gwith the squarefree monomial uC=

v∈Cv∈ K[x1, . . . , xn, y1, . . . , yn]of degreen. LetRGdenote the semigroup ring generated by all monomialsu_CwithC∈M(G)overK. LetS_G=K[{z_C}C∈M(G)]denote the polynomial ring in|M(G)|variables overK. The toric idealI_GofRGis the kernel of the surjective homomorphismπ:S_G→RGdefined byπ(z_C)=u_C. In Section3, by using the correspondence given in Section1, we show that:

• The toric ideal arising from an unmixed bipartite graph possesses a squarefree quadratic initial ideal. (Theorem3.1.)

1 Minimal vertex covers of unmixed bipartite graphs

First we recall a fact stated in [1, p.300]. LetGbe a bipartite graph without isolated vertices and letV (G)= {x₁, . . . , x_m} ∪ {y₁, . . . , y_n}denote the set of vertices ofG.

Suppose thatGis unmixed. Since{x1, . . . , xm}and{y1, . . . , yn}are minimal vertex covers ofG, we havem=n. Moreover, thanks to the “marriage theorem,”{xi, yi} ∈ E(G)for alliby relabeling the vertices.

Thanks to this fact, it follows that each minimal vertex cover of G is of the form{x_i1, . . . , x_is, y_is+1, . . . , y_in}where{i₁, . . . , i_n} = [n]. For a minimal vertex cover

C= {x_i1, . . . , x_is, y_is+1, . . . , y_in}ofG, we setC= {x_i1, . . . , x_is}. Let Ln denote the Boolean lattice on the set{x1, . . . , x_n}and let

LG= {C|Cis a minimal vertex cover ofG}(⊂Ln).

Remark 1.1 LetGandGbe unmixed bipartite graphs on{x₁, . . . , x_n}∪{y₁, . . . , y_n}.

(i) Both∅and{x1, . . . , x_n}belong toLG.

(ii) IfG=G, then we haveI (G)=I (G). HenceLG=LG follows from the pri- mary decomposition of the edge ideals.

Theorem 1.2 LetLbe a subset ofLn. Then there exists a (unique) unmixed bipar- tite graphGon{x1, . . . , xn} ∪ {y1, . . . , yn}such that L=LG if and only if∅and {x1, . . . , xn}belong toLandLis a sublattice ofLn.

Proof (“Only if”) Suppose that both C = {x_i1, . . . , x_is, y_is+1, . . . , y_in} and C = {xj₁, . . . , xj_t, yj_t+1, . . . , yj_n}are minimal vertex covers ofG. Then

{y_k|x_k∈/C∩C} = {y_is+1, . . . , y_in} ∪ {y_jt+1, . . . , y_jn},

{yk|xk∈/C∪C} = {yi_s+1, . . . , yin} ∩ {yj_t+1, . . . , yjn}.

First we show thatC∩C∈LG, that is,C1=(C∩C)∪ {yk|xk∈/C∩C}is a minimal vertex cover ofG. Suppose that an edge{xi, yj}ofGsatisfiesyj∈ {y/ k|xk∈/ C∩C} = {y_is+1, . . . , y_in} ∪ {y_jt+1, . . . , y_jn}. SinceC(resp.C) is a vertex cover of G, we havexi∈C (resp.xi∈C). Hencexi∈C∩C. ThusC1is a minimal vertex cover ofG.

Second we show thatC∪C∈LG, that is,C₂=(C∪C)∪ {y_k|x_k∈/C∪C}is a minimal vertex cover ofG. Suppose that an edge{x_i, y_j}ofGsatisfiesx_i∈/C∪C. SinceC (resp.C) is a vertex cover ofG, we havey_j∈ {y_is+1, . . . , y_in}(resp.y_j∈ {y_jt+1, . . . , y_jn}). Thusy_j ∈ {y_is+1, . . . , y_in} ∩ {y_jt+1, . . . , y_jn} = {y_k | x_k∈/C∪C} and henceC2is a minimal vertex cover ofG.

(“If”) For each elementS∈L, letS^∗ denote the set{yj |xj ∈/S}. LetI be an ideal

S∈LS∪S^∗. We will show that there exists an unmixed bipartite graphG such thatI=

x_iy_j| {x_i, y_j} ∈E(G) . Since∅ ∈Land{x₁, . . . , x_n} ∈L,I ⊂

x_iy_j |1≤i, j≤n

. Suppose that a mono- mialMof degree≥3 belongs to the minimal set of generators ofI.

Suppose thatM=xixju wherei=j anduis a (squarefree) monomial. Since xju /∈I, there exists S∈ L such that xju /∈ S∪S^∗. Moreover since xiu /∈I, there exists S∈L such that x_iu /∈

S∪S^∗

. Then we have x_i, x_j ∈/S∩S and u /∈

S∪S∪S^∗∪S^∗

. SinceLis a sublattice ofLn,S∩S∈L. Note that(S∩S)^∗= S^∗∪S^∗. Hence we haveI⊂

(S∩S)∪(S^∗∪S^∗)

.However, none of the variables inx_ix_juappear in the set(S∩S)∪(S^∗∪S^∗)contradicting the fact thatx_ix_ju∈I. Suppose thatM=yiyju wherei=j anduis a (squarefree) monomial. Since yju /∈I, there existsS∈Lsuch thatyju /∈ S∪S^∗. Moreover sinceyiu /∈I, there existsS∈L such that y_iu /∈

S∪S^∗

. Then we have y_i, y_j ∈/ S^∗∩S^∗ and u /∈ S∪S∪S^∗∪S^∗

. SinceLis a sublattice ofLn,S∪S∈L. Note that(S∪S)^∗=

S^∗∩S^∗. Hence we haveI⊂

(S∪S)∪(S^∗∩S^∗)

.However, none of the variables iny_iy_juappear in the set(S∪S)∪(S^∗∩S^∗)contradicting the fact thaty_iy_ju∈I. Thus the minimal set of generators ofI is a subset of{xiyj |1≤i, j≤n}. More- over, since eitherxi oryi belongs toS∪S^∗ for allS∈L,xiyi ∈I for alli. Hence there exists a bipartite graphGsuch thatI =I (G)and{x_i, y_i} ∈E(G). Since the primary decomposition of the edge idealI (G)ofGisI=

C∈M(G)C, it follows thatM(G)= {S∪S^∗|S∈L}. Thus we haveL=LG. Since the cardinality of each

S∪S^∗withS∈Lisn,Gis unmixed as desired.

2 Minimal vertex covers of Cohen–Macaulay bipartite graphs

As before, letGbe a finite graph on[N]andA=K[z₁, . . . , z_N]the polynomial ring inN variables over a fieldK. The edge ideal ofGis the monomial idealI (G)ofA generated by those quadratic monomialsz_iz_j such that{i, j}is an edge ofG. We say thatGis Cohen–Macaulay (overK) if the quotient ringA/I (G)is Cohen–Macaulay.

Every Cohen–Macaulay graph is unmixed.

Given a finite poset (partially ordered set) P = {p₁, . . . , p_n}, we introduce the bipartite graph G_P on the vertex set {x1, . . . , x_n} ∪ {y1, . . . , y_n}whose edges are those 2-element subsets{xi, yj}withpi≤pj. In particular for eachi∈ [n]the edge {xi, yi}belongs to GP. It is known [1] that GP is Cohen–Macaulay. Conversely, given a Cohen–Macaulay bipartite graphG, there is a finite posetP withG=G_P.

A subsetα⊂P is called a poset ideal ofP ifαenjoys the property that ifp_i∈α andp_j≤p_i, thenp_j∈α. In particular the empty set andP itself are poset ideals of P. For each poset idealαofP, we setαx= {xi|pi∈α}andαy= {yj|pj∈α}. Lemma 2.1 The set αx ∪αy is a minimal vertex cover of GP. Conversely, every minimal vertex cover ofGP is of the formβx∪βyfor some poset idealβ ofP. Proof Letαbe a poset ideal ofP. We show thatC=αx∪αy is a minimal vertex cover ofG_P. Let{x_i, y_j}be an edge ofG. Thenp_i≤p_j. Supposex_i∈α_x. Then p_i ∈α. Sinceαis a poset ideal ofP, it follows thatp_j∈α. Thusy_j∈α_y. Hence C is a vertex cover ofG. SinceG_P is unmixed and|C| =n, it follows thatC is a minimal vertex cover.

Conversely, given a minimal vertex coverC= {x_i1, . . . , x_is} ∪ {y_is+1, . . . , y_in}of G_P, where{i₁, . . . , i_n} = [n], we prove thatα= {p_i1, . . . , p_is}is a poset ideal ofP. Letp_ij ∈αandp_a< p_ij inP. Then {x_a, y_ij}is an edge of G_P. Supposep_a∈α.

Thenxa∈C. Sincexi_j ∈C, one hasyi_j ∈C. Thus neitherxanoryi_j belongs toC.

However,{x_a, y_ij}is an edge ofG_P. ThusCcannot be a vertex cover ofG_P. Hence p_a∈α. Consequently,αis a poset ideal ofG_P, as desired.

As before, letLn denote the Boolean lattice on{x₁, . . . , x_n}. A sublatticeLof Ln is called full if the rank ofL is equal ton. Here the rank ofLis defined to be the nonnegative integer−1, whereis the maximal cardinality of chains (totally ordered subsets) ofL.

LetP be a finite poset with |P| =nandJ(P )the set of all poset ideals ofP. It turns out that the subsetJ(P ) of Ln is a full sublattice of Ln. Conversely, the

classical fundamental structure theorem for finite distributive lattices [3, pp. 118–

119] guarantees that every full sublattice ofLn is of the formJ(P )for a unique posetP with|P| =n.

Theorem 2.2 A subsetLofLnis a full sublattice ofLn if and only if there exists a Cohen–Macaulay bipartite graphGon{x1, . . . , xn} ∪ {y1, . . . , yn}withL=LG. Proof (“If”) LetGbe a Cohen–Macaulay bipartite graph on the set{x₁, . . . , x_n} ∪ {y₁, . . . , y_n}andP a poset withG=G_P, where|P| =n. Lemma2.1says thatLG

coincides withJ(P ). ThusLGis a full sublattice ofLn.

(“Only if”) Suppose thatLis a full sublattice ofLn. One hasL=J(P )for a unique posetP with|P| =n. LetG=G_P. ThenGis a Cohen–Macaulay bipartite graph. Lemma2.1says thatLGcoincides withJ(P ). ThusLG=L, as required.

3 Toric ideals arising from minimal vertex covers

LetG be an unmixed bipartite graph on the vertex set{x1, . . . , xn} ∪ {y1, . . . , yn} and letK[x1, . . . , xn, y1, . . . , yn]be the polynomial ring in 2nvariables over a field K with each degx_i =degy_i =1. Let M(G)denote the set of all minimal vertex covers ofG. We associate each minimal vertex coverC of Gwith the squarefree monomialu_C=

v∈Cv∈K[x1, . . . , x_n, y1, . . . , y_n]of degreen. LetRGdenote the semigroup ring generated by all monomialsu_CwithC∈M(G)overK. LetS_G= K[{z_C}C∈M(G)]denote the polynomial ring in|M(G)|variables overK. The toric idealI_GofRGis the kernel of the surjective homomorphismπ:S_G→RGdefined byπ(z_C)=u_C.

Theorem 3.1 LetGbe an unmixed bipartite graph. Then the toric idealI_G ofRG

has a squarefree quadratic initial ideal with respect to a reverse lexicographic order.

Proof Let G0 denote the (unmixed) bipartite graph with the edge set E(G)= {{x1, y1}, . . . ,{x_n, y_n}}. ThenLG0 is the Boolean lattice on{x1, . . . , x_n}. It is known [2] that the reduced Gröbner basis of toric ideal of RG0 with respect to a suitable reverse lexicographic order is

G0= {zCz_C−z_C∩Cz_C∪C |C, C∈M(G), C=C} where the initial monomial of each binomial ofG0is the first monomial.

LetGbe an unmixed bipartite graph on the vertex set{x₁, . . . , x_n} ∪ {y₁, . . . , y_n}.

ThenLGis a sublattice ofLG0. Hence we have the following:

(i) I_G=I_G0∩S_G(by [4, Proposition 4.13 (a)]);

(ii) IfC andCbelong toM(G), thenC∩CandC∪C belong toM(G). Thus, ifz_Cz_C∈S_G, then we havez_C∩Cz_C∪C∈S_G.

Thanks to the elimination property above,G0∩SG is a Gröbner basis of the toric

idealIGofRGas desired.

Corollary 3.2 LetGbe an unmixed bipartite graph. Then the semigroup ringRGis normal and Koszul.

References

1. Herzog, J., Hibi, T.: Distributive lattices, bipartite graphs and Alexander duality. J. Algebr. Comb. 22, 289–302 (2005)

2. Hibi, T.: Distributive lattices, affine semigroup rings and algebras with straightening laws. In: Nagata, M., Matsumura, H. (eds.) Commutative Algebra and Combinatorics. Advanced Studies in Pure Math., vol. 11, pp. 93–109. North–Holland, Amsterdam (1987)

3. Hibi, T.: Algebraic Combinatorics of Convex Polytopes. Carslaw, Glebe (1992)

4. Sturmfels, B.: Gröbner Bases and Convex Polytopes. Amer. Math. Soc., Providence (1995) 5. Villarreal, R.H.: Unmixed bipartite graphs. Rev. Colomb. Mat. 41(2), 393–395 (2007)