1 Introduction
The difficulty of collision-free motion planning is measured by the topological complexity of configuration spaces. In many situations, the ambient workspace is naturally modelled as a graph, and the corresponding complexity was described conjecturally by Farber in 2005 [Reference Farber, Erdmann, Overmars, Hsu and van der StappenFar05]. Our purpose is to prove this conjecture.
Write
$\mathrm {Conf}_k(\mathsf{\Gamma})$
for the configuration space of k ordered points in the graph
$\mathsf{\Gamma}$
, denote the number of vertices of
$\mathsf{\Gamma}$
of valence at least
$3$
by
$m(\mathsf{\Gamma})$
, and write
$\mathrm {TC}_r$
for the rth higher topological complexity [Reference FarberFar03, Reference RudyakRud10]. Farber’s conjecture is the case
$r=2$
of the following result.
Theorem 1.1. Let
$\mathsf{\Gamma}$
be a connected graph with
$m(\mathsf{\Gamma})\geq 2$
. For
$k\geq 2m(\mathsf{\Gamma})$
and
$r>0$
, we have the equality
$$\begin{align*}\frac{1}{r}\,\mathrm{TC}_r(\mathrm{Conf}_k(\mathsf{\Gamma}))=m(\mathsf{\Gamma}).\end{align*}$$
The case
$m(\mathsf{\Gamma})=0$
is trivial, and the case
$m(\mathsf{\Gamma})=1$
is completely understood—see [Reference Luetgehetmann and Recio-MitterLRM19, Theorem A], for example.
Using a cohomological argument, Farber proved this result for trees and
$r=2$
[Reference Farber, Erdmann, Overmars, Hsu and van der StappenFar05]. This argument was later adapted to establish the same result for fully articulated and banana graphs and
$r=2$
[Reference Luetgehetmann and Recio-MitterLRM19], for trees and
$r>0$
[Reference Aguilar-Guzmán, Gonzalez and Hoekstra-MendozaAGGHM22] and for planar graphs and
$r>0$
[Reference KnudsenKnu21].
The idea of Farber’s argument is easily explained. First, the quantity
$\frac {1}{r}\mathrm {TC}_r$
is bounded above by the homotopy dimension of the background space, which for
$\mathrm {Conf}_k(\mathsf{\Gamma})$
is
$m(\mathsf{\Gamma})$
in the regime of interest. Second, this dimension is detected by a map from a torus of dimension
$m(\mathsf{\Gamma})$
(described geometrically below). Third, one can produce long cup products in cohomology by combining classes detecting circle factors of this torus—provided such classes exist. Since a variant of the cup length bounds topological complexity from below, one obtains the desired conclusion.
Unfortunately, the cohomological decomposability of the torus in question is equivalent to planarity [Reference KnudsenKnu21], so the requisite classes fail to exist in the nonplanar setting. We circumvent this obstacle by working at the level of fundamental groups, leveraging a theorem of [Reference Farber and OpreaFO19], following [Reference Grant, Lupton and OpreaGLO13], on the higher topological complexity of aspherical spaces to establish the necessary lower bound (Theorem 3.1).
1.1 Conventions
We say that subgroups of a fixed group are disjoint if they intersect trivially. We write
$\mathrm {cd}_R(G)$
for the cohomological dimension of the group G over the commutative ring R, which is to say the minimal length of a projective resolution of the trivial module R over the group ring
$R[G]$
. We set
$\mathrm {cd}(G)=\mathrm {cd}_{\mathbb {Z}}(G)$
.
Given a path
$\gamma $
in a space X, we denote its path homotopy class by
$[\gamma ]$
, its reverse by
$\bar \gamma $
and its change-of-basepoint isomorphism by
$\hat \gamma :\pi _1(X,\gamma (0))\to \pi _1(X,\gamma (1))$
. We denote the concatenation operation on paths by
$\star $
.
We use the ‘reduced’ convention for topological complexity in which
$\mathrm {TC}(\mathrm {pt})=0$
.
2 Graphs and their configuration spaces
For our purposes, a graph is a finite CW complex
$\mathsf{\Gamma}$
of dimension at most
$1$
. The degree or valence
$d(v)$
of a vertex v of
$\mathsf{\Gamma}$
is the number of connected components of its complement in a sufficiently small open neighbourhood. A vertex of valence at least
$3$
is called essential.
The configuration spaces of a graph
$\mathsf{\Gamma}$
depend only on the homeomorphism type of
$\mathsf{\Gamma}$
; in particular, they are invariant under subdivision. The fundamental fact concerning these configuration spaces is the following.
Theorem 2.1 [Reference AbramsAbr00].
For any graph
$\mathsf{\Gamma}$
and
$k\geq 0$
, the space
$\mathrm {Conf}_k(\mathsf{\Gamma})$
is aspherical.
In particular, if
$\mathsf{\Gamma}$
is connected and
$m(\mathsf{\Gamma})>0$
, then the configuration space
$\mathrm {Conf}_k(\mathsf{\Gamma})$
is a classifying space for its fundamental group, the pure graph braid group on k strands, denoted
$P_k(\mathsf{\Gamma})$
. We work with a basepoint
$x_0\in \mathrm {Conf}_k(\mathsf{\Gamma})$
chosen so that every coordinate is a bivalent vertex, which is always achievable after subdivision.
Fixing a vertex v, consider the subspace
$\iota _v:\mathrm {Conf}_k(\mathsf{\Gamma})_v\subseteq \mathrm {Conf}_k(\mathsf{\Gamma})$
consisting of configurations with at most one coordinate in the open star of v.
Proposition 2.2. If the open star of v is contractible, then
$\iota _v$
is a homotopy equivalence.
Proof. The assumption guarantees that
$\mathrm {Conf}_k(\mathsf{\Gamma})_{v}$
coincides with the subspace considered in [Reference Agarwal, Banks, Gadish and MiyataABGM21, Lemma 2.0.1] after subdividing.
In the remainder of the paper, we work with a connected graph
$\mathsf{\Gamma}$
. We subdivide
$\mathsf{\Gamma}$
to guarantee that every essential vertex has a contractible open star (equivalent to requiring that
$\mathsf{\Gamma}$
have no self-loops) and that distinct essential vertices have disjoint closed stars. We fix a parametrisation of each edge of
$\mathsf{\Gamma}$
and an ordering of the set of edges at each essential vertex.
3 A general lower bound
The ‘higher’ or ‘sequential’ topological complexity
$\mathrm {TC}_r$
is a numerical homotopy invariant defined in [Reference RudyakRud10] and developed in [Reference Basabe, González, Rudyak and TamakiBGRT14], recovering Farber’s topological complexity [Reference FarberFar03] for
$r=2$
and the Lusternik–Schnirelmann category for
$r=1$
. The reader is referred to these references for definitions; we recall only that
$\frac {1}{r}\mathrm {TC}_r$
is bounded above by the homotopy dimension in nonpathological settings, such as for spaces homotopy equivalent to CW complexes.
Theorem 1.1 is an immediate consequence of the following result, together with the dimensional bound and the well-known fact that the homotopy dimension of
$\mathrm {Conf}_k(\mathsf{\Gamma})$
is bounded above by
$m(\mathsf{\Gamma})$
, independent of k [Reference ŚwiątkowskiŚwi01].
Theorem 3.1. Let
$\mathsf{\Gamma}$
be a connected graph. For any
$r> 0$
and
$k\geq 4$
, we have the inequality
$$\begin{align*}\frac{1}{r}\,\mathrm{TC}_r(\mathrm{Conf}_k(\mathsf{\Gamma}))\geq \min\left\{\left\lfloor\frac{k}{2}\right\rfloor, m(\mathsf{\Gamma})\right\}. \end{align*}$$
This result recovers theorems of [Reference Aguilar-Guzmán, Gonzalez and Hoekstra-MendozaAGGHM22] and [Reference KnudsenKnu21] for trees and planar graphs, respectively. In these cases, the estimate follows from consideration of the zero-divisor cup length in the cohomology of the relevant configuration space. If such a strategy is available in the nonplanar setting, it is not without significant and non-obvious modification [Reference KnudsenKnu21, Theorem 8.1]. Instead, we aim to leverage the advances in the study of the topological complexity of aspherical spaces made in the wake of [Reference Grant, Lupton and OpreaGLO13].
Theorem 3.2 ([Reference Farber and OpreaFO19, Theorem 2.1]).
Let G be a discrete group with subgroups H and K, and fix
$r\geq 2$
. If every conjugate of H is disjoint from K, then
$$\begin{align*}\mathrm{TC}_r(BG)\geq \mathrm{cd}(H\times K\times G^{r-2}).\end{align*}$$
Our search for suitable subgroups will be organised by the following simple combinatorial object.
Definition 3.3. Fix a ground set S, a graph
$\mathsf{\Gamma}$
and a set W of essential vertices. A binary W-partition of S is a collection
$\lambda =\{\lambda (v)\}_{v\in W}$
of disjoint subsets of S of cardinality
$2$
whose union is S. We say that binary W-partitions
$\lambda $
and
$\mu $
are orthogonal, and write
$\lambda \perp \mu $
, if
$\lambda (v)\neq \mu (w)$
for every
$(v,w)\in W\times W$
.
We will apply Theorem 3.2 to subgroups
$T_\lambda :=\mathrm {im}(\tau _\lambda )$
, where
$\lambda $
is a binary W-partition of
$\{1,\ldots , k\}$
and
$\tau _\lambda :\mathbb {Z}^W\to P_k(\mathsf{\Gamma})$
a certain homomorphism. To study these toric subgroups, we construct detection homomorphisms
$\delta _\lambda :P_k(\mathsf{\Gamma})\to G_W$
, where
$G_W$
is a certain product of free groups. These homomorphisms are constructed in Section 5, and they interact according to the following result, whose proof is taken up in Section 6.
Proposition 3.4. Let
$\lambda $
and
$\mu $
be binary W-partitions of
$\{1,\ldots , k\}$
:
-
1. If
$\lambda =\mu $
, then the composite
$\mathbb {Z}^{W}\xrightarrow {\tau _\lambda } P_k(\mathsf{\Gamma})\xrightarrow {\delta _\mu } G_W$
is injective. -
2. If
$\lambda \perp \mu $
, then the composite
$\mathbb {Z}^{W}\xrightarrow {\tau _{\lambda }} P_k(\mathsf{\Gamma})\xrightarrow {\delta _{\mu }} G_W$
is trivial.
Assuming this result, we prove the theorem.
Proof of Theorem 3.1.
The cases
$m(\mathsf{\Gamma})\in \{0,1\}$
are easily treated by other means, so assume otherwise. By [Reference Luetgehetmann and Recio-MitterLRM19, Proposition 5.6] and [Reference FarberFar03, page 4], the quantity
$\mathrm {TC}_r(\mathrm {Conf}_{k}(\mathsf{\Gamma}))$
is nondecreasing in k for fixed r. Thus, we may assume without loss of generality that
$k=2d$
with
$2\leq d\leq m(\mathsf{\Gamma})$
. These assumptions imply that there exist binary W-partitions
$\lambda $
and
$\mu $
of
$\{1,\ldots , 2d\}$
with
$\lambda \perp \mu $
for some set W of essential vertices. Our aim is to show that
$\mathrm {TC}_r\geq rd$
.
Assume that
$r\geq 2$
. According to Proposition 3.4, we have the containment
$T_{\lambda }\subseteq \ker (\delta _{\mu })$
; therefore, since the latter subgroup is normal, it contains every conjugate of the former. Since
$\ker (\delta _{\mu })$
is disjoint from
$T_{\mu }$
by the same result, the group
$G=P_k(\mathsf{\Gamma})$
and subgroups
$H=T_\lambda $
and
$K=T_\mu $
satisfy the hypotheses of Theorem 3.2. We conclude the relations
$$ \begin{align*} \mathrm{TC}_r(\mathrm{Conf}_{2d}(\mathsf{\Gamma}))&=\mathrm{TC}_r(BP_{2d}(\mathsf{\Gamma}))\\ &\geq\mathrm{cd}(T_\lambda\times T_\mu\times P_{2d}(\mathsf{\Gamma})^{r-2})\\ &=\mathrm{cd}(\mathbb{Z}^{d}\times\mathbb{Z}^d\times P_{2d}(\mathsf{\Gamma})^{r-2})\\ &\geq\mathrm{cd}_{\mathbb{Q}}(\mathbb{Z}^{d}\times\mathbb{Z}^d\times P_{2d}(\mathsf{\Gamma})^{r-2}), \end{align*} $$
where the first uses homotopy invariance and asphericity, the second is Theorem 3.2, the third follows from Proposition 3.4, and the fourth follows by extension of scalars. Thus, it suffices to show that the rational homology of the group
$\mathbb {Z}^{d}\times \mathbb {Z}^d\times P_{2d}(\mathsf{\Gamma})^{r-2}$
is nonzero in degree
$rd$
. Every group in sight has homology of finite type, so the Künneth isomorphism applies, and the conclusion follows from the fact that
$H_d(\mathrm {Conf}_{2d}(\mathsf{\Gamma});\mathbb {Q})\neq 0$
for
$2\leq d\leq m(\mathsf{\Gamma})$
, which is well known—see [Reference An, Drummond-Cole and KnudsenADCK20, Lemma 3.18], for example.
In the case
$r=1$
, the claimed bound is well known; indeed, by asphericity and the Eilenberg–Ganea theorem [Reference Eilenberg and GaneaEG57], the quantity to be estimated is simply
$\mathrm {cd}(P_k(\mathsf{\Gamma}))$
, and the same rational homology calculation applies.
4 Star graphs and theta graphs
This section is devoted to the simple calculation forming the basis for our later arguments.
Definition 4.1. The star graph
$\mathsf {S}_{n}$
is the cone on the discrete space
$\partial \mathsf {S}_{n}:=\{v_1,\ldots , v_n\}$
. The theta graph
$\mathsf {\Theta }_{n}$
is the quotient
$\mathsf {S}_{n}/\partial \mathsf {S}_{n}$
.
Each star and theta graph has a canonical graph structure, which is canonically parametrised. We denote the unique essential vertex of
$\mathsf {S}_{n}$
and its image in
$\mathsf {\Theta }_{n}$
, by
$v_0$
. We denote the image of
$\partial \mathsf {S}_{n}$
in
$\mathsf {\Theta }_{n}$
by
$v_\infty $
. Note that
$\mathsf {\Theta }_{n}$
is (non-canonically) homotopy equivalent to a bouquet of
$n-1$
circles.
The case
$n=3$
is of fundamental importance. Within the configuration space
$\mathrm {Conf}_2(\mathsf {S}_{3})$
, there is the loop given by the sixfold concatenated path
$$\begin{align*}\epsilon=(\underline v_1, e_{23})\star (e_{12}, \underline v_3)\star (\underline v_2, e_{31})\star (e_{23}, \underline v_1)\star (\underline v_3, e_{12})\star (e_{31}, \underline v_2) ,\end{align*}$$
where
$\underline v_i$
denotes the constant path at
$v_i$
and
$e_{ij}:[0,1]\to \mathsf {S}_{3}$
the unique piecewise linear path from
$v_i$
to
$v_j$
with
$e_{ij}(\frac {1}{2})=v_0$
. Note that
$\epsilon $
is a loop based at the configuration
$(v_1, v_2)$
.
It is a standard fact that
$\epsilon :S^1\to \mathrm {Conf}_2(\mathsf {S}_{3})$
is a homotopy equivalence. More precisely, we have the following.
Lemma 4.2. The map
$\epsilon $
factors through an embedding
$\tilde \epsilon : S^1\to \mathrm {Conf}_2(\mathsf {S}_{3})_{v_0}$
as a deformation retract.
Proof. The image of
$\epsilon $
lies in
$\mathrm {Conf}_2(\mathsf {S}_{3})_{v_0}$
by construction, so
$\tilde \epsilon $
exists. It is easy to check that
$\epsilon $
is injective; therefore, since
$S^1$
is compact and
$\mathrm {Conf}_2(\mathsf {S}_{3})$
Hausdorff, it follows that
$\tilde \epsilon $
is an embedding. The space
$\mathrm {Conf}_2(\mathsf {S}_{3})_{v_0}$
is obtained from the image of
$\tilde \epsilon $
by attaching half-open intervals, and collapsing these intervals provides a deformation retraction.
We define a function
$q:\mathrm {Conf}_2(\mathsf {S}_{3})_{v_0}\to \mathsf {\Theta }_{3}$
by recording the coordinate of any particle in
$\mathsf {S}_{3}\setminus \partial \mathsf {S}_{3}$
and sending all other configurations to
$v_\infty $
. Using the glueing lemma, one shows easily that q is continuous.
Lemma 4.3. The following composite homomorphism is injective:
$$\begin{align*}\pi_1(\mathrm{Conf}_2(\mathsf{S}_{3}),(v_1,v_2))\xrightarrow{(\iota_{v_0})_*^{-1}}\pi_1(\mathrm{Conf}_2(\mathsf{S}_{3})_{v_0}, (v_1,v_2)) \xrightarrow{q_*}\pi_1(\mathsf{\Theta}_{3}, v_\infty).\end{align*}$$
Proof. By Proposition 2.2 and Lemma 4.2, it suffices to show that
$q_*\tilde \epsilon _*$
is injective. Since the target is a free group and, in particular, torsion-free, it suffices to show that the path homotopy class
$[q\circ \tilde \epsilon ]$
is nontrivial. Writing
$\gamma _{ij}$
for the loop in
$\mathsf {\Theta }_{3}$
induced by
$e_{ij}$
, and noting the relations
$[\gamma _{31}]=[\gamma _{32}\star \gamma _{21}]$
and
$\bar \gamma _{ij}=\gamma _{ji}$
, we have
$$ \begin{align*} [q\circ\tilde \epsilon]&=[\gamma_{23}\star \gamma_{12}\star \gamma_{31}\star\gamma_{23}\star \gamma_{12}\star \gamma_{31}]\\ &=[\gamma_{23}\star\gamma_{12}\star\gamma_{32}\star\gamma_{21}\star\gamma_{23}\star\gamma_{12}\star\gamma_{32}\star\gamma_{21}]\\ &=[\gamma_{23}\star\gamma_{12}\star\bar\gamma_{23}\star\bar\gamma_{12}\star\gamma_{23}\star\gamma_{12}\star\bar\gamma_{23}\star\bar\gamma_{12}]\\ &=[\gamma_{23}][\gamma_{12}][\gamma_{23}]^{-1}[\gamma_{12}]^{-1}[\gamma_{23}][\gamma_{12}][\gamma_{23}]^{-1}[\gamma_{12}]^{-1}. \end{align*} $$
This expression is a nonempty reduced word in the set
$\{[\gamma _{12}],[\gamma _{23}]\}$
, which forms a system of free generators for
$\pi _1(\mathsf {\Theta }_{3},v_\infty )$
, implying the claim.
Remark 4.4. One can interpret the theta graph appearing here (up to homotopy) as the configuration space of two unordered points in the quotient
$\mathsf {S}_{3}/\partial \mathsf {S}_{3}$
, regarded as a graph with a ‘sink’ vertex at which points are permitted to collide [Reference Chettih and LütgehetmannCL18]. Informally, a deformation retraction is provided by allowing particles to flow down the edges of the graph until at least one reaches the sink. The use of graphs with sinks in [Reference Luetgehetmann and Recio-MitterLRM19] inspired some of the ideas in the present article.
Remark 4.5. The same calculation shows that the composite of Lemma 4.3 is trivial at the level of homology. Ultimately, it is this fact that forms the obstacle to a cohomological proof of Farber’s conjecture for nonplanar graphs; see [Reference KnudsenKnu21] for further discussion.
5 Toric and detection homomorphisms
Fix a set W of essential vertices and a binary W-partition
$\lambda $
of
$\{1,\ldots , k\}$
. For each
$v\in W$
, given our choice of parametrisation and subdivision, there is a piecewise linear cellular embedding
$f_v:\mathsf {S}_{3}\to \mathsf{\Gamma}$
uniquely specified by requiring that it send the ith edge of
$\mathsf {S}_{3}$
to the ith edge at v for
$1\leq i\leq 3$
. These embeddings induce an embedding f from a W-indexed disjoint union of star graphs (we use our assumption on the closed stars at essential vertices). Consider the composite embedding
$$\begin{align*}\varphi_\lambda: (S^1)^W\to \mathrm{Conf}_2(\mathsf{S}_{3})^W\to \mathrm{Conf}_{k}\left(\coprod_{v\in W} \mathsf{S}_{3}\right)\to\mathrm{Conf}_{k}(\mathsf{\Gamma}),\end{align*}$$
where the first map is the canonical map
$\epsilon $
in each factor, the second is the inclusion of the subspace in which the coordinates indexed by the elements of
$\lambda (v)$
lie in the component indexed by v, and the third is induced by the embedding f.
Finally, we choose a path
$\alpha _\lambda $
in
$\mathrm {Conf}_k(\mathsf{\Gamma})$
from
$\varphi _\lambda (1)$
to
$x_0$
. We require this path to be a concatenation of coordinatewise linear edge paths in
$\mathsf{\Gamma}$
with all but one coordinate stationary. Such a path exists by our assumption that
$\mathsf{\Gamma}$
is connected and
$m(\mathsf{\Gamma})>0$
(in particular,
$\mathrm {Conf}_k(\mathsf{\Gamma})$
is connected).
Remark 5.1. By construction, the image of the embedding
$\varphi _\lambda $
lies in
$\mathrm {Conf}_k(\mathsf{\Gamma})_v$
for every essential vertex v. The same holds for the path
$\alpha _\lambda $
. Our notation will not distinguish among the various resulting paths, even though they have different codomains.
With these desiderata in hand, we are ready to define the toric homomorphism associated to
$\lambda $
. The reader is cautioned that this homomorphism depends on many choices, none of which are reflected in our notation. Most of these choices affect the definition only up to conjugation in
$P_k(\mathsf{\Gamma})$
.
Definition 5.2. Let
$\lambda $
be a binary W-partition of
$\{1,\ldots , k\}$
. The homomorphism
$\tau _\lambda $
is the composite
$$\begin{align*}\mathbb{Z}^W\cong \pi_1(S^1,1)^W\xrightarrow{(\varphi_\lambda)_*}\pi_1(\mathrm{Conf}_k(\mathsf{\Gamma}), \varphi_\lambda(1))\xrightarrow{\hat \alpha_\lambda}P_k(\mathsf{\Gamma}).\end{align*}$$
The target of the detection homomorphism
$\delta _\lambda $
will be the product of free groups
$G_W:=\prod _{v\in W}\pi _1(\mathsf {\Theta }_{d(v)}, v_\infty ))$
. To define
$\delta _\lambda $
, we note that our description of the quotient map q given in Section 4 in fact describes a map
$q_v:\mathrm {Conf}_2(\mathsf{\Gamma})_v\to \mathsf {\Theta }_{d(v)}$
for any essential vertex v in
$\mathsf{\Gamma}$
. Note that we use our subdivision assumption as well as our chosen ordering of the edges at v.
In the following definition,
$\pi $
denotes coordinate projection.
Definition 5.3. Let
$\lambda $
be a binary W-partition of
$\{1,\ldots , k\}$
. The homomorphism
$\delta _\lambda : P_k(\mathsf{\Gamma})\to G_W$
is the homomorphism with vth component the composite
$$\begin{align*}P_k(\mathsf{\Gamma})\xrightarrow{(\iota_v)_*^{-1}} \pi_1(\mathrm{Conf}_k(\mathsf{\Gamma})_v, x_0)\xrightarrow{(\pi_{\lambda(v)})_*} \pi_1(\mathrm{Conf}_2(\mathsf{\Gamma})_v, \pi_{\lambda(v)}(x_0))\xrightarrow{(q_v)_*} \pi_1(\mathsf{\Theta}_{d(v)}, v_\infty).\end{align*}$$
Note that since each coordinate of our basepoint
$x_0$
is a bivalent vertex, the composite in question does send
$x_0$
to
$v_\infty $
. We emphasise that although the target of
$\delta _\lambda $
depends only on W, the homomorphism itself depends on
$\lambda $
.
6 Proof of Proposition 3.4
In this section, we consider the interaction between the toric and detection homomorphisms defined above. At various points, we will employ an unnamed map of the form
$\mathrm {Conf}_2(\mathsf {S}_{3})\to \mathrm {Conf}_k(\mathsf{\Gamma})_w$
, which is obtained by restricting the map
$\mathrm {Conf}_2(\mathsf {S}_{3})^W\to \mathrm {Conf}_k(\mathsf{\Gamma})_w$
determined by a binary W-partition along the section of the projection onto the wth factor determined by respective basepoints.
The key result is the following.
Lemma 6.1. Let
$\lambda $
and
$\mu $
be binary W-partitions of
$\{1,\ldots , k\}$
. For
$v,w\in W$
, the composite homomorphism
is trivial unless
$v=w$
and
$\lambda (v)=\mu (v)$
.
Proof. After defining the paths
$\beta =\pi _{\mu (w)}\circ \alpha _\lambda $
and
$\gamma =q_w\circ \beta $
, we have the commutative diagram of homomorphisms
where the dashed filler arises from Remark 5.1. The claim is that the total composite is trivial unless
$v=w$
and
$\lambda (v)=\mu (v)$
. If
$v\neq w$
, then the composite map
$$\begin{align*}\mathrm{Conf}_2(\mathsf{S}_{3})\to \mathrm{Conf}_k(\mathsf{\Gamma})_w\xrightarrow{\pi_{\mu(w)}} \mathrm{Conf}_2(\mathsf{\Gamma})_w\xrightarrow{q_w} \mathsf{\Theta}_{d(w)}\end{align*}$$
is the constant map to the basepoint; indeed, the image of the embedding
$f_v:\mathsf {S}_{3}\to \mathsf{\Gamma}$
is disjoint from the open star of w, since it is contained in the closed star of v. Here we use the assumption that
$v\neq w$
as well as our assumption on the subdivision of
$\mathsf{\Gamma}$
.
Without loss of generality, then, we may take
$v=w$
. If
$\lambda (v)\cap \mu (v)=\varnothing $
, then the composite map
$$\begin{align*}\mathrm{Conf}_2(\mathsf{S}_{3})\to \mathrm{Conf}_k(\mathsf{\Gamma})_v\xrightarrow{\pi_{\mu(v)}} \mathrm{Conf}_2(\mathsf{\Gamma})_v\end{align*}$$
is constant with value
$\pi _{\mu (v)}(\varphi _\lambda (1))$
, and the claim follows as before; thus, we may assume that
$\lambda (v)\cap \mu (v)=\{1\}$
. In this case, the loop
$$\begin{align*}S^1\xrightarrow{\epsilon} \mathrm{Conf}_2(\mathsf{S}_{3})\to \mathrm{Conf}_k(\mathsf{\Gamma})_v\xrightarrow{\pi_{\mu(v)}} \mathrm{Conf}_2(\mathsf{\Gamma})_v\xrightarrow{q_v} \mathsf{\Theta}_{d(v)}\end{align*}$$
is the sixfold concatenation
$\underline v_\infty \star \gamma _{12}\star \underline v_\infty \star \gamma _{23}\star \underline v_\infty \star \gamma _{31}$
, and we calculate that
$$ \begin{align*}[\underline v_\infty\star \gamma_{12}\star \underline v_\infty\star \gamma_{23}\star \underline v_\infty\star \gamma_{31}]&=[\gamma_{12}\star\gamma_{23}\star\gamma_{31}]\\ &=[\gamma_{12}\star\gamma_{23}\star\gamma_{32}\star\gamma_{21}]\\ &=[\gamma_{12}\star\gamma_{23}\star\bar\gamma_{23}\star\bar\gamma_{12}]\\ &=[\gamma_{12}][\gamma_{23}][\gamma_{23}]^{-1}[\gamma_{12}]^{-1}\\ &=1. \end{align*} $$
Since the composite in question annihilates a generator, it is trivial.
The desired result is now within easy reach.
Proof of Proposition 3.4.
Lemma 6.1 implies that the composite
$\delta _\lambda \circ \tau _\lambda $
splits as a product of homomorphisms indexed by W, so the first claim is equivalent to the injectivity of each of these component homomorphisms. The injectivity of the component indexed by
$v\in W$
is equivalent to the injectivity of the total composite in the commutative diagram
where the homomorphism in the bottom left is induced by the inclusion
$\{1,2,3\}\subseteq \{1,\ldots , d(v)\}$
. In terms of systems of free generators, this homomorphism is induced by the inclusion
$\{[\gamma _{12}],[\gamma _{23}]\}\subseteq \{[\gamma _{12}],[\gamma _{23}],\ldots , [\gamma _{d(v)-1, d(v)}]\}$
; in particular, it is injective. Since
$\hat \gamma $
is an isomorphism, the claim follows from Lemma 4.3, which implies that the composite in the left-hand vertical column is injective.
For the second claim, suppose that
$\lambda \perp \mu $
. Since
$\delta _\mu \circ \tau _\lambda $
is a homomorphism out of a direct sum and into a product, it suffices to establish the triviality of the composite homomorphisms
for every
$(v,w)\in W\times W$
. By assumption, we have
$\lambda (v)\neq \mu (w)$
for every such pair, so the claim follows from Lemma 6.1.
Acknowledgements
The seeds of this paper were sown when Andrea Bianchi noticed an early error in [Reference KnudsenKnu21], prompting the author to reconsider the role of cohomology in the nonplanar setting. The ideas came during the 2022 workshop ‘Topological Complexity and Motion Planning’ held at CMO BIRS in Oaxaca, and the author thanks Dan Cohen, Jesús González and Lucile Vandembroucq for their skilful organisation. The author benefited from fruit-full conversations with Daciberg Gonçalves and Teresa Hoekstra Mendoza, and he thanks Andrea Bianchi, Jesús González and the anonymous referee for comments on an earlier draft.
Conflicts of Interest
The authors have no conflicts of interest to declare.
Financial support
The author was supported by NSF grant DMS-1906174.
Open access
