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$?

  • $\begingroup$ 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. $\endgroup$ – Moshe Schwartz Oct 19 '10 at 11:24
  • 1
    $\begingroup$ What's the source of this problem? (Life will be completely different if it's an olympiad problem of some sort than otherwise.) $\endgroup$ – JBL Oct 19 '10 at 12:49
  • $\begingroup$ 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$? $\endgroup$ – Pietro Majer Oct 19 '10 at 18:05
  • $\begingroup$ Pietro: You're absolutely right. I guess such a coloring provides a lower bound on $m$. $\endgroup$ – Moshe Schwartz Oct 19 '10 at 18:46
  • $\begingroup$ @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 $\endgroup$ – dvitek 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}$.

  • $\begingroup$ 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? $\endgroup$ – Greg Kuperberg Oct 19 '10 at 12:05
  • $\begingroup$ So, I removed the previous wrong claims, and added some observations. $\endgroup$ – Gjergji Zaimi Oct 20 '10 at 2:02
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Tony Huynh Oct 20 '10 at 3:18
  • 1
    $\begingroup$ Yes that's a nice way of looking at it. :) $\endgroup$ – Gjergji Zaimi Oct 20 '10 at 3:25
  • $\begingroup$ 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. $\endgroup$ – 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

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Oct 19 '10 at 14:45
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Oct 19 '10 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.