An Explicit Formula for Vertex Enumeration in the CUT(n) Polytope via Probabilistic Methods
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918098101075968 |
|---|---|
| author | Marić, Nevena |
| author_facet | Marić, Nevena |
| contents | We present an explicit closed-form formula for the vertices of the classical cut polytope $\operatorname{CUT}(n)$, defined as the convex hull of cut vectors of the complete graph $K_n$. Our derivation proceeds via a related polytope, denoted $\mathbf{1}$-$\operatorname{CUT}(n)$, whose vertices are obtained by flipping all bits of the $\operatorname{CUT}(n)$ vertices. This polytope arises naturally in a probabilistic context involving agreement probabilities among symmetric Bernoulli random variables which serves as the starting point of this work.
Our approach constructs the vertex set recursively via a binary encoding that stems from this probabilistic perspective. We prove that the resulting sequence of encoded integers, when appropriately scaled, exhibits an almost-linear behavior closely approximating the line $y = x - \frac{1}{2}$. This structure motivates the introduction of the alternating cycle function, an integer-valued map whose key property is power-of-two composition invariance. The function serves as the foundation for our closed-form enumeration formula.
The result provides a rare instance of explicit vertex characterization for a $0$/$1$-polytope and offers a transparent combinatorial construction independent of enumeration algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21787 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Explicit Formula for Vertex Enumeration in the CUT(n) Polytope via Probabilistic Methods Marić, Nevena Combinatorics Discrete Mathematics Optimization and Control Probability We present an explicit closed-form formula for the vertices of the classical cut polytope $\operatorname{CUT}(n)$, defined as the convex hull of cut vectors of the complete graph $K_n$. Our derivation proceeds via a related polytope, denoted $\mathbf{1}$-$\operatorname{CUT}(n)$, whose vertices are obtained by flipping all bits of the $\operatorname{CUT}(n)$ vertices. This polytope arises naturally in a probabilistic context involving agreement probabilities among symmetric Bernoulli random variables which serves as the starting point of this work. Our approach constructs the vertex set recursively via a binary encoding that stems from this probabilistic perspective. We prove that the resulting sequence of encoded integers, when appropriately scaled, exhibits an almost-linear behavior closely approximating the line $y = x - \frac{1}{2}$. This structure motivates the introduction of the alternating cycle function, an integer-valued map whose key property is power-of-two composition invariance. The function serves as the foundation for our closed-form enumeration formula. The result provides a rare instance of explicit vertex characterization for a $0$/$1$-polytope and offers a transparent combinatorial construction independent of enumeration algorithms. |
| title | An Explicit Formula for Vertex Enumeration in the CUT(n) Polytope via Probabilistic Methods |
| topic | Combinatorics Discrete Mathematics Optimization and Control Probability |
| url | https://arxiv.org/abs/2506.21787 |