Hypercube minor-universality

Elad Tzalik; Itai Benjamini; Or Kalifa

Hypercube minor-universality

T0 review · 0 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The d-dimensional hypercube contains every graph with at most about 2^d/d edges as a minor, and there is a graph with about 2^d/sqrt d edges that it misses.

desk verdict Genuine improvement on hypercube minor-universality with a nice new tool, but Proposition 1.2's lower-bound proof needs repair before the paper is fully rigorous. read the letter →

arxiv 2501.13730 v3 pith:4VYLJBID submitted 2025-01-23 math.CO math.MG

Itai Benjamini , Or Kalifa , Elad Tzalik This is my paper · ORCID

classification math.COmath.MG MSC 05C83

keywords minor-universalgraphshypercubeminorsboxpermutationdecompositioncombinatorialembeddingsexpanderCartesianproductseparationprofile

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The minor-universality of a graph $G$, written $m(G)$, is the largest $m$ such that every graph with at most $m$ edges and no isolated vertices appears as a minor of $G$. This paper proves that for the $d$-dimensional hypercube $Q_d$, the quantity $m(Q_d)$ is $\Omega(2^d/d)$ and also $O(2^d/\sqrt d)$. In plain terms, every graph with at most a constant multiple of $2^d/d$ edges can be found inside the hypercube as a minor, while some graph with at most a constant multiple of $2^d/\sqrt d$ edges cannot. The lower bound is carried by a new factorization statement for permutations of a product of finite sets, and the upper bound by a separation argument using a constant-degree expander as the hard graph. The same methods give a product-graph theorem for Cartesian products of arbitrary bounded connected graphs.

What carries the argument

Three tools carry the proof. A combinatorial embedding places vertices injectively and assigns each edge a walk, or road, so that roads of non-adjacent edges are disjoint; applied to the simple subdivision of a graph, Lemma 2.4 turns such an embedding into a genuine minor model. The box permutation decomposition (Proposition 1.2) states that every permutation of $[n_1]\times\cdots\times[n_d]$ factors as $2d-1$ one-dimensional permutations, where each factor moves only one coordinate, and that $2d-1$ factors are sometimes necessary. This decomposition lets the lower-bound proof route a matching through a Cartesian product one coordinate at a time, with a cycle factor separating the routes. The upper bound uses a 3-regular expander with Cheeger constant at least a fixed $h>0$: if it were a minor of $Q_d$, many pairwise disjoint roads would have to cross a single small sphere, and comparing the sphere size with the expander's expansion forces the expander to be too small.

What would settle it

On $X=[2]^d$, compute the minimum number of one-dimensional permutations needed to express the transposition swapping $(1,\ldots,1)$ with $(2,\ldots,2)$; the paper proves the minimum is $2d-1$, so any shorter factorization would falsify Proposition 1.2. For the upper bound, check whether a 3-regular expander with Cheeger constant at least the paper's $h$ exists on every even $n$ between $C2^d/\sqrt d$ and $2C2^d/\sqrt d$; if some dimension $d$ has no such expander in that window, the cited assumption and the proof of Theorem 5.1 fail.

Watch

Extended reading notes

Core claim

Theorem A is the paper's central claim: $m(Q_d)=\Omega(2^d/d)$ and $m(Q_d)=O(2^d/\sqrt d)$. Equivalently, there are absolute constants $C,C'>0$ such that every graph with no isolated vertices and at most $C2^d/d$ edges is a minor of $Q_d$, whereas some graph with no isolated vertices and at most $C'2^d/\sqrt d$ edges is not a minor of $Q_d$. This replaces earlier lower bounds of the form $2^d/d^\kappa$ with $\kappa>1$ and $2^d/d^2$, and it leaves only a $\sqrt d$ gap between the two sides. The companion Theorem B extends the phenomenon to Cartesian products: a product of connected graphs with at most $k$ vertices each becomes proportional to its number of vertices in minor-universality after two fixed helper graphs and a long cycle are inserted, while the unaugmented product is not $Ck^n/\sqrt n$-minor-universal.

Load-bearing premise

The upper bound depends on the existence of 3-regular expander graphs with Cheeger constant at least a fixed positive number on every sufficiently large even number of vertices; if such graphs only existed on a sparse set of sizes, the obstruction would not apply to every dimension $d$.

Editorial extensions

If this is right

