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.

Date & Time

November 09, 2021 | 10:30am – 12:30pm

Location

Simonyi Hall 101 and Remote Access

Speaker Affiliation

Member, School of Mathematics