Bounds on Ramsey Games via Alterations

ACO Student Seminar
Friday, September 20, 2019 - 1:05pm for 1 hour (actually 50 minutes)
Skiles 005
He Guo – Math, Georgia Tech – he.guo@gatech.edu
He Guo

In this talk we introduce a refined alteration approach for constructing $H$-free graphs: we show that removing all edges in $H$-copies of the binomial random graph does not significantly change the independence number (for suitable edge-probabilities); previous alteration approaches of Erdös and Krivelevich remove only a subset of these edges. We present two applications to online graph Ramsey games of recent interest, deriving new bounds for Ramsey, Paper, Scissors games and online Ramsey numbers (each time extending recent results of Fox–He–Wigderson and Conlon–Fox–Grinshpun–He).
Based on joint work with Lutz Warnke.