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 |