Structural transition in random mappings

In this paper we characterise the structural transition in random mappings with in-degree restrictions. Specifically, for integers 0 ≤ r≤ n, we consider a random mapping model T̂^r _n from [n]={1,2,...,n} into [n] such that Ĝ^r _n, the directed graph on n labelled vertices which represents the mapping T̂^r _n, has r vertices that are constrained to have in-degree at most 1 and the remaining vertices have in-degree at most 2. When r=n, T̂^r _n is a uniform random permutation and when r<n, we can view T̂^r _n as a 'corrupted' permutation. We investigate structural transition in Ĝ^r _n as we vary the integer parameter r relative to the total number of vertices n. We obtain exact and asymptotic distributions for the number of cyclic vertices, the number of components, and the size of the typical component in Ĝ^r _n, and we characterise the dependence of the limiting distributions of these variables on the relationship between the parameters n and r as n→∞. We show that the number of cyclic vertices in Ĝ^r _n is and the number of components is where a=n-r. In contrast, provided only that a=n-r→∞, we show that the asymptotic distribution of the order statistics of the normalised component sizes of Ĝ^r _n is always the Poisson-Dirichlet(1/2) distribution as in the case of uniform random mappings with no in-degree restrictions.