BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Searching for hidden moving targets on graphs - John Haslegrave (U
 niversity of Sheffield)
DTSTART:20150521T133000Z
DTEND:20150521T143000Z
UID:TALK58726@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:We consider two closely related games where an invisible targe
 t moves\naround a graph and a searcher probes vertices trying to discover 
 its\nlocation. For the first game we give a classification of graphs where
  the\nsearcher can guarantee to succeed in bounded time. For the second\,\
 nintroduced by Seager\, the searcher gets distance information from each\n
 probe. Carraher\, Choi\, Delcourt\, Erickson and West showed that if each\
 nedge of a graph on n vertices is subdivided m times\, where m>=n\, the\ns
 earcher wins\, and conjectured that this is best possible for complete\ngr
 aphs. We show that this is not the case\, obtaining an exact threshold of\
 nn/2 for complete graphs (except for four small values of n)\, and also gi
 ve\nan exact threshold for complete r-partite graphs. Results for the seco
 nd\ngame are joint work with Richard Johnson (Memphis) and Sebastian Koch\
 n(Cambridge).
LOCATION:MR12
END:VEVENT
END:VCALENDAR