3
$\begingroup$

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!

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

1 Answer 1

3
$\begingroup$

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

https://gilkalai.wordpress.com/2014/01/16/amazing-peter-keevash-constructed-general-steiner-systems-and-designs/

$\endgroup$
1
  • $\begingroup$ Thanks for connecting this to Steiner systems! $\endgroup$ Commented Dec 16, 2018 at 19:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .