Transversal and colorful versions of Mantel’s theorem

A classical result of Mantel states that every graph of density larger than 1/2 contains a triangle, and this result is best possible.  In this talk, we study two Mantel-inspired problems: the first one asks what is the minimum $d$ such that any triple of graphs $G_1, G_2, G_3$ on the same vertex-set all of density larger than d contains a transversal triangle, i.e., three edges $uv,vw,wu$ in $G_1,G_2,G_3$, respectively. We show that $d = (52 - 4\sqrt{7}) / 81$ suffices, which is asymptotically best possible witnessed by a construction discovered by Aharoni and DeVos. Moreover, their construction is asymptotically the only extremal configuration. The second problem, which is due to DeVos, McDonald and Montejano, states that every $k$-edge-colored graph where each color class has density more than $1/(2k-1)$ contains a non-monochromatic triangle.

This talk is based on joint works with E. Culver, B. Lidicky, F. Pfender and S. Norin.