What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?

Question

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.

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