{"id":"2750c3f1-abb1-4b87-bb50-6636c9db8846","arxiv_id":"2501.13730","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"The d-dimensional hypercube is Ω(2^d/d)-minor-universal and not C 2^d/√d-minor-universal for an absolute constant C, improving both known bounds.","lead":"This paper proves that the d-dimensional hypercube contains every graph with up to about 2^d/d edges as a minor, and that it fails to contain all graphs with about 2^d/√d edges. The result narrows the known range for the hypercube's minor-universality and adds a new upper bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the expander-family input in Theorem 5.1 is standard, and the remaining issues are typographical or presentational.","rationale":"The reader's conditional verdict is reasonable: two small corrections are needed, but neither changes the main theorems. The weakest assumption identified by the reader is the expander family in Theorem 5.1; I agree this is the most external input, but it is a standard and true fact, so it is not a genuine correctness risk. I looked for an internal inconsistency in the combinatorial embedding and box permutation arguments and found none. The lower bound of Proposition 1.2 is terse and could be expanded, but a bijection argument justifies the claim that a single i-permutation fixing all but two points swaps them, and the counting lower bound follows. The paper's central contribution is therefore sound as far as the written proof shows.","tokens_in":17490,"tokens_out":34485,"duration_ms":302173,"concrete_test":"Verify that for every sufficiently large even n there exists a 3-regular graph on n vertices with Cheeger constant at least a fixed h>0, either by consulting [Ko24, Theorem 4.1.1] or by a direct probabilistic argument on random 3-regular graphs. If the family exists for every such n, Theorem 5.1 goes through as written (after correcting the constant C); if it only exists on a sparse sequence, the upper bound would need a new averaging argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central claim m(Q_d)=Ω(2^d/d) and m(Q_d)=O(2^d/√d). The argument for the lower bound rests on the box permutation decomposition, which is used only through its upper-bound half; that half is proved by the well-dispersed lemma and the d=2 reduction, and the induction is coherent. The combinatorial embedding machinery in Section 2 and the three-step construction in Section 3 are internally consistent: in Lemma 2.4 the star sets already include the roads from f_v to the subdivision vertices, so the connectivity of the model sets is present. The upper bound in Theorem 5.1 does rely on an external input: a family of 3-regular expanders on every sufficiently large even n with a fixed Cheeger lower bound h>0. This is standard and true via the random 3-regular model, so I do not regard it as a serious risk; the cited [Ko24, Theorem 4.1.1] should be checked for the 'every n' wording, but the probabilistic method supplies it. The misprinted constant C in Theorem 5.1 and the need to relabel k in Theorem 5.3 are fixable and do not affect the asymptotic results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17718,"tokens_out":27156,"duration_ms":239038,"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.","major_comments":[],"minor_comments":[{"comment":"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":"Section 5, proof of Theorem 5.1"},{"comment":"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":"Section 5.1, Theorem 5.3"},{"comment":"The phrase \"minor-university\" should be \"minor-universality\" (a typo).","section":"Section 1, Question 3"},{"comment":"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":"Section 4, proof of Proposition 4.6"},{"comment":"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":"Section 2, Definition 2.1"},{"comment":"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.","section":"Section 3.1"}],"recommendation":"minor_revision","confidential_remarks":"The central claims are sound and the proofs are coherent; the issues I found are localized and easily fixable. The proof of Theorem B's upper bound would be cleaner if the parameter k were used consistently with the statement, and the constant in Theorem 5.1 needs a small correction. I do not see a load-bearing flaw in Theorem A."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft spots, in order:\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\nWho 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.","headline":"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.","tokens_in":18327,"tokens_out":30664,"would_cite":true,"duration_ms":239658,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["minor-universal graphs","hypercube minors","box permutation decomposition","combinatorial embeddings","expander graphs","Cartesian product minors","separation profile"],"falsifier":"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.","tokens_in":17272,"feed_emoji":"🧊","tokens_out":13581,"duration_ms":110124,"temperature":0.7,"pith_summary":"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.","feed_headline":"Hypercube minor-universality pinned between 2^d/d and 2^d/sqrt d","feed_subtitle":"The d-cube contains every graph with at most C·2^d/d edges as a minor, and misses one near C·2^d/√d edges.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the 3-regular expander family on every sufficiently large even number of vertices with Cheeger constant at least a fixed $h>0$, the graph family used as the obstruction in Theorem 5.1.","marker":"[Ko24]"},{"why":"Provides the equivalence between graph minors and vertex-disjoint connected subgraph models, which underlies the combinatorial embedding arguments in Lemmas 2.2 and 2.4.","marker":"[N17]"},{"why":"Gives the earlier lower bound on minor-universality that Theorem A improves, replacing a bound of $2^d/d^\\kappa$ for some $\\kappa>1$ with $2^d/d$.","marker":"[KR96]"},{"why":"Supplies the prior $m(Q_d)=\\Omega(2^d/d^2)$ estimate, which the paper sharpens by a factor of $d$.","marker":"[Kr19]"},{"why":"Introduces the separation-profile idea that motivates the sphere-cut argument used to rule out the expander as a minor of the hypercube.","marker":"[BST12]"}],"fun_headline_variants":["Hypercube minor-universality: lower 2^d/d, upper 2^d/sqrt d","Every graph with O(2^d/d) edges fits as a minor in Q_d","Q_d's minor-universality: all graphs with at most 2^d/d edges","Gap in hypercube minor-universality shrinks to sqrt d","Proof: Q_d contains every graph with <=2^d/d edges as minor"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Hypercube minor-universality: lower 2^d/d, upper 2^d/sqrt d","Every graph with O(2^d/d) edges fits as a minor in Q_d","Q_d's minor-universality: all graphs with at most 2^d/d edges","Gap in hypercube minor-universality shrinks to sqrt d","Proof: Q_d contains every graph with <=2^d/d edges as minor"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001291,"raw_usage":{"total_tokens":5304,"prompt_tokens":1012,"completion_tokens":4292,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":628,"completion_tokens_details":{"reasoning_tokens":4177}},"tokens_in":628,"tokens_out":4292,"duration_ms":30488,"temperature":1.0,"reasoning_tokens":4177,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:43:44.514510+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}