## 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