Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates
Combinatorica · 2024-10 · 44 (5) · 977-1010
DOI: 10.1007/s00493-024-00102-6 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorica, online erschienen am 29.04.2024. Verfasst von Victor Falgas-Ravry und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Umea University.
Abstract (Originalsprache)
Let $$\textbf{G}:=(G_1, G_2, G_3)$$ 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 $$\textbf{G}$$ G is a triple of edges $$(e_1, e_2, e_3)$$ ( e 1 , e 2 , e 3 ) with $$e_i\in G_i$$ e i ∈ G i for each i and $$\{e_1, e_2, e_3\}$$ { e 1 , e 2 , e 3 } forming a triangle in V . The triples $$\textbf{G}$$ 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 $$(\alpha _1, \alpha _2, \alpha _3)$$ ( α 1 , α 2 , α 3 ) such that if $$\vert E(G_i)\vert > \alpha _i n^2$$ | E ( G i ) | > α i n 2 for each i and n is sufficiently large, then $$\textbf{G}$$ G must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and Šámal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Győri, He, Lv, Salia, Tompkins, Varga and Zhu.
Förderung
- Umea University
Zitieren
APA
Falgas-Ravry, V., Markström, K., & Räty, E. (2024). Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates. Combinatorica, 44(5), 977-1010. https://doi.org/10.1007/s00493-024-00102-6
Vancouver
Falgas-Ravry V, Markström K, Räty E. Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates. Combinatorica. 2024;44(5):977-1010. doi:10.1007/s00493-024-00102-6
BibTeX
@article{FalgasRavry2024,
author = {Falgas-Ravry, Victor and Markström, Klas and Räty, Eero},
title = {Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates},
journal = {Combinatorica},
year = {2024},
volume = {44},
number = {5},
pages = {977--1010},
doi = {10.1007/s00493-024-00102-6}
}
EUVIMED