Rainbow triangles in three-colored graphs

József Balogh, Ping Hu, Bernard Lidický, Florian Pfender, Jan Volec, Michael Young

Research output: Contribution to journalArticlepeer-review

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 lim⁡F(n)(n3)=0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.

Original languageEnglish (US)
Pages (from-to)83-113
Number of pages31
JournalJournal of Combinatorial Theory. Series B
Volume126
DOIs
StatePublished - Sep 2017

Keywords

  • Flag algebra
  • Rainbow colorings
  • Subgraph density

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Rainbow triangles in three-colored graphs'. Together they form a unique fingerprint.

Cite this