Stability from graph symmetrization arguments in generalized Turán problems

Gerbner, Dániel; Hama Karim, Hilal ✉ [Hama Karim, Hilal (Combinatorics and...), author] Department of Computer Science and Information ... (BUTE / FEEI)

English Article (Journal Article) Scientific
Published: JOURNAL OF GRAPH THEORY 0364-9024 1097-0118 107 (4) pp. 681-692 2024
  • SJR Scopus - Discrete Mathematics and Combinatorics: D1
Identifiers
Subjects:
  • Mathematics
Given graphs (Formula presented.) and (Formula presented.), (Formula presented.) denotes the largest number of copies of (Formula presented.) in (Formula presented.) -free (Formula presented.) -vertex graphs. Let (Formula presented.). We say that (Formula presented.) is F-Turán-stable if the following holds. For any (Formula presented.) there exists (Formula presented.) such that if an (Formula presented.) -vertex (Formula presented.) -free graph (Formula presented.) contains at least (Formula presented.) copies of (Formula presented.), then the edit distance of (Formula presented.) and the (Formula presented.) -partite Turán graph is at most (Formula presented.). We say that (Formula presented.) is weakly F-Turán-stable if the same holds with the Turán graph replaced by any complete (Formula presented.) -partite graph (Formula presented.). It is known that such stability implies exact results in several cases. We show that complete multipartite graphs with chromatic number at most (Formula presented.) are weakly (Formula presented.) -Turán-stable. Partly answering a question of Morrison, Nir, Norin, Rzażewski, and Wesolek positively, we show that for every graph (Formula presented.), if (Formula presented.) is large enough, then (Formula presented.) is (Formula presented.) -Turán-stable. Finally, we prove that if (Formula presented.) is bipartite, then it is weakly (Formula presented.) -Turán-stable for (Formula presented.) large enough. © 2024 Wiley Periodicals LLC.
Citation styles: IEEEACMAPAChicagoHarvardCSLCopyPrint
2024-12-12 19:09