existence of a subset with specific properties

Question

P({1,2,...,n}) is the power set of the set {1,2,...,n}. F $\subset$ P({1,2,...,n})$\setminus${∅} but not P itself. it is known that $$\sum_{f \in F} \frac {1}{2^{|f|}} \le\frac{n}{logn}$$ I need to show that there exsits B $\subset$ {1,2,...,n} such that $\forall f \in F$, f is not a subset of B and $|B|\ge(1/2 -o(1))*n$ where o(1) is "small o" notation. I have tried to use the local lemma but I got stuck. Any ideas on how to prove it?

Answer 1

We can use the alteration method here. Choose $x \in B$ with probability $1/2$, we have that the expected size of $B$ initially is $n/2$. Next, we have that the expected number of set $f \subset B$ is $\sum_f 2^{-|f|} \leq \frac{n}{\log n}$. We remove elements in $B$ so that $f$ is no longer a subset of $B$, whose expected value is at most $\frac{n}{\log n}$. Hence, the expected size of $|B|$ is at least $n/2 - \frac{n}{\log n} = (1/2-o(1))n$. Hence proved.