Large components of bipartite random mappings

Jennie Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

Abstract

A bipartite random mapping TK,L of a finite set V = V1 ? V2, |V1/, = K and /V2/ = L, into itself assigns independently to each i ? V1 its unique image j ? V2 with probability 1/L and to each i ? V2 its unique image j ? V1 with probability 1/K. We study the connected component structure of a random digraph G(TK, L), representing TK, L,, as K ? 8 and L ? 8. We show that, no matter how K and L tend to infinity relative to each other, the joint distribution of the normalized order statistics for the component sizes converges in distribution to the Poisson-Dirichlet distribution on the simplex ? = {{xi}: S xi = 1, xi = xi+1 = 0 for every i = 1}. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17, 317-342, 2000.

Original languageEnglish
Pages (from-to)317-342
Number of pages26
JournalRandom Structures and Algorithms
Volume17
Issue number3-4
Publication statusPublished - Oct 2000

Fingerprint

Random Mapping
Poisson-Dirichlet Distribution
Order Statistics
Connected Components
Joint Distribution
Digraph
Assign
Finite Set
Infinity
Tend
Converge

Cite this

Hansen, Jennie ; Jaworski, Jerzy. / Large components of bipartite random mappings. In: Random Structures and Algorithms. 2000 ; Vol. 17, No. 3-4. pp. 317-342.
@article{524707735bde4c3aa35b88fcc8f0cb3a,
title = "Large components of bipartite random mappings",
abstract = "A bipartite random mapping TK,L of a finite set V = V1 ? V2, |V1/, = K and /V2/ = L, into itself assigns independently to each i ? V1 its unique image j ? V2 with probability 1/L and to each i ? V2 its unique image j ? V1 with probability 1/K. We study the connected component structure of a random digraph G(TK, L), representing TK, L,, as K ? 8 and L ? 8. We show that, no matter how K and L tend to infinity relative to each other, the joint distribution of the normalized order statistics for the component sizes converges in distribution to the Poisson-Dirichlet distribution on the simplex ? = {{xi}: S xi = 1, xi = xi+1 = 0 for every i = 1}. {\circledC} 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17, 317-342, 2000.",
author = "Jennie Hansen and Jerzy Jaworski",
year = "2000",
month = "10",
language = "English",
volume = "17",
pages = "317--342",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "3-4",

}

Large components of bipartite random mappings. / Hansen, Jennie; Jaworski, Jerzy.

In: Random Structures and Algorithms, Vol. 17, No. 3-4, 10.2000, p. 317-342.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Large components of bipartite random mappings

AU - Hansen, Jennie

AU - Jaworski, Jerzy

PY - 2000/10

Y1 - 2000/10

N2 - A bipartite random mapping TK,L of a finite set V = V1 ? V2, |V1/, = K and /V2/ = L, into itself assigns independently to each i ? V1 its unique image j ? V2 with probability 1/L and to each i ? V2 its unique image j ? V1 with probability 1/K. We study the connected component structure of a random digraph G(TK, L), representing TK, L,, as K ? 8 and L ? 8. We show that, no matter how K and L tend to infinity relative to each other, the joint distribution of the normalized order statistics for the component sizes converges in distribution to the Poisson-Dirichlet distribution on the simplex ? = {{xi}: S xi = 1, xi = xi+1 = 0 for every i = 1}. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17, 317-342, 2000.

AB - A bipartite random mapping TK,L of a finite set V = V1 ? V2, |V1/, = K and /V2/ = L, into itself assigns independently to each i ? V1 its unique image j ? V2 with probability 1/L and to each i ? V2 its unique image j ? V1 with probability 1/K. We study the connected component structure of a random digraph G(TK, L), representing TK, L,, as K ? 8 and L ? 8. We show that, no matter how K and L tend to infinity relative to each other, the joint distribution of the normalized order statistics for the component sizes converges in distribution to the Poisson-Dirichlet distribution on the simplex ? = {{xi}: S xi = 1, xi = xi+1 = 0 for every i = 1}. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17, 317-342, 2000.

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

M3 - Article

VL - 17

SP - 317

EP - 342

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3-4

ER -