Pursuit-evasion
Havens model a certain class of strategies for an evader in a pursuit-evasion game in which fewer than k pursuers attempt to capture a single evader, the pursuers and evader are both restricted to the vertices of a given undirected graph, and the positions of the pursuers and evader are known to both players. At each move of the game, a new pursuer may be added to an arbitrary vertex of the graph (as long as fewer than k pursuers are placed on the graph at any time) or one of the already-added pursuers may be removed from the graph. However, before a new pursuer is added, the evader is first informed of its new location and may move along the edges of the graph to any unoccupied vertex. While moving, the evader may not pass through any vertex that is already occupied by any of the pursuers.
If a k-haven (with the monotonicity property) exists, then the evader may avoid being captured indefinitely, and win the game, by always moving to a vertex of β(X) where X is the set of vertices that will be occupied by pursuers at the end of the move. The monotonicity property of a haven guarantees that, when a new pursuer is added to a vertex of the graph, the vertices in β(X) are always reachable from the current position of the evader.
For instance, an evader can win this game against three pursuers on a 3 × 3 grid by following this strategy with the haven of order 4 described in the example. However, on the same graph, four pursuers can always capture the evader, by first moving onto three vertices that split the grid onto two three-vertex paths, then moving into the center of the path containing the evader, forcing the evader into one of the corner vertices, and finally removing one of the pursuers that is not adjacent to this corner and placing it onto the evader. Therefore, the 3 × 3 grid can have no haven of order 5.
Havens with the touching property allow the evader to win the game against more powerful pursuers that may simultaneously jump from one set of occupied vertices to another.
Read more about this topic: Haven (graph Theory)