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.