Cut polytope has vertices on a line

DOI10.1016/J.ENDM.2018.11.010MaRDI QIDQ1739929zbMATH OpenOpenAlexWikidataFDO

Authors Nevena Marić

Publication date 29 April 2019

Full work available at URL https://arxiv.org/abs/1812.03212

zbMATH Keywords

cut polytopeBernoulli correlations

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The cut polytope $mCUT(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 $mathbf1$-CUT($n$) encoded as integers are approximately on the line $y=x-1/2$.

Recommendations

• scientific article; zbMATH DE number 718853
• scientific article; zbMATH DE number 17640
• On the cut polytope
• The even and odd cut polytopes
• On a positive semidefinite relaxation of the cut polytope

Cites work

• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• Geometry of cuts and metrics
• Multivariate distributions with fixed marginals and correlations
• Simplicial faces of the set of correlation matrices

This page was built for publication: Cut polytope has vertices on a line

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1739929)