A graph property is first order expressible if it can be written as a formal sentence using the universal and existential quantifiers with variables ranging over the vertices of the graph, the usual connectives and the relations $=$ and $\sim$, where $x\sim y$ stands for adjacency. First order expressible properties have been studied using random models, that is, by looking into the possible behavior of first order properties given a probability space of graphs, e.g., $G(n,p)$. For example, it is known that in $G(n,1/2)$ every first order expressible graph property has limiting probability zero or one, a phenomenon called the $0-1$ law. Since many natural graph properties are not first order expressible, there has been an effort to extend first order logic while maintaining the $0-1$ law. Along the years a number of very attractive and surprising results have been obtained. I will present some of these results and two tools enabling a new taxonomy of graph properties. No background in logic will be assumed.
Joint work with Saharon Shelah.