• shareshare
  • link
  • cite
  • add
auto_awesome_motion View all 4 versions
Publication . Article . Preprint . 2021

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

Benjamini, Itai; Ellis, David;
Open Access
Published: 21 Dec 2021 Journal: Journal of the European Mathematical Society (issn: 1435-9855, Copyright policy )
Publisher: European Mathematical Society - EMS - Publishing House GmbH
Country: United Kingdom
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 {\em $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, 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.
Comment: Full proof of Theorem 7 added. Statement of Proposition 38 has been strengthened slightly. 61 pages

Applied Mathematics, General Mathematics, Mathematics - Combinatorics, Mathematics - Group Theory, Mathematics - Probability, 05C80 (primary), 05C30, 20H15 (secondary), Combinatorics (math.CO), Group Theory (math.GR), Probability (math.PR), FOS: Mathematics

[27] J. H. Kwak and R. Nedela, Graphs and their Coverings, Lecture Notes Series No. 17, Combinatorial and Computational Mathematics Center, POSTECH, Pohang, 2005. Available at∼nedela/graphcov.pdf.

[28] F. Lazebnik, V. A. Ustimenko and A. J. Woldar, A New Series of Dense Graphs of High Girth, Bull. Amer. Math. Soc. 32 (1995), 73-79.

[29] A. Lubotzsky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277.

[30] B. D. McKay, N. Wormald, Automorphisms of random graphs with specified vertices, Combinatorica 4 (1984), 325-338.

Download fromView all 4 sources