Constructible graphs and pursuit

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

• Mark Walters (QMUL)
• Thursday 23 February 2023, 14:30-15:30
• MR12.

If you have a question about this talk, please contact ibl10.

The simplest Cops and Robbers game is as follows. Both the cop and robber are placed on a graph and then they alternately take turns where they either move to a neighbouring vertex or remain at the same vertex. The cop wins if, at some point, he is at the same vertex as the robber—the robber wins if he can ensure this never happens.

If the graph is finite then it is easy to show that a graph is cop-win if and only if it is constructible, meaning that the graph can be obtained from the one-point graph by adding dominated vertices one at a time.

But if the graph is infinite then the situation is more complicated. We will discuss what happens, including the first example of a cop-win graph that is not constructible.

Joint work with Maria Ivan and Imre Leader

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.