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$
$\endgroup$
5
3 Answers
$\begingroup$
$\endgroup$
5
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}$.
answered Oct 19, 2010 at 11:51
-
$\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$ Oct 19, 2010 at 12:05
-
$\begingroup$ So, I removed the previous wrong claims, and added some observations. $\endgroup$ Oct 20, 2010 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$ Oct 20, 2010 at 3:18
-
1$\begingroup$ Yes that's a nice way of looking at it. :) $\endgroup$ Oct 20, 2010 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$ Oct 20, 2010 at 6:43
$\begingroup$
$\endgroup$
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.
answered Oct 19, 2010 at 12:40
$\begingroup$
$\endgroup$
2
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
answered Oct 19, 2010 at 14:31
-
$\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$ Oct 19, 2010 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$ Oct 19, 2010 at 17:41
$J(3,n)$with the least amount of colors such that no triangle is monochromatic. $\endgroup$