Highest Trees of Random Mappings

We prove the exact asymptotic $1-\left({\frac{2π}{3}-\frac{827}{288π}}+o(1)\right)/{\sqrt{n}}$ for the probability that the underlying graph of a random mapping of $n$ elements possesses a unique highest tree. The property of having a unique highest tree turned out to be crucial in the solution of the famous Road Coloring Problem as well as the generalization of this property in the proof of the author's result about the probability of being synchronizable for a random automaton.

No reviews yet.

No comments yet.