#### Algebraic and Geometric Topology 5 (2005),
paper no. 44, pages 1075-1109.

## Discrete Morse theory and graph braid groups

### Daniel Farley, Lucas Sabalka

**Abstract**.
If Gamma is any finite graph, then the unlabelled configuration space
of n points on Gamma, denoted UC^n(Gamma), is the space of n-element
subsets of Gamma. The braid group of Gamma on n strands is the
fundamental group of UC^n(Gamma). We apply a discrete version of Morse
theory to these UC^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 UC^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

**AMS subject classification**.
Primary: 20F65, 20F36.
Secondary: 57M15, 57Q05, 55R80.

**E-print:** `arXiv:math.GR/0410539`

**DOI:** 10.2140/agt.2005.5.1075

Submitted: 26 October 2004.
Accepted: 28 June 2005.
Published: 31 August 2005.

Notes on file formats
Daniel Farley, Lucas Sabalka

Department of Mathematics, University of Illinois at Urbana-Champaign

Champaign, IL 61820, USA

Email: farley@math.uiuc.edu, sabalka@math.uiuc.edu

URL: www.math.uiuc.edu/~farley,
www.math.uiuc.edu/~sabalka

AGT home page

## Archival Version

**These pages are not updated anymore.
They reflect the state of
.
For the current production of this journal, please refer to
http://msp.warwick.ac.uk/.
**