# Simplicial and combinatorial versions of higher symmetric topological
complexity

Amit Kumar Paul  and  Debasis Sen  Department of Mathematics and Statistics
Indian Institute of Technology, Kanpur
Uttar Pradesh 208016
India  kamitp<EMAIL_ADDRESS>Department of Mathematics and
Statistics
Indian Institute of Technology, Kanpur
Uttar Pradesh 208016
India<EMAIL_ADDRESS>
###### Abstract.

In this paper, we introduce higher symmetric simplicial complexity
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)$ of a simplicial complex $K$ and
higher symmetric combinatorial complexity
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)$ of a finite poset $P$. These are
simplicial and combinatorial approaches to symmetric motion planning of Basabe
- González - Rudyak - Tamaki. We prove that the symmetric simplicial
complexity $\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)$ is equal to symmetric
topological complexity $\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$ of the
geometric realization of $K$ and the symmetric combinatorial complexity
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)$ is equal to symmetric topological
complexity $\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|\mathcal{K}(P)|)$ of the
geometric realization of the order complex of $P$.

###### Key words and phrases:

Topological complexity, simplicial complex, symmetric group, finite space

###### 2010 Mathematics Subject Classification:

Primary 57Q05 ; Secondary: 05E45, 06A07, 68T40.

##  1\. Introduction

The _topological complexity_ of a path connected space $X$ was introduced by
Farber (cf. [6]). It is a homotopy invariant measure of the complexity to
construct a motion-planning algorithm on the space $X$. Let $I=[0,1]$ and
$X^{I}$ denotes the free path space. Consider the fibration,

(1) $p:X^{I}\rightarrow X\times X,~{}~{}\gamma\mapsto(\gamma(0),\gamma(1)).$

Then the topological complexity of $X$ is defined to be the least positive
integer $k$ such that there exists an open cover $\\{U_{1},\cdots,U_{k}\\}$ of
$X\times X$ with continuous section of $p$ over each $U_{i}$ (i.e. a
continuous map $s_{i}:U_{i}\rightarrow X^{I}$ satisfying $p\circ
s_{i}=\operatorname{Id}_{U_{i}}$ for $i=1,2,\cdots,k$). It is denoted by
$\operatorname{\mathsf{T}C}(X)$. Generalizing the idea, Rudyak defined higher
topological complexity (cf. [13]). He introduced _n-th topological complexity_
$\operatorname{\mathsf{T}C}_{n}(X),\ n\geq 2$ such that
$\operatorname{\mathsf{T}C}_{2}(X)=\operatorname{\mathsf{T}C}(X)$. We recall
the definition of higher topological complexity in the next section. Farber
and Grant introduced symmetric topological complexity
$\operatorname{\mathsf{T}C}^{S}(X)$ of a path connected space $X$ with the
idea that the motion planning between $(p,q)$ and $(q,p)$ are inverses of each
other (cf. [7]). They observed that $\operatorname{\mathsf{T}C}^{S}(X)$ is not
a homotopy invariant. To rectify it, Basabe, González, Rudyak, and Tamaki
defined another version of symmetric topological complexity
$\operatorname{\mathsf{T}C}^{\Sigma}(X)$ and generalized it for higher version
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$ (see [2]). The
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$ is homotopy invariant and
naturally defined. In ([2]) the authors proved that this two invariants differ
by at most $1$ for $n=2$.

A simplicial approach of topological complexity, _simplicial complexity_ , was
introduced by González (cf. [8]). It is proved there that for a finite
simplicial complex $K$, the simplicial complexity
$\operatorname{\mathsf{S}C}(K)$ and the topological complexity of its
geometric realization $\operatorname{\mathsf{T}C}(|K|)$ are equal. Higher
analogue of this result was obtained in [10]. In this paper we introduce
_symmetric simplicial complexity_ $\operatorname{\mathsf{S}C}^{\Sigma}(K)$ and
its higher version $\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)$. We show that
they are equal to symmetric topological complexity of the geometric
realization of $K$. This result is a symmetric version of [10, Theorem 3.5].

######  Theorem A.

For a finite simplicial complex $K$,
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$,
for any $n\geq 2$.

(See Theorem 3.19)

A combinatorial analogue of topological complexity was introduced by Tanaka
for a finite space (or equivalently for a finite poset, see Section 4.1)
([16]). It is proved there that the combinatorial complexity
$\text{CC}^{\infty}(P)$ of a finite space $P$ represent the topological
complexity $\operatorname{\mathsf{T}C}(|\mathcal{K}(P)|)$, where
$|\mathcal{K}(P)|$ denote the realization of the order complex of $P$ (see
Section 3.1). This was generalized to higher combinatorial complexity in [10].
Moreover Tanaka introduced symmetric combinatorial complexities
$\operatorname{\mathsf{C}C}^{S}(P)$ and
$\operatorname{\mathsf{C}C}^{\Sigma}(P)$ for a finite space $P$, where the
first one is an analogue of $\operatorname{\mathsf{T}C}^{S}$ and the second
one is of $\operatorname{\mathsf{T}C}^{\Sigma}$ (cf. [17]). He proved that the
symmetric combinatorial complexities of $P$ and symmetric topological
complexities of $|\mathcal{K}(P)|$ are same:
$\operatorname{\mathsf{C}C}^{S}(P)=\operatorname{\mathsf{T}C}^{S}(|\mathcal{K}(P)|)$
and
$\operatorname{\mathsf{C}C}^{\Sigma}(P)=\operatorname{\mathsf{T}C}^{\Sigma}(|\mathcal{K}(P)|)$.
Here we introduce _higher symmetric combinatorial complexity_
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)$ for a finite space $P$ and
generalized the second result. This can also be described as a symmetric
analogue of [10, Theorem 5.6].

######  Theorem B.

For a finite space $P$,
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)=\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|\mathcal{K}(P)|)$,
$n\geq 2$.

(See Theorem 4.20)

######  1.1.

Organization.  The organization of the rest of the paper is as follows. In
Section 2, we recall basic ideas of topological complexity and symmetric
topological complexity. In Section 3, we introduce symmetric simplicial
complexity of a simplicial complex $K$ and prove Theorem A. In Section 4,
define higher symmetric combinatorial complexity of a finite space $P$ and
prove Theorem B.

######  1.2 Acknowledgements.

The first author would like to thank IIT Kanpur for PhD fellowship and the
second author would like to thank SERB for project grant MTR/2020/000343.

##  2\. Symmetric topological complexity

In this section we first recall the definition of topological complexity and
its higher versions. Then we review basic concepts of symmetric topological
complexity. For details we refer to [6, 5, 13, 7, 2].

######  2.1.

Topological complexity.  Let $q:E\rightarrow B$ be a fibration. The _sectional
category_ of $q$ is the minimum integer $k$ such that $B$ can be cover by $k$
open subsets, $U_{1}\cup U_{2}\cup\cdots\cup U_{k}=B$ and on each $U_{i}$
there is a section $s_{i}:U_{i}\to E$ of $q$. It is denoted by
$\operatorname{secat}(q)$. If no such $k$ exists then we say
$\operatorname{secat}(q)=\infty$. Then topological complexity of $X$ can be
described as $\operatorname{\mathsf{T}C}(X)=\operatorname{secat}(p)$, where
$p$ is the fibration of Equation 1.

Suppose $I_{n},n\geq 2,$ denote the wedge of $n$ intervals
$[0,1]\times\\{j\\}$, where $(0,j),j\in\\{1,2,\cdots,n\\}$ are identified. We
denote $j$-th interval by $[0,1]_{j}$ and the parameter in $[0,1]_{j}$ by
$(t,j)=t_{j}$. For any two points $t^{1}_{j},t^{2}_{j}\in[0,1]_{j}$ we write
$t^{2}_{j}\geq t^{1}_{j}$ if and only if $t^{2}\geq t^{1}$. Consider the
mapping space $X^{I_{n}}$ and the fibration

(2) $e_{n}:X^{I_{n}}\rightarrow
X^{n},~{}~{}~{}\alpha\mapsto(\alpha(1_{1}),\alpha(1_{2}),\cdots,\alpha(1_{n})).$

Then the _n-th topological complexity_ of $X$ is defined to be
$\operatorname{\mathsf{T}C}_{n}(X):=\operatorname{secat}(e_{n})$. It can be
defined alternatively as
$\operatorname{\mathsf{T}C}_{n}(X)=\operatorname{secat}(e^{\prime}_{n})$,
where

(3) $e^{\prime}_{n}:X^{I}\rightarrow
X^{n},~{}~{}~{}~{}e^{\prime}_{n}(\alpha)=(\alpha(0),\alpha(\frac{1}{n-1}),\alpha(\frac{2}{n-1}),\cdots,\alpha(1)).$

This is because $e_{n}$ and $e_{n}^{\prime}$ are both fibrational replacement
of the diagonal map $X\to X^{n}$. Clearly
$\operatorname{\mathsf{T}C}_{2}(X)=\operatorname{\mathsf{T}C}(X)$. Also it is
known that $\\{\operatorname{\mathsf{T}C}_{n}(X)\\}$ is a non-decreasing
sequence. If a space $Y$ is homotopy equivalent to $X$, then
$\operatorname{\mathsf{T}C}_{n}(Y)=\operatorname{\mathsf{T}C}_{n}(X)$ for any
$n\geq 2$. Consequently, $X$ is contractible if and only if
$\operatorname{\mathsf{T}C}_{n}(X)=1$ for any $n\geq 2$.

######  2.2.

Symmetric topological complexity.  To define symmetric topological complexity
we need the notion of _equivariant sectional category_. Let $G$ be a finite
group. A topological space $E$ with an action of a group $G$ is called a
$G$-space. A subset $U\subset E$ is called _$G$ -invariant_ if $gU\subseteq U$
for all $g\in G$. Consider another $G$-space $B$. A fibration $q:E\to B$ is
called $G$-fibration if $q$ is a $G$-map, i.e $q(gx)=gq(x)$ for all $x\in E$
and $g\in G$. The _equivariant sectional category_ of a $G$-fibration $q$ is
the minimum number $k$ such that $B$ can be cover by $G$-invariant open
subsets, $U_{1}\cup U_{2}\cup\cdots\cup U_{k}=B$ and on each $U_{i}$ there is
a $G$-section (a section which is $G$-map) of $q$. It is denoted by
$\operatorname{secat}_{G}(q)$. If no such $k$ exists then we say
$\operatorname{secat}_{G}(q)=\infty$.

Farber and Grant ([7]) introduced _symmetric topological complexity_
$\operatorname{\mathsf{T}C}^{S}(X)$ for a path connected space $X$. For
symmetric motion planning they consider a section $s:X\times X\to X^{I}$ (not
necessarily continuous) of $p$ in Equation (1), such a way that $s(x,x)(t)=x$
and $s(x,y)(t)=s(y,x)(1-t)$, for all $x,y\in X$ and $t\in I$. For this they
take the subspaces $P^{\prime}X=\\{\alpha\in
X^{I};~{}\alpha(0)\neq\alpha(1)\\}$ and $F(X;2)=\\{(x,y)\in X\times X;~{}x\neq
y\\}$ and restrict the fibration $p$ on $P^{\prime}X$,

$p^{\prime}:P^{\prime}X\to F(X;2).$

Note that $\mathbb{Z}_{2}$-acts freely on both $P^{\prime}X$ and $F(X;2)$ by
$\alpha\to\alpha^{-1}$ and $(x,y)\to(y,x)$ respectively and $p^{\prime}$ is
$\mathbb{Z}_{2}$-map. Also, $P^{\prime}X=p^{-1}(F(X;2))$. So $p^{\prime}$ is a
$\mathbb{Z}_{2}$-fibration. The symmetric topological complexity
$\operatorname{\mathsf{T}C}^{S}(X)$ is defined to be
$\operatorname{secat}_{\mathbb{Z}_{2}}(p^{\prime})+1$. The extra one comes to
define motion planning on the diagonal of $X\times X$. Farber and Grant
noticed that $\operatorname{\mathsf{T}C}^{S}(X)$ is not homotopy invariant. To
overcome this problem, Basabe, González, Rudyak, and Tamaki introduced another
version of symmetric topological complexity
$\operatorname{\mathsf{T}C}^{\Sigma}(X)$ of $X$, which is easier to handle and
natural (cf. [2]). They also generalized it to higher version
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$. In this paper we use Basabe,
González, Rudyak, and Tamaki’s definition of symmetric topological complexity.
Let us recall the definition.

Consider the symmetric group $\Sigma_{n}$ of permutations of $n$ symbols. For
any $g,g^{\prime}\in\Sigma_{n},j\in\\{1,2,\cdots,n\\}$ we have
$g^{\prime}\circ g(j)=g^{\prime}(g(j))$. Take the action (left) of
$\Sigma_{n}$ on $X^{n}$ by permuting elements: that is $g(x_{1},x_{2},\cdots
x_{n})=(x_{g(1)},x_{g(2)},\cdots,x_{g(n)})$. Also, $\Sigma_{n}$ acts on
${I_{n}}$ by $gt_{j}=t_{g(j)}$, for $t\in[0,1]$ and $j\in\\{1,2,\cdots,n\\}$.
This induces an action of $\Sigma_{n}$ on $X^{I_{n}}$ given by
$g\alpha(t_{j})=\alpha(t_{g(j)})$. So $X^{n}$ and $X^{I_{n}}$ are
$\Sigma_{n}$-spaces and the fibration $e_{n}$ in Equation 2 is a
$\Sigma_{n}$-fibration.

