(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?


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).


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$.


Your Answer

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

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