Coarse embeddings into grids and asymptotic dimension for Borel graphs of polynomial growth

Anton Bernshteyn, Jing Yu

Published 2023-02-09Version 1

Let $\mathsf{Grid}_{n,\infty}$ be the graph with vertex set $\mathbb{Z}^n$ in which two vertices $u$, $v \in \mathbb{Z}^n$ are adjacent if and only if $\|u-v\|_\infty=1$. Levin and Linial, London, and Rabinovich conjectured that every connected graph $G$ of polynomial growth admits an injective homomorphism to $\mathsf{Grid}_{n,\infty}$ for some $n<\infty$. Moreover, they conjectured that if every ball of radius $r$ in $G$ contains at most $(r+1)^\rho$ vertices, then one can take $n = O(\rho)$. Krauthgamer and Lee proved the first part of this conjecture and refuted the second. In this paper we extend their result in a number of ways: (1) We construct asymptotically injective contractions from graphs $G$ of polynomial growth to the grid graph $\mathsf{Grid}_{n,\infty}$ with $n = O(\rho)$, where $\rho$ is the asymptotic polynomial growth rate of $G$. This confirms the second part of the Levin/Linial--London--Rabinovich conjecture "in the asymptotic sense." (2) We construct coarse embeddings from graphs of polynomial growth to grid graphs, answering a question of Papasoglu. (3) We extend the Krauthgamer--Lee theorem and all our results to the realm of Borel graphs and prove that graphs generated by free Borel actions of $\mathbb{Z}^n$ are, in an appropriate sense, universal for the class of Borel graphs of polynomial growth. Along the way we find an alternative proof of the result of Papasoglu that graphs of polynomial growth rate $\rho<\infty$ have asymptotic dimension at most $\rho$. Furthermore, our proof works in the Borel setting and shows that Borel graphs of polynomial growth rate $\rho<\infty$ have Borel asymptotic dimension at most $\rho$, and hence they are hyperfinite. This generalizes a result of Jackson, Kechris, and Louveau from Schreier graphs of Borel group actions to arbitrary Borel graphs of polynomial growth and answers a question of Marks.