I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.

There are several ways to make this a precise question. I would be interested in any result. This is not my area, so it might well be common knowledge. I'd appreciate any help anyway.

Let me propose one way to make the question precise: Let $k,n$ be natural numbers and let $X(k,n)$ be the set of isomorphy classes of $k$-regular connected graphs with $n$ vertices. Then $v(k,n)=n\,|X(k,n)|$ is the total number of vertices in the union over $X(k,n)$.

Fix some $R>0$ and let $v(k,n)_{\ge R}$ denote the number of such vertices with $\mathrm{Inj}(v)\ge R$, where $\mathrm{Inj}(v)$ denotes the injectivity radius at $v$ (i.e., the radius of the largest disk around $v$ which is a tree). The question is, whether the quotient $$ \frac{v(k,n)_{\ge R}}{v(k,n)}$$ tends to 1, as $n\to\infty$, where $k$ remains fixed.

A related question of interest is the case when one fixes one finite connected $k$-regular graph and asks for all connected coverings of a degree $d$, when $d$ tends to infinity.


1 Answer 1


For fixed $k\ge 3$, $\frac{v(k,n)_{\ge R}}{v(k,n)}\to 1$. First note that most such graphs have trivial automorphism groups, so it doesn't make a difference whether you ask about isomorphism classes or all labelled graphs.

Next, for any $\ell\ge 3$, if an increasing sequence of random $k$-regular graphs is taken, the number of $\ell$-cycles converges to a fixed distribution independent of the graph size, namely the Poisson distribution with mean $\frac{(k-1)^\ell}{2\ell}$. So most vertices are far from any short cycles.

This means that there is a function $f(R)$ such that for fixed $R$ all but $f(R)$ vertices are (with high probability) the centre of a tree of radius $R$.

This survey paper has the necessary references.

  • $\begingroup$ Great. Thanks! Can you point me towards literature, where I can find, say, the result on the distribution of cycles? $\endgroup$
    – user130903
    Mar 17, 2021 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy