Name
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 limF(n)(n3)=0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jctb.2017.04.002 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Subgraph density,Flag algebra,Rainbow colorings | Journal | 126 |
ISSN | Citations | PageRank |
0095-8956 | 2 | 0.42 |
References | Authors | |
11 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Ping Hu | 2 | 32 | 4.05 |
| Bernard Lidický | 3 | 9 | 5.00 |
| Florian Pfender | 4 | 285 | 30.96 |
| Jan Volec | 5 | 40 | 8.27 |
| Michael Young | 6 | 16 | 4.39 |