Demuestre que puede formar como máximo$n$ intersecciones del mismo tamaño de$m$ subconjuntos de un conjunto de elementos$n$.

Question

Si$C_1, C_2, \dots, C_m$ son subconjuntos distintos y no vacíos de un conjunto de elementos$n$ de manera que todas las intersecciones$C_i \cap C_j$ donde$i \ne j$ tengan el mismo tamaño, entonces$n \ge m$.

¿Cuál es la forma más elegante de probar esto?

Answer 1

Supongamos que tenemos $C_i\subseteq C_j$ algunos $i,j$. A continuación, $C_i\cap C_j=C_i$ por lo tanto todos los $C_k$ contiene $C_i$ ( $|C_i\cap C_j|=|C_i\cap C_k|$ ), y la intersección de dos conjuntos es $C_i$. Así, en cada una de las $m-1$ conjuntos de $C_k$ donde $k\neq 1$ tenemos, al menos, $1$ elemento $C_k$, pero en ningún otro conjunto $C_x$, lo $n\geq |C_i|+m-1\geq m$.

Si no tenemos el $C_i\subseteq C_j$, $C_1$ tiene al menos $1$ elemento $C_2\setminus C_1$ tiene al menos $1$ elemento, y cualquiera de las $C_3\setminus C_2$ o $C_3\setminus C_1$ contiene al menos $1$ elemento y desde $|C_3\cap C_2|=|C_3\cap C_1|$ deben tener el mismo número de elementos, así que tener al menos $1$ elemento $C_3\setminus (C_1\cup C_2)$. Continuar de esta forma, por inducción tenemos, al menos, $m$ elementos en $\cup_i C_i$$n\geq m$.

Answer 2

Esto se conoce como el Uniforme de Fisher de la Desigualdad. El siguiente es un bosquejo de la prueba aparecen en "Álgebra Lineal Métodos en la Combinatoria" por Babai y Frankl.

Deje $\lambda$ común será la intersección de tamaño.

Si $|C_i| = \lambda$ algunos $i$, entonces no hay nada para mostrar. De lo contrario, deje $\gamma_i = |C_i| - \lambda$. (Nota: $\gamma_i \geq 0$ todos los $i$.)

Definir la incidencia de la matriz $A$ del conjunto del sistema a la matriz con $$a_{ij} = \begin{cases} 0 & \text{if } C_i \cap C_j = \emptyset\\ 1 & \text{if } C_i \cap C_j \neq \emptyset. \end{casos} $$

La intersección criterio se pueden resumir de la $AA^T = \lambda J + C$ donde $J$ $m \times m$ todos los 1 de la matriz y $C$ es la matriz diagonal $C = \operatorname{diag}(\gamma_1, \dots, \gamma_m)$.

Queda por mostrar el rango de $\lambda J + C$ $m$ (a partir de la cual se desprende que el $m \leq \operatorname{rank} A \leq n$). Esto se logra demostrando $\lambda J$ es positivo semi-definida e $C$ es positiva definida.