Every graph with no isolated vertices and $O(2^d/d)$ edges embeds as a minor of the $d$-cube, so the hypercube is a universal host for all graphs of that size.
Some graph with $O(2^d/\sqrt d)$ edges and no isolated vertices does not embed, so the true threshold for hypercube minor-universality lies between $2^d/d$ and $2^d/\sqrt d$.
The product theorem gives the same dichotomy for Cartesian products of bounded connected graphs: with two helper factors the product is proportional to its volume in minor-universality, and without them it fails at $Ck^n/\sqrt n$.
The permutation factorization is tight: some permutations of a box require all $2d-1$ one-dimensional moves, a standalone statement about the complexity of permuting product sets.
Because any graph can be replaced by a bounded-degree graph of comparable size that contains it as a minor, the embedding problem reduces to routing maximum-degree-3 graphs through the host.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the sphere-separation step is the real obstruction, then the upper bound may be difficult to improve without a different non-embeddable graph, since any constant-degree expander of size $\Theta(2^d/\sqrt d)$ would encounter the same sphere argument.
The box permutation decomposition resembles a sorting-network statement for product sets and may be reusable in routing problems on grids and tori, where one-dimensional moves are cheap and higher-dimensional moves are expensive.
Theorem B suggests that a product's minor-universality is governed by its volume and its diameter; the paper's Question 5 on vertex-transitive graphs is the natural next test of that principle.
The $\sqrt d$ gap between the two bounds means neither side is known to be tight, and deciding which one is would require either an embedding of all graphs with $C2^d/\sqrt d$ edges or a new obstruction beyond plain expanders.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this is a real result. Theorem A sharpens the cited lower bound by a factor d and adds a new upper bound, which is a genuine step on a natural extremal question about the hypercube. The box permutation decomposition is a useful new tool, and Theorem B is more than a routine generalization.

What is solid: the main architecture is sound. Combinatorial embeddings are handled carefully, and Lemma 2.4's connectivity is actually fine—the star sets already include the roads from f_v to the subdivision vertices, so the worry that the roads need to be added separately does not survive a close reading. The lower-bound construction via piecewise embeddings and the cycle layer works, and the expander separation argument for the upper bound is valid. The citation pattern is clean; prior results are used as benchmarks, not crutches.

Soft spots, in order:

1. The lower-bound half of Proposition 1.2 (that the swap of the two corners requires 2d-1 one-dimensional permutations) is not proved as written. The sentence 'Since σ_j swaps τ(1,...,1) and τ(2,...,2)' is asserted, but from σ = τ'σ_jτ this does not immediately follow; it needs a real argument, probably using that the other points are fixed. I checked d=2 and the statement appears true, but the proof has a genuine gap. This does not affect Theorems A or B, since only the upper-bound half of the decomposition is used, but the proposition is advertised as a key component and should be correct.

2. The constant C in Theorem 5.1 is misprinted or at least muddled: the displayed formula and the later inequality do not line up. Easy fix, no effect on asymptotics.

3. The expander input (3-regular expanders on every sufficiently large even order) is standard and true via the random regular model. I do not regard it as a real risk, but the citation to course notes [Ko24] should be supplemented with a precise statement or the standard probabilistic construction.

Who should read this: people working on minors, expanders, and product graphs. It deserves a serious referee. I would send it out, with a request to repair the Proposition 1.2 proof and clean up the constants.

Referee Report

0 major / 6 minor

Summary. The paper studies m-minor-universality of the d-dimensional hypercube Q_d, defined as the largest m such that every graph with at most m edges and no isolated vertices is a minor of Q_d. The main result, Theorem A, is that m(Q_d) = Ω(2^d/d) and m(Q_d) = O(2^d/√d). The lower bound is proved through a combinatorial embedding framework (Section 2): an embedding of the simple subdivision of H into G suffices to show H is a minor of G. Section 3 embeds all bounded-degree graphs into a product H_4 ◻ C_{6n−2} ◻ H_k ◻ G_1 ◻ … ◻ G_n, using Proposition 1.2, the box permutation decomposition, as a black box to realize matchings with prescribed vertex positions. This yields the lower bound for Q_d and, more generally, the first part of Theorem B. Proposition 1.2 — that every permutation of an n_1×…×n_d box is a composition of 2d−1 one-dimensional permutations, with a matching lower bound — is proved in Section 4 using the well-dispersed lemma. The upper bound, Theorem 5.1, uses a standard family of 3-regular expanders: if such a graph with about 2^d/√d vertices were a minor of Q_d, a sphere-separation argument would force a sphere of Q_d to contain many pairwise disjoint road vertices, contradicting the small size of spheres in the cube. A product version of the upper bound is stated as Theorem B.

Significance. If correct, the paper improves the previously known lower bound for hypercube minor-universality by a factor of d over the Krivelevich–Nenadov bound, and it gives the first upper bound of the form O(2^d/√d), leaving only a √d gap. The proof is largely self-contained: Proposition 1.2 is proved from scratch with a clean combinatorial argument, the combinatorial-embedding machinery is explicit and checkable, and the lower-bound construction is quantitative with explicit constants. The upper bound relies on one standard external input, a family of 3-regular expanders on every sufficiently large even number of vertices, which is a well-known consequence of the probabilistic method. The paper also proves a generalized product theorem and poses several attractive open problems; the box permutation decomposition is a nice standalone result. The manuscript does not use fitted constants or circular reasoning, and the central derivations are coherent.

minor comments (6)

[Section 5, proof of Theorem 5.1] The displayed definition of the constant, C := 10√2e√πh, is inconsistent with the inequalities that follow: the chain n ≤ (10/h)|S_r| < (10√2e√π/h)·2^d/√d requires C = 10√2e√π/h, and the earlier case n < 10√2e√π·2^d/√d is only ≤ C·2^d/√d if C ≥ 10√2e√π. Please correct the displayed constant accordingly.
[Section 5.1, Theorem 5.3] The proof begins by replacing k with k+1 and concludes with an obstruction of size O((k+1)^n/√n). Since the theorem is stated for factor graphs on at most k vertices and claims a bound of C k^n/√n, please either state explicitly that this proves the result after renaming the parameter and note that k=2 follows from Theorem 5.1, or apply the same sphere argument to K_k^n to obtain the stated C k^n/√n.
[Section 1, Question 3] The phrase "minor-university" should be "minor-universality" (a typo).
[Section 4, proof of Proposition 4.6] The d=2 part would be easier to follow if the correspondence between the three matrix operations (row permutation, column permutation, row permutation) and the one-dimensional permutations σ'_2, σ_1, σ_2 were stated explicitly; as written, the composition order can be confusing.
[Section 2, Definition 2.1] The codomain notation ∪_{n∈N} (V_Y)^n should be clarified: V_Y is not defined, and the image of an edge should be described as a walk of positive length in Y with the specified endpoints.
[Section 3.1] In the derivation of the hypercube lower bound, the expression "Ω(2n)" should presumably be "Ω(2^n)"; please ensure the superscript renders correctly throughout the section.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is proved from a self-contained decomposition lemma and combinatorial embedding arguments, and the upper bound's expander input is an external standard result, not a fitted or self-cited premise.

full rationale

The paper's central claims are the lower bound m(Q_d)=Omega(2^d/d) and upper bound m(Q_d)=O(2^d/sqrt(d)). The lower bound is obtained through Theorem 3.1, which is proved using combinatorial embeddings, the simple-subdivision reduction, Vizing's theorem, and Proposition 1.2 (box permutation decomposition). Proposition 1.2 is proved in Section 4 entirely within the paper: the upper-bound half is derived from the Well-dispersed Lemma and the d=2 reduction, and the lower-bound half is shown by an explicit permutation swapping (1,...,1) and (2,...,2). No fitted constants or data-driven parameters appear in this chain, and no "prediction" is renamed from a fitted input. The prior lower bounds of Kleinberg-Rubinfeld and Krivelevich are cited only as benchmarks to contextualize the improvement, not as inputs to the proof. The upper bound in Theorem 5.1 invokes a family of 3-regular expanders with bounded Cheeger constant on every sufficiently large even number of vertices, citing [Ko24, Theorem 4.1.1]. This is an external, standard existence result, not a self-citation, and it is not equivalent to the theorem being proved. The separation-profile idea is credited to [BST12], but the actual argument is carried out self-containedly using spheres and the Cheeger inequality. Other self-citations, including [BDGZ24] and [Ka24], appear only in questions or contextual remarks and are not load-bearing. No step reduces, by construction or by self-citation, to its own inputs. The paper is self-contained in the sense relevant to circularity analysis; any concerns about the expander-family assumption's exact wording for every n are correctness or rigor risks, not circularity.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No fitted parameters or invented entities appear. The only hand-set numbers are the standard constants in the proof reductions and the upper-bound constant C, which is chosen from the expander Cheeger constant h rather than estimated from data. All nonstandard structural input is the expander family, cited to [Ko24].