######  2.3 Definition ([2]).

The _symmetric topological complexity_
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$ of $X$ is defined to be:

$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X):=\operatorname{secat}_{\Sigma_{n}}(e_{n}).$

Here a $\Sigma_{n}$-invariant subset of $X^{n}$ is called _symmetric subset_
and a section on a symmetric subset of $X^{n}$ is called a _symmetric
section_. From the definition it is clear that
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)\geq\operatorname{\mathsf{T}C}_{n}(X)$.
In ([2]), authors proved that $\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$ is
homotopy invariant, for any $n\geq 2$.

######  2.4 Lemma.

Let $X$ and $Y$ be any two spaces. Then $n$ maps
$f_{1},f_{2},\cdots,f_{n}:X\to Y$ are in same homotopy class if and only if
there is a map $H:X\times I_{n}\to Y$ such that $H(x,1_{j})=f_{j}(x)$ for any
$1\leq j\leq n$.

###### Proof.

Let us assume that the maps $f_{1},f_{2},\cdots,f_{n}:X\to Y$ are in same
homotopy class. Then there are homotopy maps $H_{j}:X\times I\to Y$ such that
$H_{j}(x,0)=f_{1}(x)$ and $H_{j}(x,1)=f_{j}(x)$ for $1\leq j\leq n$. That
means $H_{j}$ is a homotopy from $f_{1}$ to $f_{j}$. Since $H_{j}$ assume the
value at $(x,0)$ for all $j$, so we can define a map $H:X\times I_{n}\to Y$
with $H(x,1_{j})=f_{j}(x)$ for $1\leq j\leq n$.

Conversely, if we restrict the map $H$ on union of $[0,1]_{i}$ and $[0,1]_{j}$
in $I_{n}$, it gives homotopy between $f_{i}$ and $f_{j}$ for $1\leq i\neq
j\leq n$. ∎

In the above case we call $H$ a _homotopy between_ $f_{1},f_{2},\cdots,f_{n}$.

######  2.5 Definition.

Assume that $\mathbf{X}$ is a $\Sigma_{n}$-space and $Y$ any topological
space. Then maps $f_{1},f_{2},\cdots,f_{n}:\mathbf{X}\to Y$, satisfying
$f_{j}(gx)=f_{g(j)}(x)$, are called _symmetrically homotopic_ if there is a
homotopy $H:\mathbf{X}\times I_{n}\to Y$ between them satisfying
$H(gx,t_{j})=H(x,t_{g(j)})$
$g\in\Sigma_{n},~{}x\in\mathbf{X},~{}t\in[0,1],~{}1\leq j\leq n$. In this case
we call $H$ a _symmetric homotopy_ between $f_{1},f_{2},\cdots,f_{n}$. Note
that the homotopy satisfies the relation
$H(gx,0)=H(x,0),~{}~{}x\in\mathbf{X},~{}g\in\Sigma_{n}$.

Let $X$ be a topological space and $A$ be a $\Sigma_{n}$-invariant subset of
$X^{n}$. Define $p_{j}:A\to X$ as the composition $A\hookrightarrow X^{n}\to
X$, where the first map is the inclusion and the second map is the projection
onto the $j$-th factor. Then clearly $p_{j}(gx)=p_{g(j)}(x),~{}x\in
A,g\in\Sigma_{n}$. We will use the following lemma to define symmetric
simplicial complexity.

######  2.6 Lemma.

With notations as above, the maps $\\{p_{j}:~{}1\leq j\leq n\\}$ are
symmetrically homotopic if and only if $e_{n}:X^{I_{n}}\to X^{n}$ admits a
symmetric section on $A$.

###### Proof.

A symmetric section $s:A\to X^{I_{n}}$ of $e_{n}$ satisfies,
$s(gx)(t_{j})=s(x)(t_{g_{(}j)}).$ A symmetric homotopy $H:A\times I_{n}\to X$
between $p_{1},p_{2},\cdots,p_{n}$ satisfies $H(gx,t_{j})=H(x,t_{g(j)}).$
Hence if we set

$s(x)(t_{j})=H(x,t_{j}),~{}~{}x\in A,t_{j}\in I_{n},$

then the existence of one of $s$ and $H$ implies the existence of the other. ∎

######  2.7 Remark.

In view of Lemma 2.6, the symmetric topological complexity
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$ can be described as the minimum
integer $k$ such that $X^{n}$ can be covered by $\Sigma_{n}$-invariant open
subsets, $U_{1}\cup U_{2}\cup\cdots\cup U_{k}=X^{n}$ and on each $U_{i}$
composition maps $p_{1},p_{2},\cdots,p_{n}:U_{i}\hookrightarrow X^{n}\to X$
are symmetrically homotopic.

The following proposition is a simple equivariant analogue of [10, Proposition
2.2].

######  2.8 Proposition.

Let $X$ be an ENR. Then $\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)=k$, where
$k$ is the minimal integer such that there exist a $\Sigma_{n}$-equivariant
section $s:X^{n}\rightarrow X^{I_{n}}$ (which is not necessarily continuous)
of the fibration $e_{n}$ and a splitting $G_{1}\sqcup G_{2}\sqcup\cdots\sqcup
G_{r}=X^{n}$, where each $G_{i}$ is locally compact and $\Sigma_{n}$-invariant
subset of $X^{n}$ and each restriction $s_{|G_{i}}:G_{i}\rightarrow X^{I_{n}}$
is continuous for $i=1,2,\cdots,r$.

###### Proof.

The proof is similar to [10, Proposition 2.2], only here the sections are
$\Sigma_{n}$-map and the subsets are $\Sigma_{n}$-invariant. ∎

Combining Remark 2.7 and Proposition 2.8, we have the following.

######  2.9 Corollary.

Let $X$ be an ENR. Then $\operatorname{\mathsf{T}C}^{\Sigma}_{n}(X)$ is the
minimal integer $k$ such that there exist a splitting $G_{1}\sqcup
G_{2}\sqcup\cdots\sqcup G_{r}=X^{n}$ with each $G_{i}$ is locally compact and
$\Sigma_{n}$-invariant subset of $X^{n}$ and on each $G_{i}$ the composition
of inclusion with the projections maps
$p_{1},p_{2},\cdots,p_{n}:G_{i}\hookrightarrow X^{n}\to X$ are symmetrically
homotopic.

##  3\. Symmetric simplicial complexity

González introduced the notion of simplicial complexity
$\operatorname{\mathsf{S}C}(K)$ for simplicial complex $K$ (cf. [8]). This is
based on contiguity of simplicial maps. It is proved in that simplicial
complexity $\operatorname{\mathsf{S}C}(K)$ is equal to the topological
complexity $\operatorname{\mathsf{T}C}(|K|)$ of the geometric realization of
$K$, for a finite simplicial complex $K$. This has been generalized for higher
simplicial complexity (cf. [10]). In this section we first recall some basic
ideas on simplicial complexes and simplicial complexity. After that we
introduce symmetric simplicial complexity
$\operatorname{\mathsf{S}C}^{\Sigma}(K)$ and its higher version
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)$. Finally we show that
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$.

######  3.1.

Simplicial complexes.  We begin by recalling some basic ideas of simplicial
complexes ([3, 4, 14]). A _simplicial complex_ $K$ consists of of a set
$V(K)$, called _vertices_ and a set $S(K)$ of finite nonempty subsets of of
$V(K)$, called _simplexes_ such that,

  1. (a)

Singleton subsets of $V(K)$ is a simplex.

  2. (b)

Any non empty subset of a simplex is a simplex.

We say $K$ is a finite simplicial complex if the set $V(K)$ is finite. A set
$\sigma\in S(K)$ with $q+1$ elements is called a $q$-_simplex_ and if
$\sigma^{\prime}\subset\sigma$ then $\sigma^{\prime}$ is called a _face_ of
$\sigma$. A _simplicial map_ $\phi:K\to L$ is a function from the vertices of
$K$ to the vertices of $L$ such that for any simplex
$\sigma=\\{v_{0},v_{1},\cdots,v_{q}\\}$ in $K$ the image
$\phi(\sigma)=\\{\phi(v_{0}),\phi(v_{1}),\cdots,\phi(v_{q})\\}$ is a simplex
in $L$ (possibly of lower dimension). For a poset $P$ the _order complex_
$\mathcal{K}(P)$ is the simplicial complex whose vertex set is $P$ and
simplexes are totally ordered finite subsets of $P$. The simplex set $S(K)$ is
naturally a poset with inclusion of faces, called _face poset_ and we denote
it by $\mathcal{X}(K)$. The order complex of $\mathcal{X}(K)$ is called the
_barycentric subdivision_ $\operatorname{sd}(K)$ of $K$. Thus the set of
vertices of $\operatorname{sd}(K)$ is the set $S(K)$ and a $q$-simplex of
$\operatorname{sd}(K)$ is a chain
$\sigma_{0}\subsetneq\sigma_{1}\subsetneq\cdots\subsetneq\sigma_{q}$ of face
inclusions of simplexes of $K$. For any simplicial complex $K$ the _geometric
realization_ $|K|$ is the set of all functions $\alpha:V(K)\to I=[0,1]$ such
that: (i) for any $\alpha$, the set $\\{v\in V(K);\alpha(v)\neq 0\\}\in S(K)$,
(ii) for any $\alpha,\sum_{v\in V(K)}\alpha(v)=1$. Then the linear map
$|\operatorname{sd}(K)|\to|K|$ takes each vertex of $\operatorname{sd}(K)$ to
the corresponding point of $|K|$ which is a homeomorphism. For any vertex
$v\in V(K)$ the _open star_ of $v$ denoted by $\operatorname{st}(v)$ and
defined as $\operatorname{st}(v)=\\{\alpha\in|K|;\alpha(v)\neq 0\\}$. Recall
that a vertex map $\phi:V(K)\to V(L)$ is a simplicial approximation of a
continuous map $f:|K|\to|L|$ if and only if
$f(\operatorname{st}(v))\subset\operatorname{st}(\phi(v))$ for all $v\in
V(K).$

The categorical product of simplicial complexes do not possess the desired
property that $|K\times L|=|K|\times|L|.$ To overcome this we need the notion
of ordered simplicial complex (cf. [4, 11]).

######  3.2 Definition.

An _ordered simplicial complex_ $K$ is a simplicial complex $K$ together with
a partial order on its set of vertices, restricting to a total order on each
of its simplices. The simplexes are denoted by ordered sets $\\{v_{0}\leq
v_{1}\leq\cdots\leq v_{q}\\}.$

######  3.3 Example.

  1. (a)

Every simplicial complex $K$ can be thought as an ordered simplicial complex
by selecting a total order on its vertex set.

  2. (b)

The order complex of a poset is an ordered simplicial complex.

  3. (c)

In particular, for any simplicial complex $K$, the subdivision
$\operatorname{sd}(K)$ is an ordered simplicial complex structure with respect
to inclusion of faces ordering.

In general, in an ordered simplicial complex vertices of each simplex is
totally ordered but a totally ordered finite subset of vertices may not be a
simplex.

######  3.4 Definition.

The _cartesian product_ $K\times L$ of two ordered simplicial complexes $K$
and $L$ is also an ordered simplicial complex whose vertex set is $V(K)\times
V(L)$ with partial order given by $(u_{1},v_{1})\leq(u_{2},v_{2})$ if and only
if $u_{1}\leq u_{2}$ and $v_{1}\leq v_{2}$. An ordered set
$\\{(u_{0},v_{0})\leq(u_{1},v_{1})\leq\cdots\leq(u_{q},v_{q})\\}$ is a
$q$-simplex in $K\times L$ if $\\{u_{0}\leq u_{1}\leq\cdots\leq u_{q}\\}$ and
$\\{v_{0}\leq v_{1}\leq\cdots\leq v_{q}\\}$ are simplexes of $K$ and $L$
respectively.

Then the projection maps $p_{1}:K\times L\to K$ and $p_{2}:K\times L\to L$
induces homeomorphism $|p_{1}|\times|p_{2}|:|K\times L|\to|K|\times|L|$. In
particular $|K^{n}|=|K|^{n}.$

The notion of homotopy of continuous maps is replaced by _contiguity_ of
simplicial maps (see [14]). For a positive integer $c$, two simplicial maps
$\phi,\phi^{\prime}:K\rightarrow L$ are called $c$-_contiguous_ if there is a
sequence of simplicial maps
$\phi=\phi^{0},\phi^{1},\phi^{2}\cdots,\phi^{c}=\phi^{\prime}:K\rightarrow L$,
such that $\phi^{i-1}(\sigma)\cup\phi^{i}(\sigma)$ is a simplex of $L$ for
each simplex $\sigma$ of $K$ and $i\in\\{1,2,\cdots,c\\}$. We write
$\phi\sim\phi^{\prime}$ if $\phi$ and $\phi^{\prime}$ are $c$-contiguous for
some positive integer $c$. This defines an equivalence relation on the set of
simplicial maps $K\rightarrow L$ and the equivalence classes are called
_contiguity classes_. If $\phi_{1},\phi_{2},\cdots,\phi_{n}:K\to L$ are
simplicial maps belonging to the same contiguity class then there is a
simplicial map $\phi_{*}:K\to L$ and a positive integer $c$ such that each
$\phi_{j}$ is $c$-contiguous with $\phi_{*}$. Simplicial approximations of a
same continuous map are $1$-contiguous, i.e, they are in same contiguity
class. For any simplicial complexes $J,K,L,M$, if the simplicial maps
$\phi,\phi^{\prime}:K\to L$ are $c$-contiguous, then for any simplicial maps
$\psi:J\to K$, $\theta:L\to M$, the composition simplicial maps
$\theta\circ\phi\circ\psi,\theta\circ\phi^{\prime}\circ\psi:J\to K\to L\to M$
are also $c$-contiguous.

