Résumé | We look at properties of graphs that can be expressed in first order (FO) logic. Given such a property A and a class G of random graphs, we are interested in the limiting probability that a graph in G satisfies A, when the number of vertices goes to infinity.
First we survey what is known for the classical model G(n,p), including zero-one laws and the celebrated theorem of Shelah and Spencer. Then we move to classes of graphs defined by a global condition, such as being acyclic or planar, under the uniform distribution. We survey recent results on zero-one laws, convergence laws, and non-convergence phenomena, both in FO and in the stronger monadic second order (MSO) logic. In particular, for graphs embeddable in a fixed surface other than the sphere, there is a striking difference between the results in FO and MSO logic. |