University of Cambridge > Talks.cam > Combinatorics Seminar > Constructible graphs and pursuit

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Constructible graphs and pursuit

Download to your calendar using vCal

  • UserMark Walters (QMUL)
  • ClockThursday 23 February 2023, 14:30-15:30
  • HouseMR12.

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

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:

Note that ex-directory lists are not shown.

Other lists

Cambridge Assessment, 1 Regent Street, Cambridge, UK MRL meeting rooms 1 & 2, Level 4 Institute of Metabolic Sciences, Addenbrooke’s Treatment Centre (ATC) S1, ARB

Other talks

Discussion II continued The Magic of Magnetism Title to be confirmed What’s my reproduction number? Life history strategies: an interdisciplinary perspective Chemical strategies for biomolecule functionalisation, and biomaterial conjugation Group Presentation 5
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity