A new random mapping model

2006/03/22 by Hansen, Jennie C., Jaworski, Jerzy
#60C05 (Primary) 05C80 #60F05 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.math/0603529

Abstract

We introduce a new random mapping model, T_n ^D, which maps the set \1,2,...,n\ into itself.The random mapping T_n ^D is constructed using a collection of exchangeable random variables D₁, ....,D_n which satisfy ∑_i=1ⁿD_i=n. In the random digraph,G_n ^D, which represents the mapping T_n ^D, the in-degree sequence for the vertices is given by the variables D₁, D₂, ..., D_n, and, in some sense,G_n ^D can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components,and the size of a typical component can be expressed in terms of expectations of various functions of D₁, D₂, ..., D_n. We also consider two special examples of T_n ^D which correspond to random mappings with preferential and anti-preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above.

Related

• Random Graph Models and Matchings
• The Class of Random Graphs Arising from Exchangeable Random Measures
• De-Preferential Attachment Random Graphs
• Random Preferential Attachment Hypergraphs
• Random graphs with forbidden vertex degrees