Discrete Morse theory and graph braid groups

If Gamma is any finite graph, then the unlabelled configuration space of n points on Gamma, denoted UCn Gamma, is the space of n-element subsets of Gamma. The braid group of Gamma on n strands is the fundamental group of UCn Gamma. We apply a discrete version of Morse theory to these UCn Gamma, for any n and any Gamma, and provide a clear description of the critical cells in every case. As a result, we can calculate a presentation for the bra id group of any tree,for any number of strands. We also give a simple proof of a theorem due to Ghrist: the space UCn Gamma strong deformation retracts onto a CW complex of dimension at most k, where k is the number of vertices in of degree at least 3 (and k is thus in dependent of n).