Subconjuntos de un conjunto con elementos comunes entre sí

Question

Dejemos que $S=\{1,2,\ldots,n\}$ . Sea $A_i\subset S$ para $i\in\{1,2,\ldots,m\}$ . Imponga las siguientes condiciones

• $|A_i|=r$ con $r<n$ para todos $i$ .
• $|A_i\cap A_j|=t$ para todos $i\neq j$ con $t<r$ .

Dejemos que $n,r,t$ se arreglen. ¿Cuál es el número máximo $m$ de subconjuntos $A_i$ que cumplan estas condiciones?

La pregunta surge de mi observación de un juego llamado Rafly, en el que hay 55 cartas, cada una con 8 imágenes. No importa qué 2 cartas elijas, tienen una y sólo una imagen común. Quiero generalizar este juego utilizando el número mínimo de $n$ imágenes, teniendo $m$ tarjetas, cada una con $r$ imágenes y $t$ imágenes comunes. Sin embargo, tengo problemas para encontrar $m$ dado $n,r$ y $t$ .

En el caso de $t=1$ Empiezo a construir las tarjetas así:

$$A_1 = \{1,2,\ldots,r\}.$$ Una nueva tarjeta debe tener un elemento común con la primera tarjeta: $$A_2 = \{c_{1,2}, r+1,\ldots, 2r-1 \},$$ donde $c_{1,2}\in A_1$ . Una nueva tarjeta debe tener un elemento común con la segunda y la primera tarjeta: $$A_3 = \{c_{1,3},c_{2,3}, 2r,2r+1,\ldots, 3r-3\},$$ donde $c_{1,3}\in A_1$ y $c_{2,3}\in A_2\setminus A_1$ . Siguiendo este razonamiento concluyo que hay $n=r(r+1)/2$ diferentes imágenes. Pero, ¿cuántas tarjetas hay? ¿Cómo se relacionan estas cantidades con $t$ ? Muchas gracias.

Answer 1

Su problema en el $t=1$ caso se preguntó aquí . Voy a proporcionar una generalización de esas ideas a su problema.

Hay $\binom{n}{t+1}$ subconjuntos de $S$ con tamaño $t+1$ . Cada conjunto $A_i$ tiene $\binom{r}{t+1}$ subconjuntos de tamaño $t+1$ . Además, el $\binom{r}{t+1}$ subconjuntos de tamaño $t+1$ para $A_i$ deben ser diferentes a los de $A_j$ porque $A_i$ y $A_j$ sólo tienen $t$ elementos en común. Por lo tanto, contando el número total de subconjuntos de tamaño $t+1$ que se encuentra en algún conjunto $A_i$ obtenemos $$m\cdot\binom{r}{t+1}\le \binom{n}{t+1}$$ Esto le da un límite superior a $m$ .

Si se alcanza la igualdad, esto significaría que cada subconjunto de tamaño $t+1$ está contenida exactamente en un conjunto $A_i$ . . Esto significa que tiene un Sistema Steiner $S(t+1,r,n)$ . No se sabe mucho sobre la existencia de los sistemas de Steiner; véase la otra respuesta para obtener más información.