{"id":"ee60143b-c787-4bf2-acfc-fea0a706715a","arxiv_id":"2506.17433","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Independent random regular graphs satisfy a dimension-free nonlinear Poincaré inequality, resolving Kleinberg's problem and giving universal approximators for all p ≥ 1.","lead":"A team of mathematicians proves a 2013 conjecture of Jon Kleinberg: the Poincaré constant for maps between two independent random regular graphs is bounded by a universal number that does not grow with graph size. The proof also yields a stochastic construction of O(1)-universal approximators for random graphs, for every exponent p including the previously open case p=1.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"All p>1 claims in Theorems 1.3 and 1.6 depend entirely on Theorem 2.2, whose proof is deferred to unpublished companion [ADTT25]; if that extrapolation is unavailable or has hidden assumptions, only the p=1 case is established.","rationale":"After reading the full argument, I find the p=1 core (Propositions 3.5 and 3.6, assembled in Corollary 6.1) to be a genuine, largely self-contained combinatorial proof: the random compression argument in Lemma 5.8 is coherent, the expansion estimates (5.21)-(5.29) check out, and the union-bound structure in Proposition 3.5 is consistent. The visible typos (the two identical lines in Definition 5.6, the vestigial 1/K term in (6.3)) and the loose constants do not affect the central claim. The single load-bearing unverified step is the passage from p=1 to all p>=1 via Theorem 2.2, whose proof is external and unpublished. This is exactly the weakest point identified by the reader, and a conditional verdict is appropriate: accept the p=1 contribution as credible, but do not treat the full all-p statement as verified until Theorem 2.2 is available with a proof. Independent evidence, including the separate proof of property D(alpha) in [ADTT24] and the corroborating work [EMN25], supports the plausibility of the main conclusion but does not substitute for the missing extrapolation proof.","tokens_in":23145,"tokens_out":32634,"duration_ms":323955,"concrete_test":"Obtain [ADTT25] and independently re-derive Theorem 2.2 for the special case p=1, q=2, with G an arbitrary d-regular graph with h(G)>0 and M the vertex set of a Delta-regular graph H with dist_H. Verify that the proof of (2.2) uses only h(G)>0, the value of gamma(G, dist_H), and the constants stated, with no extra bound on diam(M) or |M|, no doubling hypothesis, and no additional norm inequality on M. If the derivation is valid and complete, the concern is resolved; if it requires an additional hypothesis, Theorems 1.3 and 1.6 should be restated for p=1 only, or with that hypothesis made explicit.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Remark 1.8 states that the core of the proof is the case p=1, and that the case p>1 follows from a version of Matoušek's extrapolation taken from [ADTT25]. Section 6.3 applies Theorem 2.2 directly: once Corollary 6.1 gives gamma(G, dist_H) <= Gamma_0 with high probability, inequality (2.2) is invoked with p=1 and q arbitrary to conclude gamma(G, dist_H^q) <= Gamma(d,q) for every q>=1. However, Theorem 2.2 is not proved in this paper; it is relegated to an unpublished companion preprint. The step is not a minor detail: for q>1 there is no spectral-gap analogue for general metric spaces, and naive interpolation introduces a factor diam(H)^{q-1}, which is not dimension-free. Thus the full strength of Theorem 1.3 -- uniformity over all p>=1 -- is exactly as secure as Theorem 2.2. If that result is false, unavailable, or carries an unstated restriction (e.g., bounded diameter or bounded cardinality of the metric space), then what is established here is only the p=1 case, which is still a substantial result but not the theorem as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"Let G∼G(n,d) and H∼G(m,Δ) be independent random regular graphs. The paper claims that, with high probability, for every p≥1 the nonlinear Poincaré constant γ(G,dist_H^p) is bounded by Γ(d,p)=exp(10^{12}2^p log^2 d), independent of n and m (Theorem 1.3), resolving Kleinberg's 2013 problem. It further derives a stochastic analogue of the Mendel–Naor construction (Theorem 1.6) and O(1)-universal approximators for random regular graphs (Theorem 1.12). The proof isolates two typical properties, D(α) for the domain graph and R(ε) for the range graph, and establishes the p=1 inequality via a combinatorial decomposition of f into nearly injective/nearly constant parts, a random compression argument, and expansion estimates. The step from p=1 to all p≥1 is delegated to a one-sided Matoušek extrapolation stated as Theorem 2.2 and proved in an unpublished companion [ADTT25].","tokens_in":23407,"tokens_out":14721,"duration_ms":144603,"significance":"If fully established, this is a significant affirmative solution to a well-known open problem; it substantially broadens the range of nonlinear spectral gap techniques and yields new, explicit (though extremely large) dimension-free constants. The authors are explicit that the p=1 case is new for Theorem 1.6 and credit the independent work [EMN25]. The combinatorial approach and the detailed treatment of the p=1 case are genuine strengths. I found no circularity: Kleinberg's conjecture is not assumed, and the cited companion results [ADTT24], [ADTT25] are separate statements rather than restatements of the target theorem. However, the p>1 claims are only as secure as the deferred Theorem 2.2, and my reading found a separate gap in the derivation of Claim 5.9. The p=1 case appears substantial but is not fully self-contained in the submitted artifact.","major_comments":[{"comment":"The proof of Theorem 2.2 is not included; the text says only 'see [ADTT25] for a proof', and [ADTT25] is an unpublished companion preprint. This theorem is not auxiliary: Section 6.3 passes from the p=1 bound γ(G,dist_H)≤Γ0 to γ(G,dist_H^q)≤Γ(d,q) for every q≥1 exactly by invoking (2.2), and Section 6.5 uses the same step in the proof of Lemma 6.2 and hence of Theorems 1.6 and 1.12. Because general metric spaces admit no spectral-gap analogue and naive interpolation would leave a factor diam(H)^{q-1}, this is a load-bearing step and not a routine detail. As the manuscript stands, only the p=1 case is proved; the 'for every p≥1' assertions are conditional on an unverifiable external result. I ask that the proof of Theorem 2.2 be included (an appendix would suffice) or that the reference be to a publicly available, verifiable version with the same statement.","section":"§2.5 (Theorem 2.2; Eq. (2.2))"},{"comment":"The sentence 'M'_0, T_1, ..., T_{k0}, M_2(f,ε) are pairwise disjoint subsets of [n]' appears to be incorrect: vertices in M_2(f,ε) can lie at any distance from M'_0 and thus can intersect the layers T_k. Moreover, the displayed definition of M_2^{Typ} as M_2(f,ε)∩T_{k*}^{Typ} would be empty if M_2(f,ε) were disjoint from every T_k. The assertion that there exists k* satisfying (5.24) is essential for Claim 5.9, which in turn underpins Lemma 5.8 and Proposition 3.6. Please correct the statement or provide the intended pigeonhole argument; as written, the inference is not justified.","section":"§5.3 (just before (5.24))"}],"minor_comments":[{"comment":"The phrase 'every graph in A_n satisfies property R(α)' should clearly be 'property D(α)', since A_n is a subset of G(n,d) and the subsequent use of (2.1) requires the spectral bound from property D(α).","section":"§6.5 (paragraph after (6.15))"},{"comment":"In Theorem 1.12, the phrase 'the multi-graph Uk(1.9)' is a cross-reference artifact; it should read 'the multi-graph U_k'.","section":"§1.3 (display after (1.9))"},{"comment":"The exponents 'm−1.05n' and 'm−1.05·d/3 n' should be written as m^{-1.05n} and m^{-1.05dn/3} to avoid confusion with expressions such as m - 1.05n.","section":"§4 (equations (4.5)–(4.6))"},{"comment":"Reference [ADTT25] is listed only as a preprint with no arXiv identifier or institutional repository; please provide full bibliographic data so that the claimed theorem can be checked.","section":"§2.5 (reference [ADTT25])"},{"comment":"The typicality of property D(α) is imported from [ADTT24, Proposition 1.9] rather than proved here; since [ADTT24] is a companion preprint, it would be helpful to state the exact cited proposition and to confirm that the parameter α(d) in (3.1) matches the version proved there.","section":"§3.1 (Proposition 3.3(i))"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the unpublished companion [ADTT25]: the advertised full theorem is conditional on a result whose proof the reader cannot verify. I would not recommend acceptance until the proof of Theorem 2.2 is either included or made publicly available in a verifiable form. The Claim 5.9 issue may be a repairable typographical/argumentative gap, but it should be resolved before the p=1 core can be considered complete. The authors' p=1 contribution is valuable, but the paper as submitted does not yet establish the full statement of Theorems 1.3 and 1.6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a serious paper with a real new theorem inside — the p=1 case is proved in real detail and is a genuine advance — but the advertised main result for all p≥1 is not proved in the submitted text. Everything for p>1 depends on Theorem 2.2, an extrapolation statement whose proof is deferred to the unpublished companion [ADTT25]. The authors themselves flag this in Remark 1.8. If that companion never appears or has hidden restrictions, Theorems 1.3 and 1.6 are only established for p=1. That matters because Kleinberg's original problem is about p=2.\n\nWhat is actually new: the combinatorial framework itself. The p=1 inequality for maps between independent random regular graphs, with constant independent of the vertex counts, is proved directly. The random compression argument and the use of property D are new and look effective. The paper also gets the p=1 universal approximator, which was open. The proof of p=1 is detailed, with explicit constants and standard tools: Friedman's theorem, McKay–Wormald enumeration, and [MN15]'s property R. Credit where due: this is a substantial contribution, not a repackaging.\n\nThe soft spots, in proportion. First and largest: Theorem 2.2 is load-bearing and absent. For a paper that claims to resolve Kleinberg's problem — which is p=2 — this is not a formality. A referee cannot check the central deduction without a second manuscript. Second: Proposition 3.3(i) imports typicality of property D(α) from [ADTT24], another preprint; that has its own derivation, so it is less concerning, but still a dependency. Third, minor: in Section 6.5 the text says every graph in A_n satisfies property R(α) when it must mean property D(α). I also noticed the definition of n_0(d) in Section 6.1 is a bit self-referential, though harmless.\n\nNone of this kills the p=1 theorem. The central argument for p=1 looks sound, and the independent [EMN25] work corroborates the overall picture. But the paper as written overclaims: a “complete and affirmative resolution” is only true conditionally on an unpublished companion. My recommendation: send to peer review, but treat the standard as conditional acceptance. Require the companion to be posted and checked before the all-p claims are certified. If the companion fails to appear, the p=1 result still deserves publication, though the marketing and title would need to be dialed back.","headline":"Strong p=1 theorem, but the all-p claims rest on an unpublished companion; the paper as submitted overstates its resolution of Kleinberg's problem.","tokens_in":23963,"tokens_out":3326,"would_cite":true,"duration_ms":32534,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C48","05C50","05C80","46B85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The nonlinear Poincaré constant of two independent random regular graphs is bounded by a constant that depends only on the degree, not on the number of vertices.","keywords":["nonlinear Poincaré inequalities","nonlinear spectral gaps","random regular graphs","Kleinberg's problem","universal approximators","expander graphs","metric embeddings","bi-Lipschitz distortion"],"falsifier":"Find a metric space M and a d-regular graph G with positive Cheeger constant for which inequality (2.2) of Theorem 2.2 fails for some 1≤p<q; since (2.2) is the tool that extends the p=1 bounds to all p≥1, such a counterexample would reduce Theorems 1.3 and 1.6 to the p=1 case. Alternatively, for d=Δ=3, p=1, compute the maximum over f of the ratio in (1.10) as n,m→∞; non-negligible growth of this maximum would refute Theorem 1.3 at the p=1 endpoint.","tokens_in":22947,"feed_emoji":"🕸️","tokens_out":8451,"duration_ms":75659,"temperature":0.7,"pith_summary":"This paper resolves Jon Kleinberg's 2013 problem on nonlinear Poincaré inequalities: for two independent random regular graphs G and H, the nonlinear spectral gap γ(G,dist_H^p) is bounded, with high probability, by a constant Γ(d,p) that depends only on the degree d of G and on p, never on the vertex-set sizes n and m. The bound holds for any degrees d,Δ≥3 and every exponent p≥1. Because the constant is dimension-free, random regular graphs are forced apart from all maps between them: the best distortion of G into H grows at least like log n. As a corollary the paper gives a randomized construction of O(1)-universal approximators for random regular graphs for every p≥1, including the previously open endpoint p=1.","feed_headline":"Random regular graphs have a size-free Poincaré constant","feed_subtitle":"Two random regular graphs satisfy a Poincaré bound that does not grow with size, settling Kleinberg's question.","key_machinery":"The argument is carried by two high-probability combinatorial properties of random regular graphs: property D(α), asserting strong vertex expansion (every small ball grows like α(d−1)^ℓ|S|) together with the spectral bound λ_2(G)≤2.1√(d−1), and property R(ε), asserting that every sublinear-sized induced subgraph of H admits a bi-Lipschitz embedding into L1 with distortion O(1/ε) and that H is connected with logarithmic diameter. A dyadic decomposition splits the domain of f into layers M0,M1,M2 where f is essentially injective or essentially constant, and a random 'compression' scheme shrinks the image of the problematic layers, allowing the L1 embeddability of small neighborhoods to be invoked; property D(α) is the engine that makes the compression statistically efficient. A one-sided Matoušek extrapolation (Theorem 2.2) then extends the p=1 inequality to all p≥1.","core_discovery":"The central discovery is that the standard combinatorial expansion properties of random regular graphs are enough to control the whole nonlinear spectral gap. Concretely, for every d,Δ≥3 and p≥1, with probability tending to 1 the graphs G and H satisfy γ(G,dist_H^p) ≤ exp($10^{12}$ 2^p $log^{2}$ d); the right-hand side is independent of n and m and of the degree of H. Equivalently, for every f:V_G→V_H, the average p-th power of the H-distance over all pairs of vertices of G is at most that constant times the average over edges of G. The proof first establishes the case p=1 by purely combinatorial arguments and then lifts it to all p≥1; the p=1 case of the Mendel–Naor-type construction is new. Theorem 1.3 also yields a lower bound ~ log n on the bi-Lipschitz distortion between the two random metric spaces, showing that their geometries are mutually incompatible.","pith_inferences":["The disappearance of Δ from the bound suggests transport-cost or expansion arguments that are insensitive to the range graph's degree; one testable extension is whether the same size-free bound holds when H is drawn from a sparse Erdős–Rényi model rather than a regular configuration model.","The combinatorial route around martingale failure for p=1 may transfer to other metrics where the martingale methods of the earlier spectral calculus do not apply, such as discrete tori or dihedral quotient metrics.","The constants exp(10^12 2^p log^2 d) are likely far above the true optimal values; numerical evaluation of γ(G,dist_H) for 3-regular graphs with n up to a few thousand would provide a concrete lower-bound benchmark against which tighter proofs could be calibrated."],"forward_implications":["Kleinberg's problem is solved in full: for any two independent random regular graphs, γ(G,dist_H^p) is O_{d,p}(1) with high probability, regardless of graph sizes and of the degree of H.","The bi-Lipschitz distortion c_H(G) of a random d-regular graph into a random Δ-regular graph is at least Ω_d(log n) with high probability (Corollary 1.5).","Random d-regular graphs supply a stochastic construction of O(1)-universal approximators for random graphs for every p≥1, providing the missing p=1 endpoint (Theorems 1.6 and 1.12).","The proof yields an explicit, if large, constant Γ(d,p)=exp(10^12 2^p log^2 d), and shows the constant does not depend on Δ.","A single random graph H works simultaneously for an entire family of domain graphs G_n, in the sense of the sup over n in Theorem 1.6."],"supporting_citations":[{"why":"poses Kleinberg's problem (Question 2.4), defines property R(ε) and the prior deterministic Mendel–Naor construction that Theorem 1.6 randomizes.","marker":"[MN15]"},{"why":"supplies property D(α) and proves it typical for random d-regular graphs; the main combinatorial engine for the proof.","marker":"[ADTT24]"},{"why":"provides Theorem 2.2, the one-sided Matoušek extrapolation for metric spaces used to lift p=1 to all p≥1.","marker":"[ADTT25]"},{"why":"gives the original Matoušek extrapolation, used in Fact 2.1 to convert L1 distortion bounds into Poincaré constants.","marker":"[Ma97]"},{"why":"proves the Alon second-eigenvalue conjecture, used for the spectral part of property D(α).","marker":"[Fr08]"},{"why":"supplies asymptotic enumeration of regular graphs, used in Fact 4.1 to pass from rare-event bounds to uniform probabilities.","marker":"[MW91]"},{"why":"developed the local-versus-global metric property that underlies property R(ε); cited by the paper for its origin.","marker":"[ALNRRV12]"}],"fun_headline_variants":["Poincare bound for random graphs is size-free, settles question","Dimension-free Poincare constant for random regular graphs","Kleinberg's open problem solved: Poincare constant size-free","Size-free Poincare bound for random graph maps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The passage from the p=1 inequality to every p≥1 rests entirely on a metric-space extrapolation theorem (Theorem 2.2) whose proof is not included here but deferred to a companion preprint; if that theorem fails, the results are established only for p=1.","fun_headline_variants_meta":{"raw":{"variants":["Poincare bound for random graphs is size-free, settles question","Dimension-free Poincare constant for random regular graphs","Kleinberg's open problem solved: Poincare constant size-free","Size-free Poincare bound for random graph maps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000588,"raw_usage":{"total_tokens":2720,"prompt_tokens":863,"completion_tokens":1857,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":1791}},"tokens_in":479,"tokens_out":1857,"duration_ms":15485,"temperature":1.0,"reasoning_tokens":1791,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:08:52.214103+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a metric space M and a d-regular graph G with positive Cheeger constant for which inequality (2.2) of Theorem 2.2 fails for some 1≤p<q; since (2.2) is the tool that extends the p=1 bounds to all p≥1, such a counterexample would reduce Theorems 1.3 and 1.6 to the p=1 case. Alternatively, for d=Δ=3, p=1, compute the maximum over f of the ratio in (1.10) as n,m→∞; non-negligible growth of this maximum would refute Theorem 1.3 at the p=1 endpoint.","supporting_citations":[],"review_version":2}