Highest Trees of Random Mappings

Abstract

We study the heights of the trees of a random mapping of $n$ elements. Using singularity analysis of exact generating functions, we prove that the mapping has a unique highest tree with probability $1-\sqrt{\frac{\pi }{8}}{n}^{-1/2}+o(n^{-1/2})$. The property of having a unique highest tree plays a crucial role in the solution of the Road Coloring Problem [Trahtman, 2009]. More generally, we consider $c$-branches, the subtrees rooted at distance $c$ from the cycles. For all fixed $c\ge 0$ and $j\ge 1$ we show that the highest $c$-branch exceeds every other $c$-branch in height by at least $j$, except with probability asymptotic to $(2j-1)\sqrt{\frac{\pi }{8}}{n}^{-1/2}$. We also show that, for any fixed $\alpha >1$, with probability $1-\Theta (n^{-1/2})$ the part of the highest $c$-branch that lies above the second highest one (its crown) has more than $\alpha$ times as many vertices as roots. The last result is used in the author's proof that a random $2$-letter automaton with $n$ states is synchronizing with probability $1-\Theta (1/n)$.

References in corpus (1)

• On the probability of being synchronizable

Cited by in corpus (1)

• Implementation of the algorithm for testing an automaton for synchronization in linear expected time