DIMACS TR: 97-11
On the density of subgraphs in a graph
with bounded independence number
Author: Pavel Valtr
ABSTRACT
Let $\sigma(n,m,k)$ be the largest number $\sigma\in[0,1]$
such that any graph on $n$ vertices with independence
number at most $m$ has a subgraph on $k$ vertices with at least
$\sigma\cdot{k\choose 2}$ edges.
Up to a constant multiplicative factor, we determine $\sigma(n,m,k)$
for all $n,m,k$.
For $\log n\le m=k\le n$, our result gives
$\sigma(n,m,m)=\Theta({\log(n/m)\over m})$, which
was conjectured by Alon.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-11.ps.gz
DIMACS Home Page