On the connectivity of fiber graphs

DOI10.18409/JAS.V6I1.35MaRDI QIDQ2820007zbMATH OpenOpenAlexFDO

Authors Raymond Hemmecke, Tobias Windisch

Publication date 13 September 2016

Published in Journal of Algebraic Statistics (Search for Journal in Brave)

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

zbMATH Keywords

Graver basisfiber connectivityfiber graphGröbner basis

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Connectivity (05C40) Random walks on graphs (05C81) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Abstract: We consider the connectivity of fiber graphs with respect to Gr"obner basis and Graver basis moves. First, we present a sequence of fiber graphs using moves from a Gr"obner basis and prove that their edge-connectivity is lowest possible and can have an arbitrarily large distance from the minimal degree. We then show that graph-theoretic properties of fiber graphs do not depend on the size of the right-hand side. This provides a counterexample to a conjecture of Engstr"om on the node-connectivity of fiber graphs. Our main result shows that the edge-connectivity in all fiber graphs of this counterexample is best possible if we use moves from Graver basis instead.

Recommendations

• Higher connectivity of fiber graphs of Gröbner bases
• The fiber dimension of a graph
• Multigraded commutative algebra of graph decompositions
• Divisors on graphs, connected flags, and syzygies
• Crossing graphs of fiber-complemented graphs

Cited in

(6)

• The fiber dimension of a graph
• Rapid mixing and Markov bases
• scientific article; zbMATH DE number 4125433 (Why is no real title available?)
• Higher connectivity of fiber graphs of Gröbner bases
• Maximum likelihood estimation of toric Fano varieties
• Crossing graphs of fiber-complemented graphs

This page was built for publication: On the connectivity of fiber graphs

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