Departmental Colloquium
Leonardo Coregliano
Institute for Advanced Study
Continuous combinatorics and natural quasirandomness
Abstract: The theory of graph quasirandomness studies graphs that "look like" samples of the Erdős--Rényi
random graph $G_{n,p}$. The upshot of the theory is that several ways of comparing a sequence with
the random graph turn out to be equivalent. For example, two equivalent characterizations of
quasirandom graph sequences is as those that are uniquely colorable or uniquely orderable, that is,
all colorings (orderings, respectively) of the graphs "look approximately the same". Since then,
generalizations of the theory of quasirandomness have been obtained in an ad hoc way for several
different combinatorial objects, such as digraphs, tournaments, hypergraphs, permutations, etc.
The theory of graph quasirandomness was one of the main motivations for the development of the
theory of limits of graph sequences, graphons. Similarly to quasirandomness, generalizations of
graphons were obtained in an ad hoc way for several combinatorial objects. However, differently from
quasirandomness, for the theory of limits of combinatorial objects (continuous combinatorics), the
theories of flag algebras and theons developed limits of arbitrary combinatorial objects in a
uniform and general framework.
In this talk, I will present the theory of natural quasirandomness, which provides a uniform and
general treatment of quasirandomness in the same setting as continuous combinatorics. The talk will
focus on the first main result of natural quasirandomness: the equivalence of unique colorability
and unique orderability for arbitrary combinatorial objects. Although the theory heavily uses the
language and techniques of continuous combinatorics from both flag algebras and theons, no
familiarity with the topic is required as I will also briefly cover all definitions and theorems
necessary.
This talk is based on joint work with Alexander A. Razborov.
Tea in SEO 300 following the talk.
Masks required for audience members in 636.
Wednesday November 16, 2022 at 3:00 PM in 636 SEO