A rainbow version of Mantel's Theorem
Advances in Combinatorics · 2020
DOI: 10.19086/aic.12043 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Combinatorics, 2020. Verfasst von Robert Šámal und 4 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref).
Abstract (Originalsprache)
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.
Zitieren
APA
Šámal, R., Montejano, A., Maza, S. G. H. D. L., DeVos, M., & Aharoni, R. (2020). A rainbow version of Mantel's Theorem. Advances in Combinatorics. https://doi.org/10.19086/aic.12043
Vancouver
Šámal R, Montejano A, Maza SGHDL, DeVos M, Aharoni R. A rainbow version of Mantel's Theorem. Advances in Combinatorics. 2020. doi:10.19086/aic.12043
BibTeX
@article{mal2020,
author = {Šámal, Robert and Montejano, Amanda and Maza, Sebastián González Hermosillo de la and DeVos, Matt and Aharoni, Ron},
title = {A rainbow version of Mantel's Theorem},
journal = {Advances in Combinatorics},
year = {2020},
doi = {10.19086/aic.12043}
}
EUVIMED