Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2301.13829 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913242316537856 |
|---|---|
| author | Mutafchiev, Ljuben Finch, Steven |
| author_facet | Mutafchiev, Ljuben Finch, Steven |
| contents | 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 $ν_n=ν_n(T)$ denote the length of this cycle. In this paper, we establish the convergence in distribution of $ν_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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_13829 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Deepest Cycle of a Random Mapping Mutafchiev, Ljuben Finch, Steven Combinatorics Probability 60C05, 05C80 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 $ν_n=ν_n(T)$ denote the length of this cycle. In this paper, we establish the convergence in distribution of $ν_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$. |
| title | On the Deepest Cycle of a Random Mapping |
| topic | Combinatorics Probability 60C05, 05C80 |
| url | https://arxiv.org/abs/2301.13829 |