Divisional Events

<< Back to Events

Mathematics Program presents

Hunter vs. Mole

Thursday, November 14, 2013

[Hunter vs. Mole]
A lecture by
Natasha Komarov
Carnegie Mellon University

We consider a pursuit-evasion game played on a graph in which the pursuer—here referred to as “hunter”'—is not constrained by the graph but must play in the dark against a “mole.” It turns out that the graphs—which we will call “hunter-win”—on which the hunter can guarantee capture of the mole in bounded time have a nice characterization: a graph is hunter-win if and only if it is a lobster. We also define an optimal hunter strategy (and consequently an upper bound on maximum game time on hunter-win graphs) and note that an optimal hunter strategy need not take advantage of the hunter's unconstrained movement.

Location: Hegeman 204