On the maximal multiplicity of block sizes in a random set partition

Abstract: We study the asymptotic behavior of the maximal multiplicity

M_{n} = M_{n} (s i g m a)

of the blocks in a set partition of

[n] = 1, 2, ..., n

, assuming that

s i g m a

is chosen uniformly at random from the set of all such partitions. Let

W = W (n)

be the unique positive root of the equation

W e^{W} = n

and let

f_{n}

be the fractional part of

W (n)

. Furthermore, let

R_{n} = W^{l f l o o r W f l o o r} / l f l o o r W f l o o r!

and let

v a r t h e t a_{n} = m i n f_{n}, 1 - f_{n}

. We show that, over a subsequence

{n_{k}}_{k g e 1}

,

(M_{n_{k}} - R_{n_{k}}) / s q r t R_{n_{k}}

converges weakly, as

k o i n f t y

, to

m a x Z_{1}, Z_{2} - u

, where

Z_{1}

and

Z_{2}

are two independent copies of a standard normal random variable and either

u = l e f t (f r a c 1 2 p i i g h t)^{1 / 4} l i m_{k o i n f t y} v a r t h e t a_{n_{k}} f r a c s q r t n_{k} l o g^{7 / 4} n_{k} i n [0, i n f t y)

or

u = i n f t y

. The proof uses the saddle point method. A comparison with the similar statistic for random integer partitions of

n

is also given.

Recommendations

Cited In (10)

This page was built for publication: On the maximal multiplicity of block sizes in a random set partition