Cai, Xing Shi; Perarnau, Guillem The diameter of the directed configuration model. (English. French summary) Zbl 1508.05144 Ann. Inst. Henri Poincaré, Probab. Stat. 59, No. 1, 244-270 (2023). 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. Reviewer: Nicolás Sanhueza-Matamala (Praha) Cited in 1 Document MSC: 05C80 Random graphs (graph-theoretic aspects) 05C12 Distance in graphs 05C20 Directed graphs (digraphs), tournaments 60C05 Combinatorial probability Keywords:diameter; directed configuration model; distances × Cite Format Result Cite Review PDF Full Text: DOI arXiv Link References: [1] L. Addario-Berry, B. Balle and G. Perarnau. Diameter and stationary distribution of random r-out digraphs. The Electronic Journal of Combinatorics (2020), P3.28. · Zbl 1445.05093 · doi:10.37236/9485 [2] H. Amini. Bootstrap percolation in living neural networks. J. Stat. Phys. 141 (3) (2010) 459-475. · Zbl 1207.82037 · doi:10.1007/s10955-010-0056-z [3] H. Amini and A. Minca. Mathematical modeling of systemic risk. In In Advances in Network Analysis and Its Applications, Mathematics in Industry 3-26. Springer, Berlin, Heidelberg, 2013. · doi:10/dm56 [4] K. B. Athreya and P. E. Ney. Branching Processes. Grundlehren Der Mathematischen Wissenschaften. Springer-Verlag, Berlin Heidelberg, 1972. · Zbl 0259.60002 · doi:10/dft4 [5] J. Blanchet and A. Stauffer. Characterizing optimal sampling of binary contingency tables via the configuration model. Random Structures Algorithms 42 (2) (2013) 159-184. · Zbl 1257.62065 · doi:10.1002/rsa.20403 [6] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 (4) (1980) 311-316. · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8 [7] B. Bollobás and W. Fernandez de la Vega. The diameter of random regular graphs. Combinatorica 2 (2) (1982) 125-134. · Zbl 0505.05053 · doi:10.1007/BF02579310 [8] C. Bordenave. Lecture Notes on Random Graphs and Probabilistic Combinatorial Optimization. 2016. Online, Available at https://web.archive.org/web/20210420015408/http://www.i2m.univ-amu.fr/perso/charles.bordenave/_media/coursrg.pdf. [9] C. Bordenave, P. Caputo and J. Salez. Random walk on sparse random digraphs. Probab. Theory Related Fields 170 (3) (2018) 933-960. · Zbl 1383.05294 · doi:10.1007/s00440-017-0796-7 [10] X. S. Cai, P. Caputo, G. Perarnau and M. Quattropani. Rankings in directed configuration models with heavy tailed in-degrees, 2021. Available at arXiv:2104.08389 [cs, math]. [11] X. S. Cai and L. Devroye. The graph structure of a deterministic automaton chosen at random. Random Structures Algorithms 51 (3) (2017) 428-458. · Zbl 1373.05074 · doi:10.1002/rsa.20707 [12] X. S. Cai and G. Perarnau. Minimum stationary values of sparse random directed graphs, 2020. Available at arXiv:2010.07246 [cs, math]. [13] X. S. Cai and G. Perarnau. The giant component of the directed configuration model revisited. ALEA Lat. Am. J. Probab. Math. Stat. 18 (2021) 1517-1528. · Zbl 1468.60012 · doi:10.30757/ALEA.v18-55 [14] P. Caputo and M. Quattropani. Stationary distribution and cover time of sparse directed configuration models. Probab. Theory Related Fields 178 (3) (2020) 1011-1066. · Zbl 1451.05130 · doi:10.1007/s00440-020-00995-6 [15] C. Cooper and A. Frieze. The size of the largest strongly connected component of a random digraph with a given degree sequence. Combin. Probab. Comput. 13 (3) (2004) 319-337. · Zbl 1065.05085 · doi:10.1017/S096354830400611X [16] R. Durrett. Probability: Theory and Examples, 4th edition. Cambridge Series in Statistical and Probabilistic Mathematics 31. Cambridge University Press, Cambridge, 2010. · Zbl 1202.60001 · doi:10.1017/CBO9780511779398 [17] D. Fernholz and V. Ramachandran. The diameter of sparse random graphs. Random Structures Algorithms 31 (4) (2007) 482-516. · Zbl 1129.05046 · doi:10.1002/rsa.20197 [18] A. Graf. On the Strongly Connected Components of Random Directed Graphs with given Degree Sequences. PhD thesis, University of Waterloo, 2016. Available at http://hdl.handle.net/10012/10681. [19] G. H. Hardy, J. E. Littlewood and G. Pólya. Inequalities. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1988. · Zbl 0634.26008 [20] W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (301) (1963) 13-30. · Zbl 0127.10602 · doi:10/gf8mc6 [21] S. Janson. The probability that a random multigraph is simple. Combin. Probab. Comput. 18 (1-2) (2009) 205-225. · Zbl 1216.05145 · doi:10.1017/S0963548308009644 [22] R. M. Karp. The transitive closure of a random digraph. Random Structures Algorithms 1 (1) (1990) 73-93. · Zbl 0712.68076 · doi:10.1002/rsa.3240010106 [23] H. Li. Attack vulnerability of online social networks. In 2018 37th Chinese Control Conference (CCC) 1051-1056, 2018. · doi:10/ggh2kg [24] T. Łuczak and T. G. Seierstad. The critical behavior of random digraphs. Random Structures Algorithms 35 (3) (2009) 271-293. · Zbl 1214.05157 · doi:10.1002/rsa.20283 [25] A. G. Pakes. Some limit theorems for the total progeny of a branching process. Adv. in Appl. Probab. 3 (1) (1971) 176-192. · Zbl 0218.60075 · doi:10.2307/1426333 [26] M. D. Penrose. The strong giant in a random digraph. J. Appl. Probab. 53 (1) (2016) 57-70. · Zbl 1335.05164 · doi:10.1017/jpr.2015.8 [27] D. Ralaivaosaona, V. Rasendrahasina and S. Wagner. On the probability that a random digraph is acyclic. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) 25:1-25:18. Leibniz International Proceedings in Informatics (LIPIcs) 159, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany. · Zbl 07651064 · doi:10/gjmt6b [28] O. Riordan and N. Wormald. The diameter of sparse random graphs. Combin. Probab. Comput. 19 (5-6) (2010) 835-926. · Zbl 1261.05096 · doi:10.1017/S0963548310000325 [29] E. Seneta. On recent theorems concerning the supercritical Galton-Watson process. Ann. Math. Stat. 39 (6) (1968) 2098-2102. · Zbl 0176.47603 · doi:10.1214/aoms/1177698037 [30] R. van der Hofstad. Random Graphs and Complex Networks. Cambridge Series in Statistical and Probabilistic Mathematics 1. Cambridge University Press, Cambridge, England, 2016. · Zbl 1361.05002 · doi:10.1017/9781316779422 [31] R. van der Hofstad. Random Graphs and Complex Networks, 2. 2020. Online, Available at https://web.archive.org/web/20201213052702/https://www.win.tue.nl/texttildelowrhofstad/NotesRGCNII.pdf. · Zbl 1361.05002 · doi:10.1017/9781316779422 [32] P. van der Hoorn and M. Olvera-Cravioto. Typical distances in the directed configuration model. Ann. Appl. Probab. 28 (3) (2018) 1739-1792 · Zbl 1393.05101 · doi:10.1214/17-AAP1342 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.