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

Let $D(n,r)$ be a random $r$-out regular directed multigraph on the set of vertices $\{1,\ldots,n\}$. In this work, we establish that for every $r \ge 2$, there exists $η_r>0$ such that $\text{diam}(D(n,r))=(1+η_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 $π_{\max}$ and $π_{\min}$, the maximum and the minimum values of the stationary distribution. We show that with high probability $π_{\max} = n^{-1+o(1)}$ and $π_{\min}=n^{-(1+η_r)+o(1)}$. Our proof shows that the vertices with $π(v)$ near to $π_{\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+η_r+o(1))\log_r{n}$.

No reviews yet.

No comments yet.