Discrete Poincaré inequalities and universal approximators for random graphs

2025/06/20 by Altschuler, Dylan J., Dodos, Pandelis, Tikhomirov, Konstantin +1
#Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #Probability (math.PR)

paper · doi:10.48550/arxiv.2506.17433

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-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 approximators for random graphs, answering a question of Mendel and Naor.

Related

• Metric Poincaré inequalities for graphs
• A combinatorial approach to nonlinear spectral gaps
• Volume Doubling Condition and a Local Poincaré Inequality on Unweighted Random Geometric Graphs
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Product Measure Approximation of Symmetric Graph Properties