I'm looking for an answer to the following question. (An answer to a slightly different question would be good as well, since it could be useful for the same purpose.)

Given a set

Cconsisting ofnsubsets of {1, 2, ...,n}, each of sizek, does there exist some small A $\subset$ {1, 2, ...,n} such thatAintersects all (or all except a small number) of the sets inC?

Preferably, "small" will be $\epsilon$*n* where $\epsilon$ can be made arbitrarily small, as long as *n* and *k* are sufficiently large.

I'm hoping the answer is yes. Here is why some such *A* might exist: on average, each element of {1, 2, ..., *n*} intersects *k* sets in *C*, so one might hope to make do with *A* of size on the order of *n*/*k*.

This smells a bit like some version of Ramsey's theorem to me, or like the Erdős–Ko–Rado theorem, but it doesn't (as far as I can tell) follow directly from either.