Rainbow triangles in three-colored graphs
arXiv:1408.5296 · doi:10.1016/j.jctb.2017.04.002
Abstract
Erdos and Sos proposed a 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. These results imply that lim F(n) n^3/6 = 0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.
arXiv comment27 pages
References in corpus (9)
- On the Number of Pentagons in Triangle-Free Graphs
- The Clique Density Theorem
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
- Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
- Minimum number of monotone subsequences of length 4 in permutations
- A new lower bound based on Gromov's method of selecting heavily covered points
- Counting flags in triangle-free digraphs
- Turán densities of hypercubes
- The inducibility of small oriented graphs
Cited by in corpus (14)
- Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
- Inducibility of directed paths
- Solving Turán's Tetrahedron Problem for the -Norm
- Polynomial to exponential transition in Ramsey theory
- Semantic Limits of Dense Combinatorial Objects
- Closing in on Hill's conjecture
- Decomposing graphs into edges and triangles
- Kruskal--Katona-Type Problems via the Entropy Method
- Maximum Number of Almost Similar Triangles in the Plane
- Asymptotics of Ramsey numbers of double stars
- Anti-Ramsey Multiplicities
- On Turán numbers of the complete -graphs
- Frustrated Triangles
- Inducibility of rainbow graphs