Umeå University's logo

Let G:=(G₁,G₂,G₃) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in G is a triple of edges (e₁,e₂,e₃) with e_i ∈ G_i for each i and {e₁,e₂,e₃} forming a triangle in V. The triples 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 (α₁,α₂,α₃) such that if |E(G_i)| >α_in² for each i and n is sufficiently large, then 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.