We say that a graph property is expressible in the "first order language of graphs" if it can be written as a logic sentence using the universal and existential quantifiers with variables ranging over the nodes of the graph, the usual connectives AND, OR, NOT, parentheses and the relations = and ~, where x ~ y means that x and y share an edge. For example, the property that G contains a triangle can be written as
Exists x,y,z : (x ~ y) AND (x ~ z) AND (y ~ z).A classical result of Glebskii et al. 1969 and indepently Fagin 1976 states that if one samples a graph on n vertices uniformly at random from all such graphs then every first order expressible graph property holds with probability tending to either zero or one (as n tends to infinity). Since then, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdos-Renyi model.
After describing some of these results, time permitting, I will discuss some recent and ongoing work where we try to see what happens both in other models of random graphs (such as random planar graphs, random perfect graphs, random geometric graphs, ...) and when one considers other (i.e. "higher order") logics.
(Based on joint works with S. Haber, P. Heinig, T. Luczak, M. Noy, A. Taraz)