Erdős and Sós 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 limF(n)(n3)=0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.
- Flag algebra
- Rainbow colorings
- Subgraph density
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics