Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates

12/14/2022

∙

by   Victor Falgas--Ravry, et al.

∙

0

∙

share

Let 𝐆:=(G_1, G_2, G_3) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in 𝐆 is a triple of edges (e_1, e_2, e_3) with e_i∈ G_i for each i and {e_1, e_2, e_3} forming a triangle in V. The triples 𝐆 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_i)|> α_in2 for each i and n is sufficiently large, then 𝐆 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. Further, we investigate a minimum degree variant of our problem, and show the extremal behaviour in that setting is quite different to the one we see in the edge density case.