######  3.5.

Equivariant simplicial complexes.  Let $G$ be a finite group. A _simplicial
$G$-complex_ is a simplicial complex $K$ with simplicial $G$-action, that is:
the group $G$-acts on the vertex set $V(K)$ such that for a simplex
$\sigma=\\{v_{0},\cdots,v_{q}\\}\in S(K)$ we have
$g\sigma:=\\{gv_{0},\cdots,gv_{q}\\}$ is also a simplex (of same dimension).
In addition, if $K$ is an ordered simplicial complex and $G$ preserves the
ordering of each simplex of $K$, we call $K$ an _ordered simplicial
$G$-complex_. A _morphism_ between simplicial $G$-complexes $K$ and $L$ is a
simplicial map $\phi:K\to L$ such that $\phi$ is $G$-equivariant map on the
vertex set (cf. [3], [11]).

######  3.6 Example.

  1. (a)

Let $K$ be an simplicial complex. Consider it as an ordered simplicial complex
(see Example 3.3). Then $K^{n}=K\times K\times\cdots\times K$ is also an
ordered simplicial complex (see Definition 3.4). It is a simplicial
$\Sigma_{n}$-complex with natural permutation action on the vertex set
$V(K)^{n}$: $g(v_{1},v_{2},\cdots,v_{n})=(v_{g(1)},v_{g(2)},\cdots,v_{g(n)})$.
This action also preserves the ordering. So $K^{n}$ is an ordered simplicial
$\Sigma_{n}$-complex.

  2. (b)

Let $K$ be a simplicial $G$-complex. Then the face poset $\mathcal{X}(K)$ has
a natural order preserving $G$-action. Hence ts order complex
$\mathcal{K}(\mathcal{X}(K))$, which is the barycentric subdivision
$\operatorname{sd}(K),$ is also a simplicial $G$-complex. Moreover
$\operatorname{sd}(K)$ is ordered (see Example 3.3) and the $G$-action is
order preserving.

Let $K$ and $L$ be two simplicial $G$-complexes and $f:|K|\to|L|$ be a
$G$-map. A simplicial approximation $\phi:\operatorname{sd}^{r}(K)\to L$ of
$f$ is called a _$G$ -simplicial approximation_ or simply _$G$ -approximation_
if $\phi$ is $G$-equivariant on the vertex sets.

######  3.7 Lemma.

For an ordered simplicial $G$-complex $K$, there is a $G$-simplicial
approximation $\iota:\operatorname{sd}(K)\to K$ of identity
$\operatorname{Id}:|K|\to|K|$.

###### Proof.

Define a map

$\tau:\mathcal{X}(K)=V(\operatorname{sd}(K))\to V(K),~{}~{}~{}~{}\\{v_{0}\leq
v_{1}\leq\cdots\leq v_{k}\\}\mapsto v_{k},$

for any $\\{v_{0}\leq v_{1}\leq\cdots\leq v_{k}\\}\in\mathcal{X}(K)$. This
gives a simplicial map $\mathcal{K}(\tau)=\iota:\operatorname{sd}(K)\to K$.
Note that the map $\iota$ is a (order preserving) $G$-map on the vertex sets.
Since

$\operatorname{Id}(\operatorname{st}\\{v_{0}\leq v_{1}\leq\cdots\leq
v_{k}\\})\subset\operatorname{st}(\\{v_{k}\\}),$

so $\iota$ is a $G$-approximation of identity on $|K|$ (cf. [9]). ∎

Following definition is the simplicial analogue of symmetric homotopy (see
Definition 2.5).

######  3.8 Definition.

Let $K$ be a simplicial $\Sigma_{n}$-complex, $L$ be any simplicial complex.
Simplicial maps $\phi_{1},\phi_{2},\cdots,\phi_{n}:K\to L$, satisfying
$\phi_{j}(gv)=\phi_{g(j)}(v),$ are called _symmetrically contiguous_ if there
is a simplicial map $\phi_{*}:K\to L$ and a positive integer $c$ such that
$\phi_{*}(gv)=\phi_{*}(v)$, each $\phi_{j}$ is $c$-contiguous with $\phi_{*}$
with intermediate maps $\phi^{l}_{j}$ satisfying
$\phi^{l}_{j}(gv)=\phi^{l}_{g(j)}(v)$, $v\in V(K),~{}g\in\Sigma_{n},~{}1\leq
l\leq c,~{}1\leq j\leq n$.

We need the following result later.

######  3.9 Lemma.

([14, Lemma 3.5.2], [17, Lemma 2.5]) Simplicial maps
$\phi_{1},\phi_{2},\cdots,\phi_{n}:K\to L$ in the same contiguity class have
homotopic topological realization. Moreover, if $K$ is a simplicial
$\Sigma_{n}$-complex and $\phi_{1},\phi_{2},\cdots,\phi_{n}:K\to L$ are
symmetrically contiguous then the realizations also symmetrically homotopic.

###### Proof.

Assume that $\phi_{1},\phi_{2},\cdots,\phi_{n}:K\to L$ lie in same contiguity
class. Then there exist a positive integer $c$ and a simplicial map
$\phi_{*}:K\to L$ such that for each $j\in\\{1,2,\cdots,n\\}$, $\phi_{*}$ is
$c$-contiguous with $\phi_{j}$ via the simplicial maps
$\phi_{*}=\phi^{0}_{j},\phi^{1}_{j},\phi^{2}_{j},\cdots,\phi^{c}_{j}=\phi_{j}:K\to
L$. We define $H:|K|\times I_{n}\to|L|$ by,

$H(x,t_{j})=c\Big{(}\frac{l+1}{c}-t\Big{)}\big{(}|\phi^{l}_{j}|(x)\big{)}+c\Big{(}t-\frac{l}{c}\Big{)}\big{(}|\phi^{l+1}_{j}|(x)\big{)},\
\text{for}\ t_{j}\in\Big{[}\frac{l}{c},\frac{l+1}{c}\Big{]}_{j}$

where $1\leq j\leq n,l\in\\{0,1,\cdots,c-1\\}$, $x\in|K|$ and $t$ denote the
value of $t_{j}$ in $j$th interval. Then $H$ is a homotopy between
$|\phi_{1}|,|\phi_{2}|,\cdots,|\phi_{n}|$. Moreover, if the maps
$\\{\phi_{i}:~{}~{}1\leq i\leq n\\}$ are symmetrically contiguous then $H$ is
a symmetric homotopy. ∎

Iterated barycentric subdivisions of $K$ are defined by
$\operatorname{sd}^{r+1}(K):=\operatorname{sd}(\operatorname{sd}^{r}(K)).$ The
following proposition is a generalized version of [14, Theorem 3.5.6], [12,
Theorem 3.49] and [17, Lemma 3.13].

######  3.10 Proposition.

Let $K$ be a simplicial $\Sigma_{n}$-complex and $L$ be any other simplicial
complex. If $n$ maps $f_{1},f_{2},\cdots,f_{n}:|K|\rightarrow|L|$ are
symmetrically homotopic, then there is $r_{0}\in\mathbb{N}$ and simplicial
approximations
$\phi_{1},\phi_{2},\cdots,\phi_{n}:\operatorname{sd}^{r_{0}}(K)\rightarrow L$
of $f_{1},f_{2},\cdots,f_{n}$ respectively which are symmetrically contiguous.

###### Proof.

We prove the proposition in four steps.

Step I: Let $H:|K|\times I_{n}\to|L|$ be a symmetric homotopy between
$f_{1},f_{2},\cdots,f_{n}$. Since $|K|$ is compact, there are points
$0_{1}=t_{1}^{0}\leq t_{1}^{1}\leq\cdots\leq t_{1}^{c}=1_{1}$ in the first
interval of $I_{n}$ such that for any $x\in|K|$ the points $H(x,t_{1}^{l})$
and $H(x,t_{1}^{l-1})$ belong to open star $\operatorname{st}(w)$ for some
vertex $w$ of $L$ and $l\in\\{1,2,\cdots,c\\}$. We denote
$h_{j}^{l}(x)=H(x,t_{j}^{l})$ for each $j$ and $l$. By [14, Theorem 3.5.6],
there is $r_{0}\in\mathbb{N}$ (large enough) and simplicial approximation
$\psi_{1}^{l}:\operatorname{sd}^{r_{0}}(K)\rightarrow L$ of $h_{1}^{l}$ and
$h_{1}^{l-1}$ for $l\in\\{1,2,\cdots,c\\}$.

Step II: Using $\psi_{1}^{l}$ here we construct another simplicial
approximation $\phi_{1}^{l}$ of $h_{1}^{l}$ and $h_{1}^{l-1}$. Let
$S=\big{\\{}(1,j)g(1,g(j))\in\Sigma_{n};\ 1\leq j\leq n,\
g\in\Sigma_{n}\big{\\}}$ and $G$ be the subgroup of $\Sigma_{n}$ generated by
$S$. Take the induced action of $\Sigma_{n}$ on
$\operatorname{sd}^{r_{0}}(K)$. Choose and fix an element $v_{0}$ on each
$G$-orbit of $\operatorname{sd}^{r_{0}}(K)$. Now for each $l$ we define
$\phi_{1}^{l}:\operatorname{sd}^{r_{0}}(K)\rightarrow L$ as: for any vertex
$v$ of $\operatorname{sd}^{r_{0}}(K)$, $\phi_{1}^{l}(v)=\psi_{1}^{l}(v_{0})$
where $v_{0}$ is the chosen point on the $G$-orbit of $v$. We claim that
$\phi_{1}^{l}$ is a simplicial approximation of both $h_{1}^{l}$ and
$h_{1}^{l-1}$. Write $v=g^{\prime}v_{0}$ for some $g^{\prime}\in G$. Without
loss of generality we can take $g^{\prime}\in S$, i.e,
$g^{\prime}=(1,j)g(1,g(j))$ for some $j$ and $g\in\Sigma_{n}$. Observe that,

$\displaystyle h_{1}^{l}\Big{(}\operatorname{st}\big{(}v\big{)}\Big{)}$
$\displaystyle=h_{1}^{l}\Big{(}\operatorname{st}\big{(}g^{\prime}v_{0}\big{)}\Big{)}=h_{1}^{l}\Big{(}\operatorname{st}\big{(}(1,j)g(1,g(j))v_{0}\big{)}\Big{)}$
$\displaystyle=h_{1}^{l}\Big{(}(1,j)g(1,g(j))\operatorname{st}(v_{0})\Big{)}=h_{j}^{l}\Big{(}g(1,g(j))\operatorname{st}(v_{0})\Big{)}$
$\displaystyle=h_{g(j)}^{l}\Big{(}(1,g(j))\operatorname{st}(v_{0})\Big{)}=h_{1}^{l}\Big{(}\operatorname{st}(v_{0})\Big{)}\subset\operatorname{st}\big{(}\psi_{1}^{l}(v_{0})\big{)}=\operatorname{st}\Big{(}\phi_{1}^{l}\big{(}v\big{)}\Big{)}.$

The inclusion follows since $\psi_{1}^{l}$ is approximation of $h_{1}^{l}$.
Similarly we can show that
$h_{1}^{l-1}\big{(}\operatorname{st}(v)\big{)}\subset\operatorname{st}\big{(}\phi_{1}^{l}(v)\big{)}$.
So $\phi_{1}^{l}$ is a simplicial approximation of both $h_{1}^{l}$ and
$h_{1}^{l-1}$.

Step III: We now use $\phi_{1}^{l}$ to define
$\phi_{j}^{l}:\operatorname{sd}^{r_{0}}(K)\rightarrow L$ which is a simplicial
approximations of both $h_{j}^{l}$ and $h_{j}^{l-1}.$ For $1\leq j\leq n$ and
$1\leq l\leq c$,

$\phi_{j}^{l}:\operatorname{sd}^{r_{0}}(K)\rightarrow
L,~{}~{}\phi_{j}^{l}(v):=\phi_{1}^{l}\big{(}(1,j)v\big{)}\text{ for }v\in
V(\operatorname{sd}^{r_{0}}(K)).$

Note that,

$\displaystyle h_{j}^{l}\Big{(}\operatorname{st}(v)\Big{)}\cup
h_{j}^{l-1}\Big{(}\operatorname{st}(v)\Big{)}$
$\displaystyle=h_{1}^{l}\Big{(}(1,j)\operatorname{st}(v)\Big{)}\cup
h_{1}^{l-1}\Big{(}(1,j)\operatorname{st}(v)\Big{)}$
$\displaystyle=h_{1}^{l}\Big{(}\operatorname{st}\big{(}(1,j)v\big{)}\Big{)}\cup
h_{1}^{l-1}\Big{(}\operatorname{st}\big{(}(1,j)v\big{)}\Big{)}$
$\displaystyle\subset\operatorname{st}\Big{(}\phi_{1}^{l}\big{(}(1,j)v\big{)}\Big{)}=\operatorname{st}\Big{(}\phi_{j}^{l}(v)\Big{)}.$

So $\phi_{j}^{l}$ is a simplicial approximation of both $h_{j}^{l}$ and
$h_{j}^{l-1}$. In particular $\phi_{j}^{c}$ ($=\phi_{j}$, say) is a simplicial
approximation of $h_{j}^{c}=f_{j}$. Moreover, for any vertex $v$ of
$\operatorname{sd}^{r_{0}}(K)$ and $g\in\Sigma_{n}$ we denote
$u=(1,g(j))v\Leftrightarrow(1,g(j))u=v$. Then we have,

$\displaystyle\phi_{j}^{l}(gv)$
$\displaystyle=\phi_{j}^{l}\big{(}g(1,g(j))u\big{)}=\phi_{1}^{l}\big{(}(1,j)g(1,g(j))u\big{)}=\phi_{1}^{l}\big{(}u\big{)}=\phi_{1}^{l}\big{(}(1,g(j))v\big{)}=\phi_{g(j)}^{l}(v).$

Therefore the simplicial approximation $\phi_{j}^{l}$ of $h_{j}^{l}$ and
$h_{j}^{l-1}$ satisfies $\phi_{j}^{l}(gv)=\phi_{g(j)}^{l}(v)$.

Step IV: Now $h_{j}^{0}=h^{0}:|K|\to|L|$ is an $\Sigma_{n}$-equivariant map
(thought $|L|$ has trivial $\Sigma_{n}$-action), so by [12, Theorem 3.49],
there is an $\Sigma_{n}$-equivariant simplicial approximation of $h_{0}$,
$\phi_{j}^{0}=\phi^{0}:\operatorname{sd}^{r_{0}}(K)\to L$, for $r_{0}$ large
enough. So $\phi^{0}(gv)=\phi^{0}(v)$ for any vertex $v$ of
$\operatorname{sd}^{r_{0}}(K)$ and $g\in\Sigma_{n}$. We set
$\phi_{*}=\phi^{0}$. Note that the simplicial maps $\phi_{j}^{l}$ and
$\phi_{j}^{l+1}$ are $1$-contiguous (since these are approximations of same
map $h_{j}^{l}$), for $l\in\\{0,1,\cdots,c-1\\}$ and $j\in\\{1,2,\cdots,n\\}$.
So the simplicial approximations
$\phi_{1},\phi_{2},\cdots,\phi_{n}:\operatorname{sd}^{r_{0}}(K)\rightarrow L$
of $f_{1},f_{2},\cdots,f_{n}$ respectively, are symmetrically contiguous. ∎

######  3.11.

Simplicial complexity.  Here we recall simplicial complexity
$\operatorname{\mathsf{S}C}_{n}(K)$ of a simplicial complex $K$ from ([10]).
Choose a simplicial approximation
$\iota_{K^{n}}:\operatorname{sd}(K^{n})\rightarrow K^{n}$ of the identity on
$|K^{n}|=|K|^{n}$. We denote

(4) $\iota^{r}_{K^{n}}:\operatorname{sd}^{r}(K^{n})\rightarrow K^{n}$

as the iterated composition

$\operatorname{sd}^{r}(K^{n})\xrightarrow{\iota_{\operatorname{sd}^{r-1}(K^{n})}}\operatorname{sd}^{r-1}(K^{n})\xrightarrow{\iota_{\operatorname{sd}^{r-2}(K^{n})}}\cdots\xrightarrow{\iota_{\operatorname{sd}(K^{n})}}\operatorname{sd}(K^{n})\xrightarrow{\iota_{K^{n}}}K^{n}$

and
$p_{j}\circ\iota^{r}_{K^{n}}=\pi_{j}:\operatorname{sd}^{r}(K^{n})\rightarrow
K$ where $p_{j}:K^{n}\to K$ is the $j^{th}$ projection $r\geq 0,~{}1\leq j\leq
n$. Then $\operatorname{\mathsf{S}C}^{r}_{n}(K)$ is the smallest non-negative
integer $k$ such that there exist subcomplexes $\\{L_{i}\\}_{i=1}^{k}$
covering $\operatorname{sd}^{r}(K^{n})$ and the restrictions
$\pi_{j}:L_{i}\rightarrow K$, for $j=1,2,\cdots,n,$ lie in the same contiguity
class, for each $i$. If no such $k$ exists then
$\operatorname{\mathsf{S}C}^{r}_{n}(K)=\infty$. The value
$\operatorname{\mathsf{S}C}^{r}_{n}(K)$ independent of the chosen of
approximation $\iota^{r}_{K^{n}}:\operatorname{sd}^{r}(K^{n})\rightarrow
K^{n}$ of the identity on $|K|^{n}$. It is also shown that
$\\{\operatorname{\mathsf{S}C}_{n}^{r}(K)\\}_{r}$ is a decreasing sequence and
bounded below by $1$. So we define the $n$-th _simplicial complexity_ as
$\operatorname{\mathsf{S}C}_{n}(K):=\min_{r\geq
0}\\{\operatorname{\mathsf{S}C}_{n}^{r}(K)\\}.$ Following theorem relates
simplicial complexity and topological complexity.

######  3.12 Theorem ([10]).

For a finite simplicial complex $K$,
$\operatorname{\mathsf{S}C}_{n}(K)=\operatorname{\mathsf{T}C}_{n}(|K|),n\geq
2$.

######  3.13.

Symmetric simplicial complexity.  Let $K$ be a simplicial complex. Then
$K^{n}$ is a simplicial $\Sigma_{n}$-complex (See Example 3.6). A subcomplex
$L$ of $K^{n}$ is called symmetric if $gL=L$ for all $g\in\Sigma_{n}$. In this
case, $|L|$ of is $\Sigma_{n}$-invariant. To define symmetric simplicial
complexity, we choose an $\Sigma_{n}$-approximation
$\iota_{K^{n}}:\operatorname{sd}(K^{n})\to K^{n}$ of identity on $|K^{n}|$.
Such an approximation exists by Lemma 3.7. As in previous case
$\pi_{j}:\operatorname{sd}^{r}(K^{n})\rightarrow K$ denotes the composition of
$p_{j}\circ\iota^{r}_{K^{n}}.$

######  3.14 Definition.

For a simplicial complex $K$ and integer $r\geq 0$, let
$\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)$ be the smallest non-negative
integer $k$ such that there exist symmetric subcomplexes
$\\{L_{i}\\}_{i=1}^{k}$ covering $\operatorname{sd}^{r}(K^{n})$ and the
restrictions $\pi_{j}|_{L_{i}}:L_{i}\rightarrow K$ $1\leq j\leq n,$ are
symmetrically contiguous on each $L_{i}$. If no such $k$ exists then
$\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)=\infty$.

Note that the maps $\pi_{j}$ depend on the choice of an
$\Sigma_{n}$-approximation of identity. The following lemma shows that the
above definition is independent of such a choice.

######  3.15 Lemma.

The value $\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)$ is independent of the
chosen of $\Sigma_{n}$-approximation
$\iota_{K^{n}}^{r}:\operatorname{sd}^{r}(K^{n})\rightarrow K^{n}$ of the
identity on $|K|^{n}$.

###### Proof.

Let $r^{\prime}$ be any number such that $1\leq r^{\prime}\leq r$. We fix
iterated compositions of $\Sigma_{n}$-approximations
$\iota^{r^{\prime}-1}_{K^{n}}:\operatorname{sd}^{r^{\prime}-1}(K^{n})\rightarrow
K^{n}$ and
$\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}:\operatorname{sd}^{r}(K^{n})\rightarrow\operatorname{sd}^{r^{\prime}}(K^{n})$
of the identity on $|K|^{n}$. Now we take two $\Sigma_{n}$-approximations
$\iota_{\operatorname{sd}^{r^{\prime}-1}(K^{n})},\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}:\operatorname{sd}^{r^{\prime}}(K^{n})\rightarrow\operatorname{sd}^{r^{\prime}-1}(K^{n})$
of the identity on $|K|^{n}$. Let
$\pi_{j},\bar{\pi}_{j}:\operatorname{sd}^{r}(K^{n})\rightarrow K$ be the
compositions
$p_{j}\circ\iota^{r^{\prime}-1}_{K^{n}}\circ\iota_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}\circ\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}$
and
$p_{j}\circ\iota^{r^{\prime}-1}_{K^{n}}\circ\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}\circ\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}$
respectively, where $p_{j}:K^{n}\to K$ is the $j$-th projection. Let
$\pi_{j}:L\to K$ for $j\in\\{1,2,\cdots,n\\}$ be symmetrically contiguous by
the contiguity chain
$\pi_{*}=\pi^{0}_{j},\pi^{1}_{j},\cdots,\pi^{c}_{j}=\pi_{j}:L\to K$, on some
symmetric subcomplex $L$ of $\operatorname{sd}^{r}(K^{n})$. Since
$\iota_{\operatorname{sd}^{r^{\prime}-1}(K^{n})},\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}:\operatorname{sd}^{r^{\prime}}(K^{n})\rightarrow\operatorname{sd}^{r^{\prime}-1}(K^{n})$
both are approximation of identity on $|K|^{n}$, so they are $1$-contiguous
and hence $\pi_{j},\bar{\pi}_{j}:L\to K$ are $1$-contiguous. So
$\pi_{*}=\pi^{0}_{j},\pi^{1}_{j},\cdots,\pi^{c}_{j}=\pi_{j},\bar{\pi}_{j}:L\to
K$ is a contiguity chain on the subcomplex $L$. Now since
$\iota^{r^{\prime}-1}_{K^{n}}$,
$\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}$ and
$\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}$ are
$\Sigma_{n}$-simplicial maps, for any vertex $v$ of $L$ and any
$g\in\Sigma_{n}$ we have

$\displaystyle\bar{\pi}_{j}(gv)$
$\displaystyle=p_{j}\circ\iota^{r^{\prime}-1}_{K^{n}}\circ\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}\circ\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}\big{(}gv)=p_{j}\big{(}g\big{(}\iota^{r^{\prime}-1}_{K^{n}}\circ\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}\circ\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}(v)\big{)}\big{)}$
$\displaystyle=p_{g(j)}\big{(}\iota^{r^{\prime}-1}_{K^{n}}\circ\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}\circ\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}(v)\big{)}=p_{g(j)}\circ\iota^{r^{\prime}-1}_{K^{n}}\circ\bar{\iota}_{\operatorname{sd}^{r^{\prime}-1}(K^{n})}\circ\iota^{r-r^{\prime}}_{\operatorname{sd}^{r^{\prime}}(K^{n})}(v)$
$\displaystyle=\bar{\pi}_{g(j)}(v).$

So $\bar{\pi}_{j}:L\to K$ for $j\in\\{1,2,\cdots,n\\}$ are symmetrically
contiguous by the contiguity chain
$\pi_{*}=\pi_{j}^{0},\pi^{1}_{j},\cdots,\pi^{c}_{j},\pi_{j}^{c+1}=\bar{\pi}_{j}:L\to
K$, on the subcomplex $L$ of $\operatorname{sd}^{r}(K^{n})$. Similarly we can
show that if $\bar{\pi}_{j}$’s are symmetrically contiguous then $\pi_{j}$’s
are so. This is true for any $r^{\prime}$ between $1$ and $r$. Hence
$\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)$ is independent of the chosen of
$\Sigma_{n}$-approximation
$\iota_{K^{n}}^{r}:\operatorname{sd}^{r}(K^{n})\rightarrow K^{n}$ of the
identity on $|K|^{n}$. ∎

Next we show that $\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)$ is bounded
below by $\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$.

######  3.16 Lemma.

For a simplicial complex $K$,
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)\leq\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)$,
$r\geq 0,~{}n\geq 2$.

###### Proof.

Let $\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)=k$. Let us consider
symmetric subcomplexes $\\{L_{i}\\}_{i=1}^{k}$ covering
$\operatorname{sd}^{r}(K^{n})$ such that the restrictions
$\pi_{j}:L_{i}\rightarrow K$, for $j=1,2,\cdots,n,$ are symmetrically
contiguous, for each $i$. Now we apply geometric realization functor. By Lemma
3.9 we get $|\pi_{j}|:|L_{i}|\rightarrow|K|$, for $j=1,2,\cdots,n,$ are
symmetrically homotopic for each $i$. Let $H:|L_{i}|\times I_{n}\to K$ be a
symmetric homotopy between $\pi_{1},\pi_{2},\cdots,\pi_{n}$. We restrict the
map $H$ on $|L_{i}|\times j$-th interval of $I_{n}$ and denote it by $h_{j}$.
So $h_{j}:|L_{i}|\times I\to K$. For each $j$ we define an another map
$f_{j}:|L_{i}|\times I\to K$ by $f_{j}(x,t)=tp_{j}(x)+(1-t)(|\pi_{j}|(x))$,
where $p_{j}$ is the composition $|L_{i}|\hookrightarrow|K|^{n}\to K$. Now
consider the homotopy $F:|L_{i}|\times I_{n}\to K$ is defined by: for each
$x$, the path $F(x,t_{j})$ is the concatenation $(h_{j}*f_{j})(x,t)$,

$(h_{j}*f_{j})(x,t)=\begin{cases}h_{j}(x,2t)&\mbox{ if
}~{}~{}t\in[0,\frac{1}{2}]\\\ f_{j}(x,2t-1)&\mbox{if
}~{}~{}t\in[\frac{1}{2},1].\end{cases}$

