Consider a graph $G = (V,E)$ with $n$ vertices and $m$ edges, and fix an integer $s \leq n$. The goal is to find a family of sets $S_1, S_2, \dots, S_t \subset V$ such that:
- each set $S_i$ is of size $s$
- for each edge $(u,v) \in E$ there is at least one set $S_i$ such that $u,v \in S_i$.
I would like to know how large $t$ must be if each set $S_i$ is chosen independently and uniformly at random among all subsets of size $s$. We can allow to fail with a small probability, and to cover only a constant fraction of all edges.
The parameters that interest me the most are $n = m$ and $s = \sqrt{n}$.