Topology of Graph Configuration Spaces

Praphat Fernandes

In the Cartesian product of a graph with itself, the subset consisting of ordered pairs whose coordinates are at least one full edge apart is called the N=2 discretized configuration space of the graph. This space finds application in the problem of avoiding collisions of two robots that move on tracks and that can change direction only at junctions. This paper answers two questions: for what graphs are the N=2 discretized configuration spaces manifolds; and for what graphs are these spaces pseudomanifolds? The first answer provides a new proof of a known result; the second answer appears to be a new result. (Advisor Peter Haskell)