Ring graphs and complete intersection toric ideals

DOI10.1016/J.DISC.2009.03.020MaRDI QIDQ960950zbMATH OpenOpenAlexFDO

Authors Isidoro Gitler, Enrique Reyes, Rafael H. Villarreal

Publication date 29 March 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603718

complete intersection free rank primitive cycle property rank ring graph toric ideal

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

Abstract: We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Groebner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Groebner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.

Review text

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.

Recommendations

Cites work

Cited in

(53)

Describes a project that uses

Uses Software

cisimplicial

This page was built for publication: Ring graphs and complete intersection toric ideals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q960950)