Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates
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.
READ FULL TEXT