Thick Embeddings Of Graphs Into Symmetric Spaces Via Coarse Geometry

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 ≥ 3 every bounded degree graph admits 1 a coarse wiring into ℝ^k with volume at most CN^1+(1/k-2). As a corollary, the same upper bound holds for real hyperbolic space of dimension k + 1 and in both cases this result is optimal.