Abstract:

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.