![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
John Haslegrave (University of Sheffield)
Thursday 21 May 2015, 14:30-15:30
Searching for hidden moving targets on graphs
- đ¤ Speaker: John Haslegrave (University of Sheffield)
- đ Date & Time: Thursday 21 May 2015, 14:30 - 15:30
- đ Venue: MR12
Abstract
We consider two closely related games where an invisible target moves around a graph and a searcher probes vertices trying to discover its location. For the first game we give a classification of graphs where the searcher can guarantee to succeed in bounded time. For the second, introduced by Seager, the searcher gets distance information from each probe. Carraher, Choi, Delcourt, Erickson and West showed that if each edge of a graph on n vertices is subdivided m times, where m>=n, the searcher wins, and conjectured that this is best possible for complete graphs. We show that this is not the case, obtaining an exact threshold of n/2 for complete graphs (except for four small values of n), and also give an exact threshold for complete r-partite graphs. Results for the second game are joint work with Richard Johnson (Memphis) and Sebastian Koch (Cambridge).
Series This talk is part of the Combinatorics Seminar series.
Included in Lists
- All CMS events
- All Talks (aka the CURE list)
- bld31
- CMS Events
- Combinatorics Seminar
- DPMMS info aggregator
- DPMMS lists
- DPMMS Lists
- DPMMS Pure Maths Seminar
- Hanchen DaDaDash
- Interested Talks
- MR12
- School of Physical Sciences
Note: Ex-directory lists are not shown.