DIMACS TR: 97-06

Erdos and Renyi Conjecture

Author: Saharon Shelah


Affirming a conjecture of Erdos and R\'enyi we prove that for any $c_1 > 0$ for some $c_2 > 0$, if a graph $G$ has no $c_1\ \ \log n$ nodes on which the graph is complete or edgeless (i.e. $G$ exemplifies $|G| \nrightarrow (c_1 \text{ log } n)^2_2$) \underbar{then} $G$ has at least $2^{c_2n}$ non-isomorphic (induced) subgraphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-06.ps.gz
DIMACS Home Page