Structural Transition in Random Mappings

Abstract

In this paper we characterise the  structural transition in random mappings with in-degree restrictions. Specifically, for integers $0~\!\!\leq~\!\!r\leq~\!\!n$, we  consider a random mapping model $\hat{T}_n^r$ from $[n]=\{1,2, \ldots , 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. When $r=n$, $\hat{T}_n^r$ is a uniform random permutation and when $r<n$, we can view $\hat{T}_n^r$ as a 'corrupted' permutation. We investigate structural transition in $\hat{G}_n^r$ 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 $\hat{G}_n^r$, and we characterise the dependence of the limiting distributions  of these variables on the relationship between the parameters $n$ and $r$ as $n\to\infty$. We show that the number of cyclic vertices in $\hat{G}_n^r$ is $\Theta({n\over\sqrt{a}})$ and the number of components is $\Theta(\log({n\over \sqrt{a}}))$ where $a=n-r$. In contrast, provided only that $a=n-r\to\infty$, we show that the asymptotic distribution of the order statistics of the normalised component sizes of $\hat{G}_n^r$ is always the  Poisson-Dirichlet(1/2) distribution as in the case of uniform random mappings with no in-degree restrictions.