TORIC IDEALS OF FINITE GRAPHS AND ADJACENT 2-MINORS
HIDEFUMI OHSUGI and TAKAYUKI HIBI∗
Abstract
We study the problem when an ideal generated by adjacent 2-minors is the toric ideal of a finite graph.
LetX = (xij)i=1,...,m,j=1,...,n be a matrix ofmnindeterminates, and letA = K[{xij}i=1,...,m,j=1,...,n] be the polynomial ring inmnvariables over a fieldK.
Given 1 ≤ a1 < a2 ≤ mand 1 ≤ b1 < b2 ≤ n, the symbol [a1, a2|b1, b2] denotes the 2-minorxa1b1xa2b2−xa1b2xa2b1ofX. In particular [a1, a2|b1, b2] is a binomial ofA. A 2-minor [a1, a2|b1, b2] ofXisadjacent([4]) ifa2=a1+1 andb2 =b1+1. Following [2], we say that a setMof adjacent 2-minors of Xis ofchessboard typeif the following conditions are satisfied:
• if [a, a+1|b, b+1] and [a, a+1|b, b+1] withb < bbelong toM, thenb+1< b;
• if [a, a+1|b, b+1] and [a, a+1|b, b+1] witha < abelong toM, thena+1< a.
Given a setM of adjacent 2-minors of X of chessboard type, we introduce the finite graphM on the vertex set M, whose edges are{[a, a+1|b, b+ 1],[a, a+1|b, b+1]}such that
• [a, a+1|b, b+1]=[a, a+1|b, b+1],
• {a, a+1} ∩ {a, a+1} = ∅,
• {b, b+1} ∩ {b, b+1} = ∅.
For example, ifM = {[1,2|2,3],[2,3|3,4],[3,4|2,3],[2,3|1,2]}, then M is a cycle of length 4. The idealIM is generated byx12x23−x13x22,x23x34− x24x33,x32x43−x33x42andx21x32−x22x31. The binomialx32(x13x21x34x42− x12x24x31x43)belongs toIM but neitherx32 norx13x21x34x42−x12x24x31x43
belongs toIM. ThusIM is not prime.
∗This research was supported by JST CREST.
Received 10 December 2011, in final form 7 October 2012.
A fundamental fact regarding ideals generated by adjacent 2-minors is Lemma1 ([2]).LetMbe a set of adjacent2-minors ofX, and letIMbe the ideal ofAgenerated by all2-minors belonging toM. Then,IMis a prime ideal if and only ifM is of chessboard type, andM possesses no cycle of length4.
A finite graph G is said to besimple if Ghas no loop and no multiple edge. Let G be a finite simple graph on the vertex set [d] = {1, . . . , d}, and letE(G) = {e1, . . . , en} be its set of edges. LetK[t] = K[t1, . . . , td] denote the polynomial ring ind variables overK, and letK[G] denote the subring ofK[t] generated by the squarefree quadratic monomialste = titj
with e = {i, j} ∈ E(G). The semigroup ringK[G] is called theedge ring ofG. LetK[y] = K[y1, . . . , yn] denote the polynomial ring in nvariables overK. The kernelIG of the surjective homomorphismπ : K[y] → K[G]
defined by settingπ(yi)= tei fori = 1, . . . , nis called thetoric idealofG.
Clearly,IGis a prime ideal. It is known thatIGis generated by the binomials corresponding to even closed walks of G. See [7] , [6, Chapter 9] and [5, Lemma 1.1] for details.
Example2. LetGbe a complete bipartite graph with the edge setE(G)= {{i, p+j} |1≤i≤p,1≤j ≤q}.LetX=(xij)i=1,...,p,j=1,...,qbe a matrix of pq indeterminates and K[x] = K[{xij}i=1,...,p,j=1,...,q]. Then, IG is the kernel of the surjective homomorphismπ:K[x]→K[G] defined by setting π(xij)=titp+jfor 1≤i≤p,1≤j ≤q. It is known [6, Proposition 5.4] that IGis generated by the set of all 2-minors ofX. Note that each 2-minorxijxij− xijxijcorresponds to the cycle{{i, p+j},{p+j, i},{i, p+j},{p+j, i}}
ofG.
In general, a toric ideal is the defining ideal of a homogeneous semigroup ring. We refer the reader to [6] for detailed information on toric ideals. It is known [1] that a binomial idealI, i.e., an ideal generated by binomials, is a prime ideal if and only ifIis a toric ideal. An interesting research problem on toric ideals is to determine when a binomial ideal is the toric ideal of a finite graph.
Example3. The idealI = x1x2−x3x4, x1x2−x5x6, x1x2−x7x8is the toric ideal of the semigroup ring K[t1t5, t2t3t4t5, t1t2t5, t3t4t5, t2t3t5, t1t4t5, t1t3t5, t2t4t5]. If there exists a graphG such that I = IG, then three quad- ratic binomials correspond to cycles of length 4. However, this is impossible since these three cycles must have common two edgese1 and e2 such that e1∩e2 = ∅. Thus,I cannot be the toric ideal of a finite graph. This observa- tion implies that the toric ideal of a finite distributive latticeL (see [3]) is the toric ideal of a finite graph if and only ifL is planar. In fact, ifL is planar,
then it is easy to see that the toric ideal ofL is the toric ideal of a bipartite graph. IfL is not planar, then L contains a sublattice that is isomorphic to the Boolean latticeB3of rank 3. Since the toric ideal ofB3has three binomials above, the toric ideal ofL cannot be the toric ideal of a finite graph.
LetM be a set of adjacent 2-minors. Now, we determine when a binomial idealIM generated by M is the toric ideal IG of a finite graph G. SinceIG is a prime ideal, according to Lemma 1, if there exists a finite graphGwith IM = IG, thenM must be of chessboard type andM possesses no cycle of length 4.
Theorem4.LetMbe a set of adjacent2-minors. Then, there exists a finite graphGsuch thatIM=IGif and only ifMis of chessboard type,Mpossesses no cycle of length4, and each connected component ofM possesses at most one cycle.
Proof. We may assume thatMis of chessboard type andMpossesses no cycle of length 4. LetM =M1∪ · · · ∪Ms, whereM1, . . . , Ms is the set of connected components ofM. Ifi = j, thenf ∈ Mi and g ∈ Mj have no common variable. Hence, there exists a finite graphGsuch thatIM =IGif and only if for each 1≤i ≤s, there exists a finite graphGi such thatIMi =IGi. Thus, we may assume thatMis connected. Letpbe the number of vertices of M, and letq be the number of edges ofM. SinceMis connected, we have p≤q+1.
Only if. Suppose that there exists a finite graphGwithIM=IG. From [2, Theorem 2.3], the codimension ofIM is equal top. Letd be the number of vertices ofG, and letnbe the number of edges ofG. Then, we haved ≤4p−2q andn= 4p−q. The height ofIG is given in [7]. IfGis bipartite, then the codimension ofIGsatisfiesp≥n−d+1≥(4p−q)−(4p−2q)+1=q+1.
Hence, we havep = q +1 andM is a tree. On the other hand, ifGis not bipartite, then the codimension ofIGsatisfiesp≥n−d≥(4p−q)−(4p− 2q)=q. Hence, we havep∈ {q, q+1}andMhas at most one cycle.
If. Suppose thatMhas at most one cycle. Then, we havep∈ {q, q+1}. Case 1.p=q+1, i.e.,Mis a tree.
Through induction onp, we will show that there exists a connected bipartite graphGsuch thatIM = IG. Ifp = 1, then IM = IG whereGis a cycle of length 4. Letk >1, and suppose that the assertion holds forp=k−1. Suppose thatMhaskvertices. SinceMis a tree,Mhas a vertexv=[a, a+1|b, b+1]
of degree 1. LetM = M \ {v}. SinceM is a tree, there exists a connected bipartite graphGsuch thatIM =IGby the hypothesis of induction. From [5, Theorem 1.2], sinceIG is generated by quadratic binomials, any cycle ofG of length≥6 has a chord. Letv=[a, a+1|b, b+1] denote the vertex of
Mthat is incident withv. Lete= {i, j}be the edge ofGcorresponding to the common variable ofvandv. Let{1,2, . . . , d}be the vertex set ofG. We now define the connected bipartite graphGon the vertex set{1,2, . . . , d, d+1, d+ 2}with the edge setE(G)∪ {{i, d+1},{d+1, d+2},{d+2, j}}. Then, any cycle ofGof length≥6 has a chord, and hence,IGis generated by quadratic binomials. Thus,IG is generated by the quadratic binomials ofIG together withvcorresponding to the cycle{{i, d+1},{d+1, d+2},{d+2, j},{j, i}}. Therefore,IM =IG.
Case 2.p=q, i.e.,M has exactly one cycle.
Then, we havep ≥ 8. Through induction onp, we will show that there exists a graphGsuch thatIM =IG. Ifp =8, thenMis a cycle of length 8.
Then,IM =IGwhereGis the graph shown in Figure 1.
Figure1. Graph forMsuch thatMis a cycle of length 8.
Letk >8 and suppose that the assertion holds forp = k−1. Suppose that M has k vertices. IfM has a vertex v = [a, a+1|b, b +1] of degree 1, thenMwhereM =M\ {v}has exactly one cycle, and hence, there exists a graphGsuch thatIM =IGby the hypothesis of induction. Letv=[a, a+ 1|b, b+1] denote the vertex ofMthat is incident withv. Lete= {i, j}be the edge ofG corresponding to the common variable ofv andv. Suppose that the vertex set ofGis{1,2, . . . , d}. We now define the graph Gon the vertex set{1,2, . . . , d, d+1, d+2}with the edge setE(G)∪{{i, d+1},{d+ 1, d+2},{d+2, j}}. SinceG satisfies the conditions in [5, Theorem 1.2], it follows that G satisfies the conditions in [5, Theorem 1.2]. Thus, IG is generated by the quadratic binomials ofIG together withvcorresponding to the cycle{{i, d+1},{d+1, d+2},{d+2, j},{j, i}}. Therefore,IM=IG.
Suppose thatMhas no vertex of degree 1. Then,Mis a cycle of lengthk.
A 2-minorad−bc∈M is calledfreeif one of the following holds:
• Neitheranordappears in other 2-minors ofM,
• Neitherbnorcappears in other 2-minors ofM.
From [2, Lemma 1.6], M has at least two free 2-minors. Letv = [a, a + 1|b, b +1] be a free 2-minor of M. We may assume that neither xa,b nor xa+1,b+1appears in other 2-minors ofM. SinceM is a cycle,xa+1,bappears
in exactly two 2-minors ofM andxa,b+1appears in exactly two 2-minors of M. LetM = M \ {v}. SinceM is a tree, there exists a connected bipartite graph G such thatIM = IG by the argument in Case 1. Suppose that the edge{1,3}corresponds to the variablexa+1,band the edge{2,4}corresponds to the variablexa,b+1. We now define the graphGas shown in Figure 2, where vertices 1 and 2 belong to the same part of the bipartite graphG. Note thatG is not bipartite.
1
3 4
2
1 e
e⬘ 3
4
2
Figure2. New graphGarising fromG.
Lete= {1,2}ande = {3,4}. SinceGis a bipartite graph, it follows that (a) If eithereoreis an edge of an even cycleCofG, then{e, e} ⊂E(C).
(b) IfCis an odd cycle ofG, then{e, e} ∩E(C)= ∅.
LetI denote the ideal generated by all quadratic binomials inIG. Since each quadratic binomial inIG corresponds to a cycle ofGof length 4, it follows thatIM = I. Thus, it is sufficient to show thatIG = I, i.e.,IGis generated by quadratic binomials. From [5, Theorem 1.2], sinceGis bipartite and since IG is generated by quadratic binomials, all cycles ofGof length≥6 have a chord.
LetCbe an even cycle ofGof length≥6. IfE(C)∩ {e, e} = ∅, thenC has an even-chord since all cycles of the bipartite graphGof length≥6 have a chord. Suppose that{e, e} ⊂ E(C)holds. Then, either{1,3}or{2,4}is a chord ofC. Moreover, such a chord is an even-chord ofCfrom (b) above.
LetCandCbe odd cycles ofGhaving exactly one common vertex. From (b) above, we may assume thate ∈ E(C)\E(C)ande ∈ E(C)\E(C).
If{1,3}does not belong toE(C)∪E(C), then{1,3}satisfies the condition in [5, Theorem 1.2 (ii)]. If {1,3}belongs to E(C)∪E(C), then {2,4} ∈/ E(C)∪E(C)sinceCandChave exactly one common vertex. Hence,{2,4} satisfies the condition in [5, Theorem 1.2 (ii)].
LetCandCbe odd cycles ofGhaving no common vertex. Then, neither {1,3}nor{2,4}belong toE(C)∪E(C). Hence,{1,3}and{2,4}satisfy the condition in [5, Theorem 1.2 (iii)].
Thus, from [5, Theorem 1.2],IGis generated by quadratic binomials. There- fore,IG=IMas desired.
REFERENCES
1. Eisenbud, D., and Sturmfels, B.,Binomial ideals, Duke Math. J. 84 (1996), 1–45.
2. Herzog, J., and Hibi, T.,Ideals generated by adjacent2-minors, J. Comm. Algebra 4 (2012), 525–549.
3. Hibi, T.,Distributive lattices, affine semigroup rings and algebras with straightening laws, pp. 93–109 in: Commutative Algebra and Combinatorics, ed. Nagata, M., and Matsumura, H., Adv. Stud. Pure Math. 11, North-Holland, Amsterdam 1987.
4. Ho¸sten, S., and Sullivant, S.,Ideals of adjacent minors, J. Algebra 277 (2004), 615–642.
5. Ohsugi, H., and Hibi, T.,Toric ideals generated by quadratic binomials, J. Algebra 218 (1999), 509–527.
6. Sturmfels, B.,Gröbner bases and convex polytopes, Univ. Lect. Ser. 8, Amer. Math. Soc., Providence 1996.
7. Villarreal, R.,Rees algebras of edge ideals, Comm. Algebra 23 (1995), 3513–3524.
DEPARTMENT OF MATHEMATICS COLLEGE OF SCIENCE RIKKYO UNIVERSITY TOSHIMA-KU, TOKYO 171-8501 JAPAN
E-mail:ohsugi@rikkyo.ac.jp
DEPARTMENT OF PURE AND APPLIED MATHEMATICS
GRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGY OSAKA UNIVERSITY
TOYONAKA, OSAKA 560-0043 JAPAN
E-mail:hibi@math.sci.osaka-u.ac.jp
