×

Counting directed acyclic and elementary digraphs. (English) Zbl 1452.05087

The strongly connected components of directed acyclic graphs (DAGs) are only isolated vertices.
Using this fact, the authors discover that when \(m =cn\), where \(m\) is the number of directed edges, \(n\) is the number of vertices, and \(c <1\) is a constant, the asymptotic probability for a random digraph to be acyclic is an explicit function \(p(c) = e^{-c}(1- c)\). When \(m = n(1 + \mu n^{-1/3})\), the asymptotic behavior changes, and the probability for a digraph to be acyclic becomes \(n^{-1/3}C(\mu)\), where \(C(\mu)\) is an explicit function of \(\mu\). T. Łuczak and T. G. Seierstad [Random Struct. Algorithms 35, No. 3, 271–293 (2009; Zbl 1214.05157)] showed that, as \(\mu \rightarrow -\infty\), the strongly connected components of a random digraph with \(n\) vertices and \(m = n(1 +\mu n^{-1/3})\) directed edges are, with high probability, only isolated vertices and cycles, and such digraphs are called elementary digraphs. The present authors also express the probability for a random digraph to be elementary as a function of \(\mu\).
These results are obtained using techniques from analytic combinatorics, developed in particular for the study of random graphs.

MSC:

05C30 Enumeration in graph theory
05C20 Directed graphs (digraphs), tournaments
05C80 Random graphs (graph-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Citations:

Zbl 1214.05157
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. “Random maps, coalescing saddles, singularity analysis, and Airy phenomena”.Random Struct. & Algor.19.3-4 (2001), pp. 194- 246.Link. · Zbl 1016.68179
[2] E. Bender, L. Richmond, R. Robinson, and N. NWormald. “The asymptotic number of acyclic digraphs. I”.Combinatorica6.1 (1986), pp. 15-22.Link. · Zbl 0601.05025
[3] G. Collet, E. De Panafieu, D. Gardy, B. Gittenberger, and V. Ravelomanana. “Threshold functions for small subgraphs in simple graphs and multigraphs”.European Journal of Combinatorics(2020), pp. 103-113.Link. · Zbl 1442.05092
[4] P. Flajolet, B. Salvy, and G. Schaeffer. “Airy phenomena and analytic combinatorics of connected graphs”.The Electronic Journal of Combinatorics11.1 (2004).Link. · Zbl 1053.05064
[5] P. Flajolet and R. Sedgewick.Analytic combinatorics. Cambridge University press, 2009.Link. · Zbl 1165.05001
[6] I. Gessel. “Counting acyclic digraphs by sources and sinks”.Discrete Mathematics160.1-3 (1996), pp. 253-258.Link. · Zbl 0863.05042
[7] C. Goldschmidt and R. Stephenson. “The scaling limit of a critical random directed graph”. 2019.arXiv:1905.05397.
[8] T. Greenwood. “Asymptotics of bivariate analytic functions with algebraic singularities”. Journal of Combinatorial Theory A153(2018), pp. 1-30.Link. · Zbl 1369.05012
[9] S. Janson, D. Knuth, T. Łuczak, and B. Pittel. “The birth of the giant component”.Random Struct. & Algor.4.3 (1993), pp. 233-358.Link. · Zbl 0795.05127
[10] V. Liskovets. “On the number of maximal vertices of a random acyclic digraph”.Theory of Probability & Its Applications20.2 (1976), pp. 401-409.Link.
[11] T. Łuczak. “The phase transition in the evolution of random digraphs”.Journal of graph theory14.2 (1990), pp. 217-223.Link. · Zbl 0712.05051
[12] T. Łuczak and T. Seierstad. “The critical behavior of random digraphs”.Random Struct. & Algor.35.3 (2009), pp. 271-293.Link. · Zbl 1214.05157
[13] B. McKay. “On the shape of a random acyclic digraph”.Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 106. 3. 1989, pp. 459-465.Link. · Zbl 0702.05040
[14] É. de Panafieu. “Analytic combinatorics of connected graphs”.Random Struct. & Algor. (2016).Link. · Zbl 1440.05102
[15] É. de Panafieu and S. Dovgal. “Symbolic method and directed graph enumeration”.Acta Mathematica Universitatis Comenianae88.3 (2019), pp. 989-996.
[16] B. Pittel and D.Poole. “Birth of a giant (k1, k2)-core in the random digraph”.Advances in Applied Mathematics86(2017), pp. 132-174.Link. · Zbl 1358.05126
[17] D. Ralaivaosaona, D. Rasendrahasina, and S. Wagner. “On the Probability that a Random
[18] R.
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.