Abstract

Co-authors: Nathanael Ackerman (Harvard University), Diana Cai (University of Chicago), Alex Kruckman (UC Berkeley), Aleksandra Kwiatkowska (University of Bonn), Jaroslav Nesetril (Charles University in Prague), Rehana Patel (Franklin W. Olin College of Engineering), Jan Reimann (Penn State University)

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 Ackerman and 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.

Joint work with Nathanael Ackerman, Diana Cai, Alex Kruckman, Aleksandra Kwiatkowska, Jaroslav Nešetřil, Rehana Patel, and Jan Reimann.