Random sets and intersections

David Handelman

Published 2016-08-27Version 1

The following class of problems arose out of vain attempts to show that the Pascal's triangle adic transformation has trivial spectrum. Partition a set of size $N$ into sets of size $S \equiv S(N)$ (ignoring leftovers). What is the likelihood that a set of size $K \equiv K(N)$ will intersect each set in the partition in at least $R \equiv R(N)$ members (as $N$ increases)? Via elementary techniques and under reasonable hypotheses, we obtain an easy-to-use formula. Although different from the corresponding minimum problem for balls and bins (with $m = K$ balls and $n = N/S$ bins), under modest constraints, the asymptotic probabilities are the same.