Let G:=(G₁, G₂, G₃) G : = ( G 1 , G 2 , G 3 ) be a triple of graphs on the same vertex set V of size n . A rainbow triangle in G G is a triple of edges (e₁, e₂, e₃) ( e 1 , e 2 , e 3 ) with eᵢ∈ Gᵢ e i ∈ G i for each i and ₁, e₂, e₃\ { e 1 , e 2 , e 3 } forming a triangle in V . The triples G G not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities (α ₁, α ₂, α ₃) ( α 1 , α 2 , α 3 ) such that if E(Gᵢ) > α ᵢ n² | E ( G i ) | > α i n 2 for each i and n is sufficiently large, then G G must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and Šámal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Győri, He, Lv, Salia, Tompkins, Varga and Zhu.
No takes yet. Share an insight, caveat, or question.
Falgas–Ravry et al. (2024) studied this question.