David Hume

Thick topological embeddings of graphs into symmetric spaces

A topological embedding of a graph is "thick" if the images of disjoint pairs of edges and vertices are a uniformly controlled distance apart. Such embeddings are desirable for representations of transport networks and for designing circuit boards.

Inspired by the work of Kolmogorov-Barzdin, Gromov-Guth and recent developments in machine learning, we consider thick embeddings of graphs into symmetric spaces. 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 ≤ CN⋅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 ≥ cN^1+a for some a>0.

This is joint work with Benjamin Barrett.