The Aldous-Ho over-Kallenberg theorem and the theory of graph li mits 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 s ampling procedures -- a two-dimensional generaliz ation 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 countabl y infinite underlying set. The random structure i s exchangeable when its joint distribution is inva riant under permutations of the underlying set. F or example\, the countably infinite Erdő\;s& ndash\;Ré\;nyi graph is exchangeable\; moreo ver\, it is almost surely isomorphic to a particu lar graph\, known as the Rado graph\, and so we sa y that the Rado graph admits an exchangeable cons truction. On the other hand\, one can show that no infinite tree admits an exchangeable constructio n.

In joint work with Ackerman and Patel\ , we provide a necessary and sufficient condition for a countably infinite structure to admit an ex changeable construction. We also address related questions\, such as what structures admit a uniqu e exchangeable construction\, and give examples in volving graphs\, directed graphs\, and partial or ders.

Joint work with Nathanael Ack erman\, Diana Cai\, Alex Kruckman\, Aleksandra Kw iatkowska\, Jaroslav Ne&scaron\;etř\;il\, Reh ana Patel\, and Jan Reimann. \; LOCATION:Seminar Room 1\, Newton Institute CONTACT:INI IT END:VEVENT END:VCALENDAR