# Prove that you can form at most $n$ same sized intersections of $m$ subsets of an $n$ element set.

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$.

-
Thanks! Just one question, what does the ∪iCi at the end mean? I'm not sure I understand that notation. – Nico Bellic May 6 '12 at 1:15
The union of all the sets $C_1,\ldots,C_m$. – Alex Becker May 6 '12 at 1:16

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.

-
I love this proof. – Joel Cohen May 6 '12 at 1:02
Hi Austin. I'm a little confused on your terminology. Could you please elaborate from "Letting M...". – Nico Bellic May 6 '12 at 1:46
@NicoBellic I have defined incidence matrix in my answer. Does this address your confusion? – Austin Mohr May 6 '12 at 2:23
Ah I see. Thank you. Also, can you define semi-definite and definite. – Nico Bellic May 6 '12 at 3:53