License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.17
URN: urn:nbn:de:0030-drops-161035
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16103/
Go to the corresponding LIPIcs Volume Portal

Ralaivaosaona, Dimbinaina

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

pdf-format:
LIPIcs-AofA-2022-17.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{ralaivaosaona:LIPIcs.AofA.2022.17,
  author =	{Ralaivaosaona, Dimbinaina},
  title =	{{The Number of Sources and Isolated Vertices in Random Directed Acyclic Graphs}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16103},
  URN =		{urn:nbn:de:0030-drops-161035},
  doi =		{10.4230/LIPIcs.AofA.2022.17},
  annote =	{Keywords: Directed acyclic graph, generating function, central limit theorem}
}

Keywords: Directed acyclic graph, generating function, central limit theorem
Collection: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Issue Date: 2022
Date of publication: 08.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI