Inversions in split trees and conditional Galton-Watson trees

Abstract: We study

I (T)

, the number of inversions in a tree

T

with its vertices labeled 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

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. As an application, we identify the limit of

X_{n}

for complete

b

-ary trees. For

T_{n}

being split trees, 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. By exploiting the connection between inversions and the total path length, we are able to give results that are stronger and much broader compared to previous work by Panholzer and Seitz.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Inversions in split trees and conditional Galton-Watson trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993537)