Exchangeable constructions of countable structures

Logic, Games, and Graphs Seminar

Meeting Details

For more information about this meeting, contact Stephanie Geyer, Andrew Belmonte, Jan Reimann, Linda Westrick, Kristin Berrigan, Christopher Griffin.

Speaker: Cameron Freer, MIT

Abstract: The Aldous--Hoover--Kallenberg theorem and the theory of graph limits connect three kinds of objects: sequences of finite graphs, random countably infinite graphs, and certain continuum-sized measurable "limit" objects (graphons). Graphons induce exchangeable countably infinite graphs via sampling, and all exchangeable graphs arise from a mixture of such sampling procedures --- a two-dimensional generalization of de Finetti's theorem. This naturally leads to the question of which countably infinite graphs (or other structures) can arise via an exchangeable construction. More formally, consider a random structure with a fixed countably infinite underlying set. The random structure is exchangeable when its joint distribution is invariant under permutations of the underlying set. For example, the countably infinite Erdös-Rényi graph is exchangeable; moreover, it is almost surely isomorphic to a particular graph, known as the Rado graph, and so we say that the Rado graph admits an exchangeable construction. On the other hand, one can show that no infinite tree admits an exchangeable construction. In joint work with Nathanael Ackerman and Rehana Patel, we provide a necessary and sufficient condition for a countably infinite structure to admit an exchangeable construction. We also address related questions, such as what structures admit a unique exchangeable construction, and give examples involving graphs, directed graphs, and partial orders. This talk also includes joint work with Diana Cai, Alex Kruckman, Aleksandra Kwiatkowska, Jaroslav Nesetril, and Jan Reimann.


Room Reservation Information

Room Number: 114 McAllister

Date: 11/06/2019

Time: 2:30pm - 3:30pm