Structural transition in random mappings

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

In this paper we characterise the structural transition in random mappings with in-degree restrictions. Specifically, for integers 0 ≤ r≤ n, we consider a random mapping model T̂r n from [n]={1,2,...,n} into [n] such that Ĝr n, the directed graph on n labelled vertices which represents the mapping T̂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̂r n is a uniform random permutation and when r<n, we can view T̂r n as a 'corrupted' permutation. We investigate structural transition in Ĝr n 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 Ĝ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→∞. We show that the number of cyclic vertices in Ĝr n is and the number of components is where a=n-r. In contrast, provided only that a=n-r→∞, we show that the asymptotic distribution of the order statistics of the normalised component sizes of Ĝr n is always the Poisson-Dirichlet(1/2) distribution as in the case of uniform random mappings with no in-degree restrictions.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume21
Issue number1
Publication statusPublished - 24 Jan 2014

Keywords

  • Anti-preferential attachment
  • Component structure
  • Exchangeable in-degrees
  • Restricted random mappings
  • Urn schemes

ASJC Scopus subject areas

  • Geometry and Topology
  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Structural transition in random mappings'. Together they form a unique fingerprint.

  • Cite this