University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Constructible graphs and the game of cops and robbers

## Constructible graphs and the game of cops and robbersAdd to your list(s) Download to your calendar using vCal - Maria-Romina Ivan, University of Cambridge
- Thursday 05 May 2022, 15:00-16:00
- Poynting Small Lecture Theatre, additional zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
If you have a question about this talk, please contact Eoin Long. 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 finitely many times. A graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood. In this talk we focus on infinite graphs and the relation between constructible graphs and cop-win or weak cop-win graphs. We also investigate how these notions relate to the (weaker and more natural) notion of ‘locally constructible’ (every finite subgraph is contained in a finite constructible subgraph). Joint work with Imre Leader and Mark Walters. This talk is part of the Combinatorics and Probability seminar series. ## This talk is included in these lists:- Combinatorics and Probability seminar
- Poynting Small Lecture Theatre, additional zoom link: https://bham-ac-uk.zoom.us/j/88168768618
- School of Mathematics events
Note that ex-directory lists are not shown. |
## Other listsWhat's on in Physics? School of Metallurgy and Materials Colloquia Particle Physics Seminars## Other talksWaveform modelling and the importance of multipole asymmetry in Gravitational Wave astronomy Life : it’s out there, but what and why ? TBA Quantum Sensing in Space TBA TBA |