×

Ring graphs and complete intersection toric ideals. (English) Zbl 1198.05089

Let \(G\) be a simple graph with \(n\) vertices \(x_1,\ldots,x_n\) and \(q\) edges \(t_1,\ldots,t_q\). A graph satisfies the primitive cycle property (PCP) if any two primitive (i.e., chordless) cycles have at most one common edge. The free rank of \(G\), denoted frank(\(G\)), is the number of primitive cycles in \(G\), while the rank of \(G\) is defined as the dimension of the cycle space of \(G\). It is shown that \(\text{rank}(G)\leq\text{frank}(G)\). The authors seek conditions for equality to hold.
The graph \(G\) is called a ring graph if \(G\) every maximal biconnected subgraph of \(G\) can be constructed from a cycle by successively adjoining paths of length \(\geq2\) that are disjoint from the graph thus far constructed except that their terminal vertices are identified with adjacent vertices of said graph. Theorem 2.13: \(G\) is a ring graph if and only if \(\text{rank}(G)=\text{frank}(G)\), and equivalently if \(G\) satisfies the PCP and contains no subdivision of \(K_4\). All outerplanar graphs are ring graphs, and all ring graphs are planar.
Consider the polynomial ring \(R=k[x_1,\ldots,x_n]\) over a field \(k\). The edge-subring \(k[G]\) of \(R\) is the \(k\)-subalgebra \(k[t_1,\ldots,t_q]\) of \(R\). The kernel of the algebra-epimorphism \(k[t_1,\ldots,t_q]\rightarrow k[G]\), where \(t_h=\{x_i,x_j\}\mapsto x_ix_j\), is a graded prime ideal, called the toric ideal of \(G\) and is denoted by \(P(G)\). The graph \(G\) is called a complete intersection if \(P(G)\) can be generated by \(g\) polynomials, where \(g\) is the greatest length of an ascending chain of prime ideals contained in \(P(G)\). Theorem 3.3: A bipartite graph is a complete intersection if and only if it is planar and satisfies the PCP.
The final section considers these notions when \(G\) is an oriented graph.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
13F20 Polynomial rings and ideals; rings of integer-valued polynomials

Software:

cisimplicial
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, M., Combinatorial Theory (1997), Springer · Zbl 0858.05001
[2] Atiyah, M. F.; Macdonald, I. G., Introduction to Commutative Algebra (1969), Addison-Wesley: Addison-Wesley Reading MA · Zbl 0175.03601
[3] Bermejo, I.; García-Marco, I.; Salazar-González, J. J., An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection, J. Symbolic Comput., 42, 971-991 (2007) · Zbl 1147.14026
[4] Bermejo, I.; Gimenez, P.; Reyes, E.; Villarreal, R. H., Complete intersections in affine monomial curves, Bol. Soc. Mat. Mexicana (3), 11, 191-203 (2005) · Zbl 1105.14040
[5] Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2000), Springer-Verlag: Springer-Verlag New York) · Zbl 0945.05002
[6] Doering, L.; Gunston, T., Algebras arising from planar bipartite graphs, Comm. Algebra, 24, 3589-3598 (1996) · Zbl 0877.13018
[7] Gitler, I.; Reyes, E.; Villarreal, R. H., Ring graphs toric ideals, Electron. Notes Discrete Math., 28C, 393-400 (2007) · Zbl 1291.05089
[8] Gitler, I.; Valencia, C., Multiplicities of edge subrings, Discrete Math., 302, 107-123 (2005) · Zbl 1092.13032
[9] Godsil, C.; Royle, G., (Algebraic Graph Theory. Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207 (2001), Springer) · Zbl 0968.05002
[10] Harary, F., Graph Theory (1972), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[11] Herzog, J., Generators and relations of abelian semigroups and semigroup rings, Manuscripta Math., 3, 175-193 (1970) · Zbl 0211.33801
[12] T. Ishizeki, Analysis of Gröbner bases for toric ideals of acyclic tournament graphs, Masters Thesis, The University of Tokyo, 2000; T. Ishizeki, Analysis of Gröbner bases for toric ideals of acyclic tournament graphs, Masters Thesis, The University of Tokyo, 2000 · Zbl 0968.13507
[13] Katzman, M., Bipartite graphs whose edge algebras are complete intersections, J. Algebra, 220, 519-530 (1999) · Zbl 0943.13007
[14] Morales, M.; Thoma, A., Complete intersection lattice ideals, J. Algebra, 284, 755-770 (2005) · Zbl 1076.13006
[15] Oxley, J., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[16] Reyes, E., Complete intersection toric ideals of oriented graphs, Morfismos, 9, 2, 71-82 (2005)
[17] E. Reyes, Toric ideals and affine varieties, blowup algebras and combinatorial optimization problems, Ph.D. Thesis, Cinvestav-IPN, 2006; E. Reyes, Toric ideals and affine varieties, blowup algebras and combinatorial optimization problems, Ph.D. Thesis, Cinvestav-IPN, 2006
[18] Schrijver, A., Theory of Linear and Integer Programming (1986), John Wiley & Sons: John Wiley & Sons New York · Zbl 0665.90063
[19] Simis, A., On the Jacobian module associated to a graph, Proc. Amer. Math. Soc., 126, 989-997 (1998) · Zbl 0887.13014
[20] Sturmfels, B., (Gröbner Bases and Convex Polytopes. Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8 (1996), American Mathematical Society: American Mathematical Society Rhode Island) · Zbl 0856.13020
[21] Villarreal, R. H., Rees algebras of edge ideals, Comm. Algebra, 23, 3513 (1995) · Zbl 0836.13014
[22] Villarreal, R. H., (Monomial Algebras. Monomial Algebras, Monographs and Textbooks in Pure and Applied Mathematics, vol. 238 (2001), Marcel Dekker Inc.: Marcel Dekker Inc. New York)
[23] Villarreal, R. H., (Monomial Algebras and Polyhedral Geometry. Monomial Algebras and Polyhedral Geometry, Handbook of Algebra, vol. 3 (2003), Elsevier Science B.V.: Elsevier Science B.V. Amsterdam), 257-314 · Zbl 1109.13018
[24] Villarreal, R. H., Normality of semigroups with some links to graph theory, Discrete Math., 302, 267-284 (2005) · Zbl 1103.20058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.