Volume 5, issue 3 (2005)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 24
Issue 3, 1225–1808
Issue 2, 595–1223
Issue 1, 1–594

Volume 23, 9 issues

Volume 22, 8 issues

Volume 21, 7 issues

Volume 20, 7 issues

Volume 19, 7 issues

Volume 18, 7 issues

Volume 17, 6 issues

Volume 16, 6 issues

Volume 15, 6 issues

Volume 14, 6 issues

Volume 13, 6 issues

Volume 12, 4 issues

Volume 11, 5 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 4 issues

Volume 7, 4 issues

Volume 6, 5 issues

Volume 5, 4 issues

Volume 4, 2 issues

Volume 3, 2 issues

Volume 2, 2 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editorial Interests
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Author Index
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


If Γ is any finite graph, then the unlabelled configuration space of n points on Γ, denoted UCnΓ, is the space of n–element subsets of Γ. The braid group of Γ on n strands is the fundamental group of UCnΓ.

We apply a discrete version of Morse theory to these UCnΓ, for any n and any Γ, 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 UCnΓ 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 independent of n).

graph braid groups, configuration spaces, discrete Morse theory
Mathematical Subject Classification 2000
Primary: 20F65, 20F36
Secondary: 57M15, 57Q05, 55R80
Forward citations
Received: 26 October 2004
Accepted: 28 June 2005
Published: 31 August 2005
Daniel Farley
Department of Mathematics
University of Illinois at Urbana-Champaign
Champaign IL 61820
Lucas Sabalka
Department of Mathematics
University of Illinois at Urbana-Champaign
Champaign IL 61820