Dylan J. Altschuler (CMU): Geometric (non)embedding of graphs

Given a collection of points in a normed space, the corresponding ``geometric graph" is obtained by connecting any pair of points with distance less than one. Say that a graph $G$ is "geometrically embeddable" into a normed space $X$ if there exist points in $X$ whose geometric graph is isomorphic to $G$. Geometric embeddability arises naturally at the intersection of combinatorics, metric geometry, and data science.

While criteria for geometric embeddings are well-studied in Euclidean space, essentially nothing is known outside this setting. We address this gap. Our result is that asymptotically almost every regular graph $G$ on $N$ vertices has the following ``universal" non-embedding property: there is no normed space of dimension less than $c \log N$ admitting a geometric embedding of $G$. This is sharp. The proof is based on an efficient multiscale ``seeded" epsilon--net argument.

(joint with Konstantin Tikhomirov; arxiv.org/abs/2501.09142)