- To: Joel David Hamkins <hamkins@nylogic.org>
- Subject: Seminar on Logic and Games
- From: Joel David Hamkins <jdh@hamkins.org>
- Date: Wed, 20 Nov 2002 08:17:42 -0500
- Organization: City University of New York
Seminar on Logic and Games
Joel Spencer
Courant Institute - NYU
"The Ehrenfeucht Game on Random Structures"
Monday, November 25, 11 AM to 12:30 PM
Room 9207, CUNY Graduate Center
365 Fifth Avenue
(Fifth Ave and 34th Street)
Abstract: The Ehrenfeucht Game allows a combinatorialist to
show that two models have the same first order properties up
to a given quantifier depth. When applied to random models
it allows one to show a Zero-One Law. How large must n=n(k)
be so that with high probability the Duplicator wins the k
move Ehrenfeucht game? This notion, dubbed tenacity, allows
an analytic exploration of the strength of a Zero-One Law.
Key examples are the random graph G(n,p) (for a variety of
p=p(n)) and the random circular (to avoid edge effects)
bit string U(n,p).