If $C_1, C_2, \dots, C_m$ are distinct and nonempty subsets of an $n$ element set such that all the intersections $C_i \cap C_j$ where $i \ne j$ have the same size, then $n \ge m$.
What's the most elegant way of proving this?
If $C_1, C_2, \dots, C_m$ are distinct and nonempty subsets of an $n$ element set such that all the intersections $C_i \cap C_j$ where $i \ne j$ have the same size, then $n \ge m$.
What's the most elegant way of proving this?
Suppose we have $C_i\subseteq C_j$ for some $i,j$. Then $C_i\cap C_j=C_i$ hence every $C_k$ contains $C_i$ (as $|C_i\cap C_j|=|C_i\cap C_k|$), and the intersection of any two sets is $C_i$. Thus in each of the $m-1$ sets $C_k$ where $k\neq 1$ we have at least $1$ element in $C_k$ but in no other set $C_x$, so $n\geq |C_i|+m-1\geq m$.
If we have no $C_i\subseteq C_j$, then $C_1$ has at least $1$ element, $C_2\setminus C_1$ has at least $1$ element, and either $C_3\setminus C_2$ or $C_3\setminus C_1$ contains at least $1$ element and since $|C_3\cap C_2|=|C_3\cap C_1|$ they must have the same number of elements so we have at least $1$ element in $C_3\setminus (C_1\cup C_2)$. Continuing in this manner, by induction we have at least $m$ elements in $\cup_i C_i$ so $n\geq m$.
This is known as the Nonuniform Fisher Inequality. The following is a sketch of the proof appearing in "Linear Algebra Methods in Combinatorics" by Babai and Frankl.
Let $\lambda$ be the common intersection size.
If $|C_i| = \lambda$ for some $i$, then there is nothing to show. Otherwise, let $\gamma_i = |C_i| - \lambda$. (Note $\gamma_i \geq 0$ for all $i$.)
Define the incidence matrix $A$ of the set system to be the matrix with $a_{ij} = \begin{cases} 0 & \text{if } C_i \cap C_j = \emptyset\\ 1 & \text{if } C_i \cap C_j \neq \emptyset. \end{cases} $
The intersection criterion can be summed up as $AA^T = \lambda J + C$, where $J$ is the $m \times m$ all 1's matrix and $C$ is the diagonal matrix $C = \operatorname{diag}(\gamma_1, \dots, \gamma_m)$.
It remains to show the rank of $\lambda J + C$ is $m$ (from which it follows that $m \leq \operatorname{rank} A \leq n$). This is accomplished by showing $\lambda J$ is positive semi-definite and $C$ is positive definite.