0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Per Alexandersson May 12 '14 at 11:47
  • $\begingroup$ 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). $\endgroup$ – Martin Tancer May 12 '14 at 13:39
  • $\begingroup$ @MartinTancer But you also change $r$ in the process, don't you? The sets become bigger. $\endgroup$ – Felix Goldberg May 12 '14 at 14:17
  • $\begingroup$ Thank you, now I think I understand. (It is easy to confuse "r sets" and "r-sets".) $\endgroup$ – Martin Tancer May 13 '14 at 5:42
  • $\begingroup$ @MartinTancer Sorry for the confusion - I modified the text to be clearer. $\endgroup$ – Felix Goldberg May 13 '14 at 9:01
2
$\begingroup$

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.

$\endgroup$

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.