Abstract: Consider a sparse random graph whose local limit is given by a supercritical (multitype) Galton-Watson process. If $\nu$ is its exponential growth rate, it is reasonable to expect the distance between two uniformly chosen vertices to be (in probability) asymptotically equivalent to $\log_\nu (n)$, where $n$ is the size of the graph. 

This can be proved by computing the first two moments of the number of paths of a given length in order to show the (non) existence of paths whose length (does not) surpass a certain threshold. This technique, commonly known as path-counting, often relies on fairly explicit computations which are not only technically difficult, but also highly model-specific. In this work, we propose a new approach to path-counting which exploits the local structure more efficiently. In particular, we consider the special case of a stochastic block model / multitype Erdős–Rényi model and leverage the Perron-Frobenius theorem to analyse the numbers of paths of a given length. Eventually, we hope to extend our method to more general models for (sparse) random graphs, such as preferential-attachment and the configuration model.