Proof that $|\mathscr{F}_1 \cap \mathscr{F}_2| \geq \frac{|\mathscr{F}_1| \cdot |\mathscr{F}_2|}{2^n}$

127 Views Asked by At

A subsets family $\mathscr{F}$ of set $\{1, 2, \ldots, n\}$ is called hereditary set if for any $A \in \mathscr{F}$ and any $B \subset A,$ $ \ B \in \mathscr{F}$.

Proof that $|\mathscr{F}_1 \cap \mathscr{F}_2| \geq \frac{|\mathscr{F}_1| \cdot |\mathscr{F}_2|}{2^n}$ holds if $\mathscr{F}_1$ and $\mathscr{F}_2$ are hereditary sets of $\{1, 2, \ldots, n\}$.

It is possible to solve this problem with pure math induction, but I don't have any idea how to do it. Could somebody give me a hint?

1

There are 1 best solutions below

4
On BEST ANSWER

It is a result due to Kleitman.

You will find a proof by induction in this draft book page 101 Theorem 10.6.

About the mathematical accomplishments of Kleitman see here