Document

**Published in:** LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

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.

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.AofA.2022.17}, URN = {urn:nbn:de:0030-drops-161035}, doi = {10.4230/LIPIcs.AofA.2022.17}, annote = {Keywords: Directed acyclic graph, generating function, central limit theorem} }

Document

**Published in:** LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

We study block statistics in subcritical graph classes; these are statistics that can be defined as the sum of a certain weight function over all blocks. Examples include the number of edges, the number of blocks, and the logarithm of the number of spanning trees. The main result of this paper is a central limit theorem for statistics of this kind under fairly mild technical assumptions.

Dimbinaina Ralaivaosaona, Clément Requilé, and Stephan Wagner. Block Statistics in Subcritical Graph Classes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2020.24, author = {Ralaivaosaona, Dimbinaina and Requil\'{e}, Cl\'{e}ment and Wagner, Stephan}, title = {{Block Statistics in Subcritical Graph Classes}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.24}, URN = {urn:nbn:de:0030-drops-120543}, doi = {10.4230/LIPIcs.AofA.2020.24}, annote = {Keywords: subcritical graph class, block statistic, number of blocks, number of edges, number of spanning trees} }

Document

**Published in:** LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Given a positive integer n and a real number p ∈ [0,1], let D(n,p) denote the random digraph defined in the following way: each of the binom(n,2) possible edges on the vertex set {1,2,3,…,n} is included with probability 2p, where all edges are independent of each other. Thereafter, a direction is chosen independently for each edge, with probability 1/2 for each possible direction. In this paper, we study the probability that a random instance of D(n,p) is acyclic, i.e., that it does not contain a directed cycle. We find precise asymptotic formulas for the probability of a random digraph being acyclic in the sparse regime, i.e., when np = O(1). As an example, for each real number μ, we find an exact analytic expression for φ(μ) = lim_{n→ ∞} n^{1/3} ℙ{D(n,1/n (1+μ n^{-1/3})) is acyclic}.

Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2020.25, author = {Ralaivaosaona, Dimbinaina and Rasendrahasina, Vonjy and Wagner, Stephan}, title = {{On the Probability That a Random Digraph Is Acyclic}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.25}, URN = {urn:nbn:de:0030-drops-120557}, doi = {10.4230/LIPIcs.AofA.2020.25}, annote = {Keywords: Random digraphs, acyclic digraphs, asymptotics} }

Document

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Tanglegrams are structures consisting of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the two trees. We say that a tanglegram is planar if it can be drawn in the plane without crossings. Using a blend of combinatorial and analytic techniques, we determine an asymptotic formula for the number of planar tanglegrams with n leaves on each side.

Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, and Stephan Wagner. Counting Planar Tanglegrams. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2018.32, author = {Ralaivaosaona, Dimbinaina and Ravelomanana, Jean Bernoulli and Wagner, Stephan}, title = {{Counting Planar Tanglegrams}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and Ward, Mark Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.32}, URN = {urn:nbn:de:0030-drops-89259}, doi = {10.4230/LIPIcs.AofA.2018.32}, annote = {Keywords: rooted binary trees, tanglegram, planar, generating functions, asymptotic enumeration, singularity analysis} }

Document

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Janson recently proved a central limit theorem for additive functionals of conditioned Galton-Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are almost local, thus covering a wider range of functionals. Our main result is illustrated by two explicit examples: the (logarithm of) the number of matchings, and a functional stemming from a tree reduction process that was studied by Hackl, Heuberger, Kropf, and Prodinger.

Dimbinaina Ralaivaosaona, Matas Sileikis, and Stephan Wagner. Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2018.33, author = {Ralaivaosaona, Dimbinaina and Sileikis, Matas and Wagner, Stephan}, title = {{Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {33:1--33:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and Ward, Mark Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.33}, URN = {urn:nbn:de:0030-drops-89262}, doi = {10.4230/LIPIcs.AofA.2018.33}, annote = {Keywords: Galton-Watson trees, central limit theorem, additive functional} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail