A rainbow version of Mantel’s Theorem
- Department of Mathematics, Technion -- Israel Institute of Technology
- Deparment of Mathematics, Simon Fraser University
- Deparment of Mathematics, Simon Fraser University
- UMDI Facultad de Ciencias, UNAM Juriquilla
- Computer Science Institute, Charles Univeristy
- ORCID iD: 0000-0002-0172-6511
Editorial introduction
Mantel’s Theorem from 1907 is one of the oldest results in graph theory: every simple n-vertex graph with more than 14n2 edges contains a triangle. The theorem has been generalized in many different ways, including other subgraphs, minimum degree conditions, etc. This article deals with a generalization to edge-colored multigraphs, which can be viewed as a union of simple graphs, each corresponding to an edge-color class.
The case of two colors is the same as the original setting: Diwan and Mubayi proved that any two graphs G1 and G2 on the same set of n vertices, each containing more than 14n2 edges, give rise to a triangle with one edge from G1 and two edges from G2. Howere, the situation is different for three colors. Fix τ=4−√79 and split the n vertices into three sets A, B and C, such that |B|=|C|=⌊τn⌋ and |A|=n−|B|−|C|. The graph G1 contains all edges inside A and inside B, the graph G2 contains all edges inside A and inside C, and the graph G3 contains all edges between A and B∪C and inside B∪C. It is easy to check that there is no triangle with one edge from G1, one from G2 and one from G3; each of the graphs has about 1+τ24n2=26−2√781n2≈0.25566n2 edges. The main result of the article is that this construction is optimal: any three graphs G1, G2 and G3 on the same set of n vertices, each containing more than 1+τ24n2 edges, give rise to a triangle with one edge from each of the graphs G1, G2 and G3. A computer-assisted proof of the same bound has been found by Culver, Lidický, Pfender and Volec.