MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 13 characters in body

This problem has enough parameters to easily confuse. I will add some trivial cases to help motivate the problem, and encourage the poster to provide some more.

Of course, arranging that every set in S contains one of the sets in the given collection C shows that there is a solution with $s > c$; what is wanted is $s <= c$.

For $k=2$ and disjoint sets $C_1$ and $C_2$, both of size $c$, getting $s < c$ seems challenging because you have to choose at most half the sets of S. I can imagine a case where epsilon times $m > 2$, and then reducing to the case of $k=1$ and (epsilon m times $m$) also being reduced by 1, but this implies constraints on n,m and epsilon and it is not pretty, at least to me. However,a pigeonhole argument should work for the case of $n$ disjoint equinumerous $C_i$ as it does for $n=1$, provided m and epsilon fit some narrow constraints, again getting $s > c(1-$ epsilon).

If C contains all subsets of size $r$ of an $n$ set, one can choose s=1, as long as $m$ and epsilon play nice. If epsilon is less than 1/2, then $2r < n$. For larger $r$, one can try mostly disjoint sets in S of larger size; the problem reminds one of doing certain kinds of covering designs.

As my understanding of the problem develops, I will add to this. It seems to help if one relaxes the constraints on s and epsilon, and then looks for more challenging bits as you try to impose some constraints on groups of parameters. Even so, I encourage Artem to provide more motivation.

Gerhard "Ask Me About System Design" Paseman, 2011.07.15

1

This problem has enough parameters to easily confuse. I will add some trivial cases to help motivate the problem, and encourage the poster to provide some more.

Of course, arranging that every set in S contains one of the sets in the given collection C shows that there is a solution with $s > c$; what is wanted is $s <= c$.

For $k=2$ and disjoint sets $C_1$ and $C_2$, both of size $c$, getting $s < c$ seems challenging because you have to choose at most half the sets of S. I can imagine a case where epsilon $m > 2$, and then reducing to the case of $k=1$ and epsilon m also being reduced by 1, but this implies constraints on n,m and epsilon and it is not pretty, at least to me. However,a pigeonhole argument should work for the case of $n$ disjoint equinumerous $C_i$ as it does for $n=1$, provided m and epsilon fit some narrow constraints, again getting $s > c(1-$ epsilon).

If C contains all subsets of size $r$ of an $n$ set, one can choose s=1, as long as $m$ and epsilon play nice. If epsilon is less than 1/2, then $2r < n$. For larger $r$, one can try mostly disjoint sets in S of larger size; the problem reminds one of doing certain kinds of covering designs.

As my understanding of the problem develops, I will add to this. It seems to help if one relaxes the constraints on s and epsilon, and then looks for more challenging bits as you try to impose some constraints on groups of parameters. Even so, I encourage Artem to provide more motivation.

Gerhard "Ask Me About System Design" Paseman, 2011.07.15