Many disjoint monochromatic triangles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
Problem (proposed by Erdös, Faudree and Ordman [1])
Let \(f(n)\) denote the smallest integer satisfying the property that if we \(2\)color the edges of \(K_n\), there are at least \(f(n)\) edgedisjoint monochromatic triangles. Is it true that \[f(n)= (1+o(1)) \frac{n^2}{12} ?\]In 2004, Keevash and Sudakov has made significant progress on this problem. Using a fractional approach to the problem, they proved that for sufficiently large \( n\) with \( f(n) > \frac{n^2}{12.89} + o(n^2)\). Their approach further generalizes for counting monochromatic \( K_k\) [2].
In [1], Erdös, Faudree, and Ordman also propsosed:
Problem (proposed by Erdös, Faudree, and Ordman [1])
Let \(g(n)\) denote the smallest integer satisfying the property that if we \(2\)color the edges of \(K_n\), there are at least \(g(n)\) edgedisjoint monochromatic triangles all having the same color. Prove that \[ g(n)= (1+o(1)) \frac{n^2}{24}? \]This question differs from the previous one as, here, \( g(n)\) only considers monochromatic triangles of one color. Specifically, it conjectures that if the first conjecture holds then the monochromatic triangles are roughly equally split among the the two colors. As 2011, there has been little progress on the later problem.
Bibliography  

1  P. Erdös , Some recent problems and results in graph theory, Discrete Math. 164 (1997), 8185. 
2  P. Keevash and B. Sudakov. Packing triangles in a graph and its complement Journal of Graph Theory 47 (2004) 203216
