2023/12/21 by Benoît Corsini, Corsini, Benoît
Computer Science · Mathematics · #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2312.13817
openalex publication_date 2023/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
This article studies the limit of binary search trees drawn from Mallows permutations under various topologies. The main result, pertaining to the standard local topology for graphs, requires the introduction of a generalization of binary search trees to two-sided infinite sequences, referred to as redwood trees. We then show that the almost-sure local limit of finite Mallows trees is the redwood tree drawn from the two-sided infinite Mallows permutation, thus corresponding to swapping the local limit and the binary search tree structure. Building off this result, we study various other natural topologies: the rooted topology of the local structure around the root, the Gromov-Hausdorff-Prokhorov topology of the tree seen as a metric space, and the subtree size topology of the ratio of nodes split between left and right subtrees. The limit of Mallows trees under these three topologies combined with the case of the local topology allow us to draw a global picture of what large Mallows trees look like from different perspective and further strengthen the relation between finite and infinite Mallows permutations.