Rajko Nenadov

Probabilistic reasoning and Ramsey theory

Abstract: Ramsey theory studies the phenomenon that if a structure is sufficiently large, then no matter how "chaotic" it may seem, it necessarily contains highly regular patterns. Concretely, we will talk about this phenomenon in the context of graph Ramsey theory. A classical result of Ramsey states that for every graph H there exists a large graph G such that no matter how one colours the edges of G with, say, red and blue, there necessarily exists a copy of H in G with all edges having the same colour. Our focus is in understanding how large G needs to be.

While seemingly a simple combinatorial question, this and related topics have deep connections to other branches of mathematics. Starting with the work of Erdos from 1947 on the lower bound on Ramsey numbers, which pioneered the probabilistic reasoning in proving deterministic statements, these topics have been the driving force behind the development of the tools and methods that have largely shaped modern combinatorics.

In the first part of the talk, I will summarise some of the milestones and point out recent developments, highlight my contributions, and outline important open problems. In the second part, I will give an overview of proof techniques and tools.