By assumption $h_{j}(gx,t)=h_{g(j)}(x,t)$ and by definition of
$f_{j},f_{j}(gx,t)=f_{g(j)}(x,t)$ for any $g\in\Sigma_{n}$ and
$F(x,1_{j})=p_{j}(x)$. So $F$ is a symmetric homotopy and
$p_{1},p_{2},\cdots,p_{n}$ are symmetrically homotopic on $|L_{i}|$. Now we
set $G_{1}=|L_{1}|$ and
$G_{i}=|L_{i}|-(|L_{1}|\cup|L_{2}|\cup\cdots\cup|L_{i-1}|)$ for $i\geq 2$.
Then each $G_{i}$ is locally compact, $\Sigma_{n}$-invariant and
$|K^{n}|=\sqcup_{i}G_{i}$. The restrictions of $p_{j}$, for $j=1,2,\cdots,n,$
on each $G_{i}$ are also symmetrically homotopic. From Corollary 2.9, we have
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)\leq k$. So
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)\leq\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)$,
for any $r\geq 0$ and $n\geq 2$. ∎

As in the case of simplicial complexity, now we show that
$\\{\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)\\}_{r}$ is a decreasing
sequence.

######  3.17 Lemma.

For a simplicial complex $K$,
$\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)\geq\operatorname{\mathsf{S}C}_{n}^{\Sigma,r+1}(K)$,
$r\geq 0,~{}~{}n\geq 2$.

###### Proof.

Let $\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)=k$ and
$\\{L_{i}\\}_{i=1}^{k}$ be a symmetric subcomplexes covering
$\operatorname{sd}^{r}(K^{n})$ such that the restrictions
$\pi_{j}:L_{i}\rightarrow K$ $1\leq j\leq n,$ are symmetrically contiguous,
for each $i$. So there is a contiguity chain
$\pi_{*}=\pi^{0}_{j},\pi^{1}_{j},\cdots,\pi^{c}_{j}=\pi_{j}:L_{i}\to K$ such
that $\pi_{j}^{l}(gv)=\pi_{g(j)}^{l}(v)$ and $\pi_{*}(gv)=\pi_{*}(v)$ $v\in
V(L_{i})$, $l\in\\{1,2,\cdots,c\\}$. Take the subcomplexes
$\\{\operatorname{sd}(L_{i})\\}_{i=1}^{k}$ which are symmetric and covers
$\operatorname{sd}^{r+1}(K^{n})$. We choose a $\Sigma_{n}$-approximation
$\iota_{\operatorname{sd}^{r}(K^{n})}:\operatorname{sd}^{r+1}(K^{n})\rightarrow\operatorname{sd}^{r}(K^{n})$
of the identity on $|K|^{n}$. Clearly, for each $L_{i}$, the sequence of maps
$\pi_{*}\circ\iota_{\operatorname{sd}^{r}(K^{n})}=\pi^{0}_{j}\circ\iota_{\operatorname{sd}^{r}(K^{n})},\pi^{1}_{j}\circ\iota_{\operatorname{sd}^{r}(K^{n})},\cdots,\pi^{c}_{j}\circ\iota_{\operatorname{sd}^{r}(K^{n})}=\pi_{j}\circ\iota_{\operatorname{sd}^{r}(K^{n})}:\operatorname{sd}(L_{i})\to
K$ for $j\in\\{1,2,\cdots,n\\}$ give a contiguity chain. Since
$\iota_{\operatorname{sd}^{r}(K^{n})}$ is a $\Sigma_{n}$-map, for any vertex
$v$ of $\operatorname{sd}(L_{i})$, $l\in\\{1,2,\cdots,c\\}$ we have,

$\pi_{*}\circ\iota_{\operatorname{sd}^{r}(K^{n})}(gv)=\pi_{*}(g\iota_{\operatorname{sd}^{r}(K^{n})}(v))=\pi_{*}(\iota_{\operatorname{sd}^{r}(K^{n})}(v))=\pi_{*}\circ\iota_{\operatorname{sd}^{r}(K^{n})}(v),$
$\pi_{j}^{l}\circ\iota_{\operatorname{sd}^{r}(K^{n})}(gv)=\pi_{j}^{l}(g\iota_{\operatorname{sd}^{r}(K^{n})}(v))=\pi_{g(j)}^{l}(\iota_{\operatorname{sd}^{r}(K^{n})}(v))=\pi_{g(j)}^{l}\circ\iota_{\operatorname{sd}^{r}(K^{n})}(v).$

This implies that the restrictions
$\pi_{j}\circ\iota_{\operatorname{sd}^{r}(K^{n})}:\operatorname{sd}(L_{i})\rightarrow
K$, for $j\in\\{1,2,\cdots,n\\}$ are symmetrically contiguous, for each $i$.
So $\operatorname{\mathsf{S}C}_{n}^{\Sigma,r+1}\leq k$ and therefore
$\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)\geq\operatorname{\mathsf{S}C}_{n}^{\Sigma,r+1}(K)$.
∎

Above Lemma allows us to make the following definition.

######  3.18 Definition.

For a simplicial complex $K$, the _$n$ -th symmetric simplicial complexity_ or
simply _symmetric simplicial complexity_ is defined as:

$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)=\min_{r\geq
0}\\{\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(K)\\}.$

The main theorem of this section is the following.

######  3.19 Theorem.

For a finite simplicial complex $K$,
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$,
$n\geq 2$.

###### Proof.

From Lemma 3.16, it is clear that
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)\geq\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$.
Now we prove the other inequality. Let
$\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)=k$. Using Remark 2.7 we get an
symmetric open cover $\\{U_{i}\\}_{i=1}^{k}$ of $|K|^{n}$ such that the
composition maps $p_{1},p_{2},\cdots,p_{n}:U_{i}\hookrightarrow|K|^{n}\to|K|$
are symmetrically homotopic for each $i$. Since $K$ is finite, $|K|$ is
compact and so is $|K|^{n}=|K^{n}|$. Therefore by Lebesgue lemma of compact
metric spaces, there exists $\delta>0$ such that any set of diameter less than
$\delta$ is contained in one of the open sets $U_{i}$. Since, with increasing
subdivision, the diameter of simplices goes to $0$, there is a large integer
$r\geq 0$ such that realization of each simplex $\sigma$ of
$\operatorname{sd}^{r}(K^{n})$ contained one of $U_{i}$. Let $L_{i}$ be the
subcomplex of $\operatorname{sd}^{r}(K^{n})$ consisting of those simplices
whose realization contained in $U_{i}$. For each $i$, the set is $U_{i}$ is
$\Sigma_{n}$-invariant and so for each simplex $\sigma$ of $L_{i}$,
$g|\sigma|$ contained in $U_{i}$, for any $g\in\Sigma_{n}$. Therefore
$g\sigma$ is a simplex of $L_{i}$. Thus each subcomplex $L_{i}$ is symmetric.
Also $\\{L_{i}\\}_{i=1}^{k}$ covers $\operatorname{sd}^{r}(K^{n})$. Since the
maps $p_{1},p_{2},\cdots,p_{n}:U_{i}\hookrightarrow|K|^{n}\to|K|$ are
symmetrically homotopic, their restriction on $|L_{i}|$,
$p_{1},p_{2},\cdots,p_{n}:|L_{i}|\hookrightarrow|K|^{n}\to|K|$ are also
symmetrically homotopic. Now by Proposition 3.10 there is positive integer
$r_{0}$ and approximations
$\pi_{1},\pi_{2},\cdots,\pi_{n}:\operatorname{sd}^{r_{0}}(L_{i})\hookrightarrow\operatorname{sd}^{r+r_{0}}(K^{n})\rightarrow
K$ of $p_{1},p_{2},\cdots,p_{n}$ respectively such that they are symmetrically
contiguous, for each $i$. Therefore
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)\leq k$ and hence
$\operatorname{\mathsf{S}C}^{\Sigma}_{n}(K)=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|K|)$.
∎

##  4\. Symmetric combinatorial complexity

Tanaka introduced a combinatorial approach of topological complexity (cf.
[16]). The basic idea of Tanaka’s paper is to describe topological complexity
by combinatorics of finite posets. He used a combinatorial analogue of the
path-space fibration of the Equation 1 to define _combinatorial complexity_
$\operatorname{\mathsf{C}C}^{0}(P)$ of a finite poset $P$, where zero means no
barycentric subdivision of $P\times P$ is involved. It is shown that
$\operatorname{\mathsf{C}C}^{0}(P)=\operatorname{\mathsf{T}C}(P)$ but
$\operatorname{\mathsf{C}C}^{0}(P)$ does not capture
$\operatorname{\mathsf{T}C}(|\mathcal{K}(P)|)$, where $\mathcal{K}(P)$ is the
_order complex_ of $P$. To describe
$\operatorname{\mathsf{T}C}(|\mathcal{K}(P)|)$ combinatorially, Tanaka used
barycentric subdivision of $P\times P$ to define combinatorial complexity
$\operatorname{\mathsf{C}C}(P)$. Finally it is shown that for a large
barycentric subdivision of $P\times P$,
$\operatorname{\mathsf{C}C}(P)=\operatorname{\mathsf{T}C}(|\mathcal{K}(P)|)$.
The above idea has been generalized to higher versions and shown that for a
finite poset $P$,
$\operatorname{\mathsf{C}C}_{n}(P)=\operatorname{\mathsf{T}C}_{n}(|\mathcal{K}(P)|)$
(cf. [10]). Tanaka further defined a combinatorial analog of symmetric
topological complexities $\operatorname{\mathsf{T}C}^{S}(X)$ and
$\operatorname{\mathsf{T}C}^{\Sigma}(X)$ for a finite poset $P$ ([17]). We
denote this symmetric combinatorial complexities by
$\operatorname{\mathsf{C}C}^{S}(P)$ and
$\operatorname{\mathsf{C}C}^{\Sigma}(P)$ respectively. Tanaka there also used
barycentric subdivision of $P\times P$ to define these symmetric combinatorial
complexities. For a large barycentric subdivision of $P\times P$ the value is
stable and he denotes this stable value by $\operatorname{\mathsf{C}C}^{S}(P)$
and $\operatorname{\mathsf{C}C}^{\Sigma}(P)$ and proved that
$\operatorname{\mathsf{C}C}^{S}(P)=\operatorname{\mathsf{T}C}^{S}(|\mathcal{K}(P)|)$
and
$\operatorname{\mathsf{C}C}^{\Sigma}(P)=\operatorname{\mathsf{T}C}^{\Sigma}(|\mathcal{K}(P)|)$.
In this section we first recall some basic ideas of finite poset and its
connection with finite spaces. Then we recall combinatorial complexity and
symmetric combinatorial complexity $\operatorname{\mathsf{C}C}^{\Sigma}(P)$ of
a finite poset $P$. Finally we introduce higher symmetric combinatorial
complexity $\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)$ and prove
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|\mathcal{K}(P)|)$.

######  4.1.

Finite poset and finite space.  We begin by recalling the relation between
finite poset and finite space. We refer reader to [15] for this. Let $P$ be a
finite poset. We denote $U_{x}=\\{y:~{}~{}y\leq x\\}$. Then $\\{U_{x};x\in
P\\}$ generates a $T_{0}$ topology on the finite set $P$. On the other hand,
given a finite $T_{0}$ topological space $P$, let $U_{x}$ denotes the
intersection of all open sets containing $x,$ where $x\in P$. Then we can
consider $P$ as a poset, the partial relation on $P$, defined by $x\leq y$ if
and only if $U_{x}\subseteq U_{y}$. Thus a finite poset is equivalent to a
finite $T_{0}$ space. We will simply write finite space to mean a finite
$T_{0}$ space. From now onwards we assume all our finite spaces are connected.
A map between finite spaces is continuous if and only if it preserves the
partial order. Given two finite spaces $P,Q$, we denote by $Q^{P}$ the space
of maps $P\to Q$ with the compact-open topology. This finite $T_{0}$-space
corresponds to the set of order preserving maps $P\to Q$ with the pointwise
ordering, i.e. $f\leq g$ if $f(x)\leq g(x)$ for every $x\in P$.

######  4.2 Example.

Let $K$ be a finite simplicial complex. Recall that the face poset
$\mathcal{X}(K)$ is the collection of all simplices in $K$ with the partial
order of face inclusions. For any simplex $\sigma$ of $K$ we have

$U_{\sigma}=\\{\sigma^{\prime};~{}\sigma^{\prime}\leq\sigma\\}=\\{\sigma^{\prime};~{}\sigma^{\prime}\text{
is a face of}~{}\sigma\\}=\mathcal{X}(\sigma).$

So $\\{\mathcal{X}(\sigma);~{}\sigma\text{ is a simplex of}~{}K\\}$ generates
a $T_{0}$ topology on $\mathcal{X}(K)$.

######  4.3 Remark.

For any subcomplex $L$ of a finite simplicial complex $K$, we have

$\mathcal{X}(L)=\bigcup_{\sigma\in S(L)}\mathcal{X}(\sigma).$

So by Example 4.2 we can say that $\mathcal{X}(L)$ is open in
$\mathcal{X}(K)$.

Let $J_{m}$ denotes the finite space consisting of $m+1$ points with the
zigzag order

$0\leq 1\geq 2\leq\cdots\geq(\leq)m$.

