Partitions that separate all triples

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$

Here is a deterministic algorithm to achieve $O(\log n)$.

We will build the solution adding partitions one at a time. Say currently we have the partitions $P_1, P_2, \ldots, P_r$. Call a triplet $(x, y, z) $ satisfied if there exists a partition $P_i$ in which $x, y, z$ belong to different sets. Say we currently have $T$ unsatisfied triplets. We'll prove that there exists a deterministic way to find a partition $P_{r + 1}$ which splits atleast $\frac{T}{8}$ of these unsatisfied triplets.

First, we create a bipartition $(U, V)$ such that atleast $\frac{T}{4}$ of the unsatisfied triplets have exactly one element in $U$. To do this, add elements one by one in arbitrary order. When adding $x$, add it to the side which has lesser number of pairs $(y, z)$ such that both $y$ and $z$ have been processed and $(x, y, z)$ is an unsatisfied triple, breaking ties arbitrarily.

Note that, from the added vertices, we will always have lesser unsatisfied triplets with all elements on the same side than those not having all elements on the same side. So, in the end we have atleast $\frac{T}{2}$ unsatisfied triplets which have exactly one element in $U$ and exactly two elements in $V$ or vice-versa.

WLOG, we can assume that $E \geq \frac{T}{4} $ triplets have exactly one element in $U$ and two in $V$. Consider a multigraph $G$ with the vertex set $V$. For each unsatisfied triplet $(x, y, z)$ with $x \in U$ and $y, z \in V$, add an edge $(y, z)$ to $G$. We have $E \geq \frac{T}{4}$ edges in $G$. Find a cut in $G$ using a similar greedy algorithm, adding vertices one by one to the side having lesser neighbors. This cut (say $(V_1, V_2)$) has $\geq \frac{E}{2} \geq \frac{T}{8} $ edges.

Clearly, after adding the partition {$U, V_1, V_2$}, we have $\leq \frac{7T}{8}$ unsatisfied triplets left. We continue till all triplets are satisfied. Clearly, this uses $O(\log n)$ partitions.