EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates

Victor Falgas-Ravry, Klas Markström, Eero Räty

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →