Topological complexity of unordered configuration spaces of certain graphs

摘要

The unordered configuration space of n points on a graph Gamma, denoted here by UCn(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, UDn(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(UDn(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(UDn(Gamma)) = 2n + 1. (c) 2020 Elsevier B.V. All rights reserved.