PIMS-UVic Discrete Math Seminar: Daniel Král'

The theory of combinatorial limits, which provides analytic tools to represent and study large discrete structures, resulted in new views on a wide range of topics in mathematics and computer science and also opened new connections between combinatorics and other areas of mathematics. In the talk, we will introduce basic concepts from the theory of combinatorial limits and apply its methods to several specific problems from extremal combinatorics and particularly from Ramsey theory.

Ramsey theory statements guarantee the existence of ordered substructures in large objects such as in the following classical statement proven by Ramsey in 1930: if N is sufficiently large, then for any partition of k-tuples of N points into finitely many classes, there exist n points such that all k-tuples formed by these n points belong to the same class. We will study quantitative versions of Ramsey type statements and present a solution of a 30-year-old problem on the existence of high chromatic graphs with small Ramsey multiplicity. In relation to general questions concerning the interplay of combinatorial limits and extremal combinatorics, we will present, among others, a counterexample to a conjecture of Lovász on finitely forcible optima of extremal combinatorics problems.