Rainbow triangles in three-colored graphs
From MaRDI portal
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.
Recommendations
Cites work
- A new lower bound based on Gromov's method of selecting heavily covered points
- A Solution to the 2/3 Conjecture
- Flag algebras
- scientific article; zbMATH DE number 4193744 (Why is no real title available?)
- Hypergraphs do jump
- Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
- Monochromatic triangles in three-coloured graphs
- On the Caccetta-Häggkvist conjecture with forbidden subgraphs
- On the Maximum Induced Density of Directed Stars and Related Problems
- On the maximum number of five-cycles in a triangle-free graph
- On the Minimal Density of Triangles in Graphs
- On the number of pentagons in triangle-free graphs
- polymake: a framework for analyzing convex polytopes
- Rainbow copies of C₄ in edge-colored hypercubes
- The clique density theorem
- The number of cliques in graphs of given order and size
- Turán \(H\)-densities for 3-graphs
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
Cited in
(27)- On Turán numbers of the complete 4-graphs
- Rainbow triangles in arc-colored tournaments
- Disproof of a conjecture on the rainbow triangles in arc-colored digraphs
- Maximum number of almost similar triangles in the plane
- On a colored Turán problem of Diwan and Mubayi
- The Erdős-Hajnal conjecture for rainbow triangles
- Compactness and finite forcibility of graphons
- Frustrated triangles
- Rainbow copies of C₄ in edge-colored hypercubes
- scientific article; zbMATH DE number 5717204 (Why is no real title available?)
- Grünbaum colorings extended to non-facial 3-cycles
- A rainbow version of Mantel's theorem
- Semantic limits of dense combinatorial objects
- Decomposing graphs into edges and triangles
- Closing in on Hill's conjecture
- Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm
- Kruskal-Katona-type problems via the entropy method
- An unsure note on an un-Schur problem
- Maximising the number of properly 2-coloured 4-cycles
- The Rado multiplicity problem in vector spaces over finite fields
- Inducibility of rainbow graphs
- New Ramsey multiplicity bounds and search heuristics
- Rainbow triangles sharing one common vertex or edge
- Rainbow common graphs must be forests
- The four-color Ramsey multiplicity of triangles
- Inducibility of directed paths
- Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
This page was built for publication: Rainbow triangles in three-colored graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399351)
