Random mappings with a given number of cyclical points

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

Abstract

In this paper we consider a random mapping, T^n, of the finite set {1, 2,..., n} into itself for which the digraph representation Gn is constructed by: (1) selecting a random number, 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 a random permutation to the selected cyclic vertices. We investigate k^n, the size of a 'typical' component of Gn, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of k^n conditioned on L^n = m(n). As an application of our results, we show in Section 3 that provided L^n is of order much larger than vn, then the joint distribution of the normalized order statistics of the component sizes of Gn converges to the Poisson-Dirichlet(1) distribution as n ? 8. Other applications and generalizations are also discussed in Section 3.

Original languageEnglish
Pages (from-to)341-359
Number of pages19
JournalArs Combinatoria
Volume94
Publication statusPublished - Jan 2010

Fingerprint

Random Mapping
Random Permutation
Random Forest
Random number
Order Statistics
Joint Distribution
Digraph
Asymptotic distribution
Dirichlet
Finite Set
Siméon Denis Poisson
Roots
Converge
Cycle

Cite this

Hansen, Jennie C. ; Jaworski, Jerzy. / Random mappings with a given number of cyclical points. In: Ars Combinatoria. 2010 ; Vol. 94. pp. 341-359.
@article{20f66301f60242b593c3b74888c4d16a,
title = "Random mappings with a given number of cyclical points",
abstract = "In this paper we consider a random mapping, T^n, of the finite set {1, 2,..., n} into itself for which the digraph representation Gn is constructed by: (1) selecting a random number, 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 a random permutation to the selected cyclic vertices. We investigate k^n, the size of a 'typical' component of Gn, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of k^n conditioned on L^n = m(n). As an application of our results, we show in Section 3 that provided L^n is of order much larger than vn, then the joint distribution of the normalized order statistics of the component sizes of Gn converges to the Poisson-Dirichlet(1) distribution as n ? 8. Other applications and generalizations are also discussed in Section 3.",
author = "Hansen, {Jennie C.} and Jerzy Jaworski",
note = "The research in this paper was supported by the Marie Curie Intra-European Fellowship No. 501863 (RANDIGRAPH) within the 6th European Community Framework Programme.",
year = "2010",
month = "1",
language = "English",
volume = "94",
pages = "341--359",
journal = "Ars Combinatoria",
issn = "0381-7032",
publisher = "Charles Babbage Research Centre",

}

Random mappings with a given number of cyclical points. / Hansen, Jennie C.; Jaworski, Jerzy.

In: Ars Combinatoria, Vol. 94, 01.2010, p. 341-359.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Random mappings with a given number of cyclical points

AU - Hansen, Jennie C.

AU - Jaworski, Jerzy

N1 - The research in this paper was supported by the Marie Curie Intra-European Fellowship No. 501863 (RANDIGRAPH) within the 6th European Community Framework Programme.

PY - 2010/1

Y1 - 2010/1

N2 - In this paper we consider a random mapping, T^n, of the finite set {1, 2,..., n} into itself for which the digraph representation Gn is constructed by: (1) selecting a random number, 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 a random permutation to the selected cyclic vertices. We investigate k^n, the size of a 'typical' component of Gn, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of k^n conditioned on L^n = m(n). As an application of our results, we show in Section 3 that provided L^n is of order much larger than vn, then the joint distribution of the normalized order statistics of the component sizes of Gn converges to the Poisson-Dirichlet(1) distribution as n ? 8. Other applications and generalizations are also discussed in Section 3.

AB - In this paper we consider a random mapping, T^n, of the finite set {1, 2,..., n} into itself for which the digraph representation Gn is constructed by: (1) selecting a random number, 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 a random permutation to the selected cyclic vertices. We investigate k^n, the size of a 'typical' component of Gn, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of k^n conditioned on L^n = m(n). As an application of our results, we show in Section 3 that provided L^n is of order much larger than vn, then the joint distribution of the normalized order statistics of the component sizes of Gn converges to the Poisson-Dirichlet(1) distribution as n ? 8. Other applications and generalizations are also discussed in Section 3.

UR - http://www.scopus.com/inward/record.url?scp=77949525176&partnerID=8YFLogxK

M3 - Article

VL - 94

SP - 341

EP - 359

JO - Ars Combinatoria

JF - Ars Combinatoria

SN - 0381-7032

ER -