The ACO Seminar (2012-2013)

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.