On the structure of random graphs with constant $r$-balls

Abstract

We continue the study of the properties of 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$, for various choices of $F$ and $r$. This is a natural extension of the study of regular graphs.

More precisely, if $F$ is a vertex-transitive graph and $r\in \mathbb{N}$, we say a graph $G$ is $r$-locally $F$ if the ball of radius $r$ around each vertex of $G$ induces a graph isomorphic to the graph induced by the ball of radius $r$ around any vertex of $F$. We consider the following random graph model: for each $n\in \mathbb{N}$, we let $G_n=G_n(F,r)$ be a graph chosen uniformly at random from the set of all unlabelled, $n$-vertex graphs that are $r$-locally $F$. We investigate the properties possessed by the random graph $G_n$ with high probability, i.e. with probability tending to 1 as $n\to \infty$, for various natural choices of $F$ and $r$.

We prove that if $F$ is a Cayley graph of a torsion-free group of polynomial growth, and $r$ is sufficiently large depending on $F$, then the random graph $G_n=G_n(F,r)$ has largest component of order at most $n^{5/6}$ with high probability, and has at least $\exp (n^{\delta })$ automorphisms with high probability, where $\delta >0$ depends upon $F$ alone. Both properties are in stark contrast to random $d$-regular graphs, which correspond to the case where $F$ is the infinite $d$-regular tree. We also show that, under the same hypotheses, the number of unlabelled, $n$-vertex graphs that are $r$-locally $F$ grows like a stretched exponential in $n$, again in contrast with $d$-regular graphs. In the case where $F$ is the standard Cayley graph of ${\mathbb{Z}}^d$, we obtain a much more precise enumeration result, and more precise results on the properties of the random graph $G_n(F,r)$. Our proofs use a mixture of results and techniques from geometry, group theory and combinatorics.

We make several conjectures regarding what happens for Cayley graphs of other finitely generated groups.