# A set coverage problem

Given a set $$X$$ and $$k\in\mathbb{N}$$ we call a subset of $$X$$ a $$k$$-subset if its cardinality is $$k$$. If $${\cal S}$$ is a collection of subsets of $$X$$ and $$x\in X$$ we set $${\cal S}_x=\{S\in {\cal S}: x\in S\}$$.

Let $$1 be integers. Is it possible to find infinitely many integers $$n>\ell$$ such that there is a collection $${\cal L}$$ of $$\ell$$-subsets of $$\{1,\ldots,n\}$$ with the following properties?

1. every $$k$$-subset of $$\{1,\ldots,n\}$$ is contained in exactly one member of $${\cal L}$$, and
2. for all $$a,b\in\{1,\ldots,n\}$$ we have $$|{\cal L}_a|= |{\cal L}_b|$$.

EDIT. In the original version of this question I omitted the words "exactly one" in condition 1; thanks to @user44191 for spotting this!

• What's wrong with choosing the collection of all $\ell$-subsets of $\{1, \dots, n\}$? – user44191 Dec 16 '18 at 9:05
• Sorry, I omitted the word "exactly" in condition 1, i.e. the small subsets ($k$-subsets) are supposed to be in exactly one $\ell$-subset – Dominic van der Zypen Dec 16 '18 at 13:35

At first, the second condition follows from the first by averaging over all $$k$$-sets containing $$a$$. Moreover, for any $$m\leqslant k$$ and any $$m$$-set $$A\subset \{1,\dots,n\}$$ we may count the number $$N$$ of pairs $$B\subset C$$ where $$A\subset B$$, $$B$$ is a $$k$$-set and $$C$$ is an $$\ell$$-set from $$\mathcal{L}$$. For any fixed $$B$$ there exists unique such pair, thus $$N=\binom{n-m}{k-m}$$. On the other hand, for fixed $$C$$ there exists exactly $$\binom{\ell-m}{k-m}$$, so $$A$$ belongs to exactly $$\binom{n-m}{k-m}/\binom{\ell-m}{k-m}$$ sets $$C\in \mathcal{L}$$. This ratio should be integer for all $$m=1,2,\dots,k-1$$, that is called divisibility condition. They are enjoyed for infinitely many $$n$$ (say, for all $$n$$ which are congruent to $$\ell$$ modulo $$lcm\{(k-m)!\binom{\ell-m}{k-m},m=1,\dots,k-1\}$$.
At second, under divisibility conditions this construction (Steiner system) exists for large enough $$n$$, as was proved recently by P. Keevash. See for example