## Abstract

In this paper we consider a random mapping, $\hat{T}_{n,\theta}$, of the

finite set $\{1,2,...,n\}$ into itself for which the digraph

representation $\hat{G}_{n,\theta}$ is constructed by: (1) selecting a random

number, $\hat{L}_n$, of cyclic vertices, (2) constructing a uniform

random forest of size $n$ with the selected cyclic vertices as

roots, and (3) forming `cycles' of trees by applying to the selected cyclic vertices a random

permutation with cycle structure given by the Ewens sampling formula with parameter $\theta$. We investi\-gate

$\hat{k}_{n,\theta}$, the size of a `typical' component of $\hat{G}_{n,\theta}$, and we obtain the asymptotic distribution of

$\hat{k}_{n,\theta}$ conditioned on $\hat{L}_{n}=m(n)$. As an application of

our results, we show in Section 3 that provided $\hat{L}_{n}$ is of

order much larger than $\sqrt{n}$, then the joint distribution of

the normalized order statistics of the component sizes of

$\hat{G}_{n,\theta}$ converges to the Poisson-Dirichlet($\theta$) distribution as

$n\to\infty$.

finite set $\{1,2,...,n\}$ into itself for which the digraph

representation $\hat{G}_{n,\theta}$ is constructed by: (1) selecting a random

number, $\hat{L}_n$, of cyclic vertices, (2) constructing a uniform

random forest of size $n$ with the selected cyclic vertices as

roots, and (3) forming `cycles' of trees by applying to the selected cyclic vertices a random

permutation with cycle structure given by the Ewens sampling formula with parameter $\theta$. We investi\-gate

$\hat{k}_{n,\theta}$, the size of a `typical' component of $\hat{G}_{n,\theta}$, and we obtain the asymptotic distribution of

$\hat{k}_{n,\theta}$ conditioned on $\hat{L}_{n}=m(n)$. As an application of

our results, we show in Section 3 that provided $\hat{L}_{n}$ is of

order much larger than $\sqrt{n}$, then the joint distribution of

the normalized order statistics of the component sizes of

$\hat{G}_{n,\theta}$ converges to the Poisson-Dirichlet($\theta$) distribution as

$n\to\infty$.

Original language | English |
---|---|

Pages (from-to) | 307 |

Number of pages | 322 |

Journal | Ars Combinatoria |

Volume | 112 |

Publication status | Published - 2013 |