Sturmfels–Sullivant's normality conjecture for cut polytopes

From papers

Let GG be a finite graph without loops or multiple edges. For each subset SS of its vertex set, let δG(S)\delta_G(S) be the associated cut semimetric, let AGA_G be the set of all such cut semimetrics, and let Cut(G)=conv(AG){\rm Cut}^\square(G)=\operatorname{conv}(A_G) be the cut polytope. A lattice polytope is normal when its associated affine semigroup is saturated; equivalently here, if XG={(a,1):aAG}X_G=\{(\mathbf a,1):\mathbf a\in A_G\}, when

Z+(XG)=Z(XG)Q+(XG).\mathbb Z_+(X_G)=\mathbb Z(X_G)\cap\mathbb Q_+(X_G).

Sturmfels–Sullivant's conjecture. The cut polytope Cut(G){\rm Cut}^\square(G) is normal if and only if GG has no K5K_5 minor.

The conjecture is the central normality question for cut polytopes. The paper proves that normality is minor closed and establishes the conjecture for several classes of graphs, but states that the full conjecture remains open; it is enough to consider 4-connected plane triangulations.

Progress summary

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

Sources & referencesView supporting material

Primary source

Hidefumi Ohsugi, “Normality of cut polytopes of graphs is a minor closed property”, arXiv:0906.5303 (2009).

Solutions 0

No solutions have been posted yet.