Exchangeable constructions of countable structures

Add to your list(s) Download to your calendar using vCal

• Cameron Freer (Massachusetts Institute of Technology)
• Monday 25 July 2016, 14:00-14:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

SNAW05 - Bayesian methods for networks

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. 

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Featured lists
• INI info aggregator
• Interested Talks
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.