Topology of configuration space of two particles on a graph. II. (English) Zbl 1215.55006

Farber, Michael; Hanbury, Elizabeth

Algebr. Geom. Topol. 10, No. 4, 2203-2227 (2010).

This paper continues the investigation of the topology of the configuration space \(F(\Gamma ,2) := \Gamma\times\Gamma -\Delta\), where \(\Gamma\) is a finite graph and \(\Delta\) is the diagonal [K. Barnett and M. Farber, Algebr. Geom. Topol. 9, No. 1, 593–624 (2009; Zbl 1171.55007)]. A finite connected graph \(\Gamma\) which is not homeomorphic to the unit interval is called mature if the homomorphism \(H_1(F(\Gamma, 2))\rightarrow H_1(\Gamma\times\Gamma)\), induced from the subspace inclusion \(F(\Gamma, 2))\hookrightarrow \Gamma\times\Gamma\) is an isomorphism. According to results in [loc. cit.] no planar graph can be mature. In this paper maturity is established for many examples of graphs. This is done by proving a series of results describing the way the homology of \(F(\Gamma, 2)\) is affected by selectively changing \(\Gamma\). One main result of this paper (Theorem 1) shows that if \(\Gamma\) is mature and \(\hat\Gamma\) is obtained from \(\Gamma\) by adding an edge connecting two vertices \(u,v\) of \(\Gamma\), then if \(\Gamma -\{u,v\}\) is connected, \(\hat\Gamma\) is mature as well. As a corollary, it is shown that the complete graphs \(K_n\) for \(n\geq 5\) and the bipartite graphs \(K_{p,q}\) with \(p\geq 3\), \(q\geq 3\), are mature. The Betti numbers of the configuration spaces are computed in this case. It is pointed out that Theorem 1 of this paper contradicts Theorem 4.2 of C. W. Patty [Trans. Am. Math. Soc. 105, 314–321 (1962; Zbl 0113.16803)].
Various examples of non-mature graphs are described: (i) graphs with vertices of valence one, (ii) graphs such that removing the closure of an edge makes it disconnected, (iii) graphs with a double edge, and (iv) graphs that are wedges or double wedges of two connected subgraphs \(\Gamma_1\) and \(\Gamma_2\) both of which are connected and not homeomorphic to the unit interval. On the other hand, mature graphs can be produced in the following way: if \(\Gamma = \Gamma_1\cup\Gamma_2\) is the union of two mature subgraphs such that the edges incident to any vertex \(v\in \Gamma_1\cap\Gamma_2\) lie either all in \(\Gamma_1\) or all in \(\Gamma_2\), and if \(\Gamma_1\cap\Gamma_2\) is connected, then \(\Gamma\) is mature.
Techniques of proof rely on the intersection form \(I_\Gamma\) introduced in [Barnett and Farber, op. cit.] and the linking homomorphism introduced in §4 of this paper.
The paper ends by making the conjecture that a connected nonplanar graph is mature if and only if it admits a decomposition as a wedge or double wedge. Also it is indicated that no examples of graphs \(\Gamma\) are known such that \(H_1(F(\Gamma, 2))\) has nontrivial torsion.

Reviewer: Sadok Kallel (Villeneuve d’Asq)

MSC:

55R80	Discriminantal varieties and configuration spaces in algebraic topology
57M15	Relations of low-dimensional topology with graph theory

Keywords:

configuration spaces; graphs; homology; intersection form

Citations:

Zbl 1171.55007; Zbl 0113.16803

References:

[1]	A D Abrams, Configuration spaces and braid groups of graphs, PhD thesis, University of California, Berkeley (2000)
[2]	V I Arnol’d, The cohomology ring of the group of dyed braids, Mat. Zametki 5 (1969) 227 · Zbl 0277.55002
[3]	K Barnett, M Farber, Topology of configuration space of two particles on a graph, I, Algebr. Geom. Topol. 9 (2009) 593 · Zbl 1171.55007
[4]	F R Cohen, The homology of \(\mathcal C_{n+1}\)-spaces, \(n\geq 0\) (editors F R Cohen, T I Lada, J P May), Lecture Notes in Math. 533, Springer (1976) · Zbl 0334.55009
[5]	A H Copeland Jr., Homology of deleted products in dimension one, Proc. Amer. Math. Soc. 16 (1965) 1005 · Zbl 0134.42502
[6]	A H Copeland Jr., C W Patty, Homology of deleted products of one-dimensional spaces, Trans. Amer. Math. Soc. 151 (1970) 499 · Zbl 0205.53101
[7]	E Fadell, L Neuwirth, Configuration spaces, Math. Scand. 10 (1962) 111 · Zbl 0136.44104
[8]	M Farber, Collision free motion planning on graphs (editors M Erdmann, D Hsu, M Overmars, A F van der Stappen), Springer (2005) 123
[9]	M Farber, Invitation to topological robotics, Zurich Lectures in Advanced Math., European Math. Soc. (2008) · Zbl 1148.55011
[10]	D Farley, Homology of tree braid groups (editors R Grigorchuk, M Mihalik, M Sapir, Z \vSunik), Contemp. Math. 394, Amer. Math. Soc. (2006) 101 · Zbl 1102.20028
[11]	D Farley, Presentations for the cohomology rings of tree braid groups (editors M Farber, R Ghrist, M Burger, D Koditschek), Contemp. Math. 438, Amer. Math. Soc. (2007) 145 · Zbl 1143.57302
[12]	D Farley, L Sabalka, Discrete Morse theory and graph braid groups, Algebr. Geom. Topol. 5 (2005) 1075 · Zbl 1134.20050
[13]	D Farley, L Sabalka, On the cohomology rings of tree braid groups, J. Pure Appl. Algebra 212 (2008) 53 · Zbl 1137.20027
[14]	R Ghrist, Configuration spaces and braid groups on graphs in robotics (editors J Gilman, W W Menasco, X S Lin), AMS/IP Stud. Adv. Math. 24, Amer. Math. Soc. (2001) 29 · Zbl 1010.55012
[15]	R W Ghrist, D E Koditschek, Safe cooperative robot dynamics on graphs, SIAM J. Control Optim. 40 (2002) 1556 · Zbl 1012.93046
[16]	S Janson, T Łuczak, A Rucinski, Random graphs, Wiley-Interscience Ser. in Discrete Math. and Optimization, Wiley-Interscience (2000)
[17]	C W Patty, Homotopy groups of certain deleted product spaces, Proc. Amer. Math. Soc. 12 (1961) 369 · Zbl 0111.18602
[18]	C W Patty, The fundamental group of certain deleted product spaces, Trans. Amer. Math. Soc. 105 (1962) 314 · Zbl 0113.16803
[19]	B Totaro, Configuration spaces of algebraic varieties, Topology 35 (1996) 1057 · Zbl 0857.57025
[20]	V A Vassiliev, Complements of discriminants of smooth maps: topology and applications, Transl. of Math. Monogr. 98, Amer. Math. Soc. (1992) · Zbl 0762.55001