Contar todos los conjuntos de tamaño 'm' posibles de 'N' canicas bajo las restricciones de intersección y pertenencia

Question

Consideremos el caso en el que tenemos una bolsa de "N" canicas únicas, y seleccionamos al azar todos los "S" conjuntos posibles de tamaño "m" de la bolsa (con reemplazo) bajo las siguientes restricciones:

(1) - Cualquier conjunto de 'm' canicas debe tener todos los elementos únicos, es decir, no debe haber copias duplicadas de una canica en cualquier conjunto dado.

(2) - La máxima intersección entre dos conjuntos cualesquiera, es decir, el número de canicas únicas que tienen en común, puede ser de como máximo tamaño "k".

Teniendo en cuenta (1) y (2), ¿qué es "S"? De forma equivalente, ¿cuál es el número de conjuntos posibles de tamaño "m" que cumplen las restricciones mencionadas?

Answer 1

Se busca una familia de subconjuntos de $[n]$ de tamaño $m$ cuya intersección de dos cualesquiera es como máximo $k$ . Si $k \geq m$ entonces podemos tomar todos los subconjuntos de tamaño $m$ . Si $k < m$ entonces un conocido teorema de Ray-Chaudhuri y Wilson muestra un límite superior de $\binom{n}{k}$ . Una construcción trivial da un límite inferior de $\binom{n-(m-k)}{k}$ . Así que para $k \leq m$ constante, la respuesta es $\Theta(n^k)$ .

Para el teorema mencionado, véase por ejemplo el libro de Babai y Frankl "Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science".