Diameter and stationary distribution of random \(r\)-out digraphs (Q785578): Difference between revisions

Summary: 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 \(\eta_r>0\) such that \(\text{diam}(D(n,r))=(1+\eta_r+o(1))\log_r{n} \). The constant \(\eta_r\) is related to branching processes and also appears in other models of random undirected graphs. 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 tower''; 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}\).