Highest Trees of Random Mappings
Mikhail V. Berlinkov · arXiv (Cornell University) · 2015
Let $g \in Σ_n$ be a random mapping, $c>0$, and $H$ be the $c$-crown of $g$ having $r$ roots. Then for any constant $α> 1$, $|H| > αr > 0$ with probability $1 - Θ(n^{-1/2})$. Furthermore, for any fixed constant $j \geq 1$, the height gap between the highest and second-highest $c$-branches is at least $j$ with probability $1 - Θ(n^{-1/2})$.