Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.