Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(Auke found a counter-example to my original post, so I am opening this question up...)

Suppose we have $k$ sets $X_1, \dots, X_k$ which are subsets of a ground set $X$ of size $n$. We know that $|X_i| \geq t$ for all $X_i$. Then we would like to find the smallest possible set $Y$ such that $Y \cap X_i \neq \emptyset$ for all $i$.

Given fixed values for $k, n, t$, what is the largest $|Y|$ which might be necessary to do this?

share|cite|improve this question

Edit: question was slightly changed; the original question was whether we can always find $Y\subset X$ with $|Y|\leq n/t$ such that $Y\cap X_i\neq\varnothing$ for all $i$

Counterexample (correct me if I'm wrong):

$X=\{1,2,3,4\}$, so $n=4$

$X_1=\{1,2\},X_2=\{2,3\},X_3=\{3,4\},X_4=\{4,1\},X_5=\{2,4\},X_6=\{1,3\}$, so $t=2$; we must find $Y$ of size 2 (which we cannot).

share|cite|improve this answer

For the new question, if the $X_i$ are single-element subsets, then surely $Y$ may sometimes have to be all of $X$.

Also, $|Y|=k$ is of course always sufficient - simply pick a random element from each $X_i$.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.