Showing that for a family of subsets of $[n]$ enough elements appear in high frequencies

31 Views Asked by At

Let $\mathcal{F} \subseteq 2^{[n]}$ a familiy of subsets.

Assume that the following applies:

  • For every $A \subseteq [n]$ , such that $|A|\leq \alpha n$ ($\alpha > 0$ is given), there's a subset $F \in \mathcal {F}$, such that $ A \cap F = \emptyset$.

  • There exists a measure $\mu$ over $[n]$, such that if $i\sim\mu$, then for every $F\in \mathcal F$, we have $$\Pr_{i\sim\mu}[i\in F]\geq \frac9{10} $$

Using the notation $p_i=$ frequency of $i$ in $\mathcal F$ I'm trying to show that for $\theta (n)$ elements we have that $p_i \geq \frac12 +\epsilon$ for some $\epsilon > 0$.

I just cant seem to find a way to even start, so could you please give me a guideline of how to show that, it should have some connection to entropy, but I cant see how.

Thanks