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$).

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

Some partial cases.

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$.


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.