Multicolor Turán numbers II: A generalization of the Ruzsa–Szemerédi theorem and new results on cliques and odd cycles
Journal of Graph Theory · 2024-11 · 107 (3) · 629-641
DOI: 10.1002/jgt.23147 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 14.07.2024. Verfasst von Benedek Kovács und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 20 Literaturangaben.
Abstract (Originalsprache)
In this paper we continue the study of a natural generalization of Turán's forbidden subgraph problem and the Ruzsa–Szemerédi problem. Let denote the maximum number of edge‐disjoint copies of a fixed simple graph that can be placed on an ‐vertex ground set without forming a subgraph whose edges are from different ‐copies. The case when both and are triangles essentially gives back the theorem of Ruzsa and Szemerédi. We extend their results to the case when and are arbitrary cliques by applying a number theoretic result due to Erdős, Frankl, and Rödl. This extension in turn decides the order of magnitude for a large family of graph pairs, which will be subquadratic, but almost quadratic. Since the linear ‐uniform hypergraph Turán problems to determine form a class of the multicolor Turán problem, following the identity , our results determine the linear hypergraph Turán numbers of every graph of girth 3 and for every up to a subpolynomial factor. Furthermore, when is a triangle, we settle the case and give bounds for the cases , as well.
Zitieren
APA
Kovács, B., & Nagy, Z. L. (2024). Multicolor Turán numbers II: A generalization of the Ruzsa–Szemerédi theorem and new results on cliques and odd cycles. Journal of Graph Theory, 107(3), 629-641. https://doi.org/10.1002/jgt.23147
Vancouver
Kovács B, Nagy ZL. Multicolor Turán numbers II: A generalization of the Ruzsa–Szemerédi theorem and new results on cliques and odd cycles. Journal of Graph Theory. 2024;107(3):629-641. doi:10.1002/jgt.23147
BibTeX
@article{Kovcs2024,
author = {Kovács, Benedek and Nagy, Zoltán Lóránt},
title = {Multicolor Turán numbers II: A generalization of the Ruzsa–Szemerédi theorem and new results on cliques and odd cycles},
journal = {Journal of Graph Theory},
year = {2024},
volume = {107},
number = {3},
pages = {629--641},
doi = {10.1002/jgt.23147}
}
EUVIMED