On the maximal multiplicity of block sizes in a random set partition. Issue 3 (9th October 2019)

• Record Type: Journal Article
• Authors: Mutafchiev, Ljuben R.; Savov, Mladen
• Is Part Of: Random structures & algorithms. Volume 56:Issue 3(2020)
• Page Start: 867
• Page End: 891
• Publication Date: 2019-10-09
• Subjects: block size -- limiting distribution -- maximum multiplicity -- saddle point method -- set partition; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20891
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We study the asymptotic behavior of the maximal multiplicity M n = M n ( σ ) of the block sizes in a set partition σ of [ n ] = {1, 2, …, n }, assuming that σ is chosen uniformly at random from the set of all such partitions. It is known that, for large n, the blocks of a random set partition are typically of size W = W ( n ), with We W = n . We show that, over subsequences { n k } k ≥ 1 of the sequence of the natural numbers, M n k, appropriately normalized, converges weakly, as k → ∞, to max { Z 1, Z 2 − u }, where Z 1 and Z 2 are independent copies of a standard normal random variable. The subsequences { n k } k ≥ 1, where the weak convergence is observed, and the quantity u depend on the fractional part f n of the function W ( n ). In particular, we establish that lim k → ∞ 1 / ( 2 π ) 1 / 4 min { f n k, 1 − f n k } n k / log 7 / 4 n k = u ∈ [ 0, ∞ ) ∪ { ∞ } . The behavior of the largest multiplicity M n is in a striking contrast to the similar statistic of integer partitions of n . A heuristic explanation of this phenomenon is also given.