The Permuton Tree
In this talk, I will present a recent work studying the properties of the permuton tree, corresponding to the binary search tree drawn from a permuton sample, that is a random set of two-dimensional points. This project builds off recent personal works studying the height of binary search trees drawn from diverse models of random permutations. In particular, by studying the case of permuton trees, we aim to obtain general results applicable to large classes of permutations. In the work presented here, we prove two main results. The first one is that, under some regularity assumptions on the two-dimensional measure, the height of a permuton tree is asymptotically of order $c^*\log n$, independently of the distribution. This generalizes results on the height of binary search trees drawn from a uniform permutation and leads us to believe that stronger conjectures on the height of binary search trees hold, even for larger classes of permutations. The second result is a local limit of such permuton trees, in the sense of the recently introduced subtree-size topology. In particular, we prove that, under some mild assumptions on the two-dimensional measure, the local limit only depends on the behaviour of the left part of the distribution. The two results combined, along with the methods developed within this work, provide us with interesting insights on the structure of binary search trees drawn from a large class of permutations.
Area: CS52 - Trees and combinatorial probability (Michele Aleandri)
Keywords: probability, tree, permutation
Please Login in order to download this file