Time:  12:00  13:20 
Room: 
Wean Hall 7201

Speaker: 
Cameron Freer Computer Science and Artificial Intelligence Laboratory MIT 
Title: 
Invariant measures concentrated on countable structures

Abstract: 
The ErdősRé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 homogeneousuniversal trianglefree graph. We provide a complete characterization of countable structures that admit invariant measures, in terms of the notion of (grouptheoretic) 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 continuumsized 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. 