When: Sunday, May 26, 10am
Where: Schreiber 309
Speaker: Rani Hod, Tel Aviv University
Title: Component games on regular graphs
In this talk we study the Maker-Breaker component game, played on the edge set of a regular graph. Given a graph G, the s-component (1:b) game is defined as follows: in every round Maker claims one free edge of G and Breaker claims b free edges. Maker wins this game if his graph contains a connected component of size at least s; otherwise, Breaker wins the game. For all values of Breaker's bias b, we determine whether Breaker wins (on any d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths. Joint work with Alon Naor.
This work forms part of the speaker's Ph.D. thesis, "Codes, Games, and Algorithms", carried out under the supervision of Prof. Noga Alon.
