Thick embeddings of graphs into symmetric spaces via coarse geometry

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.