Rainbow triangles in three-colored graphs

Abstract

Erdos and Sos proposed a problem of determining the maximum number F(n) of rainbow triangles in 3-edge-colored complete graphs on n vertices. They conjectured that F(n) = F(a)+ F(b)+F(c)+F(d)+abc+abd+acd+bcd, where a+b+c+d = n and a, b, c, d are as equal as possible. We prove that the conjectured recurrence holds for sufficiently large n. We also prove the conjecture for n = 4k for all k. These results imply that lim F(n) n^3/6 = 0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.

27 pages

References in corpus (2)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Minimum number of monotone subsequences of length 4 in permutations

Cited by in corpus (14)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Inducibility of directed paths
• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm
• Polynomial to exponential transition in Ramsey theory
• Semantic Limits of Dense Combinatorial Objects
• Closing in on Hill's conjecture
• Decomposing graphs into edges and triangles
• Kruskal--Katona-Type Problems via the Entropy Method
• Maximum Number of Almost Similar Triangles in the Plane
• Asymptotics of Ramsey numbers of double stars
• Anti-Ramsey Multiplicities
• On Turán numbers of the complete $4$-graphs
• Frustrated Triangles
• Inducibility of rainbow graphs