2025/06/26 by Nevena Marić, Marić, Nevena
Computer Science · Decision Sciences · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2506.21787
openalex publication_date 2025/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The cut polytope CUT(n), defined as the convex hull of cut vectors in the complete graph Kn, is a central object in combinatorial optimization, with applications ranging from max-cut problems to correlation analysis. Building on a probabilistic interpretation via agreement probabilities among symmetric Bernoulli random variables, we derive an explicit closed-form formula for enumerating the vertices of the related polytope 1-CUT(n). Our approach is based on a natural binary encoding of cut vectors and introduces the alternating cycle function, a map that generates integer sequences with palindromic and recursive structure. This encoding directly captures the vertex structure and reveals that the scaled encoded vertices, perhaps unexpectedly, exhibit an almost-linear behaviour. This work provides the first explicit vertex enumeration formula for this classical polytope family.