Large components of bipartite random mappings

✍ Scribed by Jennie Hansen; Jerzy Jaworski

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 204 KB
• Volume: 17
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/1098-2418(200010/12)17:3/4<317::aid-rsa7>3.0.co;2-7

✦ Synopsis

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 .