The diameter of the directed configuration model (Q2686613)

The paper studies random digraphs generated using the directed configuration model. In this model, an \(n\)-vertex digraph is generated as follows: given a bidegree sequence \(\mathfrak{d}_n = ((d_1^-, d_1^+),\dots, (d_n^-, d_n^+))\) with \(\sum_{i} d_i^- = \sum_i d_i^+\), then one gives \(d_i^-\) heads and \(d_i^+\) tails to each vertex \(i\) and forms a digraph by choosing a random assignment between all heads and tails. This generates a random \(n\)-vertex digraph \(G_n\) with a fixed degree sequence \(\mathfrak{d}_n\). Usually one considers a sequence \((\mathfrak{d}_n)_n\) of degree sequences and investigates the properties which hold probability tending to one as \(n\) tends to infinity. The paper studies the diameter, i.e. the maximum distance between any two vertices of \(G_n\). The main result of the paper shows that, under weak assumptions on the sequence \((\mathfrak{d}_n)_n\), the diameter of \(G_n\) divided by \(\log n\) converges in probability (when \(n\) tends to infinity) to a constant, which is determined explicitly. The assumptions needed for the result to work are that the sequences \((\mathfrak{d}_n)_n\) converge in distribution, in the first moment, and in a second moment, to a discrete probability distribution \(D\) on \(\mathbb{Z}^2_{\geq 0}\) with finite expectations and second moments. The proof relies on the analysis of a breadth first search edge-exploration process of random digraphs and its coupling with the corresponding branching process. The main result is also used to deduce results in other random digraph models.