Random minimal coverings of sets

V. N. Sachkov

Diskretnaya Matematika, Tome 4 (1992) no. 3, pp. 64-74.

Résumé

A number of new results on the asymptotic behaviour of the number of coverings of $n$-sets as $n\to\infty$ is obtained. In particular, it is proved that the number of blocks in a random covering of an $n$-set is asymptotically normal with parameters $(2^{n-1}- 1/2,2^{n/2-1})$. Asymptotic formulae for the number of minimal coverings of an $n$-set are given; these formulae have different structures depending on the parity of $n$. It is proved that as $n\to\infty$ the number of blocks in a random minimal covering has a non-standard discrete distribution with mean $n/2$ and finite variance. The structure of this distribution depends on what values, odd or even, are taken by $n$ as $n\to\infty$. The number of elements covered exactly one time has the same limit distribution. An algorithm determining a correspondence between certain classes of partitions of $n$-sets and minimal coverings is given.