This finite space is called the _finite fence_ with length $m$. It behaves
like an interval in the category of finite spaces. An order preserving map
$\gamma:J_{m}\rightarrow P$ is called a combinatorial path or simply a path.
Thus a combinatorial path is just a zigzag
$\gamma(0)\leq\gamma(1)\geq\gamma(2)\leq\cdots\geq(\leq)\gamma(m)$ of elements
of $P$. If $m$ is even, inverse of a path $\gamma:J_{m}\rightarrow P$ defined
by $\gamma^{-1}:J_{m}\rightarrow P,\gamma^{-1}(i)=\gamma(m-i)$. A connected
finite space is always path-connected. Two maps $f,g:P\rightarrow Q$ between
two finite spaces are called _combinatorially homotopic_ if there exist $m\geq
0$ and a continuous map (or equivalently order preserving map) $H:P\times
J_{m}\rightarrow Q$ such that $H(x,0)=f(x)$ and $H(x,m)=g(x)$, i.e., there is
a fence $f=f_{0}\leq f_{1}\geq f_{2}\leq\cdots f_{n}=g$.

For $n\geq 2$ we denote $J_{n,m}$ be the finite poset of $nm+1$ points

$\\{0,1_{1},1_{2},\cdots,1_{n},2_{1},2_{2},\cdots,2_{n},\cdots,m_{1},m_{2},\cdots,m_{n}\\}.$

The partial ordering on $J_{n,m}$ consists of $n$ finite fences, each of
length $m$, as below:

$0\leq 1_{1}\geq 2_{1}\leq\cdots\geq(\leq)m_{1},$ $0\leq 1_{2}\geq
2_{2}\leq\cdots\geq(\leq)m_{2},$ $\cdots$ $0\leq 1_{n}\geq
2_{n}\leq\cdots\geq(\leq)m_{n}.$

We use the parameter $t_{j}$ for the $j$-th fence.

######  4.4 Definition.

Let $f_{1},f_{2},\cdots,f_{n}:P\to Q$ be $n$ order preserving maps between two
finite spaces. Then we say $f_{1},f_{2},\cdots,f_{n}$ are _combinatorially
homotopic_ if there exists $m\geq 0$ and an order preserving map $H:P\times
J_{n,m}\rightarrow Q$ such that $H(x,m_{j})=f_{j}(x)$ for $x\in P$ and
$j\in\\{1,2,\cdots,n\\}$. Moreover, if $P$ is a $\Sigma_{n}$-space then we
called $f_{1},f_{2},\cdots,f_{n}$ are _symmetrically combinatorially
homotopic_ if the maps satisfies $f_{j}(gx)=f_{g(j)}(x)$ and the homotopy map
satisfy $H(gx,t_{j})=H(x,t_{g(j)})$ for any $g\in\Sigma_{n},x\in P$ and
$j\in\\{1,2,\cdots,n\\}$. In this case the homotopy is called _symmetric
combinatorial homotopy_.

The following lemma is a generalization of [17, Proposition 2.2] .

######  4.5 Lemma.

Let $P$ be a finite $\Sigma_{n}$-space and $Q$ be arbitrary finite space. Then
any maps $f_{1},f_{2},\cdots,f_{n}:P\to Q$ are symmetrically homotopic if and
only if they are symmetrically combinatorially homotopic.

###### Proof.

Assume that $f_{1},f_{2},\cdots,f_{n}:P\to Q$ are symmetrically homotopic.
Then get a symmetric homotopy $H:P\times I_{n}\to Q$. By homotopy theory of
finite spaces, there is a $\Sigma_{n}$-map $h:J_{n,m}\to I_{n}$ such that
$j$-th fence maps to $j$-th interval and $m_{j}$ maps to $1_{j}$, for some
$m>0$ and $j\in\\{1,2,\cdots,n\\}$. Define $H^{\prime}$ as the composition map
$H^{\prime}:P\times J_{n,m}\xrightarrow{\operatorname{Id}\times h}P\times
I_{n}\xrightarrow{H}Q$. Then $H^{\prime}$ is a symmetric combinatorial
homotopy between $f_{1},f_{2},\cdots,f_{n}$.

Conversely, assume that there is a symmetric combinatorial homotopy
$H^{\prime}:P\times J_{n,m}\to Q$ between $f_{1},f_{2},\cdots,f_{n}$. We
define a $\Sigma_{n}$-map $h^{\prime}:I_{n}\to J_{n,m}$ such that each $j$-th
interval of $I_{n}$ maps to $j$-th fence of $J_{n,m}$ given by the equation

$h^{\prime}(t)=\begin{cases}2k-1&\mbox{ if }~{}~{}t=\frac{2k-1}{m},\\\
2k&\mbox{if }~{}~{}\frac{2k-1}{m}<t<\frac{2k+1}{m},\end{cases}$

for $k=0,1,2,\cdots$. Then the composition map $H:P\times
I_{n}\xrightarrow{\operatorname{Id}\times h^{\prime}}P\times
J_{n,m}\xrightarrow{H}Q$ gives a symmetric homotopy between
$f_{1},f_{2},\cdots,f_{n}$. ∎

Now onwards, we will use symmetrical homotopy to mean any one of the above
interpretations. Let us define _barycentric subdivision_ of a finite space
$P$.

######  4.6 Definition.

The _barycentric subdivision_ of a finite space $P$ is defined as the face
poset $\mathcal{X}(\mathcal{K}(P))$ of the order complex $\mathcal{K}(P)$ (see
Section 3.1). It is denoted by $\operatorname{sd}(P)$.

The following Proposition is a symmetric version for $n$ maps of [1, Lemma
4.10 and Proposition 4.11].

######  4.7 Proposition.

Let $P$ be a finite $\Sigma_{n}$-space and $Q$ be any finite space. Assume
that the maps $f_{1},f_{2},\cdots,f_{n}:P\to Q$ are symmetrically homotopic.
Then the simplicial maps
$\mathcal{K}(f_{1}),\mathcal{K}(f_{2}),\cdots,\mathcal{K}(f_{n}):\mathcal{K}(P)\to\mathcal{K}(Q)$
are symmetrically contiguous.

###### Proof.

Without loss of generality we may assume that there is symmetric homotopy
$F:J_{n,1}\times P\to Q$. We write $f_{j}^{0}(x)=F(x,0_{j})\leq
F(x,1_{j})=f_{j}(x)$ for all $x\in P$. Then we have
$f_{j}^{0}(gx)=f_{g(j)}^{0}(x)$ and $f_{j}(gx)=f_{g(j)}(x)$ for any $j$ and
any $x\in P,g\in\Sigma_{n}$. We prove our result in four steps. First we
construct sequences of order preserving maps
$f_{j}^{0},f_{j}^{1},f_{j}^{2},\cdots,f_{j}^{m}=f_{j}:P\to Q$.

Step I: Here we define the maps $f_{j}^{1}:P\to Q$. Define $A_{j}=\\{x\in
P;f_{j}^{0}(x)\neq f_{j}(x)\\}$. Note that $A_{g(j)}=g^{-1}A_{j}$. So if one
of $A_{j}$’s is empty the all $A_{j}$ are empty and in this case
$f_{j}^{1}=f_{j}$. Assume that $A_{1}$ is non empty. Then we define
$f_{j}^{1}:P\to Q$ by,

$f_{j}^{1}(x)=\begin{cases}f_{j}(x)&\mbox{ if}~{}~{}x\in A_{j}\mbox{ and it is
a maximal element of }A_{j}\\\ f_{j}^{0}(x)&\mbox{ otherwise.}\end{cases}$

We claim that the maps $f_{j}^{1}$ are order preserving. Let $x_{1},x_{2}\in
P$ with $x_{2}\geq x_{1}$. If none of them is maximal element of $A_{j}$ then
$f_{j}^{1}(x_{2})\geq f_{j}^{1}(x_{1})$, since $f_{j}^{0}$ is order
preserving. If $x_{2}$ is maximal element of $A_{j}$ and $x_{1}$ is any other
element of $P$ with $x_{2}\geq x_{1}$ (so $x_{1}$ can not be maximal of
$A_{j}$) then $f_{j}^{1}(x_{2})=f_{j}(x_{2})\geq f_{j}(x_{1})\geq
f_{j}^{0}(x_{1})=f_{j}^{1}(x_{1})$. Lastly if $x_{1}$ is maximal element of
$A_{j}$ and $x_{2}(\notin A_{j})\ x_{1}$ then
$f_{j}^{1}(x_{2})=f_{j}^{0}(x_{2})=f_{j}^{1}(x_{2})\geq
f_{j}^{1}(x_{1})=f_{j}^{1}(x_{1})$. So the maps $f_{j}^{1}$ are order
preserving.

Step II: We now show that $f_{j}^{1}(gx)=f_{g(j)}^{1}(x)$ for any $j$ and any
$x\in P,g\in\Sigma_{n}$. It is clear that $gx$ is a maximal element of $A_{j}$
if and only if $x$ is a maximal element of $g^{-1}A_{j}=A_{g(j)}$. If $gx$ is
maximal element of $A_{j}$ then
$f_{j}^{1}(gx)=f_{j}(gx)=f_{g(j)}(x)=f_{g(j)}^{1}(x)$. Also if $gx$ is not a
maximal element of $A_{j}$ then
$f_{j}^{1}(gx)=f_{j}^{0}(gx)=f_{g(j)}^{0}(x)=f_{g(j)}^{1}(x)$. So we have
$f_{j}^{1}(gx)=f_{g(j)}^{1}(x)$ holds for any $j$ and any $x\in
P,g\in\Sigma_{n}$.

Step III: Now we repeat this construction. We use $f_{j}^{1}$ and $f_{j}$ to
define $f_{j}^{2}$, and use $f_{j}^{2}$ and $f_{j}$ to define $f_{j}^{3}$ and
so on. By finiteness of $P$ and $Q$ this process will end and we get the order
preserving maps $f_{j}^{0},f_{j}^{1},f_{j}^{2},\cdots,f_{j}^{m}=f_{j}:P\to Q$
such that $f_{j}^{l}(gx)=f_{g(j)}^{l}(x)$ for any $1\leq j\leq n,0\leq l\leq
m,g\in\Sigma_{n}$ and $x\in P$.

Step IV: Now we show that the simplicial maps
$\mathcal{K}(f_{1}),\mathcal{K}(f_{2}),\cdots,\mathcal{K}(f_{n}):\mathcal{K}(P)\to\mathcal{K}(Q)$
are symmetrically contiguous. Let $C=\\{x_{0}\leq x_{1}\leq,\cdots,\leq
x_{c}\\}$ be a chain in $P$. Since the set $\\{x\in P;f_{j}^{l-1}(x)\neq
f_{j}(x)\\}$ has at most one maximal element in $C$, so by definition of
$f_{j}^{l}$ we have, $f_{j}^{l-1}$ and $f_{j}^{l}$ differ by at most one
element on $C$ (say $x_{p}$). Thus we have

$f_{j}^{l-1}(x_{0})=f_{j}^{l}(x_{0})\leq\cdots\leq f_{j}^{l-1}(x_{p})\leq
f_{j}^{l}(x_{p})\leq\cdots\leq f_{j}^{l-1}(x_{c})=f_{j}^{l}(x_{c}).$

Therefore for any chain $C$ in P, $f_{j}^{l-1}(C)\cup f_{j}^{l}(C)$ is also a
chain in $Q$. In other words for any simplex $\sigma$ of $\mathcal{K}(P)$,
$\mathcal{K}(f_{j}^{l-1})(\sigma)\cup\mathcal{K}(f_{j}^{l})(\sigma)$ is a
simplex in $\mathcal{K}(Q)$. So $\mathcal{K}(f_{j}^{l-1})(\sigma)$ and
$\mathcal{K}(f_{j}^{l})(\sigma)$ are one contiguous. Also
$f_{j}^{l}(gx)=f_{g(j)}^{l}(x)$ implies
$\mathcal{K}(f_{j}^{l})(gx)=\mathcal{K}(f_{g(j)}^{l})(x)$ holds for any $x\in
V(\mathcal{K}(P))\simeq P$. So we can say that the simplicial maps
$\mathcal{K}(f_{1}),\mathcal{K}(f_{2}),\cdots,\mathcal{K}(f_{n}):\mathcal{K}(P)\to\mathcal{K}(Q)$
are symmetrically contiguous. ∎

To prove our main theorem of this section, we need the following lemma. It is
a generalised version of [17, Lemma 2.4].

######  4.8 Lemma.

Let $K$ be a finite simplicial $\Sigma_{n}$-complex and the maps
$\phi_{1},\phi_{2},\cdots,\phi_{n}:K\to L$ are symmetrically contiguous. Then
the induced maps $\mathcal{X}(\phi_{j}):\mathcal{X}(K)\to\mathcal{X}(L)$ are
symmetrically homotopic.

###### Proof.

Assume that there is a chain of contiguous maps
$\phi_{*}=\phi_{j}^{0},\phi_{j}^{1},\cdots,\phi_{j}^{c}=\phi_{j}:K\to L$ such
that $\phi_{*}(gv)=\phi_{*}(v)$ and $\phi_{j}^{l}(gv)=\phi_{g(j)}(v)$ for
$1\leq l\leq c,1\leq j\leq n,v\in V(K)$ and $g\in\Sigma_{n}$. For each $l$ and
$j$ we define

$h_{j}^{l}:\mathcal{X}(K)\to\mathcal{X}(L),~{}~{}h_{j}^{l}(\sigma)=\phi_{j}^{l-1}(\sigma)\cup\phi_{j}^{l}(\sigma),$

