Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.13662 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909963365908480 |
|---|---|
| author | Mutafchiev, Ljuben Finch, Steven |
| author_facet | Mutafchiev, Ljuben Finch, Steven |
| contents | Let $\mathcal{T}_n$ be the set of all mappings $T:[n]\to[n]$, where $[n]=\{1,2,\ldots,n\}$. The corresponding graph $G_T$ of $T$, called a functional digraph, is a union of disjoint connected components. Each component is a directed cycle of rooted labeled trees. We assume that each $T\in\mathcal{T}_n$ is chosen uniformly at random from the set $\mathcal{T}_n$. The components and trees of $G_T$ are distinguished by their size. In this paper, we compute the limiting conditional probability ($n\to\infty$) that a vertex from the largest component of the random graph $G_T$, chosen uniformly at random from $[n]$, belongs to its $s$-th largest tree, where $s\ge 1$ is a fixed integer. This limit can be also viewed as an approximation of the probability that the $s$-th largest tree of $G_T$ is a subgraph of its largest component, which is a solution of a problem suggested by Mutafchiev and Finch (2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_13662 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Large Components and Trees of Random Mappings Mutafchiev, Ljuben Finch, Steven Combinatorics Probability 60C05, 05C80 Let $\mathcal{T}_n$ be the set of all mappings $T:[n]\to[n]$, where $[n]=\{1,2,\ldots,n\}$. The corresponding graph $G_T$ of $T$, called a functional digraph, is a union of disjoint connected components. Each component is a directed cycle of rooted labeled trees. We assume that each $T\in\mathcal{T}_n$ is chosen uniformly at random from the set $\mathcal{T}_n$. The components and trees of $G_T$ are distinguished by their size. In this paper, we compute the limiting conditional probability ($n\to\infty$) that a vertex from the largest component of the random graph $G_T$, chosen uniformly at random from $[n]$, belongs to its $s$-th largest tree, where $s\ge 1$ is a fixed integer. This limit can be also viewed as an approximation of the probability that the $s$-th largest tree of $G_T$ is a subgraph of its largest component, which is a solution of a problem suggested by Mutafchiev and Finch (2024). |
| title | Large Components and Trees of Random Mappings |
| topic | Combinatorics Probability 60C05, 05C80 |
| url | https://arxiv.org/abs/2512.13662 |