Princeton Discrete Math Seminar


Title:

Rigid Extensions and Zero-One Laws

Speaker:

Joel Spencer
Courant Institute and Institute for Advanced Study

Place:

Fine Hall 214
Princeton University

Time:

3:00 pm -
Thursday, March 13, 1997
Abstract:

A rooted graph is a (finite) graph with a designated set of roots and corresponds naturally to an extension statement: a triangle with a designated root corresponds to the sentence ``every vertex belongs to a triangle". We split rooted graphs into dense and sparse depending on whether their ratio of edges to vertices exceeds a prescribed irrational value. This yields to an notion of rigidity [roughly, dense all over] that has intriguing properties and leads to the Zero-One Law [plus some open problems] on $G\sim G(n,p)$, $p=n^{-\alpha}$, $\alpha$ irrational.


Document last modified on March 11, 19997