Topology of configuration space of two particles on a graph. I.

Discriminantal varieties and configuration spaces in algebraic topology (55R80) Relations of low-dimensional topology with graph theory (57M15) Artificial intelligence for robotics (68T40)

Abstract: In this paper we study the homology and cohomology of confguration spaces of two distinct particles on a graph. Our main tool is intersection theory for cycles in graphs. We obtain an explicit description of the cohomology algebra of the configuration space in the case of planar graphs.

Review text

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.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: Topology of configuration space of two particles on a graph. I.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017844)