DIMACS TR: 97-06
Erdos and Renyi Conjecture
Author: Saharon Shelah
ABSTRACT
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