Princeton Discrete Math Seminar


Rigid Extensions and Zero-One Laws


Joel Spencer
Courant Institute and Institute for Advanced Study


Fine Hall 214
Princeton University


3:00 pm -
Thursday, March 13, 1997

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