A cutting process for random mappings

In this paper we consider a cutting process for random mappings. Specifically, for 0 < m < n , we consider the initial (uniform) random mapping digraph G n on n labeled vertices, and we delete (if possible), uniformly and at random, m noncyclic directed edges from G n . The maximal random digraph consisting of the unicyclic components obtained after cutting the m edges is called the trimmed random mapping and is denoted by G   n m . If the number of noncyclic directed edges is less than m , then G   n mconsists of the cycles, including loops, of the initial mapping G n . We consider the component structure of the trimmed mapping G   n m . In particular, using the exact distribution we determine the asymptotic distribution of the size of a typical random connected component of G   n mas n , m → ∞ . This asymptotic distribution depends on the relationship between n and m and we show that there are three distinct cases: (i) $m=o(\sqrt{n})$ , (ii) $m=\beta\sqrt{n}$ , where β > 0 is a fixed parameter, and (iii) $\sqrt{n}=o(m)$ . This allows us to study the joint distribution of the order statistics of the normalized component sizes of G   n m . When $m=o(\sqrt{n})$ , we obtain the Poisson–Dirichlet (1/2) distribution in the limit, whereas when $\sqrt{n}=o(m)$ the limiting distribution is Poisson–Dirichlet(1). Convergence to the Poisson–Dirichlet( θ ) distribution breaks down when $m=O(\sqrt{n})$ , and in particular, there is no smooth transition from the ${\cal P}$ D (1/2) distribution to the ${\cal P}$ D (1) via the Poisson–Dirichlet distribution as the number of edges cut increases relative to n , the number of vertices in G n . © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 30, 287–306, 2007