Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-08T18:29:20.208Z Has data issue: false hasContentIssue false

Local Density in Graphs with Forbidden Subgraphs

Published online by Cambridge University Press:  17 March 2003

PETER KEEVASH
Affiliation:
Department of Mathematics, Cambridge University, Cambridge, England and Department of Mathematics, Princeton University, Princeton, NJ 08540, USA (e-mail: keevash@math.princeton.edu)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08540, USA and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: bsudakov@math.princeton.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A celebrated theorem of Turán asserts that every graph on n vertices with more than $\frac{r\,{-}\,1}{2r}n^2$ edges contains a copy of a complete graph $K_r+1$. In this paper we consider the following more general question. Let G be a $K_r+1-free graph of order n and let α be a constant, 0<α≤1. How dense can every induced subgraph of G on αn vertices be? We prove the following local density extension of Turán's theorem.

For every integer $r\geq 2$ there exists a constant $c_r < 1$ such that, if $c_r < \alpha < 1$ and every αn vertices of G span more than

\[\frac{r\,{-}\,1}{2r}(2\alpha -1)n^2\vspace*{7pt}\]

edges, then G contains a copy of $K_r+1$. This result is clearly best possible and answers a question of Erdős, Faudree, Rousseau and Schelp [5].

In addition, we prove that the only $K_r+1-free graph of order n, in which every αn vertices span at least $\frac{r\,{-}\,1}{2r}(2\alpha -1)n^2$ edges, is a Turán graph. We also obtain the local density version of the Erdős–Stone theorem.

Information

Type
Research Article
Copyright
2003 Cambridge University Press