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, ..., n}. In this work, we establish that for every r >= 2, there exists eta(r) > 0 such that 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(m)(ax) 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 7r(v) near to 7i m i n 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.