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.
Back to the ACO home page