Speaker: Kerry Ojakian, CUNY

Title: Cop and Robber Game on Graph Contractions

Abstract:
We consider the classic graph-theoretic game of cops and robber,
with a twist: certain information will be hidden from one of the
two players. In the classic game, one player controls a single robber,
while another player controls some number of cops; the game
is played on a connected simple graph. The players alternate turns,
where on a player's turn, for each of their pieces, they can move it to an adjacent
vertex or the piece can remain where it is.  The goal for the cops is that a cop and
the robber occupy the same vertex; the goal of the robber is to avoid this.

In our twist, we consider some labeling of the vertices of a graph G. The contracted
version H of this labeled graph makes all the vertices with the same label (say k) into a single
vertex labeled k; also, any edge in the original graph G from a vertex labeled j to a vertex
labeled k, becomes an edge in this contracted graph H
(i.e. we are performing the standard graph contraction, multiple times).
For example, if G is the following labeled path on 5 vertices (v, x, x, x, w), then
the contracted H would be the following path on 3 vertices: (v, x, w).
While both players are actually in G, one of the
players (the ``appearance player") will only know its locations as given by H.  
When the appearance player specifies a move, say from j to k, in H, the move is
naturally interpreted as a move actually occurring in G: the piece is moved from j
to an adjacent vertex also labeled j, on a shortest path that leads towards a vertex
labeled k (if there are multiple such paths, then the opponent adversarially chooses).

One motivation of this work is to understand play with imperfect information.
Another motivation is to better understand strategies - for example, in the path example
above, there is a sense in which every path game (and accompanying strategy) can be
reduced to the single path on three vertices along with its one natural strategy.  
This is joint work with Nancy Clarke, Danny Dyer, and William Kellough.

Zoom link below; joint viewing at Dalhousie in room Chase 227

https://us02web.zoom.us/j/88013261876?pwd=XGocyHqvseXY8metPztPoSuulEEejX.1