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.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
|
|||||||||||||||||||||||||
|
|
6
|
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 |
|||||||||||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
4
|
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\}$. |
|||||||||||
|
|
0
|
Fisher's inequality is exactly what i meant! I'm sorry if the question was a bit fuzzy.. Thanks a lot :) |
|||||
|
