Document

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

We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with n vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this extended abstract: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.

Benjamin Hackl, Alois Panholzer, and Stephan Wagner. Uncovering a Random Tree. 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. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hackl_et_al:LIPIcs.AofA.2022.10, author = {Hackl, Benjamin and Panholzer, Alois and Wagner, Stephan}, title = {{Uncovering a Random Tree}}, booktitle = {33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)}, pages = {10:1--10:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.10}, URN = {urn:nbn:de:0030-drops-160962}, doi = {10.4230/LIPIcs.AofA.2022.10}, annote = {Keywords: Labeled tree, uncover process, functional central limit theorem, limiting distribution, phase transition} }

Document

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

We study the size of the automorphism group of two different types of random trees: Galton-Watson trees and Pólya trees. In both cases, we prove that it asymptotically follows a log-normal distribution. While the proof for Galton-Watson trees mainly relies on probabilistic arguments and a general result on additive tree functionals, generating functions are used in the case of Pólya trees.

Christoffer Olsson and Stephan Wagner. Automorphisms of Random Trees. 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. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{olsson_et_al:LIPIcs.AofA.2022.16, author = {Olsson, Christoffer and Wagner, Stephan}, title = {{Automorphisms of Random Trees}}, booktitle = {33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)}, pages = {16:1--16:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.16}, URN = {urn:nbn:de:0030-drops-161026}, doi = {10.4230/LIPIcs.AofA.2022.16}, annote = {Keywords: random tree, Galton-Watson tree, P\'{o}lya tree, automorphism group, 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-dev.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-dev.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-dev.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