Mar 29, 3:30pm, Wean 8220

Cameron Freer, MIT

Model-theoretic constructions of Limit Structures

Cameron Freer, MIT

Model-theoretic constructions of Limit Structures

Abstract:

The Rado graph admits a natural probabilistic construction, by
independently flipping a weight-p coin to determine each edge, for any
fixed 0 < p < 1. This random graph is exchangeable, in the sense that
the joint distribution on edges is invariant to permutations of the
vertices. What other countable structures admit an exchangeable
construction?

The Aldous-Hoover theorem and the theory of graph limits show that any ergodic exchangeable graph can be written as a "W-random graph" for some measurable function W : [0,1]^2 -> [0,1], where vertices are drawn iid uniform from [0,1] and edges are determined by independent coin flips with weights given by W. However, for many graphs it is not clear whether such a W exists.

In 2010, Petrov and Vershik gave an exchangeable construction of Henson's universal homogeneous triangle-free graph, making use of this characterization.

Using techniques from model theory for infinitary logic, we extend their construction to provide a complete classification of countable relational structures admitting an exchangeable construction. This provides many new examples of combinatorial structures admitting symmetric probabilistic constructions, including certain posets, directed graphs, and metric spaces.

Joint work with Nate Ackerman and Rehana Patel.