The normality conjecture for cut polytopes

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 δABRE\delta_{A\vert B}\in\mathbb{R}^{\lvert E\rvert} over all unordered vertex partitions ABA\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 kNk\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.

Sources & referencesView supporting material

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.