pith. sign in

arxiv: 1812.03212 · v1 · pith:H3BCCRMLnew · submitted 2018-12-07 · 💻 cs.DM · math.CO

Cut polytope has vertices on a line

classification 💻 cs.DM math.CO
keywords polytopelineverticesadmissibleappropriateapproximatelyareabeen
0
0 comments X
read the original abstract

The cut polytope ${\rm CUT}(n)$ is the convex hull of the cut vectors in a complete graph with vertex set $\{1,\ldots,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 ${\mathbf 1}$-CUT($n$) encoded as integers are approximately on the line $y= x-1/2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.