Description:

Title: Geometric (non)embedding of graphs

Abstract: 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)