4
$\begingroup$

Consider the case where we have a bag of 'N' unique marbles, and we randomly select all 'S' possible sets of size 'm' from the bag (with replacement) under the following constraints:

(1) - Any set of 'm' marbles must have all unique elements, i.e. there must be no duplicate copies of a marble in any given set.

(2) - The maximum intersection between any two sets, i.e. the number of unique marbles they have in common, can be of at most size 'k'.

Provided (1) & (2), what is 'S'? Equivalently, what is the number of possible sets of size 'm' obeying the aforementioned constraints?

1 Answers 1

2

You're looking for a family of subsets of $[n]$ of size $m$, the intersection of any two of which is at most $k$. If $k \geq m$ then we can take all subsets of size $m$. If $k < m$ then a well-known theorem of Ray-Chaudhuri and Wilson shows an upper bound of $\binom{n}{k}$. A trivial construction gives a lower bound of $\binom{n-(m-k)}{k}$. So for $k \leq m$ constant, the answer is $\Theta(n^k)$.

For the theorem mentioned above, see for example Babai and Frankl's book "Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science".

  • 0
    Thanks so much for your answer!2010-12-22