Search Results

Documents authored by Ralaivaosaona, Dimbinaina

Document
DOI: 10.4230/LIPIcs.AofA.2022.17
The Number of Sources and Isolated Vertices in Random Directed Acyclic Graphs

Authors: Dimbinaina Ralaivaosaona

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

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.
Cite as

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
DOI: 10.4230/LIPIcs.AofA.2020.24
Block Statistics in Subcritical Graph Classes

Authors: Dimbinaina Ralaivaosaona, Clément Requilé, and Stephan Wagner

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.AofA.2020.25
On the Probability That a Random Digraph Is Acyclic

Authors: Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner

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

Abstract
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}.
Cite as

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
DOI: 10.4230/LIPIcs.AofA.2018.32
Counting Planar Tanglegrams

Authors: Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, and Stephan Wagner

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.AofA.2018.33
Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees

Authors: Dimbinaina Ralaivaosaona, Matas Sileikis, and Stephan Wagner

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

Abstract
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.
Cite as

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}
}
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 Imprint Privacy Contact