Julia Böttcher: Sparse blow-up lemmas and maker-breaker games

The blow-up lemma of Komlós, Sárközy and Szemerédi is an important tool for embedding large graphs H into dense graphs G. We recently obtained versions of this lemma for subgraphs G of sparse random and pseudo-random graphs. This has important applications in extremal graph theory on random graphs, but can also be used for the analysis of certain maker-breaker games.

In the talk I will explain our blow-up lemmas and describe their connection to maker-breaker games, after giving some necessary background.

Joint work with P. Allen, H. Hàn, Y. Kohayakawa, Y. Person.