Combinatorial degree bound for toric ideals of hypergraphs

DOI10.1142/S0218196713500331MaRDI QIDQ2854971zbMATH OpenOpenAlexFDO

Authors Elizabeth Gross, Sonja Petrović

Publication date 24 October 2013

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

bicoloringMarkov basesminimal generatorsseparatortoric ideal

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Hypergraphs (05C65) Combinatorial aspects of commutative algebra (05E40) Toric varieties, Newton polyhedra, Okounkov bodies (14M25)

Abstract: Associated to any hypergraph is a toric ideal encoding the algebraic relations among its edges. We study these ideals and the combinatorics of their minimal generators, and derive general degree bounds for both uniform and non-uniform hypergraphs in terms of balanced hypergraph bicolorings, separators, and splitting sets. In turn, this provides complexity bounds for algebraic statistical models associated to hypergraphs. As two main applications, we recover a well-known complexity result for Markov bases of arbitrary 3-way tables, and we show that the defining ideal of the tangential variety is generated by quadratics and cubics in cumulant coordinates.

Recommendations

• Bounds on the regularity of toric ideals of graphs
• A bound on degrees of primitive elements of toric ideals of graphs
• Hypergraph encodings of arbitrary toric ideals
• On complete intersection toric ideals of graphs
• Degree and regularity of Eulerian ideals of hypergraphs
• Toric algebra of hypergraphs
• Graphs and complete intersection toric ideals
• Regularity and \(h\)-polynomials of toric ideals of graphs
• Arithmetical rank of toric ideals associated to graphs
• scientific article; zbMATH DE number 850070

Cites work

• A divide-and-conquer algorithm for generating Markov bases of multi-way tables
• A finiteness theorem for Markov bases of hierarchical models
• Algebraic algorithms for sampling from conditional distributions
• Binary cumulant varieties
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• INDISPENSABLE BINOMIALS OF FINITE GRAPHS
• Indispensable monomials of toric ideals and Markov bases
• Markov bases of binary graph models
• Markov bases of three-way tables are arbitrarily complicated
• Minimal generators of toric ideals of graphs
• Minimal systems of binomial generators and the indispensable complex of a toric ideal
• On the universal Gröbner bases of toric ideals of graphs
• Rees algebras of edge ideals
• Set-theoretic defining equations of the tangential variety of the Segre variety
• Some characterizations of minimal Markov basis for sampling from discrete conditional distribu\-tions
• Toric ideals generalized by quadratic binomials
• Toric Ideals of Phylogenetic Invariants

Cited in

(16)

• Bouquet algebra of toric ideals
• Neural ideals and stimulus space visualization
• Hypergraph encodings of arbitrary toric ideals
• On the strongly robust property of toric ideals
• Goodness of fit for log-linear network models: dynamic Markov bases using hypergraphs
• Toric algebra of hypergraphs
• The Markov complexity of book graphs
• CIO and ring graphs: deficiency and testing
• Comparing invariants of toric ideals of bipartite graphs
• Hypergraph LSS-ideals and coordinate sections of symmetric tensors
• The strongly robust simplicial complex of monomial curves
• Self-dual projective toric varieties and their ideals
• Toricness of ideals generated by an arbitrary collection of 2-minors of an m × n generic matrix
• Distance reducing Markov bases
• On the dimension of the strongly robust complex for configurations in general position
• Robust graph ideals

This page was built for publication: Combinatorial degree bound for toric ideals of hypergraphs

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