0
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ Could you rephrase this question giving names to the subsets? At the moment, it is far from clear what you are asking. $\endgroup$
    – gowers
    Jul 29, 2010 at 7:10
  • 1
    $\begingroup$ 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 $. $\endgroup$ Jul 29, 2010 at 8:11
  • 1
    $\begingroup$ 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?) $\endgroup$
    – Yemon Choi
    Jul 29, 2010 at 8:39
  • 2
    $\begingroup$ @Wadim, yes, it matters, unless we want MO to be overrun with homework problems. $\endgroup$ Jul 29, 2010 at 9:49
  • 4
    $\begingroup$ But this is obviously a homework problem... $\endgroup$ Jul 29, 2010 at 10:25

2 Answers 2

7
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Nathann, I suggest you extend your answer to other fishers (like me) when you aren't in rush. Thank you in advance! $\endgroup$ Jul 29, 2010 at 9:14
  • $\begingroup$ Wikipedia has an entry on Fisher's Inequality, en.wikipedia.org/wiki/Fisher's_inequality but I don't see the application. $\endgroup$ Jul 29, 2010 at 9:53
  • 1
    $\begingroup$ Jukna's book, or at least the page needed here, is freely available at lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/sample/… $\endgroup$ Jul 29, 2010 at 9:58
  • $\begingroup$ 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 $\endgroup$ Jul 29, 2010 at 14:17
  • $\begingroup$ 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. $\endgroup$ Jul 29, 2010 at 18:28
6
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$ Jul 29, 2010 at 13:30
  • $\begingroup$ This is the proof I've seen (it's on Wikipedia I believe); it is, however, quite nice. $\endgroup$ Jul 29, 2010 at 13:59
  • $\begingroup$ 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). $\endgroup$ Jul 30, 2010 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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