Diameter and Stationary Distribution of Random $r$-out Digraphs

Abstract

Let $D(n,r)$ be a random $r$-out regular directed multigraph on the set of vertices $\{1,\dots ,n\}$. In this work, we establish that for every $r\ge 2$, there exists ${\eta }_r>0$ such that $\text{diam}(D(n,r))=(1+{\eta }_r+o(1)){\log }_{r}n$. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on $D(n,r)$. In particular, we determine the asymptotic behaviour of ${\pi }_{\max }$ and ${\pi }_{\min }$, the maximum and the minimum values of the stationary distribution. We show that with high probability ${\pi }_{\max }=n^{-1+o(1)}$ and ${\pi }_{\min }=n^{-(1+{\eta }_r)+o(1)}$. Our proof shows that the vertices with $\pi (v)$ near to ${\pi }_{\min }$ lie at the top of "narrow, slippery towers", such vertices are also responsible for increasing the diameter from $(1+o(1)){\log }_{r}n$ to $(1+{\eta }_r+o(1)){\log }_{r}n$.

31 pages