Computer Science/Discrete Mathematics Seminar II
Introduction to Continuous Combinatorics II: semantic limits
The field of continuous combinatorics studies large (dense) combinatorial structures by encoding them in a "continuous" limit object, which is amenable to tools from analysis, topology, measure theory, etc. While the syntactic/algebraic approach of "flag algebras" (Razborov '07) provides a very simple limit object for convergent sequences, the minimalist nature of the limit objects from flag algebras loses almost all information on the semantics and geometry of the original objects. On the other side of the coin, the geometric/semantic approach to the subject, typically associated with the name "graphons" (Lovász--Szegedy '04) for limits of graphs and with the name "theons" (C.--Razborov '20) for limits of arbitrary combinatorial objects, retains geometric and semantic information by producing a more complicated limit that still "looks like" the original objects.
In this lecture, I will give an introduction to the theories of graphons and theons and show some examples of theorems in the theory of quasirandomness that greatly benefit from either a semantic/geometric approach or from a hybrid approach.