Robust graph ideals

DOI10.1007/S00026-015-0288-3MaRDI QIDQ891950zbMATH OpenOpenAlexFDO

Authors Adam Boocher, Bryan Christopher Brown, Timothy Duff, Laura Lyman, Takumi Murayama, Amy Nesky, Karl Schaefer

Publication date 18 November 2015

Published in Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graph idealstoric idealsuniversal Gröbner bases

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Abstract: Let I be a toric ideal. We say I is robust if its universal Groebner basis is a minimal generating set. We show that any robust toric ideal arising from a graph G is also minimally generated by its Graver basis. We then completely characterize all graphs which give rise to robust ideals. Our characterization shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of G.

Review text

Let \(I\) be a toric ideal. \(I\) is said robust if its universal Gröbner basis is a minimal generating set. In this paper the authors prove that ``any robust toric ideal \(I_G\) arising from a graph \(G\) is also minimally generated by its Graver Basis. In other words, the minimality of the universal Gröbner basis of \(I_G\) implies that of the Graver basis of \(I_G\). This is an open question for general toric ideals. The main result of the paper is a complete characterization of all graphs which give rise to robust ideals. Such a characterization ``shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of \(G\). A relevant result in such a context is a graph theoretic characterization of circuits [\textit{R. H. Villarreal}, Commun. Algebra 23, No. 9, 3513--3524 (1995; Zbl 0836.13014)].

Recommendations

• Robustness of graph properties
• scientific article; zbMATH DE number 7055493
• Publication:4862353
• Ideals in graph algebras
• Ideals of graph homomorphisms
• On the critical ideals of graphs
• Robust \(\ell_2\)-hypergraph and its applications
• Tree robustness of a graph
• On the ideal theory of graphs
• Algorithm Theory - SWAT 2004

Cites work

• Combinatorial degree bound for toric ideals of hypergraphs
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• Minimal generators of toric ideals of graphs
• On the universal Gröbner bases of toric ideals of graphs
• Rees algebras of edge ideals
• Robust toric ideals
• Toric ideals generalized by quadratic binomials
• Universal Gröbner bases of colored partition identities

Cited in

(14)

• Bouquet algebra of toric ideals
• Hypergraph encodings of arbitrary toric ideals
• On the strongly robust property of toric ideals
• On robustness and related properties on toric ideals
• Robust toric ideals
• On the relative size of toric bases
• Strongly robust toric ideals in codimension 2
• scientific article; zbMATH DE number 7055493 (Why is no real title available?)
• The closure of a linear space in a product of lines
• The strongly robust simplicial complex of monomial curves
• Self-dual projective toric varieties and their ideals
• Toric ideals of graphs minimally generated by a Gröbner basis
• On the dimension of the strongly robust complex for configurations in general position
• Generalized robust toric ideals

This page was built for publication: Robust graph ideals

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