Computer Science/Discrete Mathematics Seminar II

The theory of graph quasirandomness studies sequences of graphs that "look like" samples of the Erdős--Rényi random graph. 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".

The theory of graph quasirandomness was one of the main motivations for the development of the theory of limits of graph sequences, graphons. Since the theory of graphons has a generalization to arbitrary combinatorial objects in the form of the theories of flag algebras and theons, it is natural to ask for a theory of quasirandomness for arbitrary combinatorial objects.

In this talk, I will introduce the theory of natural quasirandomness, which provides such generalization. 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 review all definitions and theorems necessary.