No-cut set conjecture for the metric polytope
Let be the metric polytope, and let its fractional vertices be the vertices that are not integral. The restriction of to its fractional vertices is the graph whose vertices are these fractional vertices and whose edges are the edges of joining them. No-cut set conjecture. For , the restriction of to its fractional vertices is connected.
This conjecture asks whether the fractional vertices form a connected subgraph after the integral cut vertices are removed. The supplied text does not state a resolution, so its status remains open here.
References
Primary source
Antoine Deza and Gabriel Indik, “A counterexample to a conjecture of Laurent and Poljak”, arXiv:math/0512493 (2005).
Progress summary
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.