On the Deepest Cycle of a Random Mapping

Abstract

Let ${\mathcal{T}}_n$ be the set of all mappings $T:\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$. The corresponding graph of $T$ is a union of disjoint connected unicyclic components. We assume that each $T\in {\mathcal{T}}_n$ is chosen uniformly at random (i.e., with probability $n^{-n}$). The cycle of $T$ contained within its largest component is callled the deepest one. For any $T\in {\mathcal{T}}_n$, let $\hat{I}{½}_n=\hat{I}{½}_n(T)$ denote the length of this cycle. In this paper, we establish the convergence in distribution of $\hat{I}{½}_n/\sqrt{n}$ and find the limits of its expectation and variance as $n\to \infty$. For $n$ large enough, we also show that nearly $55\%$ of all cyclic vertices of a random mapping $T\in {\mathcal{T}}_n$ lie in the deepest cycle and that a vertex from the longest cycle of $T$ does not belong to its largest component with approximate probability $0.075$.

14 pages