This is a page for information about my research and scholarship.

Current research: Pursuit-evasion games on graphs

Graph theory studies network connections. Think of Facebook, with nodes (called “vertices”) representing each person and connections (called “edges”) amongst the nodes representing who is friends with whom; in this sense, Facebook is a big graph.

“Cops & Robbers” is a game played on graphs. A team of Cops place themselves on the vertices of a given graph, and then the Robber places himself on a vertex. The two sides alternate turns: on their turn, the Cops get to move along the edges, then the Robber does the same, and they go back and forth like this. If a Cop lands on the Robber, he is caught and the Cops win. If the Robber is able to evade the Cops indefinitely, then he wins.

This game has been studied extensively since its introduction in the 1980s. Mathematicians have made great strides towards understanding what kinds of graphs allow one Cop to win, which graphs require more and how many are required, etc. However, there remain many open questions and unproven conjectures. This is a very active research area!

Since this is a game, this research can be purely recreational (as it is for me). But these results also have important applications and implications in computer science and programming. A good example is writing programs to search and organize large datasets efficiently. “Lazy Cops & Robbers” is a variant of the game wherein, on the Cops’ turn, only one of them is allowed to move. The main question becomes: Does this rule change the game significantly? For a given graph, do the same number of Cops suffice, or might we need more (and how many)?

Relevant links: