Metric Poincaré inequalities for graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918304376946688 |
|---|---|
| author | Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos |
| author_facet | Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos |
| contents | This article obtains purely metric counterparts of cornerstone results in the theory of embedding graphs into normed spaces. Our first main result is a metric analogue of Matoušek's extrapolation relating the Poincaré constants $γ(G,\varrho^p)$ and $γ(G,\varrho^q)$ for any exponents $0 < p,q < \infty$, any bounded-degree expander graph $G$, and any target metric space $\mathcal{M}=(M,\varrho)$. Our second main result provides a sharp estimate of the Poincaré constant $γ(G,\varrho)$ in terms of the cardinalities of the vertex set of $G$ and the metric space $\mathcal{M}=(M,\varrho)$, in the setting of \textit{random} graphs. This yields optimal estimates on the minimum cardinality of (bi-Lipschitz) universal metric spaces for graphs, finally establishing a nonlinear analogue of Matoušek's celebrated "incompressibility" theorem (1996). Further, we obtain estimates on the nonlinear spectral gap of metric snowflakes and sharp lower bounds on the distortion of random regular graphs into arbitrary metric spaces. Our proofs develop new nonlinear techniques, including random compression methods and a novel structural dichotomy for metric embeddings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_25489 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Metric Poincaré inequalities for graphs Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos Metric Geometry Combinatorics Probability This article obtains purely metric counterparts of cornerstone results in the theory of embedding graphs into normed spaces. Our first main result is a metric analogue of Matoušek's extrapolation relating the Poincaré constants $γ(G,\varrho^p)$ and $γ(G,\varrho^q)$ for any exponents $0 < p,q < \infty$, any bounded-degree expander graph $G$, and any target metric space $\mathcal{M}=(M,\varrho)$. Our second main result provides a sharp estimate of the Poincaré constant $γ(G,\varrho)$ in terms of the cardinalities of the vertex set of $G$ and the metric space $\mathcal{M}=(M,\varrho)$, in the setting of \textit{random} graphs. This yields optimal estimates on the minimum cardinality of (bi-Lipschitz) universal metric spaces for graphs, finally establishing a nonlinear analogue of Matoušek's celebrated "incompressibility" theorem (1996). Further, we obtain estimates on the nonlinear spectral gap of metric snowflakes and sharp lower bounds on the distortion of random regular graphs into arbitrary metric spaces. Our proofs develop new nonlinear techniques, including random compression methods and a novel structural dichotomy for metric embeddings. |
| title | Metric Poincaré inequalities for graphs |
| topic | Metric Geometry Combinatorics Probability |
| url | https://arxiv.org/abs/2509.25489 |