Research
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:
- My Google Scholar profile
- My ResearchGate profile
- My faculty page on the Emmanuel College website
- “Product Graphs and the Chaser-Runner Game”: YouTube recording of a 1-hour presentation on my research for the Talk Math With Your Friends seminar series (May 2021)
- The Cops and Robbers Theorem: Infinite Series A YouTube video from PBS about this topic. I consulted on the script for the video.
- Another video from PBS Infinite Series, a follow-up video to that first one.
- The 3x3 rooks graph is the unique smallest graph with lazy cop number 3: https://arxiv.org/abs/1606.08485
- An Introduction to Lazy Cops and Robbers on Graphs: https://www.tandfonline.com/doi/abs/10.4169/college.math.j.48.5.322
- Some expository presentations and writings, including the slides from my dissertation defense, are available on my old CMU personal page.