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<k<\ell$ 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!

  • 2
    $\begingroup$ What's wrong with choosing the collection of all $\ell$-subsets of $\{1, \dots, n\}$? $\endgroup$ – user44191 Dec 16 '18 at 9:05
  • $\begingroup$ 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 $\endgroup$ – 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


| cite | improve this answer | |
  • $\begingroup$ Thanks for connecting this to Steiner systems! $\endgroup$ – Dominic van der Zypen Dec 16 '18 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.