DIMACS TR: 97-11

On the density of subgraphs in a graph with bounded independence number

Author: Pavel Valtr


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