Every graph is eventually Turán-good

DOI10.1016/J.JCTB.2023.06.004zbMATH Open1519.05134arXiv2208.08499MaRDI QIDQ6170799FDOQ6170799

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)

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.

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

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

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)

Cites Work

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

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)