Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?.

Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=\{Y\subset X: Y\text{ contains exactly $4$ elements}.\}$$

I want to partition $\mathcal A$ into groups $A_1,A_2,\dots, A_m\subset \mathcal A$ (each of them is a collection of $4$-subsets of $X$) such that $\bigcup_{i=1}^m A_i=\mathcal A$ and such that the intersection of any two distinct $4$-subsets in each $A_k$ has cardinality at most $1$, i.e. such that for all $i\in\{1,\dots,m\}$ and $Y_1, Y_2\in A_i$, we have $$Y_1\neq Y_2 \implies \lvert Y_1\cap Y_2\rvert \le 1.$$

My question: What can be said about the smallest $m$ (depending on $n$) such that such a partition exists?

My thoughts: I was expecting that each $A_i$ can contain "roughly" $\frac n4$ elements, so we would have $$m(n)=\Theta\left(\frac{\binom n4}{\frac n4}\right)=\Theta(n^3).$$ In particular, we would have $m(n)\le c n^3$ for some constant $c\in\mathbb R$.

However, I am neither sure if this is correct, nor how to formalize this.

  • 5
    $\begingroup$ For every pair of elements of $X$, the 4-subsets containing them must be in distinct $A_i$, implying that $m(n)\geq \frac{(n-2)(n-3)}2$. $\endgroup$ Commented Jun 14, 2020 at 17:09
  • 1
    $\begingroup$ We can show that if $n$ is a power of an odd prime then $m(n)\le n^2$. $\endgroup$ Commented Jun 15, 2020 at 18:53
  • $\begingroup$ By the way, $\binom X 4$ is a handy and fairly well understood notation for the set of $4$-subsets of $X$. $\endgroup$
    – LSpice
    Commented Jun 16, 2020 at 16:00

1 Answer 1


This problem can be reformulated in terms of graph coloring:

Let the graph $G=(V,E)$, $V=\mathcal A$, $(x,y)\in E \leftrightarrow x \cap y \geq 2$

Then a partition of $\mathcal{A}$ into groups $A_1,A_2,…,A_m$ corresponds to a $m$-coloring of $G$.

The graph $G$ has degree no more than $6{n\choose 2}$, so $G$ can be colored in no more than $6{n\choose 2}+1$ colors by Brooks' theorem.

A lower bound of $\chi$ is presented in Max Alekseyev's comment, which can be interpreted as a clique of $G$.

  • 1
    $\begingroup$ The degree of every node is $$\binom{4}{2}\binom{n-4}{2}+\binom{4}{3}\binom{n-4}{1}=(3n-11)(n-4).$$ $\endgroup$
    – RobPratt
    Commented Jun 16, 2020 at 1:55
  • $\begingroup$ @RobPratt Oh yes you are right, thanks! $\endgroup$ Commented Jun 16, 2020 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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