Article
Rainbow triangles in three-colored graphs
Journal of Combinatorial Theory, Series B
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
9-1-2017
DOI
10.1016/j.jctb.2017.04.002
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)/((n)(3)) = 0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Inc.
Copyright Date
2017
Language
en
File Format
application/pdf
Citation Information
József Balogh, Ping Hu, Bernard Lidicky, Florian Pfender, et al.. "Rainbow triangles in three-colored graphs" Journal of Combinatorial Theory, Series B Vol. 126 (2017) p. 83 - 113 Available at: http://works.bepress.com/bernard-lidicky/39/
This is a manuscript of an article published as Balogh, József, Ping Hu, Bernard Lidický, Florian Pfender, Jan Volec, and Michael Young. "Rainbow triangles in three-colored graphs." Journal of Combinatorial Theory, Series B (2017): 83-113. doi: 10.1016/j.jctb.2017.04.002. Posted with permission.