Searching for hidden moving targets on graphs

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

• John Haslegrave (University of Sheffield)
• Thursday 21 May 2015, 14:30-15:30
• MR12.

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

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).

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.