Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 83-113 |
Number of pages | 31 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 126 |
DOIs | |
State | Published - Sep 2017 |
Keywords
- Flag algebra
- Rainbow colorings
- Subgraph density
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics