Sparse blow-up lemmas and maker-breaker games
Graphs, Hypergraphs, and Computing
30 January 14:00 - 15:00
Julia Böttcher - The London School of Economics and Political Science (LSE)
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.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU