BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Searching for hidden moving targets on graphs - Jo
hn Haslegrave (University of Sheffield)
DTSTART;TZID=Europe/London:20150521T143000
DTEND;TZID=Europe/London:20150521T153000
UID:TALK58726AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/58726
DESCRIPTION:We consider two closely related games where an inv
isible target moves\naround a graph and a searcher
probes vertices trying to discover its\nlocation.
For the first game we give a classification of gr
aphs where the\nsearcher can guarantee to succeed
in bounded time. For the second\,\nintroduced by S
eager\, the searcher gets distance information fro
m each\nprobe. Carraher\, Choi\, Delcourt\, Ericks
on and West showed that if each\nedge of a graph o
n n vertices is subdivided m times\, where m>=n\,
the\nsearcher wins\, and conjectured that this is
best possible for complete\ngraphs. We show that t
his is not the case\, obtaining an exact threshold
of\nn/2 for complete graphs (except for four smal
l values of n)\, and also give\nan exact threshold
for complete r-partite graphs. Results for the se
cond\ngame are joint work with Richard Johnson (Me
mphis) and Sebastian Koch\n(Cambridge).
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR