Suppose $n$ is a positive integer. Let ${\cal C}$ be a set of subsets of $X:=\{1,\ldots,n\}$ with the following properties:

  1. all members of ${\cal C}$ contain at least $2$ elements, and $X\notin {\cal C}$; and
  2. $A\neq B\in {\cal C}$ implies $|A\cap B| = 1$.

A version of Fisher's inequality states that $|{\cal C}| \leq n$. There are short proofs relying on Linear Algebra. Is there a purely combinatorial proof of this statement?

  • 2
    $\begingroup$ This is shown in the answer to your earlier question mathoverflow.net/questions/266511/…. $\endgroup$ – Tom De Medts Apr 6 '17 at 10:53
  • $\begingroup$ I don't see how, can you give me a hint? $\endgroup$ – Dominic van der Zypen Apr 6 '17 at 11:58
  • 2
    $\begingroup$ What do you mean? It's literally there: "At first, we denote $|\mathcal{C}|=m$ and do not assume for a moment that $m=n$, but prove that $m \leq n$." $\endgroup$ – Tom De Medts Apr 6 '17 at 14:39
  • $\begingroup$ You're right -- I just missed it. Thanks for the hint $\endgroup$ – Dominic van der Zypen Apr 9 '17 at 7:46

A combinatorial proof of a more general inequality is given by Douglas Woodall.

One line proof Fisher's inequality is given by Renaud Palisse

Palisse, Renaud, A short proof of Fisher's inequality, Discrete Math. 111, No.1-3, 421-422 (1993). ZBL0788.04003.

Woodall, Douglas R., A note on Fisher's inequality, J. Comb. Theory, Ser. A 77, No.1, 171-176, TA962729 (1997). ZBL0878.05011.

  • 1
    $\begingroup$ It looks like that paper deals primarily with $\lambda$-linked designs, which is a condition not imposed above. Can you comment on whether the mentioned (and elsewhere proved) Theorem 3 does apply here? Gerhard "Not Clear If It Does" Paseman, 2017.04.06. $\endgroup$ – Gerhard Paseman Apr 6 '17 at 16:41
  • $\begingroup$ @GerhardPaseman Hmm. To atone I added a somewhat algebraic and REALLY short proof. $\endgroup$ – Igor Rivin Apr 6 '17 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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