Exchangeable random structures and quasirandomness

Abstract: A random structure on a vertex set $V$ (in a fixed finite relational language) is exchangeable if its distribution is invariant under permutations of $V$. The Aldous--Hoover Theorem says all such distributions are generated from a collection of i.i.d. variables on $[0,1]$, one for each subset of $V$, using a simple rule that was later called "Euclidean structure" by combinatorialists. As the name suggests, an Euclidean structure resembles a relational structure over $[0,1]$, except for the presence of "higher-order variables".

One of the original questions of Hoover was to determine which such distributions admit simpler descriptions, that do not depend on certain variables. Very little progress was obtained in this problem until it got revisited under the light of the theories of limits of combinatorial objects and quasirandomness. It turns out that asking for a representation of an exchangeable hypergraph in which the Euclidean structure is a usual (measurable) relational structure over $[0,1]$ (i.e., which does not need any higher-order variables) is equivalent to asking for "tamer" Szemerédi regularity lemmas and was solved using the theory of hypergraphons.

The dual problem of determining when there is a representation that does not need any low-order variable is more closely related to quasirandomness, which informally is the property of "lack of correlation with simple structures".

In this talk, I will introduce exchangeability and quasirandomness theory and talk about recent progress on the aforementioned dual problem. I will assume familiarity with basic logic/model theory, but no prior knowledge in extremal combinatorics, limit theory or quasirandomness will be necessary.

This talk is based on joint works with Alexander Razborov and Henry Towsner.

discrete mathematicscombinatoricslogicprobability

Audience: researchers in the topic

---

Online logic seminar

Series comments: Description: Seminar on all areas of logic

---