On the Connectivity of Fiber Graphs

  • Raymond Hemmecke Department of Mathematics, Technische Universität München
  • Tobias Windisch Department of Mathematics, Technische Universität München
Keywords: Fiber connectivity, Gro ̈bner basis, Graver basis, Fiber graph

Abstract

We consider the connectivity of fiber graphs with respect to Gro ̈bner basis and Graver basis moves. First, we present a sequence of fiber graphs using moves from a Gro ̈bner 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 Engstro ̈m 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. 

Published
2015-06-11
Section
Articles