On the structure of random graphs that are locally indistinguishable from a lattice

Itai Benjamini, David Ellis

Published 2018-02-06Version 1

We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to the ball of radius $r$ in some fixed vertex-transitive graph $F$. This is a natural extension of the study of regular graphs. We focus on the case where $F$ is $\mathbb{L}^d$, the graph of the $d$-dimensional square lattice. In a previous work [I. Benjamini, D. Ellis, On the structure of graphs which are locally indistinguishable from a lattice, {\em Forum of Mathematics, Sigma} 4 (2016), e31.], the authors obtained a characterisation of all the $n$-vertex graphs in which the ball of radius $r$ around each vertex is isomorphic to the ball of radius $r$ in $\mathbb{L}^d$, for each pair of integers $d,r$ such that $d \geq 2$ and $r \geq 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. In this paper, we estimate the number of unlabelled, $n$-vertex graphs which have the above property (in the case where $r$ is at least linear in $d$). This number grows like a stretched-exponential, again in contrast with the situation for regular graphs. We use this estimate to obtain results on the typical properties of a uniform random such graph. In particular, we show that with high probability, the largest component of this random graph has size $O(n^{1-\epsilon})$ for some fixed $\epsilon>0$ depending only upon $d$, but that there are only $o(n)$ vertices in bounded-size components. Our proofs use a mixture of techniques and results from group theory, topology, analytic number theory and combinatorics.