Topology of configuration space of two particles on a graph. I. (English) Zbl 1171.55007

Let \(\Gamma\) be a finite graph and denote by \(F(\Gamma, 2)\subset\Gamma^2\) the subset of pairs of distinct points of \(\Gamma\). This configuration space is of importance in topological robotics (Ghrist, Koditschek, Farber). It is connected if \(\Gamma\) is not homeomorphic to an interval, and is generally aspherical by a result of C.W. Patty. In this paper the authors determine the Betti numbers \(b_1\) and \(b_2\) of \(F(\Gamma, 2)\) for \(\Gamma\) a connected planar graph such that every vertex has valence \(\geq 3\) and such that (i) the closure of the bounded connected components of the complement \({\mathbb R}^2-\Gamma\) are contractible, (ii) the closure of the unbounded component is up to homotopy the circle, and (iii) the intersection of any two of these closures is connected (Theorem 7.3). They also give an explicit description of the generators of \(H_1(F(\Gamma, 2);{\mathbb Q} )\) and \(H_2(F(\Gamma, 2);{\mathbb Z} )\) in the case of planar graphs. Some of these results are claimed to correct previous assertions found in the literature.
A key construction introduced in this paper is an “intersection form” labeled \(I_\Gamma\). With \(N\) the closure of some open neighborhood of the diagonal in \(\Gamma\times\Gamma\), the authors define the pairing
\[ I_\Gamma : H_1(\Gamma)\otimes H_1(\Gamma)\rightarrow H_2(N,\partial N) \]
and observe that when \(\Gamma\) is not the circle, \(H_2(F(\Gamma, 2)) = Ker(I_\Gamma )\) and \(H_1(F(\Gamma, 2))\cong \text{coker}(I_\Gamma)\oplus H_1(\Gamma)\oplus H_1(\Gamma )\). They then provide an explicit recipe for computing this intersection form and apply it to various graphs \(K_5, K_{3,3}\) (here for example \(F(K_{3,3},2)\) is homotopy equivalent to an orientable surface of genus \(4\)). It turns out that the cokernel always has rank \(\geq 1\) if \(\Gamma\) is a planar connected graph with an essential vertex (Proposition 7.1).
The main use of \(I_\Gamma\), and one of the major results of this paper, is to show that for a planar graph \(\Gamma\), the group \(H_2(F(\Gamma, 2))= ker(I_\Gamma )\) is freely generated by the orientation classes of embedded tori formed by the configurations of two particles where the first one runs along the boundary of one connected component of \({\mathbb R}^2-\Gamma\) and the second particle runs along the boundary of a second disjoint component (Theorem 6.1). This is then used to deduce Theorem 7.3 quoted above.
A final section discusses the cup product on the rational cohomology of \(F(\Gamma, 2)\) for \(\Gamma\) a connected planar graph having an essential vertex.


55R80 Discriminantal varieties and configuration spaces in algebraic topology
57M15 Relations of low-dimensional topology with graph theory
68T40 Artificial intelligence for robotics
Full Text: DOI arXiv


[1] A Abrams, Configuration spaces and braid groups of graphs, PhD thesis, UC Berkeley (2000)
[2] V I Arnol\(^{\prime}\)d, The cohomology ring of the group of dyed braids, Mat. Zametki 5 (1969) 227
[3] F R Cohen, The homology of \(\mathcal C_{n+1}\)-spaces, \(n \geq 0\), Lecture Notes in Math. 533, Springer (1976) 207
[4] A H Copeland Jr., Homology of deleted products in dimension one, Proc. Amer. Math. Soc. 16 (1965) 1005 · Zbl 0134.42502
[5] 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
[6] A Dold, Lectures on algebraic topology, Die Grund. der math. Wissen. 200, Springer (1972) · Zbl 0234.55001
[7] E Fadell, L Neuwirth, Configuration spaces, Math. Scand. 10 (1962) 111 · Zbl 0136.44104
[8] M Farber, Collision free motion planning on graphs, Springer Tracts in Adv. Robotics 17, Springer (2005) 123
[9] M Farber, Invitation to topological robotics, Zurich Lectures in Advanced Math., Eur. Math. Soc. (2008) · Zbl 1148.55011
[10] D Farley, Homology of tree braid groups (editors M Farber, R Ghrist, M Burger, D Koditschek), Contemp. Math. 394, Amer. Math. Soc. (2006) 101 · Zbl 1102.20028
[11] D Farley, Presentations for the cohomology rings of tree braid groups, Contemp. Math. 438, Amer. Math. Soc. (2007) 145 · Zbl 1143.57302
[12] D Farley, Presentations for the cohomology rings of tree braid groups, Contemp. Math. 438, Amer. Math. Soc. (2007) 145 · Zbl 1143.57302
[13] D Farley, L Sabalka, Discrete Morse theory and graph braid groups, Algebr. Geom. Topol. 5 (2005) 1075 · Zbl 1134.20050
[14] D Farley, L Sabalka, On the cohomology rings of tree braid groups, J. Pure Appl. Algebra 212 (2008) 53 · Zbl 1137.20027
[15] Ś R Gal, Euler characteristic of the configuration space of a complex, Colloq. Math. 89 (2001) 61 · Zbl 0982.55012
[16] R W 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
[17] R W Ghrist, D E Koditschek, Safe cooperative robot dynamics on graphs, SIAM J. Control Optim. 40 (2002) 1556 · Zbl 1012.93046
[18] C W Patty, Homotopy groups of certain deleted product spaces, Proc. Amer. Math. Soc. 12 (1961) 369 · Zbl 0111.18602
[19] C W Patty, The fundamental group of certain deleted product spaces, Trans. Amer. Math. Soc. 105 (1962) 314 · Zbl 0113.16803
[20] A Shapiro, Obstructions to the imbedding of a complex in a euclidean space. I. The first obstruction, Ann. of Math. \((2)\) 66 (1957) 256 · Zbl 0085.37701
[21] B Totaro, Configuration spaces of algebraic varieties, Topology 35 (1996) 1057 · Zbl 0857.57025
[22] V A Vassiliev, Complements of discriminants of smooth maps: topology and applications, Transl. of Math. Monogr. 98, Amer. Math. Soc. (1992) · Zbl 0762.55001
[23] W t Wu, On the realization of complexes in Euclidean spaces. III, Sci. Sinica 8 (1959) 133 · Zbl 0207.53104
[24] W t Wu, A theory of imbedding, immersion, and isotopy of polytopes in a euclidean space, Science Press (1965) · Zbl 0177.26402
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.