Tight Bounds for Hypercube Minor-Universality

Alex Scott; Dmitry Tsarev; Emma Hogan; Jane Tan; Lukas Michel; Youri Tamitegama

REVIEW 1 major objections 4 minor 16 references

Tight Bounds for Hypercube Minor-Universality

T0 review · 1 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read The $d$-dimensional hypercube is not minor-universal at $C\cdot 2^d/d$ edges, so the known lower bound is tight up to a constant factor.

desk verdict Tight hypercube minor-universality bound is nearly right, but the expander existence step cites a theorem that does not obviously give the stated 0.18 vertex expansion. read the letter →

arxiv 2502.06629 v1 pith:LINBA7KZ submitted 2025-02-10 math.CO

Emma Hogan , Lukas Michel , Alex Scott , Youri Tamitegama , Jane Tan , Dmitry Tsarev This is my paper · ORCID

classification math.CO MSC 05C8305C8005C35

keywords hypercubeminorsminor-universalityexpandergraphsedgeexpansionHammingdistancegraphembeddingCartesianproductspermutationdecomposition

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 paper proves that the hypercube $Q_d$ is not minor-universal for all sparse graphs: there are $3$-regular expander graphs with about $C\cdot 2^d/d$ edges that cannot appear as minors, for an absolute constant $C$. This settles an open question left by earlier work, whose lower bound said every graph with at most $c\cdot 2^d/d$ edges and no isolated vertices is a minor of $Q_d$, while its upper bound was weaker by a factor $\sqrt{d}$. The new upper bound matches the lower bound up to a constant factor, so the threshold for minor-universality of the hypercube is $\Theta(2^d/d)$ edges. The argument is a counting inequality over the coordinates of the cube, using edge expansion of the obstruction graph to force more vertices than $Q_d$ has. The paper also gives a shorter proof of the lower bound via a decomposition of grid permutations into one-dimensional permutations.

What carries the argument

The load-bearing object is a $3$-regular expander: a graph on $2n$ vertices with $|N(S)|\ge 0.18|S|$ for every set $S$ of at most $n$ vertices, whose existence is imported from the isoperimetric theorem for random regular graphs cited in the paper. Given a hypothetical minor, the proof passes to a subdivision $G'$ inside $Q_d$, then for each coordinate $i$ lets $S_i$ be the smaller half of the branch vertices split by bit $i$. Expansion forces at least $0.18|S_i|$ edges of $G$ to cross the $i$-th cut, so the total Hamming length of the subdivided paths is at least $0.18\sum_i|S_i|$, which is at least $0.18\cdot d|S|/8$. Every edge of $G'$ accounts for at most one unit of this length, so the subdivision would need more than $2^d$ vertices. The complementary lower-bound proof uses the lemma that every permutation of a $d$-dimensional grid factors into $2d-1$ one-dimensional permutations, which lets it route the required disjoint paths through a temporal coordinate.

What would settle it

Find, for some large $d$, a minor of $Q_d$ isomorphic to a 3-regular graph on $2n$ vertices with $2n\in[45\cdot 2^d/d,\,50\cdot 2^d/d]$ and $|N(S)|\ge 0.18|S|$ for all $|S|\le n$; the theorem says no such minor exists, so one explicit embedding would refute it.

Watch

Extended reading notes

Core claim

The paper establishes that there is an absolute constant $C>0$ such that $Q_d$ is not $(C\cdot 2^d/d)$-minor-universal. For this, it exhibits a $3$-regular graph $G$ on $2n$ vertices, with $2n$ between $45\cdot 2^d/d$ and $50\cdot 2^d/d$, whose neighbourhood expansion is $|N(S)|\ge 0.18|S|$ for every set $S$ of at most $n$ vertices, and shows that $G$ cannot be a minor of $Q_d$. The contradiction is a counting argument in the hypothetical subdivision: the sum of Hamming distances between branch vertices across all edges of $G$ is at least $0.18\sum_i|S_i|$, and because most strings in $S$ have more than $d/4$ ones, this exceeds $2^d$, more vertices than $Q_d$ has. Hence the earlier lower bound is tight up to a constant factor, resolving the open question from the predecessor paper.

