Discrete Poincar\'e inequalities and universal approximators for random graphs

Dylan J. Altschuler; Konstantinos Tyros; Konstantin Tikhomirov; Pandelis Dodos

Discrete Poincar\'e inequalities and universal approximators for random graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2506.17433 v3 pith:6XFUWEVZ submitted 2025-06-20 math.MG math.COmath.PR

Dylan J. Altschuler , Pandelis Dodos , Konstantin Tikhomirov , Konstantinos Tyros This is my paper · ORCID

classification math.MGmath.COmath.PR MSC 05C1205C4805C5005C8046B85

keywords nonlinearPoincaréinequalitiesspectralgapsrandomregulargraphsKleinberg'sproblemuniversalapproximatorsexpandermetricembeddingsbi-Lipschitzdistortion

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

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.

What 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.

The 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.

None 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.

Referee Report

2 major / 5 minor

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].

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 (2)

[§2.5 (Theorem 2.2; Eq. (2.2))] 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.
[§5.3 (just before (5.24))] 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.

minor comments (5)

[§6.5 (paragraph after (6.15))] 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(α).
[§1.3 (display after (1.9))] 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'.
[§4 (equations (4.5)–(4.6))] 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.
[§2.5 (reference [ADTT25])] 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.
[§3.1 (Proposition 3.3(i))] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No circularity found; all p>1 claims rest structurally on the authors' deferred general extrapolation theorem [ADTT25], which is a dependency risk but not a circular reduction.

full rationale

The derivation chain is not circular. The heart of the paper is the p=1 inequality, proved combinatorially in Sections 4 and 5 via Propositions 3.5 and 3.6, using the typical properties D(α) and R(ε). The extension to every p≥1 is obtained in Section 6.3 by applying Theorem 2.2, a one-sided Matoušek extrapolation for arbitrary metric spaces, whose proof is deferred to the authors' companion preprint [ADTT25]. Theorem 2.2 is a general statement whose assumptions (d-regular G with h(G)>0, arbitrary metric space M) do not include the target random-graph conclusion; it is therefore independent support rather than a restatement of the theorem. The typicality of property D(α) is also imported from the authors' earlier work [ADTT24], but that result has its own independent proof, and part (B) is Friedman's classical theorem. No parameter is fitted to the target conclusion, and no quantity is renamed as a prediction; all constants are explicit and derived in the proof. The only notable caveat is epistemic, not circular: Remark 1.8 and Section 2.5 explicitly acknowledge that the p>1 case is not proved here but taken from [ADTT25]. If that theorem were false or unavailable, Theorems 1.3 and 1.6 would be established only for p=1. This is a missing-proof dependency risk, and it is flagged here, but it does not make the derivation circular.

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

The central claim rests on established probabilistic facts about random regular graphs, particularly the strong vertex expansion property D(alpha) from [ADTT24] and the local L1 embeddability property R(epsilon) from [MN15], plus the extrapolation theorem from [ADTT25]. No data is fitted: all constants are explicit proof bounds. Two small hand-picked constants, epsilon and alpha(d), set the thresholds in the proof. No new physical entities are introduced.

free parameters (2)

epsilon = 10^-4
Small positive constant fixing the thresholds m^{2ε}, m^{4ε} in the decomposition Definition 3.4 and the image-size bound in Fact 5.7; chosen by hand for the proof, not optimized.
alpha(d) = exp(-10^11 log^2 d)
Vertex-expansion rate in property D(alpha) (Definition 3.1); imported from [ADTT24] and used in Propositions 3.6 and 5.3. It is a proof-chosen decay rate rather than a fitted quantity.

assumptions (5)

standard math Friedman's second eigenvalue theorem: random d-regular graphs satisfy lambda_2(G) <= 2.1 sqrt(d-1) with high probability.
Invoked in the proof of Proposition 3.3(i), part (B) of property D. See Section 3.1.
domain assumption Property D(alpha) holds for uniformly random d-regular graphs with alpha(d)=exp(-10^11 log^2 d) with high probability.
Assumed from [ADTT24, Proposition 1.9]; used throughout Propositions 3.6 and 5.3. This is a probabilistic fact about the model, not derived in this paper.
domain assumption Property R(epsilon) holds for uniformly random Delta-regular graphs with high probability.
Assumed from [MN15, Lemma 7.3 and Corollary 6.6]; used in Proposition 3.6 and Fact 5.1. It asserts small induced subgraphs embed into L1 with bounded distortion.
domain assumption One-sided Matoušek extrapolation for metric spaces (Theorem 2.2).
Deferred to [ADTT25]; used in Section 6.3 to promote the p=1 bound to every p >= 1. This is the load-bearing bridge for the full statement of Theorems 1.3 and 1.6.
standard math McKay-Wormald asymptotic enumeration of d-regular graphs.
Used in the proof of Proposition 3.5, Fact 4.1, to pass from Erdős-Rényi probabilities to uniform regular graphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Discrete Poincar\'e inequalities and universal approximators for random graphs." pith.science (2026). https://pith.science/paper/6XFUWEVZ

@misc{pith2026250617433,
  author       = {Pith},
  title        = {Pith review of: Discrete Poincar\'e inequalities and universal approximators for random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6XFUWEVZ}},
  note         = {Machine review of arXiv:2506.17433}
}

abstract

Nonlinear Poincar\'e inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable algorithmic applications. A basic open problem, posed by Jon Kleinberg (2013), asks whether the optimal nonlinear Poincar\'e constant for maps between two independent $3$-regular random graphs is dimension-free, i.e., independent of vertex-set sizes. We give a complete and affirmative resolution to Kleinberg's problem, also allowing for arbitrary graph degrees. As a corollary, we obtain a stochastic construction of $O(1)\text{-universal}$ approximators for random graphs, answering a question of Mendel and Naor.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Pith tools

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