Málstofa í stærðfræði

Fyrirlesari: Florian Lehner
Titill: Cops, robbers, and infinite graphs

Staðsetning: V-157, VRII.
Tími: Föstudagur 11. september, klukkan 15:00-16:00.

Ágrip:

Pursuit-evasion based searching, also known as the game of cops and robbers is a game on a graph between two players, $C$ (the cop) and $R$ (the robber). The rules are as follows: In the first round both $C$ and $R$ choose a starting vertex, in each consecutive round they are allowed to move to a neighboring vertex. The cop wins the game, if after some finite number of steps $C$ and $R$ occupy the same vertex, otherwise the robber wins.

A basic question related to this game is to characterize the class of graphs for which the cop has a winning strategy. For finite graphs it has been shown by Nowakowski and Winkler that these are exactly the constructible graphs.

For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they believed the same to be true. We disprove this conjecture and explore further modifications which may lead to an extension of the result of Nowakowski and Winkler.