

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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?

share|cite|improve this question
The [combinatorics] tag might not be the most accurate choice, but it sounds a lot closer to the question than [set-theory]. – Asaf Karagila Jan 24 '12 at 8:30
A clearly necessary condition is that $u \geq k + n/2$, since $ S_i \cap T = \emptyset$ and $S_i \cup T \subseteq U = \{ 0,1,\ldots, u-1\}$. Also note that it suffices to consider $m = |T| = \lfloor n/2 \rfloor$ and that $u = | \cup S_i |$. If $S_i$ is chosen to be pairwise disjoint, then $T$ can intersect at most half of them. Together this means that $k + n/2 \leq \inf u \leq nk$. – Willie Wong Jan 24 '12 at 11:57
By allowing each element in $U$ to belong to at most two $S_i$, you can refine the estimate above to $\inf u \leq \lceil (n+1)/2\rceil k $. – Willie Wong Jan 24 '12 at 12:18
Thanks @AsafKaragila. I haven't been on long enough to know what should go set. Question had sets, I thought set-theory. – Olives Jan 24 '12 at 15:44
@AsafKaragila: [combinatorics] is perfect, IMO. – Aryabhata Jan 26 '12 at 19:44

Your Answer



Browse other questions tagged or ask your own question.