The ACO Seminar (2011-2012)

In this talk I will present results regarding zero-one laws for extensions of the first order language of graphs.   

The first order language of graphs is a formal language in which one may express some properties of graphs.  Let p be a constant between zero and one. We say that a logic L has a limit law if every graph property expressible in L has a limiting probability in G(n,p). We say that L obeys a zero-one law if this limit is always either zero or one. Glebskii et al and independently Fagin showed that the zero-one law holds for the first order language of graphs. There are numerous results dealing with zero-one laws and limit laws for extensions of the first order language.   

A related question asked many times is the following: Given a graph property P, is there a language able to express P while still obeying the zero-one law (or a limit law)? Natural candidates for P are connectivity, k-colorability and Hamiltonicity.  We provide the following answers. There is a language able to express first order properties, connectivity and k-colorability for any finite k, while still obeying the zero-one law. On the other hand, for any language stronger than the first order language that is able to express Hamiltonicity the limit law fails.  

No prior knowledge in logic is assumed. The results described are based on joint work with Saharon Shelah.