# Thick embeddings of graphs into symmetric spaces

24.01.2023 15:00 - 17:00

David Hume (Bristol)

Inspired by the work of Kolmogorov-Barzdin in the 60’s and more recently by Gromov-Guth on thick embeddings into Euclidean spaces, we consider thick embeddings of graphs into more general symmetric spaces. Roughly, a thick embedding is a topological embedding of a graph where disjoint pairs of edges and vertices are at least a uniformly controlled distance apart (consistent with applications where vertices and edges are considered as having volume). The goal is to find thick embeddings with minimal “volume”.

We prove a dichotomy depending upon the rank of the non-compact factor of the symmetric space. For rank at least 2, there are thick embeddings of $$N$$-vertex graphs with volume $$\leq C N\log(N)$$ where $$C$$ depends on the maximal degree of the graph. By contrast, for rank at most 1, thick embeddings of expander graphs have volume $$\geq c N^{1+a}$$ for some $$a\geq 0$$.

The key tool required for these results is the notion of a coarse wiring, which is a continuous embedding of one graph inside another satisfying some additional properties. We prove that the minimal “volume” of a coarse wiring into a symmetric space is equivalent to the minimal volume of a thick embedding. We obtain lower bounds on the volume of coarse wirings by comparing the relative connectivity (as measured by the separation profile) of the domain and target, and upper bounds by direct construction.

This is joint work with Benjamin Barrett.

Join Zoom meeting ID 613 8691 2732

Passcode: A group is called an ________ group if it admits an invariant mean. (8 letters, lowercase)

Organiser:

Location:
Zoom