An extension of Turán's theorem, uniqueness and stability

MaRDI QIDQ463041zbMATH OpenFDO

Authors Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguet

Publication date 23 October 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph theoryTuran's theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: We determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $MsubsetV(G)$. For $(r-1)|M|gen$, the $(r-1)$-partite Turan graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.

Recommendations

• Exact stability for Turán's theorem
• Extension of Turán's theorem to the 2-stability number
• scientific article; zbMATH DE number 16062
• scientific article; zbMATH DE number 4202285
• An extension of a uniform asymptotic stability theorem by Matrosov
• A Generalization of the Turán Theorem and Its Applications
• An extension of a uniqueness theorem of J. A. Goldstein
• scientific article; zbMATH DE number 492678
• Some Stability and Exact Results in Generalized Turán Problems
• scientific article; zbMATH DE number 1489892

Cites work

• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• A Density Corrádi–Hajnal Theorem
• Large generalized books are \(p\)-good
• Stability for large forbidden subgraphs
• The number of graphs without forbidden subgraphs
• Turánnical hypergraphs

Cited in

(4)

• A new Turán-type theorem for cliques in graphs
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Large joints in graphs
• Extremal graphs for intersecting cliques

This page was built for publication: An extension of Turán's theorem, uniqueness and stability

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