Inversions in random node labeling of random trees

Add to your list(s) Download to your calendar using vCal

• Xing Shi Cai (Uppsala University)
• Thursday 27 July 2017, 15:00-16:00
• LTC Watson.

If you have a question about this talk, please contact Guillem Perarnau.

Inversions in labeled trees generalize inversions in permutations. We study the number of inversions in trees labeled uniformly at random. The three types of trees that we considered – complete b-ary trees, split trees and conditional Galton-Watson trees – cover a wide range of tree models. For all of these trees, we show that both the distribution and the moment generating function of inversion numbers (after normalization) converge to a limit. In particular, by revealing the connection between inversions and the total path length, our proof for Galton-Watson trees is much shorter and gives stronger result comparing to previous work by Panholzer and Seitz. Joint work with Cecilia Holmgren, Svante Janson, Tony Johansson and Fiona Skerman.

This talk is part of the Combinatorics and Probability Seminar series.

This talk is included in these lists:

• Combinatorics and Probability Seminar
• LTC Watson
• School of Mathematics Events

Note that ex-directory lists are not shown.