A rainbow version of Mantel's Theorem

Mantel's Theorem from 1907 is one of the oldest results in graph theory: every simple $n$-vertex graph with more than $\frac{1}{4}n^2$ 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 $G_1$ and $G_2$ on the same set of $n$ vertices, each containing more than $\frac{1}{4}n^2$ edges, give rise to a triangle with one edge from $G_1$ and two edges from $G_2$. The situation is however different for three colors. Fix $\tau=\frac{4-\sqrt{7}}{9}$ and split the $n$ vertices into three sets $A$, $B$ and $C$, such that $|B|=|C|=\lfloor\tau n\rfloor$ and $|A|=n-|B|-|C|$. The graph $G_1$ contains all edges inside $A$ and inside $B$, the graph $G_2$ contains all edges inside $A$ and inside $C$, and the graph $G_3$ contains all edges between $A$ and $B\cup C$ and inside $B\cup C$. It is easy to check that there is no triangle with one edge from $G_1$, one from $G_2$ and one from $G_3$; each of the graphs has about $\frac{1+\tau^2}{4}n^2=\frac{26-2\sqrt{7}}{81}n^2\approx 0.25566n^2$ edges. The main result of the article is that this construction is optimal: any three graphs $G_1$, $G_2$ and $G_3$ on the same set of $n$ vertices, each containing more than $\frac{1+\tau^2}{4}n^2$ edges, give rise to a triangle with one edge from each of the graphs $G_1$, $G_2$ and $G_3$. A computer-assisted proof of the same bound has been found by Culver, Lidický, Pfender and Volec.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.