Skip to main content
eScholarship
Open Access Publications from the University of California

Local limit of the fixed point forest

  • Author(s): Johnson, T
  • Schilling, A
  • Slivken, E
  • et al.

Published Web Location

https://arxiv.org/pdf/1605.09777.pdf
No data is associated with this publication.
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Public License
Abstract

© 2017, University of Washington. All rights reserved. Consider the following partial “sorting algorithm” on permutations: take the first entry of the permutation in one-line notation and insert it into the position of its own value. Continue until the first entry is 1. This process imposes a forest structure on the set of all permutations of size n, where the roots are the permutations starting with 1 and the leaves are derangements. Viewing the process in the opposite direction towards the leaves, one picks a fixed point and moves it to the beginning. Despite its simplicity, this “fixed point forest” exhibits a rich structure. In this paper, we consider the fixed point forest in the limit n → ∞ and show using Stein’s method that at a random permutation the local structure weakly converges to a tree defined in terms of independent Poisson point processes. We also show that the distribution of the length of the longest path from a random permutation to a leaf converges to the geometric distribution with mean e − 1, and the length of the shortest path converges to the Poisson distribution with mean 1. In addition, the higher moments are bounded and hence the expectations converge as well.

Item not freely available? Link broken?
Report a problem accessing this item