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^m consists 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^m as n, m ? 8. This asymptotic distribution depends on the relationship between n and m and we show that there are three distinct cases: (i) m = o(vn), (ii) m = ß vn, where ß > 0 is a fixed parameter, and (iii) vn = 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(vn), we obtain the Poisson-Dirichlet(1/2) distribution in the limit, whereas when vn = o(m) the limiting distribution is Poisson-Dirichlet(1). Convergence to the Poisson-Dirichlet(?) distribution breaks down when m = O(vn), and in particular, there is no smooth transition from the PD(1/2) distribution to the PD(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.