Structural transition in random mappings

作者：Hansen Jennie C^*; Jaworski Jerzy

来源：ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21(1): P1.18.

DOI：10.37236/3572

• restricted random mappings
• exchangeable in-degrees
• anti-preferential attachment
• urn schemes
• component structure

In this paper we characterise the structural transition in random mappings with in-degree restrictions. Specifically, for integers 0 %26lt;= r %26lt;= n, we consider a random mapping model (T) over cap (r)(n) from [n] = {1, 2, ..., n} into [n] such that (G) over cap (r)(n), the directed graph on n labelled vertices which represents the mapping (T) over cap (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) over cap (r)(n) is a uniform random permutation and when r %26lt; n, we can view %26lt;(T)over cap%26gt;(r)(n) as a %26apos;corrupted%26apos; permutation. We investigate structural transition in (G) over cap (r)(n) as we vary the integer parameter 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 (G) over cap (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 -%26gt; infinity. We show that the number of cyclic vertices in (G) over cap (r)(n) is Theta(n/root a) and the number of components is Theta(log(n/root a)) where a = n - r. In contrast, provided only that a = n - r -%26gt; infinity, we show that the asymptotic distribution of the order statistics of the normalised component sizes of (G) over cap (r)(n) is always the Poisson-Dirichlet(1/2) distribution as in the case of uniform random mappings with no in-degree restriction.

• 出版日期2014-1-24