Large-scale geometry of graphs of polynomial growth
In 1995, Levin and Linial, London, and Rabinovich conjectured that every connected graph $G$ of polynomial growth admits an injective homomorphism to the $n$-dimensional grid graph for some $n$. Moreover, they conjectured that if every ball of radius $r$ in $G$ contains at most $O(r^\rho)$ vertices, then one can take $n = O(\rho)$. The first part of this conjecture was proved by Krauthgamer and Lee in 2007. However, the second part of the conjecture is false, and the best possible upper bound on $n$ is $O(\rho \log \rho)$. Prompted by these results, Papasoglu asked whether a graph $G$ of polynomial growth admits a coarse embedding into a grid graph. As I will explain in this talk, the answer to Papasoglu's question is "yes." Moreover, it turns out that the dimension of the grid graph only needs to be linear in the asymptotic growth rate of $G$, which confirms the original Levin--Linial--London--Rabinovich conjecture "on the large scale." Furthermore, all these results can be extended to the realm of Borel graphs; namely, 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. This in particular implies that Borel graphs of polynomial growth are hyperfinite, which answers a question of Marks. This is joint work with Jing Yu.