Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates

Let \(\textbf{G}:=(G_1, G_2, G_3)\) $\mathbf{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 \(\textbf{G}\) $\mathbf{G}$ is a triple of edges \((e_1, e_2, e_3)\) $(e_1,e_2,e_3)$ with \(e_i\in G_i\) $e_i\in G_i$ for each i and \(\{e_1, e_2, e_3\}\) $\{e_1,e_2,e_3\}$ forming a triangle in V. The triples \(\textbf{G}\) $\mathbf{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 \((\alpha _1, \alpha _2, \alpha _3)\) $({\alpha }_1,{\alpha }_2,{\alpha }_3)$ such that if \(\vert E(G_i)\vert > \alpha _i n^2\) $|E(G_i)|>{\alpha }_i{n}^2$ for each i and n is sufficiently large, then \(\textbf{G}\) $\mathbf{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.