Time:  12:00  13:20 
Room: 
Wean Hall 7201

Speaker: 
Simi Haber CMU 
Title: 
Extending the first order language of graph theory by natural graph properties

Abstract: 
In this talk I will present results regarding zeroone laws for extensions of the first order language of graphs. The language of (simple) graphs is the first order language with a single binary relation. The theory of (simple) graphs asserts that this relation is irreflexive and symmetric Let p be a constant between zero and one. The random binomial graph G(n,p) has the set [n]={1,2,...,n} as its vertex set and any potential edge is in the graph with probability p, independently of all other edges. We say that a language 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 the zeroone law if this limit is always either zero or one. Glebskii et al and independently Fagin showed that the zeroone law holds for the first order language of graphs. There are numerous results dealing with zeroone laws and limit laws for other logics. 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 zeroone law (or a limit law)? Natural candidates for P are connectivity, kcolorability and Hamiltonicity. We provide the following answers. There is a language able to express first order properties, connectivity and kcolorability for any finite k, while still obeying the zeroone law. On the other hand, for any language stronger than the first order language that is able to express Hamiltonicity the limit law fails. The results described are based on joint work with Saharon Shelah. 