Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs. (English) Zbl 1328.05202
Summary: Let \(G\)=\((V,E)\) be a finite, simple graph. We consider for each oriented graph \(G_{\mathcal{O}}\) associated to an orientation \(\mathcal{O}\) of the edges of \(G\), the toric ideal \(P_{G_{\mathcal{O}}}\). In this paper we study those graphs with the property that \(P_{G_{\mathcal{O}}}\) is a binomial complete intersection, for all \(\mathcal{O}\). These graphs are called \(\text{CI}\mathcal{O}\) graphs. We prove that these graphs can be constructed recursively as clique-sums of cycles and/or complete graphs. We introduce chorded-theta subgraphs and some of their properties. Also we establish that the \(\text{CI}{\mathcal{O}}\) graphs are determined by the property that each chorded-theta has a transversal triangle. Finally we explicitly give the minimal forbidden induced subgraphs that characterize these graphs, these families of forbidden graphs are: prisms, pyramids, thetas and a particular family of wheels that we call \(\theta\)-partial wheels.
MSC:
| 05E15 | Combinatorial aspects of groups and algebras (MSC2010) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Atiyah, M.F., Macdonald, I.G.: Introduction to Commutative Algebra. Addison-Wesley, Reading (1969) · Zbl 0175.03601 |
| [2] | Chudnovsky, M., Kapadia, R.: Detecting a theta or prism. SIAM J. Discrete Math. 22(3), 1164-1186 (2008) · Zbl 1181.05081 · doi:10.1137/060672613 |
| [3] | Diestel, R.: Graph Theory, 2nd edn. Graduate Texts in Mathematics, vol. 173. Springer, New York (2000) · Zbl 0945.05002 |
| [4] | Dirac, G.A.: On rigid circuit graphs. Abh. Math. Semin. Univ. Hamb. 25(1-2), 71-76 (1961) · Zbl 0098.14703 · doi:10.1007/BF02992776 |
| [5] | Gitler, I., Reyes Villarreal, R.H.: Ring graphs and toric ideals. Electron. Notes Discrete Math. C 28, 393-400 (2007) · Zbl 1291.05089 · doi:10.1016/j.endm.2007.01.053 |
| [6] | Gitler, I., Reyes, E., Villarreal, R.H.: Ring graphs and complete intersection toric ideals. Discrete Math. 310, 430-441 (2010) · Zbl 1198.05089 · doi:10.1016/j.disc.2009.03.020 |
| [7] | Gitler, I., Villarreal, R.H.: Graphs, Rings and Polyhedra. Textos Nivel Avanzado. Aportaciones Matemáticas, vol. 35. Sociedad Matemática Mexicana, Mexico (2011) · Zbl 1316.13001 |
| [8] | Katsabekis, A.: Arithmetical rank of toric ideals associated to graphs. Proc. Am. Math. Soc. 138(9), 3111-3123 (2010) · Zbl 1200.14104 · doi:10.1090/S0002-9939-2010-10335-0 |
| [9] | Katzman, M.: Bipartite graphs whose edge algebras are complete intersections. J. Algebra 220, 519-530 (1999) · Zbl 0943.13007 · doi:10.1006/jabr.1999.7919 |
| [10] | Lévêque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discrete Appl. Math. 157, 3540-3551 (2009) · Zbl 1227.05238 · doi:10.1016/j.dam.2009.02.015 |
| [11] | Rédei, L.: Ein kombinatorischer Satz. Acta Litt. Szeged 7, 39-43 (1934) · JFM 60.0049.01 |
| [12] | Reyes, E.: Complete intersection toric ideals of oriented graphs. Morfismos 9(2), 71-82 (2005) |
| [13] | Reyes, E., Tatakis, C., Thoma, A.: Minimal generators of toric ideals of graphs. Adv. Appl. Math. 48, 64-72 (2012) · Zbl 1266.14041 · doi:10.1016/j.aam.2011.06.003 |
| [14] | Seymour, P.D., Weaver, R.W.: A generalization of chordal graphs. J. Graph Theory 8(2), 241-251 (1984) · Zbl 0541.05025 · doi:10.1002/jgt.3190080206 |
| [15] | Simis, A.: On the Jacobian module associated to a graph. Proc. Am. Math. Soc. 126, 989-997 (1998) · Zbl 0887.13014 · doi:10.1090/S0002-9939-98-04180-X |
| [16] | Tatakis, C., Thoma, A.: On the universal Gröbner bases of toric ideals of graphs. J. Comb. Theory, Ser. A 118, 1540-1548 (2011) · Zbl 1232.05094 · doi:10.1016/j.jcta.2011.01.005 |
| [17] | Villarreal, R.H.: Rees algebras of edge ideals. Commun. Algebra 23, 3513-3524 (1995) · Zbl 0836.13014 · doi:10.1080/00927879508825412 |
| [18] | Villarreal, R.H.: Monomial Algebras. Monographs and Textbooks in Pure and Applied Mathematics, vol. 238. Marcel Dekker, New York (2001) · Zbl 1002.13010 |
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.
