Computable representations of exchangeable graphs

Logic Seminar

Meeting Details

For more information about this meeting, contact Kristin Berrigan, Jan Reimann, Linda Westrick.

Speaker: Nathanael Ackerman, Harvard University

Abstract: A random graph is exchangeable when its distribution does not change under permutations of the underlying set. As such, an exchangeable random graph can be thought of as a probabilistic construction of an infinite graph on $\mathbb{N}$ which does not depend on the ordering of $\mathbb{N}$. A result of Aldous--Hoover--Kallenberg, which generalizes de Finetti’s theorem, gives a representation of exchangeable random graphs in terms of what are known as graphons, i.e., symmetric measurable functions from $[0,1]^2$ to $[0,1]$. In this talk we will discuss the relationship between the computability of such representations and the computability of the underlying measure. In contrast to the case of exchangeable sequences, where a version of de Finetti’s theorem is computable, we will provide both positive and negative results about the computability of such representations of computable measures. This is joint work with Avigad, Freer, Roy, and Rute.

Room Reservation Information

Room Number: 315 McAllister

Date: 11/05/2019

Time: 2:30pm - 4:00pm