Abstract
We prove that the ordered configuration spaces of planar graphs have the highest possible topological complexity generically, as predicted by a conjecture of Farber. Our argument establishes the same generic maximality for all higher topological complexities. We include some discussion of the non-planar case, demonstrating that the standard approach to the conjecture fails at a fundamental level.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abrams, A.: Configuration spaces of braid groups of graphs. PhD thesis, UC Berkeley, (2000)
Aguilar-Guzmán, J., González, J., Hoekstra-Mendoza, T.: Farley–sabalka’s morse-theory model and the higher topological complexity of ordered configuration spaces of trees. arXiv:1911.12522, (2019)
An, B.H., Drummond-Cole, G.C., Knudsen, B.: Subdivisional spaces and graph braid groups. Doc. Math. 24, 1513–1583 (2019)
Basabe, I., González, J., Rudyak, Y., Tamaki, D.: Higher topological complexity and its symmetrization. Algebr. Geom. Topol. 14, 2103–2124 (2014)
Chettih, S., Lütgehetmann, D.: The homology of configuration spaces of trees with loops. Alg. Geom. Topol. 18(4), 2443–2469 (2018)
Cohen, D., Farber, M.: Topological complexity of collision-free motion planning on surfaces. Compos. Math. 147, 649–660 (2009)
Farber, M.: Topological complexity of motion planning. Discrete Comput. Geom. 29, 211–221 (2003)
Farber, M.: Collision free motion planning on graphs. In: Erdmann, M., Overmars, M., Hsu, D., van der Stappen, F. (eds.) Algorithmic Foundations of Robotics VI, vol. 17, pp. 123–138. Springer, Berlin (2005)
Farber, M.: Configuration Spaces and Robot Motion Planning Algorithms. Lecture Notes Series Institute for Mathematical Sciences, World Scientific, Singapore (2017)
Farber, M., Grant, M.: Topological complexity of configuration spaces. Proc. Amer. Math. Soc 137, 1841–1847 (2009)
Ghrist, R.: Configuration spaces and braid groups on graphs in robotics. In Knots, braids, and mapping class groups—papers dedicated to Joan S. Birman (New York, 1998), volume 24 of AMS/IP Stud. Adv. Math., pp. 29–40. Amer. Math. Soc., 2002
Ko, K.H., Park, H.W.: Characteristics of graph braid groups. Discrete Comput. Geom. 48, 915–963 (2012)
Luetgehetmann, D., Recio-Mitter, D.: Topological complexity of configuration spaces of fully articulated graphs and banana graphs. Discrete Comput. Geom. 65, 693–712 (2019)
Rudyak, Y.: On higher analogues of topological complexity. Topol. Appl. 157, 916–920 (2010)
Scheirer, S.: Topological complexity of unordered configuration spaces of certain graphs. Topol. Appl. 285, 107382 (2020)
Sinha, D.: The homology of the little disks operad. arXiv:hep-th/0610236, (2010)
Świątkowski, J.: Estimates for homological dimension of configuration spaces of graphs. Colloq. Math. 89(1), 69–79 (2001)
Acknowledgements
The author thanks Byung Hee An and Jesus Gonzalez for helpful conversations. Special thanks are due to Andrea Bianchi, who discovered the error in an incorrect proof of the general case of Farber’s conjecture appearing in an earlier version. The author learned of Farber’s conjecture at the AIM workshop “Configuration spaces of graphs” and was reminded of it at the BIRS–CMO workshop “Topological complexity and motion planning.” While writing, the author benefited from the hospitality of the MPIM and was supported by NSF grant DMS 1906174.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Knudsen, B. Farber’s conjecture for planar graphs. Sel. Math. New Ser. 27, 90 (2021). https://doi.org/10.1007/s00029-021-00702-w
Accepted:
Published:
DOI: https://doi.org/10.1007/s00029-021-00702-w