Cut polytope has vertices on a line

DOI10.1016/J.ENDM.2018.11.010zbMATH Open1460.52015arXiv1812.03212OpenAlexW2904411152WikidataQ128811915 ScholiaQ128811915MaRDI QIDQ1739929FDOQ1739929

Authors: Nevena Marić 

Publication date: 29 April 2019

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$.

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

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

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)

Cites Work

• Simplicial faces of the set of correlation matrices
• Geometry of cuts and metrics
• Title not available (Why is that?)
• Multivariate distributions with fixed marginals and correlations

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)