Let $S$ be a set,$|S| = n$, with $n$ sufficiently large and divisible by $8$. Suppose that $A_1, \dots, A_{n/2} \subseteq S$, $|A_i| = \dfrac{n}{2}$ for all $i$. Is it always possible to choose a subset $T \subseteq S$ with $|T| = \dfrac{n}{4}$ such that $|T \cap A_i| \geq \dfrac{n}{8}$ for all $i$?

I'm considering a set of integers from $1$ to $n$. If each $A_i = \{i, i+1, \dots, i + n/2\}$, then choosing $T$ to be every 4th integer would do the trick; that is, we can let $T = \{1,5,9,13,\dots\}$. It would also work to let $T$ be spread more coarsely across the integers, for example letting $T = \{1,2,9,10,17,18,\dots\}$, or even letting $T = \{1, \dots, n/8, n/2 + 1, \dots, 5n/8\}$. I'm trying to see if this idea is true in general.

I'm having problems using a standard counting argument, because as I build $T$, I have to keep track of which $A_i$'s already intersect with $T$ a sufficient number of times and don't need to be considered anymore. Furthermore, I know that the number of sets, $n/2$, is critical to the argument, because this would definitely not work if there were, say, $2^n$ subsets of $S$.

If there are any known results related to this kind of idea, or if anyone has any clever arguments, I would be extremely grateful to hear them. Thank you.

  • 1
    $\begingroup$ This would be easier to think about if $X$ looked more like a number and less like the name of a set. Can it be something lower-case from the middle of the alphabet? $\endgroup$ – timtfj Feb 11 at 0:42
  • $\begingroup$ That's a good point. I changed $X$ to $n$. $\endgroup$ – Peter Bradshaw Feb 11 at 0:44
  • 1
    $\begingroup$ Yeah, I suppose I should write that more clearly. $\endgroup$ – Peter Bradshaw Feb 11 at 0:55
  • 1
    $\begingroup$ Maybe you need to work out what configuration of the $A_i$'s makes it hardest to get the intersections. I think it's to do with how few of them each element of $T$ is in. Roughly speaking,' "how disjoint" the $A_i$'s are. $\endgroup$ – timtfj Feb 11 at 1:14
  • 1
    $\begingroup$ I think you have to find a way to build the $A_i$'s with the minimum reuse of elements, then see whether this can force $T$ to be too big because not enough elements are in enough sets. If that can't happen, and you can prove you've got the worst-case configuration, then T can exist. I've not tried this though and and I won't be surprised if it's got nasty complicating factors. $\endgroup$ – timtfj Feb 11 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.