Sharp Threshold for Cliques in Random 0/1 Polytope Graphs

Catherine Babecki, Tycho Elling, Asaf Ferber · 2025

Read Sharp Threshold for Cliques in Random 0/1 Polytope Graphs by Catherine Babecki, Tycho Elling, Asaf Ferber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03212.txt.

Description

Catherine Babecki, Tycho Elling, and Asaf Ferber study in 2025 the graphs hidden inside random polytopes. Take random corners of a high-dimensional cube, keeping each with some chance, and join two corners when the segment between them is an edge of their convex hull. The team asks when that graph is sparse, expanding, or complete.

They give a short proof that a known cut-off governs edge density. Below a slightly lower cut-off, every vertex connects to nearly all others, a strong expansion result that settles an open question. A second, sharp threshold decides when the whole graph is one clique, with the constant pinned near 0.83.

Catalog record

CREATORCatherine Babecki, Tycho Elling, Asaf Ferber
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03212

Browse the full library · About the Tower of Babel