The ACO Seminar (2011-2012)

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.