#### Volume 5, issue 3 (2005)

 Recent Issues
Author Index
 The Journal About the Journal Editorial Board Subscriptions Editorial Interests Editorial Procedure Submission Guidelines Submission Page Ethics Statement ISSN (electronic): 1472-2739 ISSN (print): 1472-2747 To Appear Other MSP Journals
Discrete Morse theory and graph braid groups

### Daniel Farley and Lucas Sabalka

Algebraic & Geometric Topology 5 (2005) 1075–1109
 arXiv: math.GR/0410539
##### Abstract

If $\Gamma$ is any finite graph, then the unlabelled configuration space of $n$ points on $\Gamma$, denoted $U{\mathsc{C}}^{n}\Gamma$, is the space of $n$–element subsets of $\Gamma$. The braid group of $\Gamma$ on $n$ strands is the fundamental group of $U{\mathsc{C}}^{n}\Gamma$.

We apply a discrete version of Morse theory to these $U{\mathsc{C}}^{n}\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 braid group of any tree, for any number of strands. We also give a simple proof of a theorem due to Ghrist: the space $U{\mathsc{C}}^{n}\Gamma$ strong deformation retracts onto a CW complex of dimension at most $k$, where $k$ is the number of vertices in $\Gamma$ of degree at least 3 (and $k$ is thus independent of $n$).

##### Keywords
graph braid groups, configuration spaces, discrete Morse theory
##### Mathematical Subject Classification 2000
Primary: 20F65, 20F36
Secondary: 57M15, 57Q05, 55R80