On the structure of random graphs with constant \(r\)-balls (Q2693149)

Summary: 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.