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

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.

• 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$. – Max Alekseyev Jun 14 at 17:09
• We can show that if $n$ is a power of an odd prime then $m(n)\le n^2$. – Alex Ravsky Jun 15 at 18:53
• By the way, $\binom X 4$ is a handy and fairly well understood notation for the set of $4$-subsets of $X$. – LSpice Jun 16 at 16:00

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$$.
• The degree of every node is $$\binom{4}{2}\binom{n-4}{2}+\binom{4}{3}\binom{n-4}{1}=(3n-11)(n-4).$$ – RobPratt Jun 16 at 1:55