Cut polytope has vertices on a line
share
The cut polytope CUT(n) is the convex hull of the cut vectors in a complete graph with vertex set {1,...,n}. It is well known in the area of combinatorial optimization and recently has also been studied in a direct relation with admissible correlations of symmetric Bernoulli random variables. That probabilistic interpretation is a starting point of this work in conjunction with a natural binary encoding of the CUT(n). We show that for any n, with appropriate scaling, all vertices of the polytope 1-CUT(n) encoded as integers are approximately on the line y= x-1/2.
READ FULL TEXT