How to prove this inequality about a family of sets with certain property

79 Views Asked by At

Let $A_1,\cdots,A_m\subset[n]$ be such that if $A_i\cap A_j=\emptyset$,then $A_i\cup A_j=[n]$.Prove that $m\leq2^{n-1}+\binom{n-1}{[\frac{n-2}{2}\,\,]}$.I already know that we can take a maximal family of intersecting sets,say $B_1,\cdots,B_k$(It is obvious that $k\leq2^{n-1}$).And because it is maximal,by using the condition ${A_i}$ satisfies,one obtain that $A_i$ is either $B_j$ or $B_j^{\,c}$ for some $j$.Thus we can denote $A_1\cdots A_m$ as $B_1\cdots B_k,B_1^c,\cdots,B_s^c$.Note that $B_1^c,\cdots,B_s^c,B_1,\cdots,B_s$ is an anti-chain,by Sperner's Lemma we have$2s\leq\binom{n}{[\frac{n}{2}]}$.Thus we get a inequality which is closed to the inequality we want to porve.But I don't know what to do after this.

1

There are 1 best solutions below

0
On BEST ANSWER

I've now figured out how to prove it.Ant this is a brief answer.
We can use such a theorem:
Theorem(Bollobas):If $C_1,\cdots,C_m $ is an intersecting antichain in $[n]$ such that $max{C_i}\leq\frac{n}{2}$,then
$\sum_{i=1}^m\frac{1}{\binom{n-1}{|A_i|-1\,\,\,}}\leq1$.
The proof of the theorem is given by considering cyclic permutations,quite similar to the proof of Erdos-Ko-Rado theorem. We can use this theorem to prove the desired inequality.By swapping some $B_i$ and $B_i^c$,we can assume $max\{|B_1|,\cdots,|B_s|\}\leq\frac{n}{2}$.By applying the theorem we obtain the desired inequality