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.

(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|improve this question
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.