3
$\begingroup$

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

2 Answers 2

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

1

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