Cut ideals of K₄-minor free graphs are generated by quadrics

DOI10.1307/MMJ/1320763056MaRDI QIDQ654935zbMATH OpenOpenAlexFDO

Authors Alexander Engström

Publication date 28 December 2011

Published in Michigan Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.1762, https://projecteuclid.org/euclid.mmj/1320763056

zbMATH Keywords

\(K_{4}\)-minor free graphscut ideals

Mathematics Subject Classification ID

Applications of graph theory (05C90) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: Cut ideals are used in algebraic statistics to study statistical models defined by graphs. Intuitively, topological restrictions on the graphs should imply structural statements about the corresponding cut ideals. Several theorems and many computer calculations support that. Sturmfels and Sullivant conjectured that the cut ideal is generated by quadrics if and only if the graph is free of K4-minors. Parts of the conjecture has been resolved by Brennan and Chen, and later by Nagel and Petrovic. We prove the full conjecture by introducing a new type of toric fiber product theorem.

Review text

The cut ideal \(I_{G}\) of a finite graph \(G\) describe questions in applied science (statistics, optimization, computer science, etc) into questions in commutative algebra. In [\textit{B. Sturmfels} and \textit{S. Sullivant}, Mich. Math. J. 57, 689--709 (2008; Zbl 1180.13040)] the algebraic properties of cut ideals for graphs with up to six vertices were studied and a number of conjectures were outlined. The paper under review considers one of these conjectures, namely: The cut ideal \(I_{G}\) is generated by quadrics if and only if \(G\) is free of \(K_{4}\)-minors. The conjecture follows as a corollary of Theorem 2.6, which gives a description of generating set of \(I_G\), and was proven by induction on the number of vertices of \(G\).

Recommendations

• Strong Koszulness of the toric ring associated to a cut ideal
• Toric geometry of series-parallel graphs
• Properties of cut ideals associated to ring graphs
• Monomial cut ideals
• The toric ideal of a graphic matroid is generated by quadrics

Cites work

• A note on standard systems and ultrafilters
• Algebraic algorithms for sampling from conditional distributions
• Algebraic Statistics for Computational Biology
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 48904 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Lectures on algebraic statistics
• Markov bases of binary graph models
• Multigraded commutative algebra of graph decompositions
• Properties of cut ideals associated to ring graphs
• Toric fiber products
• Toric geometry of cuts and splits
• Toric geometry of series-parallel graphs

Cited in

(18)

• Retracts and algebraic properties of cut algebras
• Ideals of graph homomorphisms
• Seminormality, canonical modules, and regularity of cut polytopes
• Lexicographic and reverse lexicographic quadratic Gröbner bases of cut ideals
• Multigraded commutative algebra of graph decompositions
• Gorenstein cut polytopes
• Monomial cut ideals
• A Gröbner basis characterization for chordal comparability graphs
• The \(h^\ast\)-polynomial of the cut polytope of \(K_{2,m}\) in the lattice spanned by its vertices
• Strong Koszulness of the toric ring associated to a cut ideal
• Toric geometry of series-parallel graphs
• Markov chain Monte Carlo methods for the regular two-level fractional factorial designs and cut ideals
• scientific article; zbMATH DE number 4116574 (Why is no real title available?)
• The three-state toric homogeneous Markov chain model has Markov degree two
• A note on seminormality of cut polytopes
• Classes of cut ideals and their Betti numbers
• Cycle algebras and polytopes of matroids
• Normality of cut polytopes of graphs is a minor closed property

This page was built for publication: Cut ideals of \(K_{4}\)-minor free graphs are generated by quadrics

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