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

EMIS/ELibM Electronic Journals

Outdated Archival Version

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