- Series
- Job Candidate Talk
- Time
- Wednesday, February 1, 2023 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Leonardo Coregliano – Institute for Advanced Study – lenacore@ias.edu – https://www.math.ias.edu/~lenacore/
- Organizer
- Tom Kelly

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.