Partitions that separate all triples

Question

Let $A=\{1,2,\dots,n\}$, and $\mathcal{A}_1,\dots,\mathcal{A}_k$ be partitions of $A$ into three sets. Suppose that for each pairwise distinct $x,y,z\in A$, there exists $1\leq i\leq k$ such that $x,y,z$ are all in different sets in the partition $\mathcal{A}_i$. What is the minimum possible $k$?

Since we are interested in partitions into three sets, we might want to write each element of $A$ in base three. Then we can have $\mathcal{A}_i$ be the partition into three sets according to whether the $i$th digit is $0,1,$ or $2$. But this is not enough, because three pairwise distinct elements $x,y,z$ might not have a digit in which they are all distinct.

Answer 1

A probabalistic argument claims it goes as $\log n$. For large $n$ there are $\frac {n^3}6$ triplets and a given partition (if the three pieces are the same size) covers $\frac {n^3}{27}$ of them. If we randomly assign the partition we cover $\frac 6{27}$ of the triplets, so a triplet is not covered with chance $\frac 79$ To expect less than one triplet uncovered, we need $k$ partitions with $\frac {n^3}6\left(\frac 79\right)^k \lt 1$ or $k \gt \frac {\log \frac {n^3}6}{-\log \frac 79}\approx 3 \log n$

Answer 2

This is a low-$n$ analysis but is too long for a comment:

Let $k(n)$ be the minimum number of partitions of $\{1\cdots n\}$ such that there exists a set of partitions $S_n \{A_1, \ldots , A_k\}$ that splits every triplet of $\{1\cdots n\}$.

Clearly $k(3) = 1$ and $k(4) = 2$. The latter can be proven by noting that any 3-partition of four numbers must have two numbers in the same box, so $k(4)>1$, and an example of a two element set that covers all the triplets among $\{1\cdots 4\}$ is $$ S_4 = \left\{ \matrix{(1|2|34) \\ (12|3|4)}\right\} $$ This trival proof is presented because it provides a pattern for one way to determine $k(n)$.

Clearly if $m<n$ then $k(m)\leq k(n)$. So our next two cases can be handled together.

$k(5) > 2$ since a partition of $5$ numbers can cover at most $4$ triplets, and there are $\binom{5}{3}=10$ triplets to be covered. Yet $k(6) \leq 3$ because the following example covers all the triplets among $\{1\cdots 6\}$: $$ S_6 = \left\{ \matrix{(12|34|56) \\ (23|45|61)\\ (14|25|36)}\right\} $$ Therefore $k(6) = 3$ and $k(5) = 3$ (a valid $S_5$ may be obtained simply by omitting all instances of the number $6$ from $S_6$).

It turns out that all valid $S_6$ sets of partitions can be obtained from the one presented, by permutations of the numbers $\{1\cdots 6\}$; in that sense, the answer for $n=6$ is unique.

$k(7)$ is more difficult but still tractable. First, although a partition of $\{1\cdots 7\}$ can cover (that is, split up) twelve triplets (if the partition groups one group of three and two groups of two numbers), ad $3\times 12 = 36 > \binom{7}{3} = 35$, nonetheless $k(7) > 3$. Proof:

If you have $S_7$ and eliminate all instances of the number $7$, you are left with a valid partitioning of six numbers, which we just saw must (up to permutations) be the $S_6$ presented above. But then when you add $7$ back into the mix, it will be in a box of three numbers, thus forming a triplet which will neet to be covered elsewhere. Without loss of generality, we might place $7$ with $12$ in $A_1$, then $7$ must either share a box with $45$ in $A_2$, or share a box with $36$ in $A_3$ (or both).

If $7$ shares a box with $45$ then since you need to split $(7,2,3)$ the $7$ must share the box with $14$ in $A_3$; but then $(1,4,7)$ is unsplit. If $7$ shares a box with $35$ then since you need to split $(7,1,4)$ the $7$ must share the box with $23$ in $A_2$; but then $(2,3,7)$ is unsplit. Therefore, $k(7) > 3$.

Then $k(7) = 4$; here is an example $S_7$: $$ S_7 = \left\{ \matrix{(123|45|67) \\ (124|36|57) \\ (246|17|35)\\ (135|467|2) }\right\} $$ This is beginning to remind me of Ramsey theory. I would now be very surprised if $k(n)$ can be shown to grow logarithmically with $n$, but sub-linear growth is not out of the question.