Local limit of the fixed point forest

DOI10.1214/17-EJP36MaRDI QIDQ513069zbMATH OpenFDO

Authors Tobias Johnson, Anne Schilling, Erik Slivken

Publication date 3 March 2017

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.09777, https://projecteuclid.org/euclid.ejp/1487127646

zbMATH Keywords

fixed pointspermutationsPoisson point processsorting algorithmStein's methodtreesweak convergence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Combinatorial probability (60C05) Limit theorems in probability theory (60F99) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: 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 $noinfty$ 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 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.

Recommendations

• Expected size of a tree in the fixed point forest
• Fixed points and cycle structure of random permutations
• Fixed points of 321-avoiding permutations
• The number of occurrences of patterns in a random tree or forest permutation
• A new generation tree for permutations, preserving the number of fixed points

Cited in

(2)

• And/or trees: A local limit point of view
• A decorated tree approach to random permutations in substitution-closed classes

This page was built for publication: Local limit of the fixed point forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513069)