Search games and Kakeya sets

יום א', 14/10/2018 - 14:30

I'll describe a search game with a surprising geometric connection. A hunter and a rabbit move on an n-vertex graph without seeing each other until they meet. At each step, the hunter moves to a neighboring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time.  We show that an optimal rabbit strategy for the cycle yields a Kakeya set: a plane set of zero area that contains a unit segment in every direction. Kakeya sets have been studied intensively in harmonic analysis since their discovery by Besicovitch (1919); their connection to search games is new and yields insights in both directions. (Based on joint work with Y. Babichenko, R. Peretz, P. Sousi and P. Winkler and on earlier work by Adler et al (2003).)