Premium
The largest connected component in a random mapping
Author(s) -
Jaworski Jerzy,
Mutafchiev Ljuben
Publication year - 1994
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/rsa.3240050109
Subject(s) - digraph , combinatorics , component (thermodynamics) , mathematics , random graph , connected component , set (abstract data type) , image (mathematics) , discrete mathematics , physics , computer science , graph , artificial intelligence , quantum mechanics , programming language
A random mapping ( T; q ) of a finite set V = {1, 2,…, n } into itself assigns independently to each i ϵ V its unique image j = TT ( i ) E V with probability q for i = j and with probability \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{1 - q}}{{n - 1}} $\end{document} for j ≠ i . The purpose of the article is to determine the asymptotic behaviour of the size of the largest connected component of the random digraph G T (q) representing thes mapping as n – x , regarding all possible values of the parameter q = q(n) . © 1994 John Wiley & Sons, Inc.