PC Seminar: Wiener Index and Convergence Rates for Split Trees

Abstract: The Wiener index of a graph is the sum over the graph distance of all pairs. For a tree, it can be described using the framework of additive functionals.

Once sufficiently good error bounds are known for additive functionals are known, these can be used to show limits of the Wiener index and the path length.

We study the Wiener index on split trees, a random model covering many random trees of logarithmic height, such as $m$-ary search trees, tries and increasing trees, and show its limit distribution.

This is a seminar in our seminar series on Probability and Combinatorics (PC).