Discrete Morse theory and graph braid groups

Farley, Daniel¹ ; Sabalka, Lucas¹

¹Department of Mathematics, University of Illinois at Urbana-Champaign, Champaign IL 61820, USA

Algebraic and Geometric Topology, Tome 5 (2005) no. 3, pp. 1075-1109

Résumé

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).

Détail

DOI : 10.2140/agt.2005.5.1075

Keywords: graph braid groups, configuration spaces, discrete Morse theory

Bibliographie

[1] A Abrams, private communication

[2] A Abrams, Configuration spaces of braid groups of graphs, PhD thesis, University of California, Berkeley (2000)

[3] A Abrams, Configuration spaces of colored graphs, Geom. Dedicata 92 (2002) 185

[4] A Abrams, R Ghrist, Finding topology in a factory: configuration spaces, Amer. Math. Monthly 109 (2002) 140

[5] M Bestvina, N Brady, Morse theory and finiteness properties of groups, Invent. Math. 129 (1997) 445

[6] M R Bridson, A Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer (1999)

[7] K S Brown, The geometry of rewriting systems: a proof of the Anick–Groves–Squier theorem, from: "Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989)", Math. Sci. Res. Inst. Publ. 23, Springer (1992) 137

[8] M M Cohen, A course in simple-homotopy theory, Graduate Texts in Mathematics 10, Springer (1973)

[9] F Connolly, M Doig, Braid groups and right angled Artin groups

[10] J Crisp, B Wiest, Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups, Algebr. Geom. Topol. 4 (2004) 439

[11] M Farber, Collision free motion planning on graphs

[12] R Forman, Morse theory for cell complexes, Adv. Math. 134 (1998) 90

[13] Ś R Gal, Euler characteristic of the configuration space of a complex, Colloq. Math. 89 (2001) 61

[14] R Ghrist, Configuration spaces and braid groups on graphs in robotics, from: "Knots, braids, and mapping class groups—papers dedicated to Joan S. Birman (New York, 1998)", AMS/IP Stud. Adv. Math. 24, Amer. Math. Soc. (2001) 29

[15] R W Ghrist, D E Koditschek, Safe cooperative robot dynamics on graphs, SIAM J. Control Optim. 40 (2002) 1556

[16] K A Mihaĭlova, The occurrence problem for direct products of groups, Mat. Sb. $($N.S.$)$ 70 (112) (1966) 241

[17] M H A Newman, On theories with a combinatorial definition of “equivalence.”, Ann. of Math. $(2)$ 43 (1942) 223

[18] C P Rourke, B J Sanderson, Introduction to piecewise-linear topology, Springer Study Edition, Springer (1982)

[19] J C Stillwell, Classical topology and combinatorial group theory, Graduate Texts in Mathematics 72, Springer (1980)

[20] J Świątkowski, Estimates for homological dimension of configuration spaces of graphs, Colloq. Math. 89 (2001) 69