# Finding the smallest partition of a set S which satisfies a given property.

Here is a problem I've encountered while working on graph colouring, and I haven't been able to find the solution (both online and with my own efforts). A problem like this may have been studied previously, perhaps in another guise. Any insights are appreciated.

Let $S$ be a set whose elements are the $\binom{n}{k}$ $k$-subsets of some $n$-set. Let $S_1, S_2, \ldots, S_t$ denote a partition of $S$. What is the smallest size of a partition (the smallest value of $t$) such that for each $i \in \{1,2,\ldots, t\}$ and each element $x$ of the $n$-set, $x$ is an element of at most $\ell$ of the $k$-subsets in $S_i$?

Let $f(n,k,\ell)$ denote the smallest size of such a partition.

An example for $n = 4$, $k = 2$, and $\ell = 2$:

Here, $S = \{ \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\} \}$. We can easily see that $f(4,2,2) = 2$, as $S_1 = \{ \{1,2\}, \{1,3\}, \{3,4\}\}, S_2 = \{ \{1,4\}, \{2,3\}, \{2,4\}\}$ is a valid partition, and no valid partition of size $1$ exists because each element appears in $3 > \ell$ sets.

So far, I've just been able to determine a simple upper bound for $f(n,k,\ell)$. Let $1,2\ldots, n$ be the elements of the $n$-set. Let $X_i$, for $1 \leq i \leq n - k + 1$, be the set of subsets which contain the element $i$, and do not contain any element $j$ such that $j < i$. Then, $X_1,X_2,\ldots, X_{n - k + 1}$ is a partition of $S$. Each $X_i$ can itself be partitioned into $\alpha_i = \left \lceil \frac{|X_i|}{\ell} \right \rceil$ sets $S^i_1, S^i_2, \ldots, S^i_{\alpha_i}$ each which contain at most $\ell$ $k$-subsets. Then the partition $S^1_1, S^1_2, \ldots, S^1_{\alpha_i}, S^2_1, S^2_2, \ldots, S^{n-k+1}_{\alpha_{n-k+1}}$ of $S$ is a partition of size $\alpha_1 + \alpha_2 + \ldots + \alpha_{n-k+1}$ which satisfies our condition, and so $f(n,k,\ell) \leq \sum\limits^{n-k+1}_{i=1} \alpha_i$, where $\alpha_i = \left \lceil \frac{|X_i|}{\ell} \right \rceil = \left \lceil \binom{n-i}{k-1}/\ell \right \rceil$.

Unfortunately I expect this upper bound is far from tight (It gives $f(4,2,2) \leq 4$).

• S is a subset of the power set on the n-set. – user451844 Aug 11 '17 at 0:49
• That's Correct. – Sbard Aug 11 '17 at 0:58
• sorry that was my useful insight for right now. – user451844 Aug 11 '17 at 0:59

We can obtain a lower bound by double counting the number $P$ of pairs $(x,S)$ where $x\in s\in S$. Each element $s\in S$ participate at $|s|=k$ such pairs, so $P=k{n\choose k}$. On the other hand, for each $x$ each of $S_i$ contains at most $\ell$ elements $s\ni x$, so $P\le t\ell n$. Thus $t\ge {n\choose k}\frac {k}{n\ell}$.
For $\ell=1$ we obtain more tight bounds. In this case each $S_i$ consists of mutually disjoint subsets, so $|S_i|\le \lfloor\frac nk\rfloor$, so $t\ge {n\choose k}\lfloor\frac nk\rfloor^{-1}$. On the other hand we can show that $f(n,n/2,1)=\frac 12 {n\choose k}$, considering a partition in which each $S_i$ consists of two sets whose union is $S$.