Skip to main content
8 of 10
added 234 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$. On the other hand, if I understood the notation in this question right, it suffices to pick $n\ge 2k\max\{k,\sqrt[l]r\}$.

Let us try to provide a more refined analysis.

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

Your question admits two interpretations via studied subjects.

The first interpretation belongs to graph theory. According to it, a quadruple $(n,k,l,r)$ of natural numbers with $l\le k\le n$ 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$.

The second interpretation is combinatorial. Namely, given natural numbers $n\ge d,k$, let $A(n, d, k)$ be the maximal possible number of binary vectors of length $n$, (Hamming) distance at least $d$ apart, and constant weight (that is, the number of $1’$s) $k$. This subject looks more studied than the previous, see the references. According to this interpretation, a quadruple $(n,k,l,r)$ of natural numbers with $l\le k\le n$ is admissible iff $r\le A(n,2(k-l+1),k)$.

Now I am reading the first paper, trying to use it to obtain bounds for $n$.

References

[E] Joakim Ekberg, Geometries of Binary Constant Weight Codes, Master thesis, Karlstadt Universitet, Faculty 2 Department of Mathematics, 2006.

[EV] Tuvi Etzion, Alexander Vardy, A New Construction for Constant Weight Codes.

Alex Ravsky
  • 5.4k
  • 1
  • 17
  • 31