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

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