{"id":"6c2f55b4-7122-49d3-b73e-df52e459619a","arxiv_id":"2501.14286","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A generalized roll-back method is claimed to embed edge-colored subdivisions of complete graphs into families of expanders, but key steps in the proof are flawed.","lead":"This paper develops a colorful roll-back method for embedding edge-colored graphs, including subdivisions of complete graphs, into families of pseudorandom expanders, with applications to distance graphs over finite fields. The proof of the main theorems contains gaps, including an unjustified inequality and an inconsistent use of a degree parameter.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.6 is inapplicable in the proof of Theorem 1.3: the asserted bound |V(F)|+5sD < c|V|/2 does not follow from the stated hypotheses, and feasible parameters violate it.","rationale":"The reader is right that the proof of Theorem 1.3 has a load-bearing gap around Lemma 3.6, but the specific reason identified by the reader is not the true obstruction. The claim that D must be at least Δmon(H) is not necessary: Lemma 3.6 can embed the star forest with all vertices labelled roots, so high monochromatic degrees only make the goodness condition easier, and the Path Connection Lemma is applied after deleting the branch vertices, to a graph of maximum monochromatic degree at most 2. The real problem is quantitative: the proof asserts |V(F)|+5sD < c|V|/2 without deriving it from the hypotheses. The derivation skips the 5sD term and, as the numeric example shows, the asserted inequality can fail even when every hypothesis of Theorem 1.3 is met. Since the entire existence proof depends on Lemma 3.6, the main theorem is not established as written. The paper's roll-back framework is promising and the gap may be repairable, but that would require either a modified hypothesis controlling sD relative to Δ^2 or a new argument for embedding the star forest that avoids the strong loss of 5sD vertices.","tokens_in":17354,"tokens_out":39163,"duration_ms":332862,"concrete_test":"Evaluate the exact inequality |V(F)|+5sD < c|V|/2 for the feasible parameter set (n=10^12, t=1, D=3, p=1.6×10^{-8}, β=3.2×10^2, s≈4×10^{10}, ℓ=75, c=0.12, Δ=1.4×10^4), using |V(H)|=7×10^9. If the inequality is false, as this calculation indicates, Lemma 3.6 does not apply and Theorem 1.3 is unproven as stated; an independent construction of the star forest embedding in this parameter regime would be needed to refute the concern.","verdict_should_be":"REJECT","load_bearing_attack":"In the proof of Theorem 1.3, Lemma 3.6 is the only mechanism that produces the initial good embedding of the star forest F. Its hypothesis is |V(F)|+5sD < c|V|/2. The proof derives Δ^2 < c|V|/4 from |V|>|V(H)|>(1/2)ℓΔ^2 and then asserts 'This implies Δ(Δ+1) ≤ c|V|/2 − 5sD'. That implication is invalid: Δ^2 < c|V|/4 gives only Δ(Δ+1) < 2Δ^2 < c|V|/2, with no margin left for the 5sD term. Combining the size condition |V(H)|≤|V|−6sD with |V(H)|≥(ℓ/2)Δ^2 yields Δ^2≤(2/ℓ)(|V|−6sD), so the needed inequality collapses to roughly sD < 2|V|/(5ℓ), which is not implied by the only available bound sD < |V|/6. Concretely, take t=1, D=3, n=10^12, p=1.6×10^{-8}, β=3.2×10^2 (so s≈4×10^{10}, ℓ=75), c=0.12, Δ=1.4×10^4. These satisfy Δ≤(1−c)pn and |V(H)|≤n−6sD, but |V(F)|+5sD≈5.9×10^{11} > c n/2 = 6×10^{10}. Hence Lemma 3.6 cannot be invoked and the proof of the central theorem has no valid starting step in this regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a colorful generalization of the roll-back method for embedding edge-colored graphs into families of expander-like graphs. The main technical contributions are the Forest Extension Lemma and the Path Connection Lemma, which are then applied to prove Theorem 1.3, asserting that a family of (p,β)-jumbled graphs on n vertices contains every [t]-edge-colored subdivision of K_Δ with paths between branch vertices of length at least ℓ, provided Δ ≤ (1−c)pn and |V(H)| ≤ n − 6sD. The authors derive finite-field corollaries (Theorems 1.7 and 1.8) for distance graphs over finite vector spaces.","tokens_in":17719,"tokens_out":13024,"duration_ms":104703,"significance":"If the main theorem were correct, the paper would substantially generalize earlier work of Draganić, Krivelevich, and Nenadov and would give new nearly spanning embedding results for edge-colored graphs and for distance graphs over finite fields. The lower-level roll-back framework—Removal Lemma, Vertex Extension Lemma, Forest Extension Lemma, Path Connection Lemma—is carefully developed and appears to be a useful contribution in its own right. However, the proof of the central embedding theorem contains load-bearing quantitative errors and an omitted hypothesis, so the advertised applications are not currently supported.","major_comments":[{"comment":"The proof miscomputes the size of a subdivision: for H a subdivision of K_Δ with paths of length at least ℓ, the number of vertices is at least Δ + (ℓ−1)Δ(Δ−1)/2, which is strictly smaller than (1/2)ℓΔ² for all Δ≥2. Thus the displayed inequality |V(H)| > (1/2)ℓΔ² is false, and the subsequent conclusion Δ² < c|V|/4 does not follow in the stated form. Even accepting the claimed bound, the step \"This implies Δ(Δ+1) ≤ c|V|/2 − 5sD\" is unjustified: Δ² < c|V|/4 gives only Δ(Δ+1) < c|V|/2, with no margin for the term 5sD. A concrete feasible parameter choice is t=1, n=10¹², p=1.6×10⁻⁸, β=3.2×10², D=3, c=0.12, Δ=1.4×10⁴, which satisfies all hypotheses of Theorem 1.3 but gives |V(F)|+5sD ≈ 6×10¹¹ > c n/2 = 6×10¹⁰, so Lemma 3.6 cannot be invoked. This invalidates the first step of the proof of the central theorem.","section":"§3, proof of Theorem 1.3"},{"comment":"Theorem 1.3 does not assume D ≥ Δmon(H), but its proof applies the Path Connection Lemma (Lemma 2.10), whose hypotheses explicitly require Δmon(H) ≤ D. In a [t]-edge-colored subdivision of K_Δ, a branch vertex can have as many as Δ−1 incident edges of the same color, so Δmon(H) can be much larger than D. In the finite-field application Theorem 1.7, D is set to 3 while Δ is allowed to be as large as (1/4)q⁻¹|E|; this is incompatible with the stated proof. The theorem either needs the missing hypothesis D ≥ Δmon(H), which would invalidate the D=3 applications, or a different extension argument that avoids the Path Connection Lemma's degree restriction.","section":"§1.2, Theorem 1.3 and §2, Lemmas 2.9–2.10"},{"comment":"The proof states \"Since |V(H)| < |V′|−6sD, we can extend…\", but the hypotheses only give |V(H)| ≤ |V|−6sD and |V′| ≥ |V|−s, which yield |V(H)| ≤ |V′|−6sD+s, not the strict inequality |V(H)| < |V′|−6sD. An additional slack of order s in the size hypothesis is needed before the Path Connection Lemma can be applied in the final step.","section":"§3, proof of Theorem 1.3"}],"minor_comments":[{"comment":"The statement of Theorem 1.5 uses the size condition \"|V(H)| ≤ n − 6s∆\", while the proof and Theorem 3.4 use \"n − 6sD\"; this mismatch should be fixed.","section":"§1.2, Theorem 1.5"},{"comment":"In the proof of Lemma 3.5 the notation e_{G_j}(V_j,V) is used for the edge count between subsets of the same vertex set; this is standard but should be defined explicitly in the family setting.","section":"§2, Lemma 3.5"},{"comment":"The inequality \"|V| > (2/c)s\" is stated without derivation; it does follow from the hypothesis via 5sD, but the argument should be spelled out for readability.","section":"§3, Lemma 3.6"}],"recommendation":"reject","confidential_remarks":"The paper has a well-organized technical framework, and the roll-back lemmas seem individually plausible. However, the central theorem's proof fails at its first numerical step, and the missing Δmon(H) ≤ D hypothesis conflicts with the D=3 finite-field applications. These are load-bearing issues rather than local presentation fixes, because the advertised parameter regime is exactly what the applications require. I would encourage the authors to revisit the parameter dependencies and either prove a corrected theorem or develop a different starting-step argument; a resubmission along those lines could merit re-review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The colorful roll-back machinery—Forest Extension Lemma 2.9 and Path Connection Lemma 2.10—is a real generalization of DKN, and the s-joined results (Theorems 1.4, 1.5) seem to follow cleanly from it. But Theorem 1.3, the advertised jumbled-graph result, is not proven as stated: the proof invokes Lemma 3.6 without the condition D ≥ Δ_mon(H), and the inequality needed to apply Lemma 3.6 does not close.\n\nThe new work is the definition of (s,D)-good embedding for edge-colored families with roll-back, and the path-constructible embedding theorem. That part is well organized and the proofs of the lemmas are mostly standard but carefully adapted. Credit is due: this is a substantial extension of the DKN framework.\n\nThe soft spots are load-bearing. In Theorem 1.3, H is an edge-colored subdivision of K_Δ, so a branch vertex can have up to Δ−1 incident edges of the same color. The Path Connection Lemma requires Δ_mon(H) ≤ D, but no such hypothesis appears. Lemma 3.6 also states no Δ_mon(F) ≤ D condition, yet its conclusion of a (2s,D)-good embedding is impossible for a star forest with a monochromatic degree above D. The proof of Theorem 1.3 tries to get |V(F)|+5sD < c|V|/2 from Δ^2 < c|V|/4, but Δ(Δ+1) ≤ c|V|/2 − 5sD does not follow: the c|V|/2 bound has no margin for 5sD. The stress-test example (t=1, D=3, n=10^12, p=1.6×10^{−8}, β=320, c=0.12, Δ=1.4×10^4) satisfies the stated hypotheses up to the star-forest size condition, and indeed violates it, so Lemma 3.6 cannot be invoked. The finite-field Theorem 1.7 sets D=3 and inherits both problems; it claims every R-distance subdivision of K_Δ, which is unproven for large Δ with monochromatic branch degree.\n\nThat said, the s-joined Theorems 1.4 and 1.5 include the Δ_mon(H) ≤ D hypothesis and may well be correct. The paper is thoughtful and the literature is handled honestly. The central claim just needs more hypotheses and a repaired estimate.\n\nThis paper is for researchers working on embedding problems in pseudorandom graphs and distance graphs over finite fields. The framework is worth a serious referee—send it out—but the referee should focus on Lemma 3.6's hypotheses and the D ≥ Δ_mon(H) condition. I would not cite Theorem 1.3 as it stands.","headline":"Colorful roll-back lemmas are genuinely new, but Theorem 1.3's proof has a load-bearing gap that the finite-field application inherits; the s-joined results look solid.","tokens_in":18263,"tokens_out":6253,"would_cite":false,"duration_ms":50794,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C35","05C15","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper's roll-back method proves that pseudorandom graph families contain every nearly spanning edge-colored subdivision of a complete graph, and that large finite-field sets contain all such distance graphs with long branch distances.","keywords":["edge-colored graphs","roll-back method","pseudorandom graphs","subdivisions of complete graphs","jumbled graphs","distance graphs over finite fields","graph embedding"],"falsifier":"Look at the first step of the proof of Theorem 1.3: Lemma 3.6 is asked to embed the star forest $F$ of branch vertices and their neighbors with $\\Delta(F)\\le D$. Take a subdivision of $K_4$ and color all four edges at one branch vertex with color 1, set $D=3$, and choose $p|V|$ large enough to satisfy the theorem's other hypotheses; the hypotheses of Theorem 1.3 can still hold, but $F$ violates the degree condition used by Lemma 3.6. This concrete configuration is the place to test whether the stated theorem and its proof are consistent.","tokens_in":17125,"feed_emoji":"🔄","tokens_out":8410,"duration_ms":72818,"temperature":0.7,"pith_summary":"This paper develops a colorful version of the roll-back method for embedding large edge-colored graphs into families of expander graphs. The central result, Theorem 1.3, says that if $G_1,\\dots,G_t$ are $(p,\\beta)$-jumbled graphs on the same vertex set, then the family contains every $[t]$-edge-colored subdivision of $K_\\Delta$ whose branch-to-branch paths have length at least $\\ell$, provided $\\Delta$ is below the average degree by a constant factor and the subdivision leaves at least $6sD$ vertices unused. This moves close to both trivial obstructions: the target cannot have degree above the host's maximum degree, and it cannot have more vertices than the host. As an application, large subsets of finite vector spaces contain every nearly spanning distance graph that is a subdivision of a complete graph, with long distances between branch vertices. The contribution is an extension of the known roll-back framework from monochromatic trees and subdivisions to edge-colored families with a wider usable parameter range.","feed_headline":"Pseudorandom graphs contain every large colored subdivision","feed_subtitle":"A colorful roll-back proof reaches near the degree and vertex limits, finding distance graphs in finite-field subsets.","key_machinery":"The load-bearing object is the $(s,D)$-good embedding of a rooted, $[t]$-edge-colored graph into a family $\\mathcal{G}$. For $X \\subseteq V\\times[t]$, the deficit function $R(X,\\varphi)$ compares the number of external neighbors of $X$ in the auxiliary bipartite graph $B_{\\mathcal{G}}$ against the embedding demand $\\sum_{(v,i)\\in X}(D - \\deg_{H_i}(\\varphi^{-1}(v)))$ plus a parent-color correction $|P_{\\varphi(H)}\\cap X|$; an embedding is good when $R(X,\\varphi)\\ge 0$ for all $X$ of size at most $2s$. The roll-back operation consists of attaching a new vertex by an edge of a specified color and, crucially, removing non-root leaves while preserving goodness. The Forest Extension Lemma and Path Connection Lemma then let the proof build path-constructible graphs; in the jumbled case, Lemma 3.5 finds a vertex whose monochromatic degree exceeds $(1-c)p|V|$ in every color, enabling the initial star-forest embedding. The path length $\\ell = 2\\lceil \\log s / \\log(D-1)\\rceil + 3$ sets the buffer needed for the connecting trees.","core_discovery":"The paper claims that the colorful roll-back lemmas, the Forest Extension Lemma and the Path Connection Lemma, are enough to embed any nearly spanning edge-colored subdivision of a complete graph into any sufficiently pseudorandom graph family, and that the obstruction threshold is essentially the trivial degree and order obstructions. In the jumbled setting of Theorem 1.3, the proof first uses the pseudorandom property to find a vertex of high monochromatic degree in every color and embeds the star forest of branch vertices and their neighbors; then the Path Connection Lemma fills in the long paths and the roll-back removal mechanism discards unused tree branches. The vertex budget is $|V(H)| \\le |V| - 6sD$ with $s = 2t^{1/2}\\beta p^{-1}$, so the slack vanishes as the family becomes more pseudorandom. For finite fields, since the distance graph $G_r$ is $(q^{-1}+O(q^{-(d+1)/2}), 2q^{(d-1)/2})$-jumbled, the same theorem yields $R$-distance subdivisions in every set $E$ with $|E| = \\Omega(|R|^{1/2} q^{(d+1)/2})$.","pith_inferences":["A natural extension not stated in the paper is that the same good-embedding machinery should handle other path-constructible colored targets, such as grids or subdivided cycles with prescribed color sequences, whenever the initial forest and path lengths satisfy the two extension lemmas.","If the apparent gap between $D$ and $\\Delta$ in Theorem 1.3 is repaired by taking $D$ close to $\\Delta$, the slack $6sD$ would grow, so the finite-field thresholds stated with $D=3$ would need a separate argument rather than a simple parameter substitution.","Lemma 3.5 suggests a general principle: in a jumbled family, a single vertex can serve as a hub in every color simultaneously, which may support colored stars and trees with many colors beyond the subdivision application treated here.","The trade-off between the path length $\\ell$ and the color-degree parameter $D$ may be exploitable in other settings: larger $D$ shortens the required connecting paths, which could be useful when the host family is only weakly pseudorandom."],"forward_implications":["If Theorem 1.3 is correct, every $(p,\\beta)$-jumbled family with average degree $pn$ embeds an $\\ell$-subdivision of $K_\\Delta$ whenever $\\Delta \\le (1-c)pn$ and the target leaves $6sD$ vertices unused, so both natural obstructions can be approached simultaneously.","The monochromatic roll-back theorem is recovered and extended to a wider parameter range, including host average degree as high as $n^{1/2}$ rather than only $n^{1/5}$.","In finite fields, any $E \\subseteq \\mathbb{F}_q^d$ with $|E| > 72|R|^{1/2}q^{(d+1)/2}$ contains every $R$-distance subdivision of a complete graph with branch distances at least $(d+2)\\lceil \\log_2 q\\rceil + 16$, provided the subdivision is not larger than $|E|$ minus the threshold; the exponent $(d+1)/2$ matches the single-edge threshold.","For merely $s$-joined families, the same machinery embeds edge-colored expansions of $K_\\Delta$, so near-spanning structures with higher underlying degree are also accessible.","The dependence of the threshold on $t=|R|$ is necessary in general, while the paper conjectures that the $|R|$-dependence in the finite-field corollary can be removed."],"supporting_citations":[{"why":"Supplies the monochromatic roll-back framework and the subdivision-embedding theorem this paper generalizes; its Removal Lemma and Path Connection approach are the basis of Section 2.","marker":"[6]"},{"why":"Introduces good embeddings and the leaf-extension induction for embedding trees into expanders, the origin of the method.","marker":"[7]"},{"why":"Defines the auxiliary bipartite graph and colorful good embeddings for edge-colored trees; the graph-family model and motivation come from this work.","marker":"[5]"},{"why":"Provides the s-joined expansion propositions used to find the subsets $W$ and $V'$ and the discussion of roll-back results.","marker":"[19]"},{"why":"Proves the jumbledness of distance graphs over finite fields and the single-edge threshold that the finite-field corollaries build on.","marker":"[15]"},{"why":"Gives the independent derivation of the same finite-field distance graph jumbledness used for Theorems 1.7 and 1.8.","marker":"[18]"}],"fun_headline_variants":["Roll-back embedding finds colorful subdivisions in expanders","Edge-colored graphs fit into pseudorandom families via roll-back","Pseudorandom graphs host every large colored subdivision","Nearly spanning colored subdivisions appear in expanders","Colorful roll-back proof embeds subdivisions in expanders"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the fixed parameter $D$ is at least the maximum monochromatic degree of the branch-vertex star forest, which for a subdivision of $K_\\Delta$ is $\\Delta-1$, yet the theorem as stated only requires $D\\ge 3$ and its finite-field corollary takes $D=3$ with large $\\Delta$.","fun_headline_variants_meta":{"raw":{"variants":["Roll-back embedding finds colorful subdivisions in expanders","Edge-colored graphs fit into pseudorandom families via roll-back","Pseudorandom graphs host every large colored subdivision","Nearly spanning colored subdivisions appear in expanders","Colorful roll-back proof embeds subdivisions in expanders"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000891,"raw_usage":{"total_tokens":3898,"prompt_tokens":1053,"completion_tokens":2845,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":669,"completion_tokens_details":{"reasoning_tokens":2770}},"tokens_in":669,"tokens_out":2845,"duration_ms":18059,"temperature":1.0,"reasoning_tokens":2770,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:17:11.293333+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look at the first step of the proof of Theorem 1.3: Lemma 3.6 is asked to embed the star forest $F$ of branch vertices and their neighbors with $\\Delta(F)\\le D$. Take a subdivision of $K_4$ and color all four edges at one branch vertex with color 1, set $D=3$, and choose $p|V|$ large enough to satisfy the theorem's other hypotheses; the hypotheses of Theorem 1.3 can still hold, but $F$ violates the degree condition used by Lemma 3.6. This concrete configuration is the place to test whether the stated theorem and its proof are consistent.","supporting_citations":[{"cited_title":"Dragani´ c, M","cited_arxiv_id":null,"evidence_quote":"Supplies the monochromatic roll-back framework and the subdivision-embedding theorem this paper generalizes; its Removal Lemma and Path Connection approach are the basis of Section 2."},{"cited_title":"Friedman and N","cited_arxiv_id":null,"evidence_quote":"Introduces good embeddings and the leaf-extension induction for embedding trees into expanders, the origin of the method."},{"cited_title":"Chakraborti and B","cited_arxiv_id":null,"evidence_quote":"Defines the auxiliary bipartite graph and colorful good embeddings for edge-colored trees; the graph-family model and motivation come from this work."},{"cited_title":"Iosevich and M","cited_arxiv_id":null,"evidence_quote":"Proves the jumbledness of distance graphs over finite fields and the single-edge threshold that the finite-field corollaries build on."},{"cited_title":"Medrano, P","cited_arxiv_id":null,"evidence_quote":"Gives the independent derivation of the same finite-field distance graph jumbledness used for Theorems 1.7 and 1.8."}],"review_version":1}