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

## ABOUT THE SPEAKER:

Joel Spencer is a Professor of Mathematics and Computer Science at the
Courant Institute of New York University. A disciple of Paul Erd"os,
he works in probabilistic methods, combining discrete mathematics and
probability theory. His involvement with logic began with joint work
with Saharon Shelah on Zero-One Laws. He is the coauthor of Ramsey
Theory and, more recently, The Probabilistic Method and is co-founder
of the journal Random Structures and Algorithms.

dimacs-www@dimacs.rutgers.edu
Document last modified on November 1, 1995