Combinatorics Seminar
When: Sunday, November 22, 10am
Where: Schreiber 309
Speaker: Simon Litsyn, Tel Aviv University
Title: Policemen and Thieves in Graphs
Abstract:
To save on municipal budget we wish to minimize the number of
policemen in a city described by a graph. The policemen are
positioned at graph vertices (cross-roads) and are in control of
their own vertex along with its neighbors. Whenever a criminal
occurs in her vicinity, the guard sends alarm signal to the
central office. The condition is that having known the set of
worried policemen, the department head should be able to locate
the unique vertex where the crime happens. We will prove that in
Manhattan the police posts have to be placed at exactly 35% of
the street intersections. We will also survey known results on
the problem in alternative settings: different types of graphs,
the number of thieves greater than one, and the graphical radius
of control greater than one.