Structural transition in random mappings (Q405093)

The authors characterise the structural transition in random mappings with in-degree restrictions. Consider a random mapping model \(\hat{T}_n^r\) from \([n] = \{1, 2, \dots, n \}\) into \([n]\) such that \(\hat{G}_n^r\), the directed graph on \(n\) labelled vertices which represents the mapping \(\hat{T}_n^r\), has \(r\) vertices that are constrained to have in-degree at most \(1\) and the remaining vertices have in-degree at most \(2\). \(\hat{T}_n^n\) is a uniform random permutation and \(\hat{T}_n^r\) \((r < n)\) can be viewed as a `corrupted' permutation. They obtain exact and asymptotic distributions for the number of cyclic vertices, the number of components, and the size of the typical component in \(\hat{G}_n^r\) and characterise the dependence of the limiting distributions of these variables on the relationship between the parameters \(n\) and \(r\) as \(n \rightarrow \infty \). It is shown that the number of cyclic vertices in \(\hat{G}_n^r\) is \(\Theta(\frac{n}{\sqrt{n-r}})\) and the number of components is \(\Theta(\log(\frac{n}{\sqrt{n-r}})\). In contrast, provided only that \(n - r \rightarrow \infty\), the asymptotic distribution of the order statistics of the normalised component sizes of \(\hat{G}_n^r\) is always the Poisson-Dirichlet(\(\frac{1}{2}\)) distribution as in the case of uniform random mappings with no in-degree restrictions.