Geometric shapes aren’t just pretty ornaments on a chalkboard. In optimization, they’re enormous, living laboratories where tiny binary decisions ripple into sweeping consequences. The CUT(n) polytope—the convex hull of cut vectors of a complete graph Kn—has loomed as a central but stubborn mystery: its vertices are famously elusive to describe with a neat, closed-form formula. The new work from the School of Computing at Union University in Belgrade, led by Nevena Marić, confronts that mystery head-on. It doesn’t just enumerate vertices; it reveals a surprisingly tidy, almost-linear backbone behind them, built from a probabilistic idea, a clever binary encoding, and a curious little function with a knack for zigzags and symmetry.
In plain terms, a vertex of CUT(n) is one of the binary corner points that describe which pairs of nodes in a complete graph sit on different sides of a cut. There are a lot of those corners as n grows—exponentially many, in fact. Yet the authors show that, if you flip all the bits to get the 1-CUT(n) polytope, you can track every vertex with a single closed-form recipe. What’s more, they attach to each vertex a unique integer via a binary encoding, and, strikingly, those integers align with a near-straight line when you scale them properly. It’s as if someone laid a road map over a sprawling city and you could read the terrain by looking at a single, cleverly drawn line.
Scholars typically chase vertex descriptions with heavy algorithms or by marching through the polytope’s skeleton. This paper instead gives you a direct formula—the kind of thing you can program once and then view as a crisp, algebraic fingerprint of the polytope’s entire vertex set. That’s especially notable because 0/1-polytopes like CUT(n) encode many combinatorial objects (matchings, stable sets, and more). A transparent, closed-form vertex description in this realm is rare and valuable, both as a theoretical milestone and as a practical benchmark for vertex-enumeration tools. The work also emphasizes a beautiful bridge between probability and geometry: the vertices of a purely geometric object emerge from agreement probabilities among symmetric Bernoulli random variables, a probabilistic lens that reframes how we think about cuts and correlations.
The research is anchored in a clear, human curiosity: can we peel back the onion of a famous polytope long enough to see a simple core? The answer, as this paper demonstrates, is yes. The authors walk us from a probabilistic interpretation of agreement probabilities to a binary encoding that turns a geometric listing problem into a number-theory tale. And they do so with a sense of elegance that makes the result feel inevitable in hindsight—even though it’s built from a sequence of clever, non-obvious steps. The lead author, Nevena Marić, based at the Union University School of Computing in Belgrade, Serbia, guides the narrative with the patience of a good professor and the wit of a mathematician who enjoys surprising connections.
A probability dance with cuts
The cut polytope CUT(n) collects all the way you can separate a graph’s vertices into two parts and then read off which pairs cross the cut. Each such partition yields a 0/1 vector: a 1 wherever an edge straddles the cut, and a 0 otherwise. Take all these vectors and form their convex hull; that hull is CUT(n). It’s a 0/1-polytope, and its vertices are precisely the non-redundant cut vectors associated with bipartitions of the vertex set. In the context of optimization, CUT(n) is the natural feasible region for the Max-Cut problem, a classical workhorse in combinatorial optimization with ties to physics, network design, and beyond.
A closely related object, the 1-CUT(n) polytope, arises when you flip every bit of a CUT(n) vertex. That bit-flip operation isn’t just a playful trick: it maps to a probabilistic interpretation. If you imagine n symmetric Bernoulli random variables (binary coins that land heads for 1 and tails for 0 with equal probability), the set of all attainable agreement probabilities between pairs (P(Bi = Bj)) forms a convex polytope. Huber and Marić showed that this agreement-probability polytope is exactly 1-CUT(n). In other words, the corners of a probabilistic landscape—where variables agree or disagree in extreme ways—are in one-to-one correspondence with flipping the cut’s corners.
That probabilistic perspective is more than a tidy story. It provides a natural way to describe the vertices of 1-CUT(n): they correspond to diagonal Bernoulli distributions where the two possible states are essentially mirror images of each other. When you take these diagonal distributions and map them to the corresponding agreement vectors, you land on the vertices of 1-CUT(n). It’s a neat bridge from randomness to geometry, and the bridge is sturdy enough to carry a direct, explicit vertex formula across it.
Binary encoding and the almost linear order
Once the probabilistic backbone is in place, the paper introduces a binary encoding to keep track of vertices in a compact, readable way. Instead of working with the n-bit vectors directly, they encode each with an integer in the range {0, 1, …, 2n−1}. The encoding is simple in principle: you treat the n-bit vector as a binary number and read it as an integer. This seems mundane, but it unlocks a remarkable visualization: if you plot the encoded vertex values against their index in the natural lexicographic ordering, the points line up almost like a straight line when you scale them by a factor that grows with n.
Concretely, for a fixed n, you obtain a sequence vn(1), vn(2), …, vn(2n−1) of integers, each the binary-encoded image of a vertex of 1-CUT(n). The paper proves that this sequence is strictly increasing with k and that, when you scale by 2^{(n−1)/2}, the points sit very close to the line y = x − 1/2. It’s not a perfect line, but the deviations have a tidy, structured pattern. This near-linearity is more than a pretty picture: it signals that the vertex set is arranged in a highly regular way, a clue that something deeper is at work below the surface combinatorics.
That near-linearity isn’t accidental. It frames the problem in a way that reveals a hidden recursive backbone. If you look at vn(k) through its recursive structure, you find a relation that connects vn(k) in dimension n to vn−1(·) in dimension n−1. In short, the geometry speaks in the language of a sequence of nested, binary-encoded steps. The authors make this precise with a recurrence that splits k into two halves and relates the two halves back to a lower-dimensional vertex set. The upshot is a clean, elegant engine that can churn out all encoded vertices in one pass, without chasing the polytope’s graph or exploring its facets one by one.
At the heart of this recursion sits a new integer-valued function, the alternating cycle function. It’s a mouthful, but the idea is beautifully simple: it encodes a kind of alternating rhythm that appears when you flip and recombine bits in a controlled way. The function has a few striking properties—periodicity, a wave-like pattern within each period, and a symmetry under certain compositions—that make it a natural building block for the explicit vertex formula. The authors show that the vertices of 1-CUT(n) can be written in terms of this alternating cycle function, layered across scales that are powers of two. The result is a closed-form description of the entire vertex set, not as an algorithm that searches for vertices, but as a single, compact expression with a transparent combinatorial structure.
The alternating cycle function and the explicit formula
Let’s give the intuition without getting lost in symbols. The alternating cycle function SN(k) behaves like a zigzag: as k runs through a block of length 2N, the value of SN(k) climbs from N down to 1 and then climbs back up to N, in a nicely palindromic, periodic fashion. This zigzag isn’t random; it has a kind compositional invariance when you feed it arguments that themselves come from the same family of functions with doubled periods. In particular, SN(S2N(k)) = SN(k), and SN composed with itself (in a few precise ways) yields stable, predictable results. This makes SN a perfect candidate to orchestrate a hierarchical construction across dimensions that are themselves powers of two.
From there, the authors assemble the explicit formula for the encoded vertices of 1-CUT(n). They prove that for n ≥ 3, the encoded vertex vn(k) can be written as a sum of a linear base term and a layered contribution from the alternating cycle function evaluated at progressively larger powers of two. In more intuitive terms: you start with a linear scaffold that accounts for the broad spread of the vertex values, and you attach successive, intricately structured zigzag layers that refine the details. Each layer corresponds to a level j in the hierarchy, weighted by a factor that grows as 2^{j^2}. The entire expression is finite, explicit, and valid for every n.
To make this concrete, the paper walks through worked examples. For n = 5, the eight- to sixteen-step decomposition reveals a vertex sequence that climbs in a precise pattern, matching the explicit numbers the formula predicts. The upshot is a complete, closed-form catalog of the encoded vertices for 1-CUT(n); by a simple complement, you also get the encoded vertices for CUT(n) itself. The corollary states that the encoded CUT(n) vertices w_n(k) are simply the complement of the 1-CUT(n) vertices in the encoding sense: w_n(k) = 2^{n a2} – 1 – v_n(k), where 2^{n a2} is the total number of potential binary coordinates (the dimension of the polytope’s binary face), and the encoding aligns with the same k-ordering.
What makes this result compelling isn’t just that a formula exists, but how it was built. The alternating cycle function acts like a micro-oscillating engine that, when stacked across scales, produces a globally consistent description of a complex object. It’s a vivid example of how a probabilistic starting point—where agreement probabilities among random bits become the coordinates of a geometric object—can be pushed all the way to a closed-form vertex enumeration. That blend of probability, combinatorics, and geometric intuition is exactly the kind of cross-pollination that makes theoretical computer science feel alive.
Why this matters beyond the math
Explicit vertex descriptions for 0/1-polytopes are a rare breed. In many famous families—stable set polytopes, matching polytopes, and others—no closed-form vertex list exists; researchers rely on algorithmic or implicit descriptions that are powerful but opaque. Here, we don’t just get a list; we get the full, algebraic blueprint that generates every vertex. That’s a rare clarity in a landscape where many problems are NP-hard to even state, let alone solve exactly. The work provides a concrete, testable benchmark for vertex-enumeration algorithms. If a new method claims to beat the old ones, it should reproduce the explicit formulas the authors derive, and it should do so efficiently for growing n. This is the sort of paper that quietly raises the bar for what “solved” looks like in the realm of 0/1-polytopes.
Beyond benchmarking, the paper helps crystallize a philosophy about structure. The cut polytope is central to max-cut, a problem with practical relevance in designing networks, circuits, and even certain physical systems. By revealing a hidden, nearly linear ordering and a compositional mechanism behind CUT(n)’s vertices, the authors invite a new way of thinking about why certain optimization landscapes look deceptively simple at scale. The probabilistic angle—using agreement patterns of Bernoulli variables as a lens on a purely geometric object—also hints at potential extensions to other families of polytopes where marginals and pairwise agreements play a guiding role. It’s a reminder that probability isn’t just a separate toolbox for statistics; it can be a language for geometry itself.
As a final note, this work grounds itself in a real place and a real researcher. The study and its explicit formula come from Nevena Marić and colleagues at Union University in Belgrade, Serbia, a reminder that bold theoretical advances aren’t restricted to a handful of famous labs. They can emerge from thoughtful, carefully argued work in classrooms and universities around the world. The paper closes with a practical appendix—a vertex-generation algorithm that lets other researchers reproduce and experiment with the construction in a straightforward, one-pass procedure. It’s the kind of contribution that invites others to pick up the baton and run with it, perhaps toward new polytopes or into new probabilistic interpretations of geometry.
