Every graph is eventually Turán-good

DOI10.1016/J.JCTB.2023.06.004MaRDI QIDQ6170799zbMATH OpenFDO

Authors Natasha Morrison, JD Nir, Serguei Norine, Paweł Rzążewski, Alexandra Wesolek

Publication date 10 August 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.08499

zbMATH Keywords

extremal graph theorygeneralized Turán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: Let $H$ be a graph. We show that if $r$ is large enough as a function of $H$, then the $r$-partite Tur'an graph maximizes the number of copies of $H$ among all $K_{r+1}$-free graphs on a given number of vertices. This confirms a conjecture of Gerbner and Palmer.

Recommendations

• On Turán-good graphs
• Some results on k-Turán-good graphs
• Turan's Graph Theorem
• scientific article; zbMATH DE number 2237374
• An extremal property of Turán graphs
• scientific article; zbMATH DE number 3819765
• Hadwiger's conjecture is true for almost every graph
• On the Turán properties of infinite graphs
• Turán's theorem and k‐connected graphs
• scientific article; zbMATH DE number 1833098

Cites work

• scientific article; zbMATH DE number 3222643 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3298603 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Many \(T\) copies in \(H\)-free graphs
• Maximizing five-cycles in \(K_r\)-free graphs
• On complete subgraphs of different orders
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• On the number of pentagons in triangle-free graphs
• On the structure of linear graphs
• Paths are Turán-good
• Pentagons vs. triangles
• Some exact results for generalized Turán problems
• Some sharp results on the generalized Turán numbers
• Subgraph densities in \(K_r\)-free graphs
• Supersaturation for subgraph counts

Cited in

(5)

• On triangle-free graphs maximizing embeddings of bipartite graphs
• A localized approach to generalized Turán problems
• On extremal values of some degree-based topological indices with a forbidden or a prescribed subgraph
• Stability from graph symmetrization arguments in generalized Turán problems
• On generalized Turán numbers of intersecting cliques

This page was built for publication: Every graph is eventually Turán-good

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170799)