On the Deepest Cycle of a Random Mapping

• Published in: arXiv.org 2024-02
• Main Authors: Mutafchiev, Ljuben, Finch, Steven
• Format: Article
• Language: English
• Subjects: Apexes; Mapping
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2301.13829

Let \(\mathcal{T}_n\) be the set of all mappings \(T:\{1,2,\ldots,n\}\to\{1,2,\ldots,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 \(\nu_n=\nu_n(T)\) denote the length of this cycle. In this paper, we establish the convergence in distribution of \(\nu_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\).