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



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


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.

Document last modified on November 1, 1995