5
$\begingroup$

Suppose we have a collection on sets $\{S_1, \ldots, S_n\}$ and where each set $S_i \subset \{0, \ldots, u-1\}$ and has $\left| S_i \right| = k$.

Also, given a fixed $m \le \frac{n}{2}$, we also know that any set $T \subset \{0,\ldots,u-1\}$ where $\left|T\right| \le m$ there is at most $n-1$ sets that have a non-empty intersection. Or inother words, there exists a set $S_i$ for some $i$ such that $S_i \bigcap T = \phi$

What is smallest value of $u$ that can satisfy these constraints? (Or at least a lower bound on $u$)

It seems to me that $u$ must be dependent on both $m$ and $k$, but I cannot figure out how to show it. Does anyone have any insight that might help show this?

EDIT: I guess the more important case that I am thinking of is when $k=n$. If $n$ is larger than ${k+m\choose m}$ there is a clear assignment of the sets so that every $m$ elements does not cover the entire set. So the lower bound mentioned $u\ge k+m$ can be achieved. But it is not clear when $k=n$. Does anyone have any insight for this?

  • 0
    @Aryabhata No I did mean that $m\le \frac{n}{2}$. Though, if $k\ge m$ (which with the question update it will be) $u\ge k+m$ which then gives that $u\ge 2m$.2012-01-26

0 Answers 0