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

### Itai Benjamini

Weizmann Institute of Science, Rehovot, Israel### David Ellis

University of Bristol, UK

## 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∈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∈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→∞$, 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_{δ})$ automorphisms with high probability, where $δ>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 $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.

## Cite this article

Itai Benjamini, David Ellis, On the structure of random graphs with constant $r$-balls. J. Eur. Math. Soc. 25 (2023), no. 2, pp. 515–570

DOI 10.4171/JEMS/1181