Inversions in split trees and conditional Galton-Watson trees

Fiona Skerman, Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson

Research output: Contribution to journalArticle (Academic Journal)peer-review

Abstract

We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider Xn, the normalized version of I(Tn), for a sequence of trees Tn. For fixed Tn's, we prove a sufficient condition for Xn to converge in distribution. As an application, we identify the limit of Xn for complete b-ary trees. For Tn being split trees, we show that Xn converges to the unique solution of a distributional equation. Finally, when Tn's are conditional Galton–Watson trees, we show that Xn converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].
Original languageEnglish
Pages (from-to)335-364
JournalCombinatorics, Probability and Computing
Early online date31 Oct 2018
DOIs
Publication statusPublished - 2019

Bibliographical note

Proxy date of acceptance added to output record.

Fingerprint Dive into the research topics of 'Inversions in split trees and conditional Galton-Watson trees'. Together they form a unique fingerprint.

Cite this