free parameters (2)

Upper-bound constant C = 10√(2eπ)/h (as intended; the text displays C := 10√2e√πh)
Hand-set absolute constant in Theorem 5.1 chosen to dominate the sphere-size bound; it depends on the expander Cheeger lower bound h and is not fitted to data.
Lower-bound constant 1/16 = 1/16
Chosen so that the binary-tree reduction and Vizing matching partition leave enough room in the product graph; an arbitrary proof constant.

assumptions (5)

domain assumption There exists a family of 3-regular expander graphs on every sufficiently large even n with Cheeger constant at least a fixed h>0.
Used in Theorem 5.1 to supply hard-to-embed graphs with linear edge-expansion; cited to [Ko24, Theorem 4.1.1], not proved in the paper.
standard math Minor relation is transitive and Cartesian product is monotone under minors: if H≤G then H□L≤G□L.
Used throughout Section 3 to transfer minor-universality from smaller products to Q_d.
standard math Vizing's theorem: every graph with maximum degree 3 has edge-chromatic number at most 4.
Used in Step 3 of the lower bound and in the upper-bound separation argument to select a large matching among crossing edges.
standard math The binomial coefficient satisfies |S_k| ≤ binom(d,⌈d/2⌉) < √(2e/π) 2^d/√d.
Used in Theorem 5.1 to bound sphere sizes in the hypercube; follows from Stirling's formula.
domain assumption Every cycle C_m is a minor of Q_d for d ≥ ⌈log m⌉.
Used in Section 3.1 to embed C_{6n−2} into a hypercube of logarithmic dimension.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hypercube minor-universality." pith.science (2026). https://pith.science/paper/4VYLJBID

@misc{pith2026250113730,
  author       = {Pith},
  title        = {Pith review of: Hypercube minor-universality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4VYLJBID}},
  note         = {Machine review of arXiv:2501.13730}
}

abstract

A graph $G$ is $m$-minor-universal if every graph with at most $m$ edges (and no isolated vertices) is a minor of $G$. We prove that the $d$-dimensional hypercube, $Q_d$, is $\Omega\left(\frac{2^d}{d}\right)$-minor-universal, and that there exists an absolute constant $C >0$ such that $Q_d$ is not $\frac{C2^d}{\sqrt{d}}$-minor-universal. Similar results are obtained in a more generalized setting, where we bound the size of minors in a product of finite connected graphs. A key component of our proof is the following claim regarding the decomposition of a permutation of a box into simpler, one-dimensional permutations: Let $n_1, \dots, n_d$ be positive integers, and define $X := [n_1] \times \dots \times [n_d]$. We prove that every permutation $\sigma: X \to X$ can be expressed as $\sigma = \sigma_1 \circ \dots \circ \sigma_{2d-1}$, where each $\sigma_i$ is a one-dimensional permutation, meaning it fixes all coordinates except possibly one. We discuss future directions and pose open problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Tight Bounds for Hypercube Minor-Universality
math.CO 2025-02 accept novelty 7.0 of 10

The d-dimensional hypercube fails to contain 3-regular expander graphs with about C*2^d/d edges as minors, making the minor-universality threshold of the hypercube exactly of order 2^d/d.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages · cited by 1 Pith paper

[1]

Bollobás and P.A

B. Bollobás and P.A. Catlin and P. Erdős, Hadwiger's Conjecture is True for Almost Every Graph, European Journal of Combinatorics, Volume 1, Issue 3, Pages 195-199, 1980

work page 1980
[2]

Benjamini, Y

I. Benjamini, Y. Dikstein, R. Gross, M. Zhukovskii, Randomly Twisted Hypercubes: Between Structure and Randomness, Random Structures & Algorithms, Volume 66, Issue 1, 2024

work page 2024
[3]

Barrett and D

B. Barrett and D. Hume. Thick embeddings of graphs into symmetric spaces via coarse geometry. Preprint available from arXiv:2112.05305

arXiv
[4]

Benjamini, O

