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

Victor Falgas-Ravry, Eero Räty, Klas Markström

Abstract: Let

m a t h b f 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

m a t h b f G

is a triple of edges

(e_{1}, e_{2}, e_{3})

with

e_{i} i n G_{i}

for each

i

and

e_{1}, e_{2}, e_{3}

forming a triangle in

V

. The triples

m a t h b f 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

(a l p h a_{1}, a l p h a_{2}, a l p h a_{3})

such that if

v e r t E (G_{i}) v e r t > a l p h a_{i} n^{2}

for each

i

and

n

is sufficiently large, then

m a t h b f G

must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and v{S}'amal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Gy"ori, He, Lv, Salia, Tompkins, Varga and Zhu.

This page was built for publication: Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508223)