Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2010-11 > A New Bound for the Cops and Robbers Problem
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

A New Bound for the Cops and Robbers Problem

Wednesday 01 December 2010, 3.30pm-5.00pm
NAB 2.14, New Academic Building

Professor Alex Scott
Professor of Mathematics
University of Oxford

Personal Profile


Abstract:

The game of Cops and Robbers is played on a finite, connected graph. A number of cops and one robber are placed on the vertices of the graph, and moves are made along the edges of the graph. At each turn, the cops each move along an edge, and then the robber moves. The goal of the cops is to capture the robber, while the robber wishes to avoid the cops indefinitely.

Meyniel conjectured 25 years ago that, for graphs on n vertices, at most O(n^{1/2}) cops are needed for the cops to win. The best previous upper bound was due to Chiniforooshan, who showed that O(n/log n) cops suffice. We give a substantial improvement on this.

This is joint work with Benny Sudakov (UCLA).

Share:Facebook|Twitter|LinkedIn|
  Alex Scott