Structural transition in random mappings

Jennie C. Hansen¹ ; Jerzy Jaworski²

¹Heriot-Watt University
²Adam Mickiewicz University

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

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.

Détail

DOI : 10.37236/3572

Classification : 60C05, 05C05, 05C80, 60G09
Mots-clés : restricted random mappings, exchangeable in-degrees, anti-preferential attachment, urn schemes, component structure