for any $\sigma\in\mathcal{X}(K)$. Since
$\mathcal{X}(\phi_{j}^{l-1})(\sigma)=\phi_{j}^{l-1}(\sigma)$ and
$\mathcal{X}(\phi_{j}^{l})(\sigma)=\phi_{j}^{l}(\sigma)$, so
$\mathcal{X}(\phi_{j}^{l-1})\leq h_{j}^{l}\geq\mathcal{X}(\phi_{j}^{l})$. We
define a combinatorial homotopy $H:\mathcal{X}(K)\times
J_{n,2c}\to\mathcal{X}(L)$ by,

$H(\sigma,m_{j})=\begin{cases}h_{j}^{\frac{m+1}{2}}(\sigma)&\mbox{ if
}~{}~{}m\mbox{ is odd,}\\\
\mathcal{X}\big{(}\phi_{j}^{\frac{m}{2}}\big{)}(\sigma)&\mbox{ if
}~{}~{}~{}~{}m\mbox{ is even}.\end{cases}$

Now $\mathcal{X}(\phi_{j}^{l-1})\leq h_{j}^{l}\geq\mathcal{X}(\phi_{j}^{l})$
implies $H$ is order preserving and
$H(\sigma,2c_{j})=\mathcal{X}(\phi_{j}^{c})(\sigma)=\phi_{j}(\sigma)$. Also

$\mathcal{X}(\phi_{j}^{l})(g\sigma)=\phi_{j}^{l}(g\sigma)=\phi_{g(j)}^{l}(\sigma)=\mathcal{X}(\phi_{g(j)}^{l})(\sigma),$

and

$h_{j}^{l}(g\sigma)=\phi_{j}^{l-1}(g\sigma)\cup\phi_{j}^{l}(g\sigma)=\phi_{g(j)}^{l-1}(\sigma)\cup\phi_{g(j)}^{l}(\sigma)=h_{g(j)}^{l}(\sigma).$

Hence $H$ is a symmetric homotopy between $\mathcal{X}(\phi_{j}),~{}1\leq
j\leq n$. ∎

######  4.9.

Combinatorial complexity.  Here we recall the basics of higher combinatorial
complexity $\operatorname{\mathsf{C}C}_{n}(P)$ as introduced in ([10]).
Consider the mapping space $P^{J{n,m}}$, and the canonical order preserving
map

(5) $q_{n,m}:P^{J_{n,m}}\rightarrow
P^{n},~{}~{}q_{n,m}(\gamma)=(\gamma(m_{1}),\gamma(m_{2}),\cdots,\gamma(m_{n})).$

Note that Tanaka considered the following map to define
$\operatorname{\mathsf{C}C}_{2}(P)$,

$q_{m}:P^{J_{m}}\rightarrow P\times P\text{ defined by
}q_{m}(\gamma)=(\gamma(0),\gamma(m)),~{}~{}m\geq 0.$

Let $\tau_{P^{n}}:\operatorname{sd}(P^{n})\rightarrow P^{n}$ be the map
sending $p_{0}\leq p_{1}\leq\cdots\leq p_{n}$ to the last element $p_{n}$.
This is a weak homotopy equivalence, and the induced simplicial map
$\mathcal{K}(\tau_{P^{n}}):\mathcal{K}(\operatorname{sd}(P^{n}))=\operatorname{sd}(\mathcal{K}(P^{n}))\rightarrow\mathcal{K}(P^{n})$
is a simplicial approximation of the identity on $|\mathcal{K}(P^{n})|$ (see
[9]). For $r\geq 0$, we define

(6) $\tau_{P^{n}}^{r}:\operatorname{sd}^{r}(P^{n})\rightarrow P^{n}$

as the composition

$\operatorname{sd}^{r}(P^{n})\xrightarrow{\tau_{\operatorname{sd}^{r-1}(P^{n})}}\operatorname{sd}^{r-1}(P^{n})\xrightarrow{\tau_{\operatorname{sd}^{r-2}(P^{n})}}\cdots\xrightarrow{\tau_{\operatorname{sd}(P^{n})}}\operatorname{sd}(P^{n})\xrightarrow{\tau_{P^{n}}}P^{n}$.

Note that $\tau_{P^{n}}^{0}$ is identity map on $P^{n}$. For $r\geq 0$,
$\operatorname{\mathsf{C}C}_{n}^{r}(P)$ is defined to be the smallest non-
negative integer $k$ such that there exist an open cover
$\\{Q_{i}\\}_{i=1}^{k}$ of $\operatorname{sd}^{r}(P^{n})$ and an positive
integer $m$, with a map $s_{i}:Q_{i}\rightarrow P^{J_{n,m}}$ such that
$q_{n,m}\circ s_{i}=\tau_{P^{n}}^{r}$ on $Q_{i}$ for each $i$. If no such $k$
exists, then $\operatorname{\mathsf{C}C}_{n}^{r}(P)=\infty$. The sequence
$\\{\operatorname{\mathsf{C}C}_{n}^{r}(P)\\}$ is a decreasing sequence on $r$.
So we have the following definition for _$n$ -th combinatorial complexity_.

######  4.10 Definition.

The _$n$ -th combinatorial complexity_ $\operatorname{\mathsf{C}C}_{n}(P)$ of
$P$ is defined as:

$\operatorname{\mathsf{C}C}_{n}(P)=\min_{r\geq
0}\\{\operatorname{\mathsf{C}C}_{n}^{r}(P)\\}.$

We have the following theorem.

######  4.11 Theorem ([10]).

For any finite space $P$, we have
$\operatorname{\mathsf{C}C}_{n}(P)=\operatorname{\mathsf{T}C}_{n}(|\mathcal{K}(P)|)$,
$n\geq 2$.

######  4.12.

Symmetric combinatorial complexity.  In ([17]), Tanaka defined symmetric
combinatorial complexity $\operatorname{\mathsf{C}C}^{\Sigma}(P)$ for a finite
space $P$. He considered the mapping space $P^{J_{2m}}$ and the canonical map

$q_{2m}:P^{J_{2m}}\rightarrow P\times
P,~{}~{}~{}q_{2m}(\gamma)=(\gamma(0),\gamma(2m)),~{}~{}m\geq 0.$

Note that $P^{J_{2m}}$ and $P\times P$ both are $\mathbb{Z}_{2}$-spaces where
the non trivial action is given by $\gamma\to\gamma^{-1}$ and $(x,y)\to(y,x)$.
Also $q_{2m}$ is a $\mathbb{Z}_{2}$-map. Tanaka defined
$\operatorname{\mathsf{C}C}_{2,2m}^{\Sigma,r}(P)$ as the smallest non-negative
integer $k$ such that there exist $\mathbb{Z}_{2}$-invariant open cover
$\\{Q_{i}\\}_{i=1}^{k}$ of $\operatorname{sd}^{r}(P\times P)$ and on each
$Q_{i}$ there is a $\mathbb{Z}_{2}$-map $s_{i}:Q_{i}\rightarrow P^{J_{2m}}$
with $q_{2m}\circ s_{i}=\tau_{P\times P}^{r}$. If no such $k$ exists, then
$\operatorname{\mathsf{C}C}_{2,2m}^{\Sigma,r}(P)=\infty$. He proved that
$\\{\operatorname{\mathsf{C}C}_{2,2m}^{\Sigma,r}(P)\\}$ is a decreasing
sequence on $m$ and $r$ both. He defined the _symmetric combinatorial
complexity_ $\operatorname{\mathsf{C}C}^{\Sigma}(P)$ as the limit of
$\operatorname{\mathsf{C}C}_{2,2m}^{\Sigma,r}(P)$ as $m\to\infty,r\to\infty$.

Let us define $n$-th symmetric combinatorial complexity. Here we consider the
space $P^{J{n,m}}$ and the map $q_{n,m}:P^{J_{n,m}}\rightarrow P^{n}$ as in
Equation 5. Note that ${J_{n,m}}$ is a $\Sigma_{n}$-space, the action given by
$g(t_{j})=t_{g(j)},t\in\\{1,2,\cdots,m\\},j\in\\{1,2,\cdots,n\\}$. This
induces an action of $\Sigma_{n}$ on $P^{J{n,m}}$ given by
$g\gamma(t_{j})=\gamma(t_{g(j)})$. Also $P^{n}$ is a $\Sigma_{n}$-space, the
action is given by $g(x_{1},x_{2},\cdots
x_{n})=(x_{g(1)},x_{g(2)},\cdots,x_{g(n)})$ and the maps $q_{n,m}$ in Equation
5 and $\tau_{P^{n}}^{r}$ in Equation 6 are $\Sigma_{n}$-maps.

######  4.13 Definition.

Let $P$ be a finite space. We define
$\operatorname{\mathsf{C}C}_{n,m}^{\Sigma,r}(P)$ as the minimum number $k$
such that there is a $\Sigma_{n}$-invariant open cover $\\{Q_{i}\\}_{i=1}^{k}$
of $\operatorname{sd}^{r}(P^{n})$ and on each open set there is
$\Sigma_{n}$-map $s_{i}:Q_{i}\to P^{J_{n,m}}$ satisfying $q_{n,m}\circ
s_{i}=\tau_{P^{n}}^{r}$. If no such $k$ exists, then we define
$\operatorname{\mathsf{C}C}_{n,m}^{\Sigma,r}(P)$ to be $\infty$.

######  4.14 Lemma.

Let $P$ be a finite space. Then
$\operatorname{\mathsf{C}C}_{n,m}^{\Sigma,r}(P)\geq\operatorname{\mathsf{C}C}_{n,m+1}^{\Sigma,r}(P)$,
for any $m,r\geq 0$ and $n\geq 2$.

###### Proof.

We assume that $\operatorname{\mathsf{C}C}_{n,m}^{\Sigma,r}(P)=k$ and
$\\{Q_{i}\\}_{i=1}^{k}$ is a $\Sigma_{n}$-invariant open cover of
$\operatorname{sd}^{r}(P^{n})$ such that on each open set there is
$\Sigma_{n}$-map $s_{i}:Q_{i}\to P^{J_{n,m}}$ satisfying $q_{n,m}\circ
s_{i}=\tau_{P^{n}}^{r}$. Consider the retraction map $R:J_{n,m+1}\rightarrow
J_{n,m}$ sending each $(m+1)_{j}$ to $m_{j}$ for $1\leq j\leq n$. Clearly this
is an order preserving map and it induces a $\Sigma_{n}$-map
$R^{*}:P^{J_{n,m}}\rightarrow P^{J_{n,m+1}},\gamma\rightarrow\gamma\circ R$.
Then we have the following commutative diagram.

