Discrete Poincaré inequalities and universal approximators for random graphs

Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov and Konstantinos Tyros · 2025

Read Discrete Poincaré inequalities and universal approximators for random graphs by Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov and Konstantinos Tyros (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-17433.txt.

Introduction

Dylan Altschuler, Pandelis Dodos, Konstantin Tikhomirov, and Konstantinos Tyros settle a math question left open since 2013. The question asks if a key bending cost for maps between random graphs stays flat as the graphs grow, with no tie to their size. Such costs rule how well graphs can sit in plain space with small stretch, a tool with wide use in algorithm craft.

Their 2025 proof says yes: the best cost for two independent random graphs is size-free, for any link count per node, not just three. As a knock-on, they build random stand-ins that fake the spans of any graph to a flat grade. That answers a second open question from Mendel and Naor. Random graphs, it turns out, hold a stiff shape core that size cannot soften.

Catalog record

CREATORDylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov and Konstantinos Tyros
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-17433

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Discrete Poincaré inequalities and universal approximators for random graphs Thanks: 2020 Mathematics Subject Classification : 05C12, 05C48, 05C50, 05C80, 46B85. Thanks: Key words : expander graphs, random regular graphs, nonlinear Poincaré inequalities. Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov and Konstantinos Tyros Abstract . Nonlinear Poincaré 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é constant for maps between two independent 3 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 ) ​ -universal O(1)\text{-universal} approximators for random graphs, answering a question of Mendel and Naor. 1. Introduction 1.1. Nonlinear spectral gaps Let d\geqslant 3 be an integer, let G=(V_{G},E_{G}) be a d -regular graph, set n:=|V_{G}| , and write the eigenvalues of the adjacency matrix A_{G} of G in increasing order as (1.1) \lambda_{n}(G)\leqslant\cdots\leqslant\lambda_{2}(G)\leqslant\lambda_{1}(G)=d. It is a standard observation that the quantity \frac{d}{2(d-\lambda_{2}(G))} (essentially, the reciprocal of the spectral gap) can also be defined as the best constant \gamma\in(0,\infty] such that for any f\colon V_{G}\to\mathbb{R}^{k} , (1.2) \frac{1}{|V_{G}|^{2}}\sum_{v,u\in V_{G}}\big\|f(v)-f(u)\big\|_{2}^{2}\leqslant\frac{\gamma}{|E_{G}|}\sum_{\{v,u\}\in E_{G}}\big\|f(v)-f(u)\big\|_{2}^{2}. Nonlinear (i.e., non-Euclidean) Poincaré inequalities are extensions of ( 1.2 ) to other norms and, more generally, functions taking values in metric spaces. Such inequalities have proven indispensable in the study of embeddings and metric dimension reduction, and hold a role of central importance in a number of areas, especially metric geometry and algorithm design. Some of the earlier appearances of nonlinear Poincaré inequalities came from the study of bi-Lipschitz embeddings, such as the works of Enflo [ E76 ] , Bourgain–Milman–Wolfson [ BMW86 ] , Gromov [ Gr83 ] , Pisier [ Pi86 ] , Linial–London–Rabinovich [ LLR95 ] , and Matoušek [ Ma97 ] . Gromov [ Gr03 ] initiated the usage of nonlinear Poincaré inequalities in the context of coarse embeddings, with connections to the Novikov conjecture. This line of work was further investigated by Ozawa [ Oz04 ] , Kasparov–Yu [ KY06 ] , and Pisier [ Pi10 ] , eventually leading to Lafforgue’s [ La08 ] construction of superexpanders , regular graphs with remarkable coarse non-embeddability properties. Alternate constructions of superexpanders were also given by Mendel–Naor [ MN14 ] , and de Laat–de la Salle [ dLdS23 ] . More recently, nonlinear Poincaré inequalities have found spectacular algorithmic applications. We refer the reader to the works of Andoni–Naor–Nikolov–Razenshteyn–Waingarten [ ANNRW18 ] and Mendel–Naor [ MN15 ] , as well as the survey paper of Eskenazis [ Es22 ] , for an overview of these exciting developments. A systematic study of nonlinear versions of ( 1.2 ) was undertaken in a series of papers [ MN13 , MN14 , Na14 , MN15 ] by Mendel and Naor. The following definition—which first appeared in [ MN14 ] —conceptualizes and unifies the aforementioned nonlinear Poincaré inequalities. Definition 1.1 (Nonlinear spectral gap) . Let d\geqslant 3 be an integer, and let G=(V_{G},E_{G}) be a d\text{-regular} graph. Also let \mathcal{M}=(M,\varrho) be a metric space, and let p\geqslant 1 . By \gamma(G,\varrho^{p}) we denote the smallest constant \gamma\in(0,\infty] such that for any f\colon V_{G}\to M , (1.3) \frac{1}{|V_{G}|^{2}}\sum_{v,u\in V_{G}}\varrho\big(f(v),f(u)\big)^{p}\leqslant\frac{\gamma}{|E_{G}|}\sum_{\{v,u\}\in E_{G}}\varrho\big(f(v),f(u)\big)^{p}. 1.2. Main results In this paper we shall focus on nonlinear spectral gaps when the metric space \mathcal{M} is the vertex set of a uniformly random regular graph H equipped with the shortest-path distance {\rm dist}_{H} . In addition to being a natural setting with intrinsic interest—random regular graphs are ubiquitous in mathematics and theoretical computer science—there are also significant motivating applications that will be discussed shortly. 1.2.1. ​ A basic open question in this context, asked by Jon Kleinberg [ MN15 , Question 2.4] , is the following. Problem 1.2 (Kleinberg) . Let G and H be two independent and uniformly random 3-regular graphs. Is the Poincaré constant \gamma(G,{\rm dist}_{H}^{2}) bounded by a universal constant, independent of |V_{G}| and |V_{H}| , with high probability? Our first main result resolves this question affirmatively with significant added generality. In particular, our result holds when G and H have arbitrary (possibly different) degrees, and it upper bounds \gamma(G,{\rm dist}_{H}^{p}) for any p\geqslant 1 , independently of the degree of H . (For the remainder of this article, for any pair n\geqslant d\geqslant 3 , G(n,d) denotes the set of all d -regular graphs on [n]:=\{1,\dots,n\} , and \mathbb{P}_{G(n,d)} denotes the uniform probability measure on G(n,d) ; we will always assume dn is even.) Theorem 1.3 (Affirmative solution of Kleinberg’s problem) . Let d,\Delta\geqslant 3 be integers, and for every p\geqslant 1 , set (1.4) \Gamma(d,p):=\exp\Big(10^{12}\,2^{p}\,\log^{2}d\Big). Then 1 1 1 See Section 2 for details concerning our asymptotic notation. , (1.5) \mathbb{P}_{G(n,d)}\times\mathbb{P}_{G(m,\Delta)}\Big[(G,H)\colon\gamma(G,{\rm dist}_{H}^{p})\leqslant\Gamma(d,p)\text{ for every }p\geqslant 1\Big]\geqslant 1-O_{d,\Delta}\Big(\frac{1}{\min\{n,m\}^{\tau}}\Big), where \tau=\tau(d,\Delta)>0 . Letting \mathcal{M}=(M,\varrho_{\mathcal{M}}) and \mathcal{N}=(N,\varrho_{\mathcal{N}}) be metric spaces, recall that the ( bi-Lipschitz ) distortion of \mathcal{M} into \mathcal{N} , denoted by c_{\mathcal{N}}(\mathcal{M}) , is defined as the smallest constant D>0 for which there exists a map 2 2 2 Note that this map e is necessarily injective. e\colon M\to N and (a scaling factor) s>0 such that s\varrho_{\mathcal{M}}(i,j)\leqslant\varrho_{\mathcal{N}}\big(e(i),e(j)\big)\leqslant sD\varrho_{\mathcal{M}}(i,j) for all i,j\in M . Theorem 1.3 together with a standard application of ( 1.3 )—reproduced in Subsection 6.4 for the reader’s convenience—yield that independent random regular graphs, viewed as metric spaces, have mutually incompatible geometries. Corollary 1.4 (Bi-Lipschitz distortion between random regular graphs) . Let d,\Delta\geqslant 3 be integers. Then, for any pair of m\geqslant n of positive integers, (1.6) \mathbb{P}_{G(n,d)}\times\mathbb{P}_{G(m,\Delta)}\Big[(G,H)\colon c_{H}(G)\geqslant\Omega_{d}(\log n)\Big]\geqslant 1-O_{d,\Delta}\Big(\frac{1}{n^{\tau}}\Big), where \tau=\tau(d,\Delta)>0 is as in Theorem 1.3 , and c_{H}(G) denotes the bi-Lipschitz distortion of (V_{G},{\rm dist}_{G}) into (V_{H},{\rm dist}_{H}) . 1.2.2. ​ Our second main result concerns sequences (G_{n}) of regular graphs with degree d\geqslant 3 and |V_{G_{n}}|\to\infty , that satisfy, with high probability, a nonlinear Poincaré inequality with respect to a uniformly random regular graph H with a Poincaré constant \gamma(G_{n},{\rm dist}_{H}^{2}) bounded independently of n and the size of the vertex set and the degree of H . The existence of a single sequence (G_{n}) of 3 -regular graphs with this property is a celebrated result of Mendel and Naor [ MN15 , Theorem 1.2] that utilizes the nonlinear spectral calculus developed in [ MN13 , MN14 ] . In this work, Mendel and Naor mention the absence of tools for studying nonlinear spectral gaps of random graphs, and they allude to the natural question of whether their result can be achieved by a randomized construction. The following theorem affirms that this is the case; random regular graphs of any fixed degree d\geqslant 3 provide the desired alternative construction. Theorem 1.5 (Random version of the Mendel–Naor construction) . Let d\geqslant 3 be an integer, and for every p\geqslant 1 , let \Gamma(d,p) be as in ( 1.4 ). There exist positive constants C(d) and \tau^{\prime}=\tau^{\prime}(d) with the following property. For every integer n with n\geqslant C(d) and dn an even integer, there is a nonempty subset \mathcal{A}_{n} of G(n,d) with (1.7) \mathbb{P}_{G(n,d)}\big[\mathcal{A}_{n}\big]\geqslant 1-O_{d}\Big(\frac{1}{n^{\tau^{\prime}}}\Big), such that if G_{n}\in\mathcal{A}_{n} , then, for any integer \Delta\geqslant 3

Read the complete text