In this talk I will present results regarding zero-one 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 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 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 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.

The results described are based on joint work with Saharon Shelah.