Load-bearing premise

The weakest load-bearing premise is that 3-regular graphs of the required size really exist with the expansion property $|N(S)|\ge 0.18|S|$ for every set $S$ of at most $n$ vertices; this is imported from a cited isoperimetric theorem for random regular graphs and not proved in the paper.

Editorial extensions

If this is right

The threshold for hypercube minor-universality is $\Theta(2^d/d)$: every graph with at most $c2^d/d$ edges and no isolated vertices embeds, while some graphs with $C2^d/d$ edges do not.
The upper and lower bounds from the predecessor paper now match up to constants, closing the open question about which bound was tight.
A 3-regular expander of size about $2^d/d$ cannot be embedded as a minor no matter how its branch vertices are placed, because it would require more vertices than the cube has.
The new self-contained proof of the lower bound gives a shorter route to the positive result than the original argument.
The obstruction graph is itself very regular (3-regular), so the failure is not due to pathological irregularity but to expansion.

Reading between the lines

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

One extension the paper does not pursue: apply the same coordinate-splitting count to other Cartesian-product host graphs, to see whether the $\Theta(2^d/d)$ threshold is special to hypercubes or holds for broader families of products.
The existence of the 0.18-expander is imported; an explicit construction at the stated sizes would make the argument checkable by computation and might be a useful lemma for later work.
Optimizing the constants $0.18$, $45$, and $50$ could pin down the leading constant of the threshold instead of only its order of magnitude.
By the same counting logic, $r$-regular expanders with larger degree should yield obstructions at correspondingly larger edge budgets, suggesting a family of tight thresholds indexed by degree.

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

Short version: this paper answers a real open question with a clean counting argument, but the proof of Theorem 3.1 leans on a citation that needs checking. I would send it to referees, not desk-reject.

The new thing is quantitative. Benjamini, Kalifa and Tzalik showed Q_d is not K*2^d/sqrt(d) minor-universal; this paper improves the obstruction to C*2^d/d, matching the lower bound up to a constant and resolving one of their explicit questions. The upper-bound proof is genuinely neat: take a 3-regular expander on about 2^d/d vertices, assume a subdivision in Q_d, sum Hamming distances, and get more than 2^d vertices. I read that part carefully, and the inequalities hold given the expansion property. The lower-bound section is also a nice compression of the BKT argument.

Now the soft spot, which the stress-test note correctly identifies. The proof asserts that almost every 3-regular graph has |N(S)| >= 0.18|S| for all |S| <= n, citing [6, Theorem 1] and saying 0.18 satisfies the condition when r=3. But [6] is Bollobas's isoperimetric-number paper, and its standard theorem is an edge-isoperimetric statement. For r=3 the guaranteed constant is r/2 - sqrt(r-1) ~ 0.086, and converting edge boundary to vertex boundary loses up to another factor of r. That does not produce 0.18. So the expansion lemma, as cited, is not derived. It is probably true — random 3-regular graphs should be vertex expanders with a much better constant — but the authors need to cite a vertex-expansion result or give a short proof. As written, the key inequality |V(G')| > 2^d has no documented foundation.

Everything else looks solid. No circularity, no fitted parameters; the lower-bound reproduction is not used as evidence for the upper bound. The citation pattern is fine. This is a short, readable paper for anyone in extremal or structural graph theory following hypercube minor-universality.

Recommendation: accept for peer review, and ask the authors to fix the expander citation before publication. If they cannot, a two-line proof that random 3-regular graphs have vertex expansion > 0.18 should close the gap; I expect that proof to be straightforward.

Referee Report

1 major / 4 minor

Summary. The paper resolves a question of Benjamini, Kalifa and Tzalik about hypercube minor-universality. It proves that for an absolute constant C, the d-dimensional hypercube Q_d is not C*2^d/d-minor-universal, matching the lower bound from [5] up to a constant factor. The proof uses a 3-regular expander graph on 2n vertices, with n on the order of 2^d/d, and a Hamming-distance counting argument: assuming the expander is a minor of Q_d, the authors derive that any subdivision would require more than 2^d vertices, a contradiction. The paper also reproduces a short proof of the lower bound. The main new contribution is the upper-bound theorem, which is presented in Section 3.

