No-cut set conjecture for the metric polytope
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.
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
Antoine Deza and Gabriel Indik, “A counterexample to a conjecture of Laurent and Poljak”, arXiv:math/0512493 (2005).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.