2026-07-20T01:58:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8908 2024-03-06T10:43:43Z ddc:004 open_access

Inversions in Split Trees and Conditional Galton-Watson Trees Cai, Xing Shi Holmgren, Cecilia Janson, Svante Johansson, Tony Skerman, Fiona inversions random trees split trees Galton-Watson trees permutation cumulant 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xing Shi Cai and Cecilia Holmgren and Svante Janson and Tony Johansson and Fiona Skerman 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.15 urn:nbn:de:0030-drops-89085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode