Monotonicity of unordered graph motion-planning complexity
Let $\Gamma$ be a connected finite graph, viewed as a one-dimensional CW complex with at least one edge, and for $k \ge 1$ let $$B_k(\Gamma) = \{(x_1, \dots, x_k) \in \Gamma^k : x_i \ne x_j \text{ for } i \ne j\} / \mathfrak{S}_k$$ be its unordered configuration space, with the quotient topology. Write $\operatorname{TC}$ for Farber's topological complexity in the reduced convention: $\operatorname{TC}(X)$ is the least $q \ge 0$ such that $X \times X$ is covered by open sets $U_0, \dots, U_q$, each admitting a continuous section of the endpoint map $C([0,1], X) \to X \times X$, $\gamma \mapsto (\gamma(0), \gamma(1))$. Let $m(\Gamma)$ be the number of vertices of degree at least $3$ and $m_3(\Gamma)$ the number of degree $3$. Knudsen proved that $\operatorname{TC}(B_k(\Gamma)) = 2m(\Gamma)$ for all $k \ge 2m(\Gamma) + m_3(\Gamma)$ when $m(\Gamma) \ge 2$ and $\Gamma$ has no non-separating trivalent vertex, and Jankiewicz and Schreve proved the same equality, in the same range of $k$, whenever $m(\Gamma) > 0$.
Problem. Is $$\operatorname{TC}(B_k(\Gamma)) \le \operatorname{TC}(B_{k+1}(\Gamma))$$ for every such graph $\Gamma$ and every integer $k \ge 1$?
Source: Knudsen (2026), §1.2, the monotonicity question among his future directions (arXiv 2023, revised 2026). Stated for connected graphs by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- AT — Algebraic Topology
- Secondary
- GT
- Keywords
- AIM Open Applied Problems, configuration spaces, graph braid groups, topological complexity
References
@article{knudsen2026,
author = {Knudsen, Ben},
title = {On the stabilization of the topological complexity of graph braid groups},
journal = {J. Appl. Comput. Topol.},
volume = {10},
number = {2},
year = {2026},
pages = {9},
doi = {10.1007/s41468-026-00232-4},
eprint = {2302.04346},
archivePrefix = {arXiv},
}
@article{jankiewicz2025,
author = {Jankiewicz, Kasia and Schreve, Kevin},
title = {Products of free groups inside graph braid groups},
journal = {Math. Z.},
volume = {311},
number = {4},
year = {2025},
pages = {87},
doi = {10.1007/s00209-025-03871-y},
eprint = {2404.08863},
archivePrefix = {arXiv},
}
@misc{aim-unordered-graph-motion-monotonicity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Monotonicity of unordered graph motion-planning complexity}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/508-unordered-graph-motion-monotonicity.md},
note = {Entry 508 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00914, "Monotonicity of unordered graph motion-planning complexity", clopen.solutions.