Large components of bipartite random mappings

Jennie Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

5 Citations (Scopus)

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 Dive into the research topics of 'Large components of bipartite random mappings'. Together they form a unique fingerprint.

  • Cite this