MATH Seminar

Title: Continuous Combinatorics and Natural Quasirandomness
Job Talk: Combinatorics
Speaker: Leonardo Nagami Coregliano, Postdoctoral Memb of Institute for Advanced Study
Contact: Liana Yepremyan, liana.yepremyan@emory.edu
Date: 2023-01-26 at 10:00AM
Venue: MSC W201
Download Flyer
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.
See All Seminars