Graver-basis edge-connectivity conjecture for fiber graphs

Let AZd×nA\in\mathbb{Z}^{d\times n} be an integer matrix with ker(A)Z0n={0n}\ker(A)\cap\mathbb{Z}_{\geq 0}^n=\{\mathbf{0}_n\}. For each right-hand side, let the Graver fiber graph be the fiber graph whose edges are defined by the Graver basis of AA; its edge-connectivity is the minimum number of edges whose removal disconnects the graph, and its minimal degree is the minimum vertex degree.

Graver-basis edge-connectivity conjecture. In all Graver fiber graphs of AA, the edge-connectivity equals the minimal degree.

The source motivates this conjecture from results showing that Graver moves give strong edge-connectivity properties, while noting that the corresponding vertex-connectivity question is unresolved. The supplied text gives no resolution of this edge-connectivity conjecture.

Sources & referencesView supporting material

Primary source

Raymond Hemmecke and Tobias Windisch, “On the Connectivity of Fiber Graphs”, arXiv:1405.0812 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.