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$ 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$ 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
    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
    Jun 16, 2020 at 1:55
  • $\begingroup$ @RobPratt Oh yes you are right, thanks! $\endgroup$ Jun 16, 2020 at 12:33

You must log in to answer this question.

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