{"id":"53dafce7-0da5-4e91-b375-30984c32d2bf","arxiv_id":"2502.06629","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper proves that certain sparse 3-regular expander graphs with about a constant times 2^d/d edges cannot appear as minors of the d-dimensional hypercube. That closes a sqrt(d) gap in the known bounds and pins down the exact order of the hypercube's minor-universality threshold.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1 depends on an unstated verification that [6, Theorem 1] supplies vertex expansion 0.18 for 3-regular graphs; the standard edge-isoperimetric reading would not suffice.","rationale":"The reader's weakest assumption was that the expander existence theorem from [6] indeed delivers vertex expansion 0.18 for 3-regular graphs in the required size range. My stress-test concurs: this is the only externally imported step on which the upper-bound proof rests, and the exact verification is omitted from the manuscript. The rest of Section 3 is a clean counting argument and, assuming the expander property, the inequalities check out. I do not see an internal contradiction or a flaw in the minor-to-subdivision reduction. The concern is therefore not that the theorem is false, but that the proof as written does not exhibit the needed implication from [6, Theorem 1]; a short verification or an explicit statement of the theorem would remove the risk. Accordingly, I recommend CONDITIONAL acceptance: the mathematical result is plausible and well argued, but the cited expander condition should be made explicit and checked before the paper is finalized.","tokens_in":5808,"tokens_out":45624,"duration_ms":389865,"concrete_test":"Retrieve the exact statement of [6, Theorem 1] and substitute r = 3. Write out the guaranteed inequality for every set S of size at most 2n/2. If the theorem yields |N(S)| ≥ 0.18|S| directly, the proof is complete as written. If it yields only an edge-boundary lower bound, test whether translating it to vertex boundary can still give 0.18|S|; if not, redo the final estimate with the true constant (possibly much smaller) and check whether the contradiction remains.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central counting contradiction in Theorem 3.1 needs a 3-regular graph G on 2n vertices with |N(S)| ≥ 0.18|S| for every S with |S| ≤ n. The proof asserts this is 'well-known' and cites [6, Theorem 1], adding only 'observe that 0.18 satisfies the condition in the theorem when r = 3.' The preprint does not state which theorem is being invoked or how the condition is met. This is load-bearing: if [6, Theorem 1] is the standard edge-isoperimetric bound for random regular graphs, its r = 3 constant is r/2 − sqrt(r−1) ≈ 0.086, and converting edge boundary to the vertex boundary N(S) can lose another factor of up to 3, so the claimed 0.18 |S| lower bound on |N(S)| would not follow. The argument needs either a genuine vertex-expansion theorem with a constant above 0.18, or an explicit derivation from [6] that the vertex boundary of every set is at least 0.18|S|. Without this, the inequality |V(G')| > 2^d in the final paragraph has no foundation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":6002,"tokens_out":18747,"duration_ms":151362,"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":[{"comment":"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.","section":"Section 3, Theorem 3.1"}],"minor_comments":[{"comment":"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":"Section 2, Theorem 2.2"},{"comment":"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":"Section 3, paragraph after (2)"},{"comment":"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.","section":"Section 3, final inequality"},{"comment":"There are several typographical artefacts: 'thei r' in the abstract, ' /greaterorequalslant' in the proof of Theorem 3.1, and 'define' in the Introduction. These should be corrected in a final version.","section":"Abstract and text"}],"recommendation":"major_revision","confidential_remarks":"The paper's main idea is sound and the counting argument is convincing modulo the expander existence. The citation gap is likely fixable by adding a short probabilistic lemma. I would not recommend reject, as the missing piece is a standard result that can be proved in a page. The lower-bound section is a reproduction and, while it has a notational mismatch, it does not affect the central claim. The paper would be suitable for publication after the expander lemma is supplied and the presentation issues are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nNow 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.\n\nEverything 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.\n\nRecommendation: 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.","headline":"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.","tokens_in":6595,"tokens_out":4372,"would_cite":true,"duration_ms":39169,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C80","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["hypercube minors","minor-universality","expander graphs","edge expansion","Hamming distance","graph embedding","Cartesian products","permutation decomposition"],"falsifier":"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.","tokens_in":5576,"feed_emoji":"🧊","tokens_out":13586,"duration_ms":109687,"temperature":0.7,"pith_summary":"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.","feed_headline":"Expander graphs prove hypercube minor bound is tight","feed_subtitle":"A counting argument over cube coordinates matches the known lower bound, closing the open question on the threshold.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior lower bound that $Q_d$ is $c2^d/d$-minor-universal and the weaker upper bound $K2^d/\\sqrt{d}$, and provides the embedding strategy the short lower-bound proof follows.","marker":"[5]"},{"why":"Poses the exact question the paper answers: whether the lower bound or the $\\sqrt{d}$-weaker upper bound is tight.","marker":"[5, Question 1]"},{"why":"Gives the existence of 3-regular graphs on $2n$ vertices whose small neighbourhoods expand by a factor 0.18, the obstruction family on which Theorem 3.1 depends.","marker":"[6, Theorem 1]"}],"fun_headline_variants":["Hypercube minor threshold set by expander graphs","Expander graphs close hypercube minor question","Counting argument proves hypercube bound is tight","3-regular expanders break hypercube minor universality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hypercube minor threshold set by expander graphs","Expander graphs close hypercube minor question","Counting argument proves hypercube bound is tight","3-regular expanders break hypercube minor universality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000249,"raw_usage":{"total_tokens":1513,"prompt_tokens":873,"completion_tokens":640,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":489,"completion_tokens_details":{"reasoning_tokens":581}},"tokens_in":489,"tokens_out":640,"duration_ms":6422,"temperature":1.0,"reasoning_tokens":581,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:51:16.375416+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Hypercube minor-universality","cited_arxiv_id":"2501.13730","evidence_quote":"Supplies the prior lower bound that $Q_d$ is $c2^d/d$-minor-universal and the weaker upper bound $K2^d/\\sqrt{d}$, and provides the embedding strategy the short lower-bound proof follows."}],"review_version":1}