BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Strategies\, infinite games and catching robbers - Dr Maria Ivan\,
  DPMMS
DTSTART:20250124T180000Z
DTEND:20250124T190000Z
UID:TALK227305@talks.cam.ac.uk
CONTACT:Daniel Nguyen
DESCRIPTION:The game of cops and robbers is played on a fixed graph G. The
  cop picks a vertex to start at\, and the robber then does the same. Then 
 they move alternately\, with the cop moving first: at each turn the player
  moves to an adjacent vertex or does not move. The game is won by the cop 
 if he lands on the robber. The graph G is called cop-win if the cop has a 
 winning strategy\, and weak cop-win if the cop has a strategy that ensures
  that the robber is either caught or visits each vertex only\nfinitely man
 y times.\n\nHow can we characterise the graphs on which we can\, if we are
  smart enough\, catch the robber? On a finite graph\, we know the answer e
 xactly. These are called `constructible' graphs: obtained recursively from
  the one-point graph by repeatedly adding dominated vertices. \n\nWhat abo
 ut infinite graphs? This notion totally fails to describe the cop-win grap
 hs. \n\nIn this talk we investigate the relation between constructible gra
 phs and cop-win or weak cop-win graphs. We also investigate how these noti
 ons relate to the (weaker and more\nnatural) notion of ‘locally construc
 tible’ (every finite subgraph is contained in a finite constructible sub
 graph). It turns out that we can have exotic examples\, locally constructi
 ble\, on which the robber can outsmart the robber.
LOCATION:Venue to be confirmed
END:VEVENT
END:VCALENDAR