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

Question

Also asked on MO: 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

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.

Answer 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)

Answer 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}}$$

Now $${n\choose 4}= \sum _{i=1}^m |A_i| \leq m {n(n-1)\over 12}$$ so $$\boxed{m\geq {(n-2)(n-3)\over 2}}$$