On the structure of random graphs with constant r-balls

DOI10.4171/JEMS/1181MaRDI QIDQ6297396arXivFDO

Authors Itai Benjamini, David Ellis

Publication date 6 February 2018

Published in arXiv

Full work available at URL https://doi.org/10.4171/JEMS/1181

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Other geometric groups, including crystallographic groups (20H15)

arXiv classification

math.COmath.GRmath.PR

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 $rinmathbbN$, 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 $ninmathbbN$, 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.

This page was built for publication: On the structure of random graphs with constant $r$-balls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6297396)