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 robbers

Add to your list(s) Download to your calendar using vCal

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.