Oct 4, 3:30pm, Wean 8220

Simcha Haber, CMU

An extension of the Ehrenfeucht Fraisse game with random graphs applications

Simcha Haber, CMU

An extension of the Ehrenfeucht Fraisse game with random graphs applications

Abstract:

Consider a formal language L able to describe some properties of
graphs, and a sequence of random graphs G(n). If for any L-property P,
the probability that G(n) has P tends either to one or to zero, we say
that the 0-1 law holds for (L,G(n)). Studying 0-1 laws serves to get a
better understanding of the logic L and of the random graph G(n). The
Ehrenfeucht Fraisse game is a model theoretic tool that is commonly
used in this field when the logic under discussion is the first order
logic. We will present an extension of this game and its relation to
logics with Lindstrom quantifiers. We will then use the game to
describe some new results and to give new proofs for known theorems.