Farber's theorem for Topological Complexity $TC$ and $TC$ of a robot moving on $8$ and a bouquet of seven circles.

In this post, we will be introducing Farber's other theorems that will be helpful to us to find the topological complexity of one robot moving on number $8$ and on a bouquet of $7$ circles.

Farber's Theorem:

Michael Farber gave a theorem which gives the upper bound for $TC(X)$. The theorem is as below:

Farber's Theorem $1$: "For any path-connected paracompact locally contractible space $X$ one has

$TC(X) \leq  2\dim X + 1$

where $\dim X$ denotes the covering dimension of $X$. "

This means that if we know the dimension of any space $X$, then we can find the upper bound of the $TC(X)$. For example, if the space is a circle, then its dimension is $1$. Therefore, the upper bound for the $TC(S^1)$ of a robot moving on a circle $S^1$ is $3$, i.e., $TC(S^1) \leq 3$. If space is a sphere $S^2$, then its dimension is $2$. Therefore, $TC(S^2) \leq 5$.

Also, Farber gave a Lemma on finding the $TC(X)$ using the Lusternik-Schnirelmann Category $cat(X)$. Below is the Lemma:

Farber's Lemma $1$: "One has

$cat(X)  \leq TC_2(X)  \leq  cat(X \times X).$ "

Mathematician Lazar Lyusternik and Lev Schirelmann first introduced the definition of Lusternik- Schirelmann category $cat(X)$.

John Oprea and Jeff Strom(2010) in their paper "Lusternik-Schirelmann category, complements of skeleta and a theorem of Dranishnikov" stated the definition of Lusternik-Schirelmann category $cat(X)$ as:

"The Lusternik–Schnirelmann category of a space $X$, denoted $cat(X)$, is the smallest integer $m$ so that $X$ can be covered by open sets $U_0, U_1, \cdots, U_m$, each of which is contractible to a point in $X$."

This means that any space $X$ can be divided into smallest integer $m$ such that each part is contractible to a point in space $X$ itself. For example, if the space is a circle $S^1$, then the $cat(S^1)$ will be $2$ because there are two minimum open sets(curve) which will be contractible to a point in space $S^1$.

Now, if we use the rule of inequalities and combine the Theorem $1$ and Lemma $1$, we will get:

$$cat(X) \leq TC(X) \leq 2\dim X +1$$

For the case of circle $S^1, cat(S^1)$ is $2$ and $dim S^1$ is $1$. Therefore, we will have:

$$2 \leq TC(S^1) \leq 3.$$

We already solved this problem in one of our last posts as we founded that the $TC(S^1)$ is $2$. Our challenge is to find the $TC$ of a robot moving on a number $8$ and on the bouquet of seven circles.

Topological Complexity of a robot moving on 8 and a bouquet of seven circles:

We know that the $cat(8)$ and of the bouquet of seven circles is $2$ and their dimension is $1$. Therefore, we get:

  $$2 \leq TC(S^1) \leq 3.$$

Now, we have to find the exact $TC$ to solve our problem. Let's introduce the new theorem of Farber based on graphs and Betti numbers of independent 1-dimensional space $b_1$.

Farber's Theorem $2$: "If $X$ is a connected finite graph then

$$TC(X) =  \begin{cases} 1 & \text {if} \, b_1(X) =0, \\ 2 & \text{if} \,  b_1(X)=1, \\ 3 & \text{if} \,  b_1(X) > 1. \end{cases}$$

Here, a graph(as in Graph Theory) is something where there are points in space called vertices, and they are connected by a line called edges. Betti numbers $b_t$ are the total numbers of $t$-independent higher dimensional surfaces(or $t$ dimensional holes) in any space $X$. To find the 1st-Betti numbers of graphs, the formula is $m-n+k$ where $m$ is edges, $n$ is vertices, and $k$ is the total numbers of connected components of the graph. This formula can only be used to find 1st-Betti numbers(i.e. it is not applicable when $t \neq 1$). To understand Betti numbers in depth, watch this lecture on Homology and to learn more about graph theory, read this article.

To understand it more clearly, let's take an example of $8$ as shown in Figure $1$. Here, there is only one vertex $1$ which is the center of $8$ and two edges(loops). Now, Betti numbers of $1$-independent higher dimensional surfaces $b_0$ is $1$, $1$-dimensional surface $b_1$ is $2$, and $2$-dimensional surface $b_2$ is $0$.

Now, if the graph(space) is a line, then there is one edge, two vertices, and one connected component. According to the formula to find the Betti number $b_1$ of a graph, we get:
$$m-n+k=1-2+1=0$$
From above theorem, we know that $b_1$ is $0$ and so, the $TC$ is 1.

If the graph is a circle $S^1$, then there is one edge, one vertex, and one connected component. So, $b_1$ will be 1. Therefore, from the theorem, $TC$ of a robot moving on a circle will be $2$.

Figure 1: Graph with vertex (1} and two edges(loops)

We know that space $8$ and a bouquet of seven circles are connected finite graphs. Also, for the space $8$:
  $$b_1(8)=m-n+k=2-1+1$$
and for bouquet of seven circles (rose with seven petals), $b_1$ is $7$($m-n+k=7-1+1$). According to the above theorem, in both our cases, $b_1(X) >1$.  Therefore, the topological complexity of a robot moving on a number $8$ and on a bouquet of seven circles is $3$, i.e., $TC=3$.

References:

Farber, Michael (2005) Topology of Robot Motion Planning, Springer. Printed in the Netherlands., 195-240.

Oprea, John; Strom, Jeff Lusternik-Schnirelmann category, complements of skeleta and a theorem of Dranishnikov. Algebr. Geom. Topol. 10 (2010), no. 2, 1165–1186.


Posted by Chintan Patel.