Para$m$ subconjuntos distintos$A_1,A_2,...,A_m$ de$\{1,2,...,n\}$, tal que$|A_i \cap A_j|=k \neq 0$ para cualquier$i \neq j$, demuestre$m\leq n$.

Question

Una hermosa problema combinatorio:

Para $m$ distintos subconjuntos $A_1,A_2,...,A_m$ de $\{1,2,...,n\}$ tal que $|A_i \cap A_j|=k \neq 0$ cualquier $i \neq j$, demuestran $m\leq n$.

Creo que algunas formas de inclusión-exclusión de los principios puede ser útil aquí. Sin embargo, es claro para mí cómo se aplican. En el caso de que $k=1$ ya sacado de mí. Empecé en el orden inverso, y han averiguado el caso de que $k=n$ o $n-1$ o $n-2$. Pero parece difícil argumentar general $k$ (tal vez hacia atrás inducción?). Cualquier idea se agradece. Gracias de antemano.

Answer 1

Considere la posibilidad de la "incidencia de la matriz" $M$ de su sistema. Esta es la $m\times n$ la matriz con un uno en la posición $(i,j)$ si $j\in A_i$ y un cero en caso contrario. Entonces $MM^t$ es $m\times m$ matriz diagonal con entradas de $|A_i|>k$ e $k$s en otros lugares. Esta es una matriz positiva definida y por lo de la fila $m$. Pero si $m>n$, el rango de $M$ es en la mayoría de las $n$, y por lo que de $MM^t$ es en la mayoría de las $n$, una contradicción.