The largest connected component in a random mapping. (English) Zbl 0792.60008
Summary: A random mapping \((T;q)\) of a finite set \(V=\{1,2,\dots,n\}\) into itself assigns independently to each \(i \in V\) its unique image \(j=T(i) \in V\) with probability \(q\) for \(i=j\) and with probability \((1-q)/(n-1)\) for \(j \neq i\). The purpose of the article is to determine the asymptotic behavior of the size of the largest connected component of the random digraph \(G_ T(q)\) representing this mapping as \(n \to \infty\), regarding all possible values of the parameter \(q=q(n)\).
References:
| [1] | and , Probability, distributions related to local structure of a random mapping, in Random Graphs ’89, Wiley, New York, 1992. |
| [2] | Random Graphs, Academic, New York, 1985. |
| [3] | Erdös, Publ. Math. Inst. Hung. Acad. Sci. 5 pp 17– (1960) |
| [4] | An Introduction to Probability Theory and its Applications, Wiley, New York, 1957. |
| [5] | On some model of a random mapping, Teubner-Texte zur Mathematik. in Graph and Other Combinatorial Topics, Teubner Publisching House, 1983, pp. 134–137. |
| [6] | Random mappings, Ph.D. dissertation, Adam Mickiewicz University, Poznán, Poland, 1985 (in Polish). |
| [7] | Random mappings with independent choices of images, in Random Graphs ’87, Wiley, New Yorkl, 1990, pp. 89–101. |
| [8] | Katz, Ann. Math. Statist. 26 pp 512– (1955) |
| [9] | Random Mappings, Optimization Software, New York, 1986. |
| [10] | On some stochastic problems of discrete mathematics, in Mathematics and Education in Mathematics, Bulg. Akad. Nauk, Sofia, Bulgaria, 1984, pp. 57–80. |
| [11] | Pavlov, Theory Probab, Its. Appl. 22 pp 509– (1977) |
| [12] | An Introduction to Combinatorial Analysis, Wiley, New York, 1958. · Zbl 0078.00805 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
