Combinatorics Seminar

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.

w3c valid   accessible website
redesigned by barak soreq