|
---|---
$\textstyle{P^{J_{n,m}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{R^{*}}$$\scriptstyle{q_{n,m}}$$\textstyle{P^{J_{n,m+1}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{n,m+1}}$$\textstyle{Q_{i}\subset\operatorname{sd}^{r}(P^{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{P^{n}}^{r}}$$\scriptstyle{s_{i}}$$\scriptstyle{s^{\prime}_{i}}$$\textstyle{P^{n}}$

Note that the composition map $R^{*}\circ
s_{i}=s^{\prime}_{i}:Q_{i}\rightarrow P^{{n,m+1}}$ is a $\Sigma_{n}$-map and
holds $q_{n,m+1}\circ s^{\prime}_{i}=\tau_{P^{n}}^{r}$ for each $i$. Thus,
$\operatorname{\mathsf{C}C}_{n,m+1}^{\Sigma,r}(P)\leq k$.

∎

######  4.15 Remark.

Since for any $m$ the value
$\operatorname{\mathsf{C}C}_{n,m}^{\Sigma,r}(P)\geq 1$, so by Lemma 4.14 the
value is stable for large $m$. We denote the stable value by
$\operatorname{\mathsf{C}C}^{\Sigma,r}_{n}(P)$.

For $r\geq 0$, let $\rho_{j}:\operatorname{sd}^{r}(P^{n})\rightarrow P$ denote
the composition of $\tau^{r}_{P^{n}}:\operatorname{sd}^{r}(P^{n})\rightarrow
P^{n}$ and the $j$-th projection $p_{j}:P^{n}\to P$ for $j=1,2,\cdots,n$. We
have the following lemma which gives an alternative formulation of the
definition for $\operatorname{\mathsf{C}C}^{\Sigma,r}_{n}(P)$.

######  4.16 Lemma.

With notations as above, $\operatorname{\mathsf{C}C}^{\Sigma,r}_{n}(P)$ is the
minimal number $k$ such that there exist a $\Sigma_{n}$-invariant open cover
$\\{Q_{i}\\}_{i=1}^{k}$ of $\operatorname{sd}^{r}(P^{n})$ and the maps
$\rho_{1},\rho_{2},\cdots,\rho_{n}:Q_{i}\rightarrow P$ are symmetrically
homotopic.

###### Proof.

The existence of maps $s:Q\to P^{J_{n,m}}$ and $H:Q\times J_{n,m}\to P$ are
equivalent by exponential law. Let $\mathbf{x}=(x_{1},x_{2},\cdots,x_{n})\in
Q$. We set $s(\mathbf{x})(t_{j})=H(\mathbf{x},t_{j}),$ for $t_{j}$ is
parameter for $j$-th fence and $j\in\\{1,2,\cdots,n\\}$. If $Q$ is an
$\Sigma_{n}$-invariant set then $s$ is an $\Sigma_{n}$-map if and only if $H$
satisfy the relation $H(g\mathbf{x},t_{j})=H(\mathbf{x},t_{g(j)})$. Also we
have,

$\displaystyle q_{n,m}\circ s_{i}=\tau_{P^{n}}^{k}$
$\displaystyle\Leftrightarrow[q_{n,m}\circ
s_{i}(\mathbf{x})](j)=[\tau_{P^{n}}^{k}(\mathbf{x})](j)$
$\displaystyle\Leftrightarrow s(\mathbf{x})(m_{j})=\rho_{j}(\mathbf{x})$
$\displaystyle\Leftrightarrow H(\mathbf{x},m_{j})=\rho_{j}(\mathbf{x})$
$\displaystyle\Leftrightarrow H\text{ is a homotopy between
}\rho_{1},\rho_{2},\cdots,\rho_{n}.$

Hence the Lemma follows. ∎

The value $\operatorname{\mathsf{C}C}^{\Sigma,r}_{n}(P)$ depends on $r$. If we
increase $r$ the value $\operatorname{\mathsf{C}C}^{\Sigma,r}_{n}(P)$ will
decrease. We have the following Proposition for $r=0$. This is a symmetric
version of [10, Theorem 4.9].

######  4.17 Proposition.

For any finite space $P$, we have
$\operatorname{\mathsf{C}C}_{n}^{\Sigma,0}(P)=\operatorname{\mathsf{T}C}_{n}^{\Sigma}(P)$,
$n\geq 2$.

###### Proof.

Using Lemma 4.16 we get, $\operatorname{\mathsf{C}C}_{n}^{\Sigma,0}(P)$ is the
minimal integer $k$ such that there exist a $\Sigma_{n}$-invariant open cover
$\\{Q_{i}\\}_{i=1}^{k}$ of $P^{n}$ and the projection maps
$\rho_{1},\rho_{2},\cdots,\rho_{n}:Q_{i}\rightarrow P$ are symmetrically
homotopic if and only if $\operatorname{\mathsf{T}C}_{n}^{\Sigma}(P)=k$ (using
Lemma 4.5 and Remark 2.7).

∎

######  4.18 Lemma.

Let $P$ be a finite space, and $r\geq 0$ and $n\geq 2$. Then we have,

  1. (i)

$\operatorname{\mathsf{C}C}_{n}^{\Sigma,r}(P)\geq\operatorname{\mathsf{S}C}_{n}^{\Sigma}(\mathcal{K}(P))$,

  2. (ii)

$\operatorname{\mathsf{C}C}_{n}^{\Sigma,r}(P)\geq\operatorname{\mathsf{C}C}_{n}^{\Sigma,r+1}(P)$.

###### Proof.

(i) Assume that $\operatorname{\mathsf{C}C}_{n}^{\Sigma,r}(P)=k$. By Lemma
4.16 there exists a symmetric open cover $\\{Q_{i}\\}_{i=1}^{r}$ of
$\operatorname{sd}^{r}(P^{n})$ such that
$\rho_{1},\rho_{2},\cdots,\rho_{n}:Q_{i}\rightarrow P$ are symmetrically
homotopic. By Proposition 4.7 we can say that the maps
$\mathcal{K}(\rho_{1}),\mathcal{K}(\rho_{2}),\cdots,\mathcal{K}(\rho_{n}):\mathcal{K}(Q_{i})\rightarrow\mathcal{K}(P)$
are symmetrically contiguous. Since $Q_{i}$ is symmetric open set implies the
subcomplex $\mathcal{K}(Q_{i})$ is symmetric and
$\\{\mathcal{K}(Q_{i})\\}_{i=1}^{k}$ is a cover of
$\mathcal{K}(\operatorname{sd}^{r}(P^{n}))=\operatorname{sd}^{r}(\mathcal{K}(P^{n}))$.
Also
$\mathcal{K}(\rho_{j})=\mathcal{K}(p_{j}\circ\tau^{r}_{P^{n}})=\mathcal{K}(p_{j})\circ\iota^{r}_{\mathcal{K}(P^{n})}=\pi_{j}$,
for $j=1,2,\cdots,n$ and by Lemma 3.7 $\iota^{r}_{\mathcal{K}(P^{n})}$ is
$\Sigma_{n}$-approximation of identity. So,
$\operatorname{\mathsf{S}C}^{\Sigma,r}_{n}(\mathcal{K}(P))\leq k$ and
therefore $\operatorname{\mathsf{S}C}_{n}^{\Sigma}(\mathcal{K}(P))\leq k$.

(ii) Let $\operatorname{\mathsf{C}C}_{n}^{\Sigma,r}(P)=k$. Then we have a
$\Sigma_{n}$-invariant open cover $\\{Q_{i}\\}_{i=1}^{k}$ of
$\operatorname{sd}^{r}(P^{n})$ such that on each $Q_{i}$ there is a
$\Sigma_{n}$-map $s_{i}:Q_{i}\to P^{J_{n,m}}$ satisfying $q_{n,m}\circ
s_{i}=\tau_{P^{n}}^{r}$ for some $m\geq 0$. Let us take the open cover
$\\{U_{i}\\}_{i=1}^{k}$ of $\operatorname{sd}^{r+1}(P^{n})$, where
$U_{i}=\tau^{-1}_{\operatorname{sd}^{r}(P^{n})}(Q_{i})$ and set
$s^{\prime}_{i}=s_{i}\circ\tau_{\operatorname{sd}^{r}(P^{n})}:U_{i}\to
P^{J_{n,m}}$ such that the following diagram commutes:

|  |  |
---|---|---|---
$\textstyle{U_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{\operatorname{sd}^{r}(P^{n})}}$$\scriptstyle{s^{\prime}_{i}}$$\textstyle{Q_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s_{i}}$$\textstyle{P^{J_{n,m}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{n,m}}$$\textstyle{\operatorname{sd}^{r+1}(P^{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{\operatorname{sd}^{r}(P^{n})}}$$\textstyle{\operatorname{sd}^{r}(P^{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau^{r}_{P^{n}}}$$\textstyle{P^{n}}$

Here $Q_{i}$ is $\Sigma_{n}$-invariant implies $U_{i}$ so and $s_{i}$ is a
$\Sigma_{n}$-map implies $s^{\prime}_{i}$ also. So we get a
$\Sigma_{n}$-invariant open cover $\\{U_{i}\\}_{i=1}^{k}$ of
$\operatorname{sd}^{r+1}(P^{n})$ and a $\Sigma_{n}$-map $s^{\prime}_{i}$ on
each $U_{i}$ such that $q_{n,m}\circ s^{\prime}_{i}=\tau_{P^{n}}^{r+1}$.
Therefore $\operatorname{\mathsf{C}C}_{n}^{\Sigma,r+1}(P)\leq k$.

∎

We get $\\{\operatorname{\mathsf{C}C}_{n}^{\Sigma,r}(P)\\}_{r}$ is a
decreasing sequence bounded below by $1$. So we make the following definition.

######  4.19 Definition.

For a finite space $P$, the _$n$ -th symmetric combinatorial complexity_
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)$ of $P$ is defined as:

$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)=\min_{r\geq
0}\\{\operatorname{\mathsf{C}C}^{\Sigma,r}_{n}(P)\\}.$

Let us now prove our main theorem. This can be viewed as a symmetric version
of [10, Theorem 5.6] and higher analogue of [17, Theorem 3.15].

######  4.20 Theorem.

For a finite space $P$,
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)=\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|\mathcal{K}(P)|)$,
for any $n\geq 2$.

###### Proof.

In (i) of Lemma 4.18, if we take $r\to\infty$, we get
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)\geq\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))$.
Let us prove
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)\leq\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))$.
Let $\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))=k$ and
$\\{L_{i}\\}_{i=1}^{k}$ be a collection of symmetric subcomplexes covering
$\operatorname{sd}^{r}(\mathcal{K}(P^{n}))$ such that the restrictions
$\pi_{1},\pi_{2},\cdots,\pi_{n}:L_{i}\rightarrow\mathcal{K}(P)$ are
symmetrically contiguous, for some $r\geq 0$ and for each $i$. By Lemma 4.8
the maps
$\mathcal{X}(\pi_{1}),\mathcal{X}(\pi_{2}),\cdots,\mathcal{X}(\pi_{n}):\mathcal{X}(L_{i})\rightarrow\mathcal{X}(\mathcal{K}(P))=\operatorname{sd}(P)$
are symmetrically homotopic. So the composition maps
$\tau_{P}\circ\mathcal{X}(\pi_{1}),\tau_{P}\circ\mathcal{X}(\pi_{2}),\cdots,\tau_{P}\circ\mathcal{X}(\pi_{n}):\mathcal{X}(L_{i})\rightarrow
P$ are also symmetrically homotopic. Using Remark 4.3, since $L_{i}$ is a
subcomplex of $\operatorname{sd}^{r}(\mathcal{K}(P^{n})),$ so
$\mathcal{X}(L_{i})$ is open in
$\mathcal{X}(\operatorname{sd}^{r}(\mathcal{K}(P^{n})))=\operatorname{sd}^{r+1}(P^{n})$,
for each $i$. Now $\\{L_{i}\\}_{i=1}^{k}$ is a collection of symmetric
subcomplexes covering $\operatorname{sd}^{r}(\mathcal{K}(P^{n}))$ implies
$\\{\mathcal{X}(L_{i})\\}_{i=1}^{k}$ is a symmetric open cover of
$\operatorname{sd}^{r+1}(P^{n})$. Also for any $j\in\\{1,2,\cdots,n\\}$ we
have,

$\displaystyle\tau_{P}\circ\mathcal{X}(\pi_{j})$
$\displaystyle=\tau_{P}\circ\mathcal{X}(\mathcal{K}(p_{j}\circ\tau^{k}_{P^{n}}))=\tau_{P}\circ\operatorname{sd}(p_{j}\circ\tau^{k}_{P^{n}})$
$\displaystyle=\tau_{P}\circ\operatorname{sd}(p_{j})\circ\operatorname{sd}(\tau^{k}_{P^{n}})=p_{j}\circ\tau_{P^{n}}^{k+1}=\rho_{j},$

where $p_{j}:P^{n}\to P$ is the $j$-th projection. Hence
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)\leq
k=\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))$ and using Theorem
3.19 we have
$\operatorname{\mathsf{C}C}^{\Sigma}_{n}(P)=\operatorname{\mathsf{S}C}^{\Sigma}_{n}(\mathcal{K}(P))=\operatorname{\mathsf{T}C}^{\Sigma}_{n}(|\mathcal{K}(P)|)$,
for any $n\geq 2$. ∎

## References

  * [1] J. Barmak & E.G. Minian, “Strong homotopy types, nerves and collapses,” (English summary) Discrete Comput. Geom. 47 (2012), no. 2, pp. 301 - 328.
  * [2] I. Basabe, J. González, Y. B. Rudyak & D. Tamaki, “Higher topological complexity and its symmetrization,” Algebr. Geom. Topol. 14 (2014), no. 4, pp. 2103 - 2124.
  * [3] G. E. Bredon, Introduction to compact transformation groups, Pure and Applied Mathematics, 46, Academic Press, New York-London, 1972, xiii+459.
  * [4] S. Eilenberg & N. Steenrod, “Foundations of algebraic topology,” Princeton University Press, Princeton, New Jersey (1952), xv+328.
  * [5] M. Farber, Invitation to topological robotics, Zurich Lectures in Advanced Mathematics, European Mathematical Society (EMS), Zürich, (2008) x+133.
  * [6] M. Farber, “Topological complexity of motion planning,” Discrete Comput. Geom. 29 (2003), no. 2, pp. 211 - 221.
  * [7] M. Farber and M. Grant, “Symmetric motion planning,” Contemp. Math. 438, Amer. Math. Soc. (2007), pp. 85 - 104.
  * [8] J. González, “Simplicial complexity: piecewise linear motion planning in robotics,” New York J. Math. 24 (2018), pp. 27 - 292.
  * [9] K.A. Hardie and J.J.C Vermeulen, “Homotopy theory of finite and locally finite $T_{0}$ spaces,” Exposition. Math. 11 (1993), pp. 331 - 341.
  * [10] A. K. Paul, “ Higher analogs of simplicial and combinatorial complexity,” Topology Appl. 267 (2019).
  * [11] M. Pors, S. Sarkar & P. Zvengrowski, “ Remarks about $\Delta$-complexes and applications,” Homology Homotopy Appl. 19 (2017), no. 1, pp. 89 - 110.
  * [12] V. V. Prasolov, Elements of homology theory, Graduate Studies in Mathematics 81, American Mathematical Society, Providence, RI, 2007, x+418.
  * [13] Y. B. Rudyak, “ On higher analogs of topological complexity,” Topology Appl. 157 (2010), no. 5, pp. 916 - 920.
  * [14] E. H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966, xiv+528.
  * [15] R.E. Stong, “Finite topological spaces,” Trans. Amer. Math. Soc. 123 1966 pp. 325 - 340.
  * [16] K. Tanaka, “A combinatorial description of topological complexity for finite spaces,” (English summary) Algebr. Geom. Topol. 18 (2018), no. 2, pp. 779 - 796.
  * [17] K. Tanaka, “Symmetric topological complexity for finite spaces and classifying spaces,” Topol. Methods Nonlinear Anal. 54 (2019), no. 2, pp. 477 - 493.