Bounds for ground set of Steiner system (inverse EKR style problem)

Question

Imagine we have $r$ subsets of a ground set $S$, each of size $k$, such that each set of size $l$ is contained in at most one of the $r$ sets. What can we say about the minimum value of $|S|$? I am primarily interested in lower bounds but any info about upper bounds would be helpful as well

Answer 1

I am still studying relevant sources, trying to provide the required bounds. So I am going to update this answer accordingly.

If $l>k$ or $r=1$ then the required condition always holds, so we assume that $1\le l\le k$ and $r\ge 2$. 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 on $n$. The other lower bound, $n\ge\frac{k^2r}{k+(r-1)(l-1)}$, can be easily obtained from this question.

A straighforward upper bound on $n$ can be provided by the greedy algorithm, but it looks complicated. Namely, it suffices to have $${n\choose k}> (r-1)\sum_{i=l}^k{k\choose i}{n-k \choose k-i}.$$ If I understood the notation in this question right, it suffices to pick $n\ge 2k\max\{k,\sqrt[l]r\}$. In this my answer is considered the special case when $k=q^s$ and $l=q^{s-1}+1$, where $q$ is a power of the prime. In this case it suffices to pick $n=q^t$, provided ${t\choose s}_q\ge 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 much more studied than the previous, see [E] and [EV]. 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)$.

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.

[R] Rodl, On a Packing and Covering Problem, 1985.