Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am not very much into combinatorics, but I want to solve the following problem. Any pointers to existing literature are very much appreciated.

Let $n,m$ be integers. I wish to find a set $S = \{S_1, \dots, S_m\}$ as small as possible such that $\forall i: S_i \subset [n]$ and $|S_i| = n/2$, and

$\forall A \subset [n]$ with $|A| = n/2: \exists j$ s.t. $|A \cap S_j| \ge (1/4 + \epsilon) n$,

for some $0 \le \epsilon \le 1/4$.

In other words, I wish to find a family of $n/2$ subsets of $[n]$ of small size such that any other $n/2$-subset of $[n]$ has a large intersection with at least one of the subsets.

So far, I figured out that for $\epsilon = 0$, $m \le 2 \log n$ sets are enough: for $i = 1 \dots \log n$, set

  • $S_{2i-1} = \{y :$ the $i$th bit of the binary representation of y is $0$ $\}$
  • $S_{2i} = \{y :$ the $i$th bit of the binary representation of y is $1$ $\}$

I am not so much interested in lower bounds but rather in constructions of upper bounds.

Thanks for any help, Chris

share|improve this question
    
Actually, I just figured out that for $\epsilon = 0$, $m = 2$ is enough. Simply take $S_1 = \{1, \dots, n/2\}$, and $S_2 = \{n/2 + 1, \dots, n \}$. Best, Chris –  Chris Feb 20 '13 at 20:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.