LIPIcs.AofA.2022.16.pdf
- Filesize: 0.64 MB
- 16 pages
Document
Automorphisms of Random Trees
Authors
Christoffer Olsson 
,
Stephan Wagner
-
Part of:
Volume:
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-08
File
Document Identifiers
Author Details
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.AofA.2022.16
https://doi.org/10.4230/LIPIcs.AofA.2022.16
Abstract
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Random graphs
- Mathematics of computing → Generating functions
Keywords
- random tree
- Galton-Watson tree
- Pólya tree
- automorphism group
- central limit theorem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
László Babai. Automorphism groups, isomorphism, reconstruction. In Handbook of combinatorics, Vol. 1, 2, pages 1447-1540. Elsevier Sci. B. V., Amsterdam, 1995.
- Miklós Bóna and Philippe Flajolet. Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab., 46(4):1005-1019, 2009. URL: https://doi.org/10.1239/jap/1261670685.
- Michael Drmota. Random trees. SpringerWienNewYork, Vienna, 2009. An interplay between combinatorics and probability. URL: https://doi.org/10.1007/978-3-211-75357-6.
- Cecilia Holmgren and Svante Janson. Limit laws for functions of fringe trees for binary search trees and random recursive trees. Electron. J. Probab., 20:no. 4, 51, 2015. URL: https://doi.org/10.1214/EJP.v20-3627.
- Cecilia Holmgren, Svante Janson, and Matas Šileikis. Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees. Electron. J. Combin., 24(2):Paper No. 2.51, 49, 2017. URL: https://doi.org/10.37236/6374.
- Mikhail Isaev, Angus Southwell, and Maksim Zhukovskii. Distribution of tree parameters by martingale approach, 2019. URL: http://arxiv.org/abs/1912.09838.
- Svante Janson. Random cutting and records in deterministic and random trees. Random Structures & Algorithms, 29(2):139-179, 2006. URL: https://doi.org/10.1002/rsa.20086.
- Svante Janson. Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees. Random Structures Algorithms, 48(1):57-101, 2016. URL: https://doi.org/10.1002/rsa.20568.
-
Olav Kallenberg. Foundations of modern probability. Springer, New York, 1997.
- David Matthews. Automorphisms of Random Recursive Trees. PhD thesis, University of Southhampton, 2017. URL: https://eprints.soton.ac.uk/415900.
-
Kathleen A. McKeon. The expected number of symmetries in locally-restricted trees. I. In Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., pages 849-860. Wiley, New York, 1991.
- Kathleen A. McKeon. The expected number of symmetries in locally restricted trees. II. Discrete Appl. Math., 66(3):245-253, 1996. URL: https://doi.org/10.1016/0166-218X(94)00164-9.
- Dimbinaina Ralaivaosaona and Stephan Wagner. A central limit theorem for additive functionals of increasing trees. Combin. Probab. Comput., 28(4):618-637, 2019. URL: https://doi.org/10.1017/s0963548318000585.
- Dimbinaina Ralaivaosaona, Matas Šileikis, and Stephan Wagner. A central limit theorem for almost local additive tree functionals. Algorithmica, 82(3):642-679, 2020. URL: https://doi.org/10.1007/s00453-019-00622-4.
- Stephan Wagner. Central limit theorems for additive tree parameters with small toll functions. Combinatorics, Probability and Computing, 24(1):329-353, 2015. URL: https://doi.org/10.1017/S0963548314000443.
- Le Yu. Automorphisms of random trees. PhD thesis, Drexel University, 2012. URL: https://researchdiscovery.drexel.edu/esploro/outputs/doctoral/Automorphisms-of-random-trees/991014632289304721.