Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.15
URN: urn:nbn:de:0030-drops-89085
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8908/
Cai, Xing Shi ; Holmgren, Cecilia ; Janson, Svante ; Johansson, Tony ; Skerman, Fiona
Inversions in Split Trees and Conditional Galton-Watson Trees
| pdf-format: |
|
Abstract
We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].
BibTeX - Entry
@InProceedings{cai_et_al:LIPIcs:2018:8908,
author = {Xing Shi Cai and Cecilia Holmgren and Svante Janson and Tony Johansson and Fiona Skerman},
title = {{Inversions in Split Trees and Conditional Galton-Watson Trees}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {15:1--15:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-078-1},
ISSN = {1868-8969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8908},
URN = {urn:nbn:de:0030-drops-89085},
doi = {10.4230/LIPIcs.AofA.2018.15},
annote = {Keywords: inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant}
}
| Keywords: | inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant | |
| Seminar: | 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 18.06.2018 |
