Rainbow triangles in three-colored graphs

摘要

Erdos and Sos proposed the 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 = 4(k) for all k >= 0. These results imply that lim F(n)/((n)(3)) = 0.4, and determine the unique limit object. In the proof we Use flag algebras combined with stability arguments. (C) 2017 Elsevier Inc. All rights reserved.