Stationary distribution and cover time of sparse directed configuration models

We consider sparse digraphs generated by the configuration model with given in-degree and out-degree sequences. We establish that with high probability the cover time is linear up to a poly-logarithmic correction. For a large class of degree sequences we determine the exponent γ≥1 of the logarithm and show that the cover time grows as nlogγ(n), where n is the number of vertices. The results are obtained by analysing the extremal values of the stationary distribution of the digraph. In particular, we show that the stationary distribution π is uniform up to a poly-logarithmic factor, and that for a large class of degree sequences the minimal values of π have the form 1nlog1−γ(n), while the maximal values of π behave as 1nlog1−κ(n) for some other exponent κ∈[0,1]. In passing, we prove tight bounds on the diameter of the digraphs and show that the latter coincides with the typical distance between two vertices.