On the connectivity of fiber graphs

DOI10.18409/JAS.V6I1.35zbMATH Open1344.05080arXiv1405.0812OpenAlexW2962776665MaRDI QIDQ2820007FDOQ2820007

Tobias Windisch, Raymond Hemmecke

Publication date: 13 September 2016

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

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.

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

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go Gr��bner basis]Graver basisfiber connectivityfiber graph

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)

Cited In (5)

• The fiber dimension of a graph
• Rapid mixing and Markov bases
• Title not available (Why is that?)
• 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)