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

Solution 1:

In case it helps, here are values for small $n$: $$m(4)=1, m(5)=5, m(6)=15, m(7)=18, m(8)=35, m(9)=42.$$ For all $n$, we have $m(n)\le\binom{n}{4}$ (trivially) and $m(n)\le m(n-1)+\binom{n-1}{3}$ by extending an optimal coloring for $n-1$ with one in which each 4-subset that contains $n$ gets its own color.

The independence number $\alpha(n)$ is the size of a largest independent set and provides a lower bound on the chromatic number: $m(n) \ge \lceil\binom{n}{4}/\alpha(n)\rceil$. At least for $n \le 9$, this lower bound is tight. The values of $\alpha(n)$ are OEIS A004037.

Solution 2:

Proposition 1. If $n$ is a power of an odd prime then $m(n)\le n^2$.

Proof. It is well-known (see, for instance, [Lan]) that there exists a field $F$ of order $n$. For each elements $x,y$ of $F$ let $A(x,y)$ consists of all four-element subsets $\{a,b,c,d\}$ of $F$ such that $a+b+c+d=x$ and $a^2+b^2+c^2+d^2=y$. We claim that for each $x,y\in F$ and each distinct $Y_1, Y_2\in A(x,y)$ we have $|Y_1\cap Y_2|=1$. Suppose to the contrary that
$Y_1=\{a,b,c_1,d_1\}$ and $Y_2=\{a,b,c_2,d_2\}$. Then $c_1+d_1=c_2+d_2$ and $c_1^2+d_1^2=c_2^2+d_2^2$. That is $c_1-c_2=d_2-d_1$ and $c_1^2- c_2^2=d_2^2-d_1^2$. Since $c_1=c_2$ iff $d_1=d_2$ iff $\{a,b,c_1,d_1\}=\{a,b,c_2,d_2\}$, we see that $e=c_1-c_2=d_2-d_1$ and so $c_1+c_2=d_2+d_1$. This follows $2c_1=2d_2$, so $c_1=d_2$ and $d_1=c_2$, a contradiction. $\square$

Proposition 2. For sufficiently large $n$, $m(n)\le (n+n^{0.525})^2$.

Proof. It follows from Proposition 1, because for sufficiently large $x$ there is a prime belonging to $[x-x^{0.525}, x]$, see [BHP]. $\square$.

References

[BHP] R. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II. Proc. Lond. Math. Soc., (3) Ser. 83 (2001) 532–562.

[Lan] Serge Lang, Algebra, Addison-Wesley, Reading, Mass., 1965 (Russian translation, Moskow, 1968)

Solution 3:

I don't think there is such upper bound since you can take this partition $A_i =\{Y_i\}$ for each four element $Y_i$ in $X$, so $$m= {n\choose 4}$$

On the other hand we have lower bound:

Let $\mathcal{A} = \{A_1,A_2,....A_m\}$ and we seek for $m$. Let $\mathcal{P}$ be a set of all pairs in $X$. For fixed $A_i$ make a bipartite graph $ G=(A_i,\mathcal{P})$ where $Y_l\in A_i$ is connected to pair $P_j$ iff $P_j\subset Y_l$. Clearly the degree of each $Y_l$ is ${4\choose 2}=6$ and the degree of each pair $P_j$ is at most $1$ (since no pair can appear in two sets from $A_i$). So we have $$|A_i|\cdot 6 \leq {n\choose 2} \implies \boxed{|A_i|\leq {n(n-1)\over 12}}$$