Topological complexity of unordered configuration spaces of certain graphs

DOI10.1016/J.TOPOL.2020.107382MaRDI QIDQ2216663zbMATH OpenOpenAlexFDO

Authors Steven Scheirer

Publication date 16 December 2020

Published in Topology and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.12838

zbMATH Keywords

graphsdiscrete Morse theoryconfiguration spacestopological complexity

Mathematics Subject Classification ID

Discriminantal varieties and configuration spaces in algebraic topology (55R80) Relations of low-dimensional topology with graph theory (57M15) Lyusternik-Shnirel'man category of a space, topological complexity à la Farber, topological robotics (topological aspects) (55M30)

Abstract: The unordered configuration space of $n$ points on a graph $Gamma,$ denoted here by $U{C}^n(Gamma),$ can be viewed as the space of all configurations of $n$ unlabeled robots on a system of one-dimensional tracks, which is interpreted as a graph $Gamma.$ The topology of these spaces is related to the number of vertices of degree greater than 2; this number is denoted by $m(Gamma).$ We discuss a combinatorial approach to compute the topological complexity of a "discretized" version of this space, $U{D}^n(Gamma),$ 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 $2m(Gamma)$, then $TC(U{D}^n(Gamma))=2m(Gamma)+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 $Gamma,$ we have $TC(U{D}^n(Gamma))=2n+1.$

Recommendations

• Topological complexity of \(n\) points on a tree
• Topological complexity of unordered configuration spaces of surfaces
• Topological complexity of configuration spaces of fully articulated graphs and banana graphs
• Topological complexity of configuration spaces
• Linear motion planning with controlled collisions and pure planar braids

Cites work

• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 5250987 (Why is no real title available?)
• A user's guide to discrete Morse theory
• Configuration spaces and robot motion planning algorithms
• Discrete Morse theory and graph braid groups.
• Graph braid groups and right-angled Artin groups.
• Homological and finiteness properties of picture groups
• Homology of tree braid groups.
• Morse theory for cell complexes
• On the cohomology rings of tree braid groups.
• Presentations of graph braid groups.
• Topological complexity of \(n\) points on a tree
• Topological complexity of motion planning

Cited in

(14)

• Bounds for the higher topological complexity of configuration spaces of trees
• Topological complexity of \(n\) points on a tree
• Topological complexity of graphic arrangements
• Topological complexity of configuration spaces
• Topological complexity of unordered configuration spaces of surfaces
• scientific article; zbMATH DE number 4051659 (Why is no real title available?)
• Farber's conjecture for planar graphs
• Farber's conjecture and beyond
• Farley-Sabalka's Morse-theory model and the higher topological complexity of ordered configuration spaces on trees
• Topological complexity of configuration spaces of fully articulated graphs and banana graphs
• The topological complexity of the ordered configuration space of disks in a strip
• Two robots moving geodesically on a tree
• Relative topological complexity and configuration spaces
• Totally normal cellular stratified spaces and applications to the configuration space of graphs

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)