# Joel Spencer

DIMACS Center - Rutgers University
CoRE Building, 1st Floor Lecture Hall
Piscataway, New Jersey
Friday, November 10, 1995
11:00 AM

## Topic of Discussion

ALMOST ALWAYS, ALMOST NEVER, RARELY IN BETWEEN

## Abstract:

Random graphs G(n,p) have from the outset been considered in an evolutionary way: as the adjacency probability p evolves (from zero to one) the random graph on n vertices evolves from empty to full.

The ``interesting regions'' of p are functions of n: connectivity occurs at Theta((ln n)/n) triangles appear at Theta(1/n), the diameter becomes two at Theta(square.root{(ln n)/n}), and so forth. For interesting properties A there always seems to be a sharp threshold phenomenon: The probability f_{n,A}(p) that A holds in G(n,p) moves from near zero to near one (or visa versa) in a very short interval around a threshold function p=p(n) of particular form.

The classic results of Glebskii et.al. and Fagin give that for p=1/2 and A any first order property, f_{n,A}(p) is near zero or near one. Roughly speaking, p=1/2 is a boring place where no threshold phenomena are occuring. We now look more generally at p=p(n). Where are the interesting places -- those p=p(n) that are threshold functions for some first order property A? At such threshold functions, such as p=c/n, how can f_{n,A}(p) behave? Given A, how can its spectra of threshold functions be characterized? For random graphs and, to a lesser degree, for other random structure there are now fairly complete answers.