# partitioning the 3-sets of [n]={1,…,n} into families

Let $F_1,...,F_m$ be a partition of the 3-element subsets of $[n]$ into families such that no three subsets in any one family $F_i$ are all contained in one 4-element subset of $[n]$. What is the minimum value of $m$?

-
I don't know if this helps, but this is equivalent to coloring the vertices of the Johnson graph $J(3,n)$ with the least amount of colors such that no triangle is monochromatic. –  Moshe Schwartz Oct 19 '10 at 11:24
What's the source of this problem? (Life will be completely different if it's an olympiad problem of some sort than otherwise.) –  JBL Oct 19 '10 at 12:49
Moshe: I'm not sure if I get it. Do you mean colors = the classes of the partition? But e.g. isn't {1,2,3} {1,2,4} {1,2,5} a triangle in J(3,n) although these three sets are allowed to be in the same $F_i$? –  Pietro Majer Oct 19 '10 at 18:05
Pietro: You're absolutely right. I guess such a coloring provides a lower bound on $m$. –  Moshe Schwartz Oct 19 '10 at 18:46
@JBL: Methinks this is a bit too hard to be an olympiad problem, unless the answer turns out to be 2 for all $n$. :P –  drvitek Oct 19 '10 at 22:20

Tony Huynh's update can be easily generalized to show that $$n\geq k\left(R(\underbrace{3,3,\dots,3}_{k-1})-1\right)+3\implies m\geq k$$ and so we get a very weak lower bound on $m$ which at least shows that $m _{min}\to \infty$.

For an easy upper bound $m_{min}\le \lfloor\frac{n+1}{2}\rfloor$, which you can see by partitioning the triples $(a,b,c)$ in classes according to $a+b+c\pmod{\lfloor\frac{n+1}{2}\rfloor}$.

-
For the lower bound, are you requiring that no three triples lie in a 4-tuple, or that no three triples lie in a 5-tuple? –  Greg Kuperberg Oct 19 '10 at 12:05
So, I removed the previous wrong claims, and added some observations. –  Gjergji Zaimi Oct 20 '10 at 2:02
Thanks Gjergji. Just to make sure that I am following, doesn't $n \geq R(\underbrace{3,3,\dots,3}_{k-1})+1$ imply that $m \geq k$. That is, if $(F_1, \dots, F_{k-1})$ is a partition of the 3-sets of $[n]$, then we automatically get a $(k-1)$ edge-colouring of $K_{n-1}$ by looking at how the 3-sets containing $n$ are distributed among $F_1, \dots, F_{k-1}$. –  Tony Huynh Oct 20 '10 at 3:18
Yes that's a nice way of looking at it. :) –  Gjergji Zaimi Oct 20 '10 at 3:25
Thanks, Gjergji, that's a very elegant argument for an upper bound of (n+1)/2. For those who asked, this question does not come from an olympiad, it came up in the course of researching a problem in discrete geometry. –  Moti Novick Oct 20 '10 at 6:43

For a crude lower bound, one can consider the largest possible size for a set in your partition. One candidate is to take a collection of 2-subsets of $[2n]$,which are triangle-free and then add the point $2n+1$ to each 2-subset. By Turan's theorem, we get a collection of $n^2$ triples, such that the union of any three is not a 4-set. This is not best possible, but perhaps it is of the right order.

Update. I believe that $m >2$ for all $n \geq 7$.

Proof. Towards a contradiction, let $(F_1, F_2)$ be a partition of the 3-sets of $[n]$, such that the union of any three members of $F_i$ is not a 4-set. Consider the 3-sets of the form $(1,2,k)$. We may assume that $F_1$ contains at least half of these sets, and since $n \geq 7$, it contains at least 3 sets of this form. By relabelling, we may assume that $(1,2,3), (1,2,4)$, and $(1,2,5)$ are each in $F_1$. But this means that $(2,3,4)$, $(2,3,5)$, and $(2,4,5)$ are each not in $F_1$, and hence in $F_2$, a contradiction.

-

In their investigations into Frankl's union closed sets conjecture, Theresa Vaughn and some of her colleagues considered such configurations of three sets. I think they were more interested in the size of F_1 than in m. You might ask her about this problem.

My take on it is that m can be made small, perhaps even m=2, by arranging the 3-sets in cycles. When I get back to Frankl's problem, I may have more to say.

Gerhard "Ask Me About System Design" Paseman, 2010.10.19

-
Although m=2 seems optimistic, it feels as if I can take the answer for n=5 and replicate it somehow. If I haven't miscalculated, m=2 for n = 4,5, and 6, and I suspect the idea works for n=7 as well. Gerhard "Ask Me About System Design" Paseman, 2010.10.19 –  Gerhard Paseman Oct 19 '10 at 14:45
Perhaps we can add my and Tony's suggestions together. Suppose we have a 2-partition of the 3-sets of an n-set. Now look at the three sets which contain point n+1 and two of the other n points. Perhaps there is a way to divide those n choose 2 sets into the two groups. For example, any four-set containing point n+1 has one of the 3-subsets in the partition already, so divide the other 3 3-sets appropriately among the two partitions. When I see how to resolve potential conflicts, I will add that to the post. Gerhard "Hand Waving is Our Trademark" Paseman, 2010.10.19 –  Gerhard Paseman Oct 19 '10 at 17:41