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.
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.
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
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 either $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\}$.