On the deepest cycle of a random mapping

DOI10.1016/J.JCTA.2024.105875MaRDI QIDQ6543047zbMATH OpenFDO

Authors Ljuben Mutafchiev, Steven R. Finch

Publication date 24 May 2024

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTA.2024.105875

zbMATH Keywords

deepest cyclelargest componentlimit distributionlongest cyclerandom functional graph

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05)

Review text

This paper provides asymptotic distributional results on the structure of a random mapping from a set of size \(n\) to itself. As any such mapping gives rise to a directed graph where every component has at most one cycle, a random mapping gives rise to a random directed graph that has this property. The main theorem of the paper provides the asymptotic distribution of the length of the cycle that is inside the largest component of the associated random digraph. It states that this random variable scaled by \(n^{1/2}\) converges in distribution as \(n\to \infty\) to a certain random variable that is given explicitly. Also, the asymptotic values of the expected value and the variance are given.

Recommendations

• Random mappings with a given number of cyclical points.
• The asymptotic distribution of the diameter of a random mapping
• scientific article; zbMATH DE number 17682
• scientific article; zbMATH DE number 4081611
• Random mappings with Ewens cycle structure.

Cites work

• A monte carlo method for factorization
• A Problem of the Allocation of Particles in Cells and Random Mappings
• Cycle Length in a Random Function
• Factorization of the Eighth Fermat Number
• Functional graphs of polynomials over finite fields
• scientific article; zbMATH DE number 4014826 (Why is no real title available?)
• scientific article; zbMATH DE number 3151315 (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 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• Limit Measures Arising in the Asympyotic Theory of Symmetric Groups. I.
• Logarithmic combinatorial structures: A probabilistic approach
• Probabilistic Methods in Combinatorial Analysis
• Probability of Indecomposability of a Random Mapping Function
• The Asymptotic Distribution of Maximum Tree Size in a Random Forest
• The stationary distribution of the infinitely-many neutral alleles diffusion model

This page was built for publication: On the deepest cycle of a random mapping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6543047)