Thick embeddings of graphs into symmetric spaces via coarse geometry
HTML articles powered by AMS MathViewer
- by Benjamin Barrett, David Hume, Larry Guth and Elia Portnoy;
- Trans. Amer. Math. Soc. 378 (2025), 885-909
- DOI: https://doi.org/10.1090/tran/9109
- Published electronically: December 12, 2024
- HTML | PDF | Request permission
Abstract:
We prove estimates for the optimal volume of thick embeddings of finite graphs into symmetric spaces, generalising results of Kolmogorov-Barzdin and Gromov-Guth for embeddings into Euclidean spaces. We distinguish two very different behaviours depending on the rank of the non-compact factor. For rank at least 2, we construct thick embeddings of $N$-vertex graphs with volume $CN\ln (1+N)$ and prove that this is optimal. For rank at most $1$ we prove lower bounds of the form $cN^a$ for some (explicit) $a>1$ which depends on the dimension of the Euclidean factor and the conformal dimension of the boundary of the non-compact factor. The main tool is a coarse geometric analogue of a thick embedding called a coarse wiring, with the key property that the minimal volume of a thick embedding is comparable to the “minimal volume” of a coarse wiring for symmetric spaces of dimension at least $3$. In the appendix it is proved that for each $k\geq 3$ every bounded degree graph admits a coarse wiring into $\mathbb {R}^k$ with volume at most $CN^{1+\frac {1}{k-1}}$. As a corollary, the same upper bound holds for real hyperbolic space of dimension $k+1$ and in both cases this result is optimal.References
- Itai Benjamini, Oded Schramm, and Ádám Timár, On the separation profile of infinite graphs, Groups Geom. Dyn. 6 (2012), no. 4, 639–658. MR 2996405, DOI 10.4171/GGD/168
- Misha Gromov and Larry Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates, Duke Math. J. 161 (2012), no. 13, 2549–2603. MR 2988903, DOI 10.1215/00127094-1812840
- Larry Guth, Recent progress in quantitative topology, Surveys in differential geometry 2017. Celebrating the 50th anniversary of the Journal of Differential Geometry, Surv. Differ. Geom., vol. 22, Int. Press, Somerville, MA, 2018, pp. 191–216. MR 3838118
- David Hume, A continuum of expanders, Fund. Math. 238 (2017), no. 2, 143–152. MR 3640615, DOI 10.4064/fm101-11-2016
- David Hume, John M. Mackay, and Romain Tessera, Poincaré profiles of groups and spaces, Rev. Mat. Iberoam. 36 (2020), no. 6, 1835–1886. MR 4163985, DOI 10.4171/rmi/1184
- David Hume, John M. Mackay, and Romain Tessera, Poincaré profiles of Lie groups and a coarse geometric dichotomy, Geom. Funct. Anal. 32 (2022), no. 5, 1063–1133. MR 4498840, DOI 10.1007/s00039-022-00617-4
- S. Kelly, A topological embedding of the binary tree into the square lattice, Preprint, arXiv:2311.13195.
- A. N. Kolmogorov and Y. M. Barzdin, On the realization of networks in three-dimensional space, Selected Works of Kolmogorov, Kluwer, Dordrecht, vol. 3, 1993, pp. 194–202.
- F. López, B. Pozzetti, S. Trettel, M. Strube and A. Wienhard, Symmetric spaces for graph embeddings: a Finsler-Riemannian approach, Proceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021.
- Pierre Pansu, Dimension conforme et sphère à l’infini des variétés à courbure négative, Ann. Acad. Sci. Fenn. Ser. A I Math. 14 (1989), no. 2, 177–212 (French, with English summary). MR 1024425, DOI 10.5186/aasfm.1989.1424
- R. Raistrick, Dependence of the coarse wiring profile on the choice of parameter, Preprint, arXiv:2311.08436.
- Wolfgang Woess, Lamplighters, Diestel-Leader graphs, random walks, and harmonic functions, Combin. Probab. Comput. 14 (2005), no. 3, 415–433. MR 2138121, DOI 10.1017/S0963548304006443
Bibliographic Information
- Benjamin Barrett
- MR Author ID: 1279644
- David Hume
- MR Author ID: 1029452
- ORCID: 0000-0003-2195-6071
- Larry Guth
- MR Author ID: 786046
- Received by editor(s): April 19, 2022
- Received by editor(s) in revised form: January 24, 2023, and November 28, 2023
- Published electronically: December 12, 2024
- Additional Notes: The appendix was written by the third and fourth authors
- © Copyright 2024 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 378 (2025), 885-909
- MSC (2020): Primary 51F30; Secondary 53C23
- DOI: https://doi.org/10.1090/tran/9109