Large components of bipartite random mappings

Jennie Hansen; Jerzy Jaworski

Large components of bipartite random mappings

Research output: Contribution to journal › Article › peer-review

Abstract

A bipartite random mapping T_K,L of a finite set V = V₁ ? V₂, |V₁/, = K and /V₂/ = L, into itself assigns independently to each i ? V₁ its unique image j ? V₂ with probability 1/L and to each i ? V₂ its unique image j ? V₁ with probability 1/K. We study the connected component structure of a random digraph G(T_{K, L}), representing T_{K, 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 ? = {{x_i}: S x_i = 1, x_i = x_i+1 = 0 for every i = 1}. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17, 317-342, 2000.

Original language	English
Pages (from-to)	317-342
Number of pages	26
Journal	Random Structures and Algorithms
Volume	17
Issue number	3-4
Publication status	Published - Oct 2000

Cite this

@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}. {\textcopyright} 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17, 317-342, 2000.",

author = "Jennie Hansen and Jerzy Jaworski",

year = "2000",

month = oct,

language = "English",

volume = "17",

pages = "317--342",

journal = "Random Structures and Algorithms",

issn = "1098-2418",

publisher = "John Wiley and Sons Ltd",

number = "3-4",

}

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

SN - 1098-2418

VL - 17

SP - 317

EP - 342

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3-4

ER -

Large components of bipartite random mappings

Abstract

Other files and links

Fingerprint

Cite this