Abstract: We consider a variation of cop vs. robber on graph, representing a situation in which an anti-incursion is navigating a linked list of ports attempting to intercept an enemy packet in minimal expected time. The robber/enemy is not restricted by the graph edges and instead picks a time-independent probability distribution on V(G) and moves according to this fixed distribution. The cop/anti-incursion program moves from vertex to adjacent vertex with the goal of minimizing expected capture time. Players move simultaneously. We show that -- rather surprisingly! -- when the distribution is known, the expected capture time (with best play) on any connected n-vertex graph is exactly n. Time permitting, we will also discuss what bounds are known about the case of an unknown distribution.

Abstract: We examine variations of cops and robbers games on graphs. Our goals are to introduce some randomness into their study, and to estimate (expected) capture time. We show that a cop chasing a random walker can capture him in expected time n+o(n). We also discuss games in which the players move in the dark (showing that a cop can capture an immobile hider in time n on any graph) and in which the players suffer various restrictions on their movements.
Slides are available here.

Abstract: We consider a variation on the cops and robbers pursuit-evasion game in which the robber proceeds according to a random walk, and address the question of (expected) capture time. It turns out that the drunk can be captured in n + o(n) steps by a somewhat intelligent cop. We will motivate this result by showing examples of graphs that confound cops that follow a couple of obvious strategies. Time permitting, we will briefly discuss the intuition behind the proof of this result.

Abstract: In the original cop and robber game, the cop and robber move alternately from vertex to adjacent vertex on a graph with full information. We consider a variation in which the robber proceeds according to a random walk, and address the question of the expected length of this game (which will be answered with an upper bound of n + o(n)). We will motivate this result by showing examples of graphs that confound cops that follow some of the most obvious strategies. We will also discuss a theorem on the speed of a random walk (which bounds the probability that a random walk is at distance 4 at the end of 4 steps). Time permitting, we will briefly discuss the main ideas of the proof, as well as some related questions that remain open.

Abstract: We will consider a pursuit-evasion game in which the evader celebrated his victory too early and with a bit too much vigor. As a result, he now moves according to a random walk. We'll see that the cop is going to catch him with probability 1 -- so the only question is how long does this take? The answer is no more than n+o(n). We will discuss the obvious strategies for the cop -- and see that they fail! We'll also describe a smarter strategy, and give some intuition as to why we might expect that one to give us the n+o(n) we claim.

Abstract: Random walks are an important concept in several areas of mathematics, from probability to mathematical finance. In this talk, we'll explore the idea of a random walk on a graph and in particular, give a survey of some interesting results about hitting times. Time permitting, we will talk about a slightly more general version of a random walk and see how it can be used to improve on the hitting time in various situations.

Abstract: There has been a robbery in Graphtown! The robber strategically positioned his attack knowing the location of the one cop in town, so things look grim. Fortunately, the cop and robber are both omniscient, and they only move one at a time between adjacent vertices. So who you gonna call? Well, maybe not a combinatorics consultant, but if you did, she'd tell you a characterization of graphs on which a cop can capture a robber, and a neat winning strategy that always works.

Abstract: The so-called Happy Ending Problem of Erdös, Szekeres, and Klein -- one of the results which led to the development of Ramsey theory -- says that among any five points in the plane, no three of which are colinear, there are always four points forming a convex quadrilateral. We will consider some generalizations of this problem. This will give us an excuse to discuss a neat proof of Ramsey's theorem for hypergraphs. Time permitting, we'll end with some related problems and currently open conjectures.

Abstract: We present a method of producing normal subgroups of F(r), the free group on r generators, not containing a given word. Special attention is given to the normal subgroups of F(2). We use connections with alegbraic topology to produce such subgroups and clearly state for what class of words these subgroups are not easily obtainable.
Slides are available here.