Document Open Access Logo

The Number of Sources and Isolated Vertices in Random Directed Acyclic Graphs

Author Dimbinaina Ralaivaosaona

PDF
Thumbnail PDF

File

LIPIcs.AofA.2022.17.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Dimbinaina Ralaivaosaona
  • University of Stellenbosch, South Africa

Funding

This work is based on the research supported in part by the National Research Foundation of South Africa (grant number: 129413).

Acknowledgements

I want to thank the anonymous referees for their helpful comments which helped to improve the presentation of this paper.

Cite As Get BibTex

Dimbinaina Ralaivaosaona. The Number of Sources and Isolated Vertices in Random Directed Acyclic Graphs. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.AofA.2022.17

Abstract

For a positive integer n and a real number p ∈ (0,1), a random directed acyclic digraph 𝔻_{ac}(n,p) is obtained from the binomial random digraph model 𝔻(n,p) conditioned to be acyclic, i.e., directed cycles are forbidden. In the binomial random digraph model 𝔻(n,p), every possible directed edge (excluding loops) occurs independently with probability p. Sources and sinks are among the most natural characteristics of directed acyclic graphs. We investigate the distribution of the number of sources in 𝔻_{ac}(n,p) when p is of the form λ/n, where λ is a fixed positive constant. Because of symmetry, the number of sinks will have the same distribution as the number of sources. Our main motivation is to understand how this distribution changes as we pass through the critical point p = 1/n. Since we are in the sparse regime, it makes sense to include the number of isolated vertices as well. In a directed graph an isolated vertex can be regarded as a vertex that is both a source and a sink. We prove asymptotic normality for each of these parameters when p = λ/n. Our method is based on the analysis of a multivariate generating function from a work of Gessel.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Generating functions
Keywords
  • Directed acyclic graph
  • generating function
  • central limit theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. D. Barbour. Poisson convergence and random graphs. Math. Proc. Cambridge Philos. Soc., 92(2):349-359, 1982. URL: https://doi.org/10.1017/S0305004100059995.
  2. A. D. Barbour, MichałKaroński, and Andrzej Ruciński. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B, 47(2):125-145, 1989. URL: https://doi.org/10.1016/0095-8956(89)90014-2.
  3. É. de Panafieu, S. Dovgal, D. Ralaivaosaona, V. Rasendrahasina, and S. Wagner. The birth of the strong components, 2020. URL: http://arxiv.org/abs/2009.12127.
  4. I. M. Gessel. Counting acyclic digraphs by sources and sinks. Discrete Mathematics, 160(1):253-258, 1996. Google Scholar
  5. H.-K. Hwang. On convergence rates in the central limit theorems for combinatorial structures. European Journal of Combinatorics, 19(3):329-343, 1998. URL: https://doi.org/10.1006/eujc.1997.0179.
  6. M. Karoński and A. Ruciński. Poisson convergence and semi-induced properties of random graphs. Math. Proc. Cambridge Philos. Soc., 101(2):291-300, 1987. URL: https://doi.org/10.1017/S0305004100066664.
  7. R. M. Karp. The transitive closure of a random digraph. Random Structures & Algorithms, 1(1):73-93, 1990. Google Scholar
  8. V. A. Liskovec. On the enumeration of strongly connected directed graphs. Dokl. Akad. Nauk BSSR, 17:1077-1080, 1163, 1973. Google Scholar
  9. V. A. Liskovets. On the number of maximal vertices of a random acyclic digraph. Theory of Probability & Its Applications, 20(2):401-409, 1976. Google Scholar
  10. T. Łuczak. The phase transition in the evolution of random digraphs. Journal of Graph Theory, 14:217-223, 1990. Google Scholar
  11. T. Łuczak and T. Seierstad. The critical behavior of random digraphs. Random Structures & Algorithms, 35:271-293, 2009. Google Scholar
  12. B. D. Mckay. On the shape of a random acyclic digraph. Mathematical Proceedings of the Cambridge Philosophical Society, 106(3):459-465, 1989. URL: https://doi.org/10.1017/S0305004100068195.
  13. F. W. Olver, D. W. Lozier, Ronald F. Boisvert, and C. W. Clark. NIST Handbook of Mathematical Functions. Cambridge University Press, USA, 1st edition, 2010. Google Scholar
  14. 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), volume 159 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1-25:18, 2020. Google Scholar
  15. R. W. Robinson. Counting labelled acyclic digraphs. In New Directions in Graph Theory (Ed. F. Harary). New York: Academic Press, 1973. Google Scholar
  16. R. P. Stanley. Acyclic orientations of graphs. Discrete Mathematics, 5(2):171-178, 1973. Google Scholar
  17. The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.9), 2019. https://www.sagemath.org. Google Scholar
  18. P. Zbigniew. On the number of vertices of given degree in a random graph. J. Graph Theory, 8(1):167-170, 1984. URL: https://doi.org/10.1002/jgt.3190080119.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact