The normality conjecture for cut polytopes

At least 5 years old · documented by

Let G(V,E)G(V,E) be a graph, and let Cut⁡□(G)\operatorname{Cut}^\square(G) be the convex hull of the cut points δA∣B∈R∣E∣\delta_{A\vert B}\in\mathbb{R}^{\lvert E\rvert} over all unordered vertex partitions A∣BA\vert B of GG. A polytope is normal if every lattice point in kPkP is a sum of kk lattice points from PP for every k∈Nk\in\mathbb{N}. Normality conjecture for cut polytopes. The cut polytope Cut⁡□(G)\operatorname{Cut}^\square(G) is normal if and only if the graph GG has no K5K_5 minor. This is described as the most well-known conjecture in the area and concerns the relationship between normality of cut polytopes and the graph-minor structure of GG. The supplied text does not state whether the conjecture has been resolved.

References

Primary source

Michał Lasoń and Mateusz Michałek, “A note on seminormality of cut polytopes”, arXiv:2012.07907 (2020).

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.