# 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