6
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ This is shown in the answer to your earlier question mathoverflow.net/questions/266511/…. $\endgroup$
    – Tom De Medts
    Commented Apr 6, 2017 at 10:53
  • $\begingroup$ I don't see how, can you give me a hint? $\endgroup$
    – Dominic van der Zypen
    Commented Apr 6, 2017 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
    Commented Apr 6, 2017 at 14:39
  • $\begingroup$ You're right -- I just missed it. Thanks for the hint $\endgroup$
    – Dominic van der Zypen
    Commented Apr 9, 2017 at 7:46

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Apr 6, 2017 at 16:41
  • $\begingroup$ @GerhardPaseman Hmm. To atone I added a somewhat algebraic and REALLY short proof. $\endgroup$
    – Igor Rivin
    Commented Apr 6, 2017 at 17:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .