*Also asked on MSE: [What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?](https://math.stackexchange.com/questions/3717109/).*


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.



What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?
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](https://en.wikipedia.org/wiki/Brooks%27_theorem).


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


