Let $X$ be an $n$ element base set. Suppose I have a subset family $\mathscr{F} \subset 2^X$ satisfying the following property:
(*) For any subset $Y \subset X$, we can find an element $F \in \mathscr{F}$ such that $|F \cap Y| \geq 0.01 |Y|$. In other words, $F$ "partially covers" $Y$.
I want to find a family of sets $F_1, \cdots, F_t$ in $\mathscr{F}$ such that $F_1 \cup \cdots \cup F_t = X$ (they cover $X$), with $t$ as small as possible. How small can $t$ be in general in terms of $|X| = n$?
It is not hard to show that $t = O(\log n)$ by a greedy algorithm: each iteration, if $Y$ is the set of uncovered elements, we can use (*) to choose one $F \in \mathscr{F}$ and shrink $Y$ by a constant factor.
On the other hand, I have an example showing that $t = \Omega(\log n / \log\log n)$. The example is to set $X = \{1,2,\cdots, 100 k!\}$, and $\mathscr{F}$ consists of sum-free subsets of $X$. Then (*) is satisfies with $0.01$ replaced with $1/3$ due to a classical probabilistic argument. On the other hand, Schur's theorem shows that $X$ cannot be written as the union of $k$ sum-free subsets. So $t \geq k = \Omega(\log n / \log\log n)$.
I also know a probabilistic construction where $t = \Omega(\log n)$: sample $n$ uniformly random subsets of $X$.
I have two questions:
Can we show an explicit example where $t = \Omega(\log n)$?
Can we impose an additional assumption on $\mathscr{F}$, such that with this additional assumption, $t$ is a constant?
