Abstract
In the classical theory of random graphs and structures the properties of interest are typically both uniformly definable and invariant under isomorphisms: connectivity, size and number of components, chromatic number, Hamiltonicity, degree sequence, substructure occurrences and counts, etcetera. It is thus natural to ask, for the different models of random structures, whether the logical complexity it takes to defining such properties has any influence on their asymptotic probability. In this lecture we will start by discussing and proving the first and best known case with a clear and definite answer: the 0-1 law for first-order logic under the uniform probability measure. As we will see, the proof does actually show more and gives also the 0-1 law for several of the fixed-point and infinitary logics at the core of finite model theory. Then we will discuss sparse random graphs and structures, i.e. graphs and structures with a number of edges and tuples that is linear in the number of individual points. Although the theory there is quite different, it still makes sense to study the asymptotic probabilities of logically defined properties. While first-order logic still has a clear and definite answer in this case, fixed-point and infinitary logics are much more challenging and many questions remain open.