Hypercube minor-universality

Itai Benjamini , Or Kalifa , and Elad Tzalik · 2025

Read Hypercube minor-universality by Itai Benjamini , Or Kalifa , and Elad Tzalik (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-2501-13730.txt.

Description

Itai Benjamini, Or Kalifa, and Elad Tzalik study how large a graph the hypercube can contain in compressed form. Their 2025 paper uses graph minors, which shrink a graph by merging connected parts. A graph is called minor-universal for a size bound if every graph up to that size appears inside it as a minor.

The authors prove the hypercube of a given dimension holds all graphs up to a size that grows like its vertex count divided by the dimension. They also prove a matching style upper bound with a slightly weaker denominator, so the truth sits in a narrow band. A key step shows any reshuffling of a grid's points splits into a short product of one-coordinate reshuffles. The same bounds extend to products of other connected graphs.

Catalog record

CREATORItai Benjamini , Or Kalifa , and Elad Tzalik
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13730

Browse the full library · About the Tower of Babel