*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 21 November, 4:30 in Fine Hall 224. Speaker: Rani Hod (Georgia Tech) Title: Component games on regular graphs 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 her 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 every 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. ----------- Next week: no seminar (Thanksgiving). Week after: Noga Alon. Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)