## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 287-306 |

Number of pages | 20 |

Journal | Random Structures and Algorithms |

Volume | 30 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - Jan 2007 |

## Keywords

- Component structure
- Poisson-Dirichlet distribution
- Random mappings