Skip to main content
4 of 10
added 25 characters in body
Alex Ravsky
  • 5.4k
  • 1
  • 17
  • 31

If $l>k$ then the required condition always holds, so we assume that $1\le l\le k$. Let $n=|S|$. Then there are ${n\choose l}$ subsets of size $l$ of $S$, and each of the given $r$ subsets contains ${k\choose l}$ of subsets of size $l$. Therefore $r\cdot {k\choose l}\le {n\choose l}$, which provides a lower bound for $n$.

Your question is related with known subjects. Let us call a quadruple $(n,k,l,r)$ of natural numbers with $l\le k\le n$ admissible, if there exists a family of sets satisfying the condition from your question. Then $(n,k,l,r)$ is admissible iff the generalized Kneser graph $K(n,k,l-1)$ has a clique of size $r$. In particular, when $l=1$ this holds iff $n\ge rk$.

To be continued....

Alex Ravsky
  • 5.4k
  • 1
  • 17
  • 31