Premium
Large components of bipartite random mappings
Author(s) -
Hansen Jennie,
Jaworski Jerzy
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200010/12)17:3/4<317::aid-rsa7>3.0.co;2-7
Subject(s) - mathematics , combinatorics , simplex , bipartite graph , dirichlet distribution , joint probability distribution , poisson distribution , distribution (mathematics) , discrete mathematics , statistics , mathematical analysis , graph , boundary value problem
A bipartite random mapping T K , L of a finite set V = V 1 ∪ V 2 , | V 1 |= K and | V 2 |= L , into itself assigns independently to each i ∈ V 1 its unique image j ∈ V 2 with probability 1/ L and to each i ∈ V 2 its unique image j ∈ V 1 with probability 1/ K . We study the connected component structure of a random digraph G ( T K , L ), representing T K , L , as K →∞ and L →∞. 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 }: ∑ 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