Combinatorics, Probability and Computing



Local Density in Graphs with Forbidden Subgraphs


PETER KEEVASH a1 and BENNY SUDAKOV a2 1
a1 Department of Mathematics, Cambridge University, Cambridge, England and Department of Mathematics, Princeton University, Princeton, NJ 08540, USA (e-mail: keevash@math.princeton.edu)
a2 Department of Mathematics, Princeton University, Princeton, NJ 08540, USA and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: bsudakov@math.princeton.edu)

Abstract

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<α[less-than-or-equal]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 Erdos, 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 Erdos–Stone theorem.

(Received November 1 2001)
(Revised September 28 2002)



Footnotes

1 Supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.