# Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ such that every set in $\mathcal{F}$ meets $E$.

Lovasz (Problem 13.25 in his Problems & Exercises books) has proved that if $F$ is an $r$-uniform family of sets that every $k$ sets in $F$ intersect, then: $$\tau(\mathcal{F}) \leq \frac{r-1}{k-1}+1.$$

I wonder whether it is possible to strengthen the conclusion if we assume that $\mathcal{F}$ is $k$-wise $t$-intersecting (that is, every $k$ sets in $\mathcal{F}$ intersect in at least $t$ points).

I can obtain the following by mimicking the proof, but I feel there ought to be a better result somewhere: $$\tau(\mathcal{F}) \leq \frac{r-t}{k-1}+1.$$

• I have a friend who wrote a masters thesis on Helly's type theorems, maybe you can find something there? www2.math.su.se/gemensamt/grund/exjobb/matte/2008/rep2/… – Per Alexandersson May 12 '14 at 11:47
• I think I do not understand the question. It seems to me that if I duplicate the points so that newly I have $t$ copies of each point, then the condition that every $k$ sets intersect becomes the condition that every $k$ sets intersect in at least $t$ points. But this "duplication" does not change the transversal number (intersection pattern). – Martin Tancer May 12 '14 at 13:39
• @MartinTancer But you also change $r$ in the process, don't you? The sets become bigger. – Felix Goldberg May 12 '14 at 14:17
• Thank you, now I think I understand. (It is easy to confuse "r sets" and "r-sets".) – Martin Tancer May 13 '14 at 5:42
• @MartinTancer Sorry for the confusion - I modified the text to be clearer. – Felix Goldberg May 13 '14 at 9:01

This is the best possible bound. If $\mathcal F$ consists of every $r$-set of a set with $r+\frac{r-t}{k-1}$ elements, then it is still $k$-wise $t$-intersecting.