Structural transition in random mappings
The authors characterise the structural transition in random mappings with in-degree restrictions. Consider a random mapping model \(\hat{T}_n^r\) from \([n] = \{1, 2, \dots, n \}\) into \([n]\) such that \(\hat{G}_n^r\), the directed graph on \(n\) labelled vertices which represents the mapping \(\hat{T}_n^r\), has \(r\) vertices that are constrained to have in-degree at most \(1\) and the remaining vertices have in-degree at most \(2\). \(\hat{T}_n^n\) is a uniform random permutation and \(\hat{T}_n^r\) \((r < n)\) can be viewed as a `corrupted' permutation. They obtain exact and asymptotic distributions for the number of cyclic vertices, the number of components, and the size of the typical component in \(\hat{G}_n^r\) and characterise the dependence of the limiting distributions of these variables on the relationship between the parameters \(n\) and \(r\) as \(n \rightarrow \infty \). It is shown that the number of cyclic vertices in \(\hat{G}_n^r\) is \(\Theta(\frac{n}{\sqrt{n-r}})\) and the number of components is \(\Theta(\log(\frac{n}{\sqrt{n-r}})\). In contrast, provided only that \(n - r \rightarrow \infty\), the asymptotic distribution of the order statistics of the normalised component sizes of \(\hat{G}_n^r\) is always the Poisson-Dirichlet(\(\frac{1}{2}\)) distribution as in the case of uniform random mappings with no in-degree restrictions.
- A critical point for random graphs with a given degree sequence
- A cutting process for random mappings
- A functional central limit theorem for random mappings
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Brownian bridge asymptotics for random \(p\)-mappings
- Epidemic process on a random graph: some preliminary results
- How random is the characteristic polynomial of a random matrix ?
- scientific article; zbMATH DE number 4209190 (Why is no real title available?)
- scientific article; zbMATH DE number 3896009 (Why is no real title available?)
- scientific article; zbMATH DE number 3978019 (Why is no real title available?)
- scientific article; zbMATH DE number 16479 (Why is no real title available?)
- scientific article; zbMATH DE number 17682 (Why is no real title available?)
- scientific article; zbMATH DE number 3380631 (Why is no real title available?)
- Limit Measures Arising in the Asympyotic Theory of Symmetric Groups. I.
- Logarithmic combinatorial structures: A probabilistic approach
- On distributions related to transitive closures of random finite mappings
- On random mappings with a single attracting centre
- On the Asymptotic Distribution of Large Prime Factors
- Order statistics for decomposable combinatorial structures
- Random mappings with a given number of cyclical points.
- Random Mappings with a Single Attracting Center
- Random mappings with an attracting center: Lagrangian distributions and a regression function
- Random mappings with constraints on coalescence and number of origins
- Random mappings with exchangeable in-degrees
- Random permutations and Brownian motion
- Univariate Discrete Distributions
- Limit theorems for the logarithm of the order of a random \(A\)-mapping
- The component counts of random functions
- Predecessors and successors in random mappings with exchangeable in-degrees
- Random mappings with Ewens cycle structure.
- Random mappings with a given number of cyclical points.
- Structure vs. randomness for bilinear maps
- Random maps with sociological flavor
This page was built for publication: Structural transition in random mappings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405093)
