Topological complexity of unordered configuration spaces of certain graphs

Abstract

The unordered configuration space of $n$ points on a graph $\Gamma ,$ denoted here by $U{C}^n(\Gamma ),$ can be viewed as the space of all configurations of $n$ unlabeled robots on a system of one-dimensional tracks, which is interpreted as a graph $\Gamma .$ The topology of these spaces is related to the number of vertices of degree greater than 2; this number is denoted by $m(\Gamma ).$ We discuss a combinatorial approach to compute the topological complexity of a "discretized" version of this space, $U{D}^n(\Gamma ),$ and give results for certain classes of graphs. In the first case, we show that for a large class of graphs, as long as the number of robots is at least $2m(\Gamma )$, then $TC(U{D}^n(\Gamma ))=2m(\Gamma )+1.$ In the second, we show that as long as the number of robots is at most half the number of vertex-disjoint cycles in $\Gamma ,$ we have $TC(U{D}^n(\Gamma ))=2n+1.$

24 pages, 4 figures, minor revisions