0

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.

Pietro Majer
  • 56,550
  • 4
  • 116
  • 260
newbie
  • 9
  • 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 07: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 Singla Jul 29 '10 at 08: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 08:39
  • Yemon, does it matter? – Wadim Zudilin Jul 29 '10 at 08:54
  • 2
    @Wadim, yes, it matters, unless we want MO to be overrun with homework problems. – Gerry Myerson Jul 29 '10 at 09:49
  • 4
    But this is obviously a homework problem... – Wadim Zudilin Jul 29 '10 at 10:25
  • I took the liberty of editing and changing the headers – Pietro Majer Jul 29 '10 at 13:33
  • @Wadim: that was my suspicion but I want to encourage users to own up if this is the case, because sometimes this is done as an honest mistake (not reading the FAQ). – Yemon Choi Jul 29 '10 at 17:37

2 Answers2

7

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

Nathann Cohen
  • 1,654
  • 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 09:14
  • Wikipedia has an entry on Fisher's Inequality, http://en.wikipedia.org/wiki/Fisher's_inequality but I don't see the application. – Gerry Myerson Jul 29 '10 at 09:53
  • 1
    Jukna's book, or at least the page needed here, is freely available at http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/sample/172-173.pdf – Gerry Myerson Jul 29 '10 at 09: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
6

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

Pietro Majer
  • 56,550
  • 4
  • 116
  • 260
  • 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: http://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