Logic Seminar
Leonardo Coregliano
University of Chicago
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.
Tuesday November 5, 2024 at 4:00 PM in 636 SEO