The Erdős-Rényi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph (sometimes known as the countable random graph) that is invariant under arbitrary permutations of the underlying set of vertices. For which other countable structures does such an invariant measure exist?

Until recent work of Petrov and Vershik (2010), the answer was not known even for Henson's countable homogeneous-universal triangle-free graph. We provide a complete characterization of countable structures that admit invariant measures, in terms of the notion of (group-theoretic) definable closure. This leads to new examples, including a complete list of countable homogeneous graphs and partial orders that satisfy our criterion.

Our proof uses infinitary logic to build on Petrov and Vershik's constructions sampling from continuum-sized graphs. In the case that our measure is concentrated on a graph, the continuum sized object we construct is in fact a graph limit in the sense of Lovász and Szegedy (2006).

Joint work with Nate Ackerman and Rehana Patel.