Significance. If the expander-existence step is supplied, the theorem is significant: it tightens the previously known upper bound from K*2^d/sqrt(d) to C*2^d/d, thereby matching the known lower bound up to a constant and answering Question 1 of Benjamini et al. The counting argument is elegant and the paper is well structured. The lower-bound proof is a useful simplification of the argument in [5]. However, the central proof currently relies on an unverified and, on the standard reading of the cited reference, incorrect claim about vertex expansion of random 3-regular graphs.

major comments (1)

[Section 3, Theorem 3.1] The existence of a 3-regular graph G on 2n vertices with |N(S)| >= 0.18|S| for every S of size at most n is asserted with a bare reference to [6, Theorem 1]. The cited theorem of Bollobás concerns the edge-isoperimetric number of random r-regular graphs; it gives |∂S|/|S| >= r/2 - sqrt(r-1) - o(1), which for r=3 is about 0.086. Since |∂S| <= 3|N(S)|, that theorem yields only |N(S)| >= 0.0287|S|, too weak for the counting inequality. The sentence 'observe that 0.18 satisfies the condition in the theorem when r=3' is unexplained and appears inconsistent with the standard content of [6]. This is load-bearing: the final contradiction |V(G')| > 2^d uses the constant 0.18 directly. The authors must either prove a correct vertex-expansion lemma for random 3-regular graphs (for example, by a union-bound argument in the configuration model) or cite a source that genuinely gives a vertex-boundary expansion of 0.18.

minor comments (4)

[Section 2, Theorem 2.2] In the application of Lemma 2.1, σ is initially a permutation of Q_a □ {0}, which is a-dimensional. Lemma 2.1 would yield a decomposition into 2a-1 one-dimensional permutations, not 2d-1. The proof should clarify that σ is extended to a permutation of Q_d (fixing the remaining coordinates) before applying Lemma 2.1, or, alternatively, the number of time steps should be adjusted to match the dimension of the grid on which σ is defined.
[Section 3, paragraph after (2)] The statement 'Without loss of generality, we may assume that S_i = {s ∈ S : s_i = 1}' can be justified by flipping coordinate i in the hypercube; this should be stated explicitly, since it is not immediately obvious that the counting argument is invariant under coordinate flips.
[Section 3, final inequality] The verification that 0.18*(d/8)*45*(2^d/d) - 50*(2^d)/(2d) >= 2^d for sufficiently large d should be made explicit. Direct calculation gives 1.0125*2^d - 25*(2^d/d), which exceeds 2^d for d > 2000. Adding this one line would remove any doubt about the constants.
[Abstract and text] There are several typographical artefacts: 'thei r' in the abstract, ' /greaterorequalslant' in the proof of Theorem 3.1, and 'deﬁne' in the Introduction. These should be corrected in a final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 3.1 is a counting argument built on an externally cited expander-existence theorem; no fitted parameter or load-bearing self-citation appears.

full rationale

The paper's negative result is not obtained by assuming the conclusion. Theorem 3.1 invokes a standard existence theorem for 3-regular expander graphs (Bollobás [6]) to supply a graph G with |N(S)| ≥ 0.18|S|; this is an external, parameter-free input whose stated assumptions do not include the target non-universality claim. Given that graph, the contradiction is a self-contained counting inequality: a subdivision of G in Q_d must use enough vertices because each coordinate cut in Q_d induces at least 0.18|S_i| edges of G, and the total Hamming weight of the branch vertices is bounded below by d|S|/8. No quantity is fitted to the target 'Q_d is not m-universal'; there are no self-citations by the present authors; and the reproduction of the lower-bound proof from [5] in Section 2 is not used as evidence for the upper bound. The possible mismatch between the edge-isoperimetric theorem in [6] and the vertex-expansion requirement is a correctness or verification issue, not circularity, because the proof explicitly states the needed expansion property and attributes it to an external theorem.

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

The central upper bound uses no fitted constants; the only substantive inputs are the existence of high-expansion cubic graphs and elementary counting bounds. No new objects are postulated.

assumptions (5)

standard math Hall's theorem ensures any regular bipartite multigraph decomposes into perfect matchings.
Used in Lemma 2.1 to build the first one-dimensional permutation, the core of the shortening of the lower-bound proof.
domain assumption Bollobas' theorem on the isoperimetric number of random regular graphs guarantees a 3-regular graph on 2n vertices with |N(S)| >= 0.18|S| for all |S| <= n, for sufficiently large n.
Invoked in Section 3 to produce the expander obstruction; it is cited as [6, Theorem 1] and not proved in this paper.
standard math A graph of maximum degree at most 3 that appears as a minor of a host graph also appears as a topological minor, i.e., as a subdivision subgraph.
Used at the start of the Section 3 contradiction to pass from a 3-regular minor to a subdivision G' inside Q_d.
standard math For large d, the number of binary strings of length d with at most d/4 ones is much smaller than 2^d/d, and in particular smaller than |S|/2 under the chosen interval for n.
Used in Section 3 to lower bound the total number of ones among the 2n branch vertices, yielding the contradictory lower bound on |V(G')|.
standard math Coordinate flips are automorphisms of the hypercube, so one may assume S_i = {s in S : s_i = 1}.
Used in Section 3 to rewrite the sum of |S_i| as the total number of 1s in the branch vertex strings.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tight Bounds for Hypercube Minor-Universality." pith.science (2026). https://pith.science/paper/LINBA7KZ

@misc{pith2026250206629,
  author       = {Pith},
  title        = {Pith review of: Tight Bounds for Hypercube Minor-Universality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LINBA7KZ}},
  note         = {Machine review of arXiv:2502.06629}
}

abstract

Benjamini, Kalifa and Tzalik recently proved that there is an absolute constant $c>0$ such that any graph with at most $c\cdot2^d/d$ edges and no isolated vertices is a minor of the $d$-dimensional hypercube $Q_d$, while there is an absolute constant $K > 0$ such that $Q_d$ is not $(K\cdot2^d/\sqrt{d})$-minor-universal. We show that $Q_d$ does not contain 3-uniform expander graphs with $C\cdot2^d/d$ edges as minors. This matches the lower bound up to a constant factor and answers one of their questions.

Figures

Figures reproduced from arXiv: 2502.06629 by the authors.

**Figure 1.** Constructing paths (xi−1, i−1)→(xi , i) and (zi−1, i−1)→(zi , i) when zi = xi−1. Proof. Let G be a 3-regular graph with 2n vertices, where 2n ∈ [45 · 2 d/d, 50 · 2 d/d], that satisfies the following expansion property: for any set S ⊆ V (G) of at most n vertices, |N(S)| > 0.18|S|, where N(S) denotes the neighbours of S in V (G) \ S. It is well-known that such a graph exists (in fact, almost every 3-regular graph sat… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

[6]

Bollobás

B. Bollobás. The isoperimetric number of random regular graphs. European Jour- nal of combinatorics , 9(3):241–244, 1988

work page 1988
[5]

Hypercube minor-universality

I. Benjamini, O. Kalifa and E. Tzalik. Hypercube minor-u niversality. arXiv preprint arXiv:2501.13730 , 2025

work page Pith review arXiv 2025
[1]

N. Alon. Asymptotically optimal induced universal grap hs. Geometric and Func- tional Analysis , 27:1–32, 2017

work page 2017
[2]

Alon and R

N. Alon and R. Nenadov. Optimal induced universal graphs for bounded-degree graphs. Mathematical Proceedings of the Cambridge Philosophical S ociety, 166:61– 74, 2019

work page 2019
[3]

Alstrup, S

S. Alstrup, S. Dahlgaard and M. B. T. Knudsen. Optimal ind uced universal graphs and adjacency labeling for trees. Journal of the ACM , 64(4):1–22, 2017

work page 2017
[4]

Babai, F

L. Babai, F. Chung, P. Erdös, R. Graham and J. Spencer. On g raphs which contain all sparse graphs. In P. L. Hammer, A. Rosa, G. Sabidussi and J . Turgeon, editors, Theory and Practice of Combinatorics , volume 60 of North-Holland Mathematics Studies, pages 21–26. North-Holland, 1982

work page 1982
[7]

Bonamy, C

M. Bonamy, C. Gavoille and M. Pilipczuk. Shorter labelin g schemes for planar graphs. SIAM Journal on Discrete Mathematics , 36(3):2082–2099, 2022

work page 2022
[8]

F. R. K. Chung. Universal graphs and induced-universal g raphs. Journal of Graph Theory, 14(4):443–454, 1990. 6

work page 1990

Show all 16 references

[9]

Diestel and D

R. Diestel and D. Kühn. A universal planar graph under the minor relation. Journal of Graph Theory , 32(2):191–206, 1999

1999
[10]

Georgakopoulos

A. Georgakopoulos. On graph classes with minor-univer sal elements. Journal of Combinatorial Theory, Series B , 170:56–81, 2025

2025
[11]

Komjáth, A

P. Komjáth, A. H. Mekler and J. Pach. Some universal grap hs. Israel Journal of Mathematics, 64(2):158–168, 1988

1988
[12]

V. V. Lozin and G. Rudolf. Minimal universal bipartite g raphs. Ars Combinatoria, 84:345–356, 2007

2007
[13]

J. Pach. A problem of Ulam on planar graphs. European Journal of Combinatorics, 2(4):357–361, 1981

1981
[14]

R. Rado. Universal graphs and universal functions. Acta Arithmetica, 9:331–340, 1964

1964
[15]

Robertson, P

N. Robertson, P. Seymour and R. Thomas. Quickly excludi ng a planar graph. Journal of Combinatorial Theory, Series B , 62(2):323–348, 1994

1994
[16]

A. Y. Wu. Embedding of tree networks into hypercubes. Journal of Parallel and Distributed Computing , 2(3):238–249, 1985. 7

1985

Pith tools

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

[1] [6]

Bollobás

B. Bollobás. The isoperimetric number of random regular graphs. European Jour- nal of combinatorics , 9(3):241–244, 1988

work page 1988

[2] [5]

Hypercube minor-universality

I. Benjamini, O. Kalifa and E. Tzalik. Hypercube minor-u niversality. arXiv preprint arXiv:2501.13730 , 2025

work page Pith review arXiv 2025

[3] [1]

N. Alon. Asymptotically optimal induced universal grap hs. Geometric and Func- tional Analysis , 27:1–32, 2017

work page 2017

[4] [2]

Alon and R

N. Alon and R. Nenadov. Optimal induced universal graphs for bounded-degree graphs. Mathematical Proceedings of the Cambridge Philosophical S ociety, 166:61– 74, 2019

work page 2019

[5] [3]

Alstrup, S

S. Alstrup, S. Dahlgaard and M. B. T. Knudsen. Optimal ind uced universal graphs and adjacency labeling for trees. Journal of the ACM , 64(4):1–22, 2017

work page 2017

[6] [4]

Babai, F

L. Babai, F. Chung, P. Erdös, R. Graham and J. Spencer. On g raphs which contain all sparse graphs. In P. L. Hammer, A. Rosa, G. Sabidussi and J . Turgeon, editors, Theory and Practice of Combinatorics , volume 60 of North-Holland Mathematics Studies, pages 21–26. North-Holland, 1982

work page 1982

[7] [7]

Bonamy, C

M. Bonamy, C. Gavoille and M. Pilipczuk. Shorter labelin g schemes for planar graphs. SIAM Journal on Discrete Mathematics , 36(3):2082–2099, 2022

work page 2022

[8] [8]

F. R. K. Chung. Universal graphs and induced-universal g raphs. Journal of Graph Theory, 14(4):443–454, 1990. 6

work page 1990