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 C consisting of n subsets of {1, 2, ..., n}, each of size k, does there exist some small A $\subset$ {1, 2, ..., n} such that A intersects all (or all except a small number) of the sets in C?
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.