Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777609 | Journal of Combinatorial Theory, Series B | 2017 | 31 Pages |
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=4k for all kâ¥0. These results imply that limâ¡F(n)(n3)=0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
József Balogh, Ping Hu, Bernard Lidický, Florian Pfender, Jan Volec, Michael Young,