Topological complexity of unordered configuration spaces of certain graphs

and give results for certain classes of graphs. In the first case, we show that for a large class of graphs, as long as the number of robots is at least

2 m (G a m m a)

, then

T C (U D^{n} (G a m m a)) = 2 m (G a m m a) + 1.

In the second, we show that as long as the number of robots is at most half the number of vertex-disjoint cycles in

G a m m a,

we have

T C (U D^{n} (G a m m a)) = 2 n + 1.

Review text

Topological complexity is a homotopy invariant of topological spaces introduced by \textit{M. Farber} [Discrete Comput. Geom. 29, No. 2, 211--221 (2003; Zbl 1038.68130)] to measure how far is a topological space from admitting a motion planner. Let \(X\) be a path-connected topological space, its topological complexity, denoted \(\mathrm{TC}(X)\), is defined as the sectional category (Schwarz genus) of the path space fibration \(\pi \colon X \times [0,1] \to X\times X\), \(\pi(\gamma)=(\gamma(0),\gamma(1))\). That is, \(\mathrm{TC}(X)\) is the smallest integer \(k\) such that there exist open sets \(U_1, \ldots,U_k \subset X\times X\) which cover \(X\times X\) and continuous sections \(s_i \colon U_i \to P(X)\) of the path space fibration. If there is no such \(k\), we let \(\mathrm{TC}(X) = \infty\). For a graph \(\Gamma\), let \(C^n(\Gamma)\) denote the space of all configurations of \(n\) distinct points on \(\Gamma\). The space \(C^n(\Gamma)\) will be called the ordered topological configuration space. Analogously, let \(D^n(\Gamma)\) denote a discretization of \(C^n(\Gamma)\), referred to as the ordered discrete configuration space. Moreover, let \(UC^n(\Gamma)\) and \(UD^n(\Gamma)\) denote the unordered topological and discrete configuration spaces, respectively. See Page 2 for the formal definitions. The discretization of the topological configuration spaces is justified by Theorem 1.2, which claims that, under suitable conditions on \(\Gamma\), in order to study the topology of \(C^n(\Gamma)\) and \(UC^n(\Gamma)\), it is enough to study \(D^n(\Gamma)\) and \(UD^n(\Gamma)\), respectively. In the paper under review, the author proves three main results which we state below. In order to do so, we recall some notation. Let \(\Gamma\) be a graph, then \(m(\Gamma)\) stands for the number of vertices of degree at least three and \(ν(\Gamma)\) refers to the maximum cardinality of a collection of vertex-disjoint cycles in \(\Gamma\) (see Pages 3 and 5 for precise definitions). See Definition 4.1 for the notion of \(S\)-graph. Theorem 1.8. Let \(\Gamma\) be an \(S\)-graph, and let \(n\) be an integer satisfying \(n \geq 2m(\Gamma)\). Then \(\mathrm{TC}(UD^n(\Gamma))=2m(\Gamma) + 1\). Theorem 1.9. Let \(\Gamma\) be any graph with \(\nu = \nu(\Gamma) \geq 2\), and let \(n\) be an integer satisfying \(1 \leq n \leq \frac{1}{2} \nu\). Then \(\mathrm{TC}(UD^n(\Gamma))=2n + 1\). Theorem 2.2. Let \(\Gamma\) be any graph with \(\nu = \nu(\Gamma) \geq 2\), and let \(n\) be an integer satisfying \(2 \leq n \leq \nu\). Then \(\mathrm{TC}(D^n(\Gamma))=2n + 1\). In order to prove these theorems, discrete Morse theory plays a key role. In particular, the author extends some results from D. Farley and L. Sabalka: \textit{D. S. Farley} [Trans. Am. Math. Soc. 357, No. 9, 3567--3584 (2005; Zbl 1137.20032)], \textit{D. Farley} and \textit{L. Sabalka} [Algebr. Geom. Topol. 5, 1075--1109 (2005; Zbl 1134.20050) and J. Pure Appl. Algebra 212, No. 1, 53--71 (2008; Zbl 1137.20027)].

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Topological complexity of unordered configuration spaces of certain graphs

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