Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $2 \leq k \leq n - 2$. I need to prove that any collection of sub-sets of [n] such that 2 different of them have exactly k common elements, consists of at most $n$ sub-sets.

Thanks.

share|improve this question
3  
Could you rephrase this question giving names to the subsets? At the moment, it is far from clear what you are asking. –  gowers Jul 29 '10 at 7:10
1  
I think question is: For $ 2 \leq k \leq n-2$, let A_1, A_2,...,A_t be all the distinct subsets of {1,2,...n} such that |A_i \cap A_j | = k for $i \neq j$ (not uniquely defined but take any such list of subsets). Then prove that $t \leq n $. –  Pooja Jul 29 '10 at 8:11
1  
When you say you "need to prove this", is this for use in some other result or to solve some problem? or an exercise? (That is, do you know in advance that the answer is what you claim?) –  Yemon Choi Jul 29 '10 at 8:39
2  
@Wadim, yes, it matters, unless we want MO to be overrun with homework problems. –  Gerry Myerson Jul 29 '10 at 9:49
3  
But this is obviously a homework problem... –  Wadim Zudilin Jul 29 '10 at 10:25
show 3 more comments

2 Answers

Although we have by now the best answer, that is a precise reference, I wish to post my solution too -it's quick and self contained, and it may possibly differ from the original proof, at least in the language. Consider the $n\times r$ incidence matrix $A,$ with coefficient $a_{i\\,j}$ equals to 1 or 0 according whether $i\in A_j$ or not. By the assumption on the intersections, the $r\times r$ square symmetric matrix $A^tA$ has all non-diagonal elements equals to $k$. Moreover, its $i$-th diagonal element is $|A_i|\geq k$, with equality for at most one index. The determinant of such a matrix is easily computed (it's nice: substract the first column from all the others getting a lot of zeros; then expand. Incidentally, we can also get the characteristic polynomial this way), and turns out to be strictly positive. Of course, this may only happen if $r\le n$, for $\operatorname{rank}(A^tA)\leq n$, proving the claim.

In fact, to prove that $\det(A^tA)>0$ it would be sufficient to prove that the quadratic form $x\mapsto \frac{(Ax\cdot Ax)}{k}$ is positive-definite. Actually, it writes as $\left(\sum_{i=1}^rx_i\right)^2+\sum_{i=1}^r\alpha_i x_i^2,$ with all $\alpha_i\geq0$ and equality for at most one index. It's clearly non-negative; to show it's positive-definite I do not have a safer argument than the above computation of the determinant, though I think there's an even quicker way (edit: indeed, as darij grinberg remarks below, it's a sum of two non-negative quadratic forms, whose null-spaces have zero intersection).

PS: thanks for the nice exercise. I'd be curiuos then to know if the bound $r\leq n$ is sharp. For instance if $k=n-2$, a convenient family of $n$ subsets is given by the $A_i:=[n]\setminus \{i\}$.

share|improve this answer
2  
For proving that it is positive-definite, just note that if $\left(Ax,Ax\right)=0$; then $0=\left(Ax,Ax\right)=\left(\sum_{i=1}^r x_i\right)^2+\sum_{i=1}^r \alpha_i x_i^2$, which yields (since $\alpha_i\geq 0$ with equality for at most one $i$) that $\sum_{i=1}^r x_i=0$ and all but (at most) one $x_i$ are $0$, so that all $x_i$ must be $0$. –  darij grinberg Jul 29 '10 at 13:30
    
This is the proof I've seen (it's on Wikipedia I believe); it is, however, quite nice. –  Daniel Litt Jul 29 '10 at 13:59
    
here it is: en.wikipedia.org/wiki/Fisher%27s_inequality (I was not aware of it; though I was pretty sure that what I wrote was the standard way). –  Pietro Majer Jul 30 '10 at 15:44
add comment

I'm sorry, I am a bit in a hurry but this result is called "Fisher's inequality", and you will find its proof as section 14.2.1 of Jukna's book "Extremal Combinatorics"

Nathann

share|improve this answer
    
Nathann, I suggest you extend your answer to other fishers (like me) when you aren't in rush. Thank you in advance! –  Wadim Zudilin Jul 29 '10 at 9:14
    
Wikipedia has an entry on Fisher's Inequality, en.wikipedia.org/wiki/Fisher's_inequality but I don't see the application. –  Gerry Myerson Jul 29 '10 at 9:53
1  
Jukna's book, or at least the page needed here, is freely available at lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/sample/… –  Gerry Myerson Jul 29 '10 at 9:58
    
Sorry for that ! I went back to this page as soon as I arrived home, but you were faster than I. I knew it would take several hours, and I thought it would be better to have a reference than nothing in the meantime :-) Nathann –  Nathann Cohen Jul 29 '10 at 14:17
    
This is a perfect answer and should be accepted. Giving OP the benefit of the doubt, let's suppose that the question is not a HW question but needed in research --- maybe OP is a graduate student who has not taken combinatorics and has found a need for this inequality in some other application. Then the final paper should include a good citation, and this is one such. –  Theo Johnson-Freyd Jul 29 '10 at 18:28
add comment

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.