I. Benjamini, O. Schramm, and \'A . Tim \'a r. On the separation profile of infinite graphs. Groups Geom. Dyn. , 6(4):639--658, 2012

work page 2012
[5]

Fountoulakis, D

N. Fountoulakis, D. Kühn, and D. and Osthus, Minors in random regular graphs, Random Structures & Algorithms, Volume 35, Issue 4, Pages 444 - 463, 2008

work page 2008
[6]

Gromov and L

M. Gromov and L. Guth. Generalizations of the Kolmogorov-Barzdin embedding estimates. Duke Math. J., 161(13):2549--2603, 2012

work page 2012
[7]

Guth, Recent progress in quantitative topology, Surveys in Differential Geometry, 22(1):191–216, 2017

L. Guth, Recent progress in quantitative topology, Surveys in Differential Geometry, 22(1):191–216, 2017

work page 2017
[8]

Hoory, N

S. Hoory, N. Linial, and A. Wigderson, Expander Graphs and Their Applications, Bulletin of the American Mathematical Society, Volume 43, Number 4, Pages 439–561, October 2006

work page 2006

Show all 14 references

[9]

O. Kalifa. Thick embeddings into the Heisenberg group and coarse wirings into groups with polynomial growth. arXiv preprint arXiv:2410.20956v1 , 2024

2024 arXiv
[10]

A. N. Kolmogorov and Y. M. Barzdin. On the realization of networks in three-dimensional space. In Selected Works of Kolmogorov, Kluwer, Dordrecht, 3:194--202, 1993

1993
[11]

Kowalski, An Introduction to Expander Graphs, ETH Zürich, Version of January 8, 2024

E. Kowalski, An Introduction to Expander Graphs, ETH Zürich, Version of January 8, 2024. Available at kowalski@math.ethz.ch

2024
[12]

Krivelevich, B

M. Krivelevich, B. Sudakov, Minors in Expanding Graphs, Geometric and Functional Analysis, Volume 19, pages 294–331, 2009

2009
[13]

Sergey Norin, Graph Minor Theory, Lecture notes for the topics course on Graph Minor theory, March 13, 2017, Winter 2017

2017
[14]

Robbins, ``A remark on Stirling's formula,'' Mathematical Notes, edited by F

H. Robbins, ``A remark on Stirling's formula,'' Mathematical Notes, edited by F. A. Ficken, University of Tennessee, University of Tennessee, Knoxville, Tenn., 1955

1955

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Bollobás and P.A

B. Bollobás and P.A. Catlin and P. Erdős, Hadwiger's Conjecture is True for Almost Every Graph, European Journal of Combinatorics, Volume 1, Issue 3, Pages 195-199, 1980

work page 1980

[2] [2]

Benjamini, Y

I. Benjamini, Y. Dikstein, R. Gross, M. Zhukovskii, Randomly Twisted Hypercubes: Between Structure and Randomness, Random Structures & Algorithms, Volume 66, Issue 1, 2024

work page 2024

[3] [3]

Barrett and D

B. Barrett and D. Hume. Thick embeddings of graphs into symmetric spaces via coarse geometry. Preprint available from arXiv:2112.05305

arXiv

[4] [4]

Benjamini, O

I. Benjamini, O. Schramm, and \'A . Tim \'a r. On the separation profile of infinite graphs. Groups Geom. Dyn. , 6(4):639--658, 2012

work page 2012

[5] [5]

Fountoulakis, D

N. Fountoulakis, D. Kühn, and D. and Osthus, Minors in random regular graphs, Random Structures & Algorithms, Volume 35, Issue 4, Pages 444 - 463, 2008

work page 2008

[6] [6]

Gromov and L

M. Gromov and L. Guth. Generalizations of the Kolmogorov-Barzdin embedding estimates. Duke Math. J., 161(13):2549--2603, 2012

work page 2012

[7] [7]

Guth, Recent progress in quantitative topology, Surveys in Differential Geometry, 22(1):191–216, 2017

L. Guth, Recent progress in quantitative topology, Surveys in Differential Geometry, 22(1):191–216, 2017

work page 2017

[8] [8]

Hoory, N

S. Hoory, N. Linial, and A. Wigderson, Expander Graphs and Their Applications, Bulletin of the American Mathematical Society, Volume 43, Number 4, Pages 439–561, October 2006

work page 2006