# Bounds for the higher topological complexity of configuration spaces of
trees

Teresa I. Hoekstra-Mendoza

###### Abstract

For a tree $T$, we show that the higher topological complexity of the
unordered configuration space of $n$ points in $T$ is maximal for many values
of $n$.

##  1 Introduction

The concept of topological complexity “TC” was introduced by Farber motivated
by the most basic problem of robot motion planning: finding the smallest
number of continuous instructions for a robot to move from one point to
another in a path-connected space.

Rudyak extended Farber’s notion of topological complexity by defining, for
$s\geq 2$, the $s$th topological complexity $TC_{s}(X)$ of a path-connected
space $X$ which recovers Farber’s original notion for $s=2.$

Given a topological space $X$, the $s$-topological complexity $TC_{s}(X)$ can
be described as $TC_{s}(X)+1$ being the minimal number of open sets which
cover the product $X^{s}$ such that on each open set, $e_{s}$ admits a
section. Here $e_{s}:PX\rightarrow X^{s}$ is the sequential evaluation defined
in Section 2.2.

The space $X$ is often viewed as the space of configurations of some real-
world system. One example is when $X$ is the space of configurations of $n$
robots which move around a factory along a system of one-dimensional tracks.
Such a system of tracks can be interpreted as a graph (a one-dimensional CW
complex).

For a finite graph $\Gamma$ and a positive integer $n$, let
$\mathcal{C}^{n}\Gamma$ denote the configuration space of $n$ ordered points
on $\Gamma$,

$\mathcal{C}^{n}\Gamma=\left\\{(x_{1},\ldots,x_{n})\in\Gamma^{n}\colon
x_{i}\neq x_{j}\mbox{ for }i\neq j\right\\}.$

The usual right action of the $n$-symmetric group $\Sigma_{n}$ on
$\mathcal{C}^{n}\Gamma$ is given by
$(x_{1},\ldots,x_{n})\cdot\sigma=(x_{\sigma(1)},\ldots,x_{\sigma(n)})$, and
$U\mathcal{C}^{n}\Gamma$ stands for the corresponding orbit space, the
configuration space of $n$ unlabelled points on $\Gamma$. Both
$\mathcal{C}^{n}\Gamma$ and $U\mathcal{C}^{n}\Gamma$ are known to be
aspherical ([1]); their corresponding fundamental groups are denoted by
$P_{n}\Gamma$ (the pure $n$-braid group on $\Gamma$) and $B_{n}\Gamma$ (the
full $n$-braid group or, simply, the $n$-braid group on $\Gamma$). We focus on
the case of a tree $\Gamma=T$ (a tree is a connected graph which has no
cycles).

Our main goal is to study the topological complexity of the configuration
spaces $\mathcal{C}^{n}T.$ The topological complexity of these configuration
spaces is related to the number of essential vertices of $T$, which are the
vertices of degree greater than or equal to three–more specifically, on how
many vertices of degree exactly three there are in relation to the number of
essential vertices of higher degree, and on how they are distributed along the
tree $T$.

In [10] Scheirer gave bounds for the usual ($s=2$) topological complexity of
the configuration spaces of trees. Using slightly different techniques, we
generalize Scheirer’s results for any $s\geq 2$.

We start section two with some terminology we shall use, as well as an
introduction to discrete Morse theory and topological complexity. We also give
a desription of Abrams’ discrete model, and Farley and Sabalka’s discrete
gradient vector field, which are the tools we will use in the rest of the
paper.

In section three we give a description of how to obtain cup products in the
cohomology ring of $U\mathcal{D}^{n}T$ for any tree $T$ and any $n\geq 4$,
noticing that when the tree is binary, its cohomology ring is an exterior face
ring.

In section four we prove our main results; we prove that the higher
topological complexity or $U\mathcal{D}^{n}T$ is maximal for any tree $T$ and
many values of $n$.

Finally in section five we compare our results in the special case when $s=2$
to Scheirer’s results, and how to obtain at Scheirer’s terminology starting
from ours and viceversa.

##  2 Preliminaries

We start this section by introducing some notation and terminology which we
shall use thoughout the paper.

Fix once and for all a planar embedding together with a root (a vertex of
degree 1) for $T$. Order the vertices of $T$ as they are first encountered
through the walk along the tree that (a) starts at the root vertex, which is
assigned the ordinal 0, and that (b) takes the left-most branch at each
intersection given by an essential vertex (turning around when reaching a
vertex of degree 1). Vertices of $T$ will be denoted by the assigned non-
negative integer. An edge of $T$, say with endpoints $r$ and $s$, will be
denoted by the ordered pair $(r,s)$, where $r<s$. Furthermore, the ordering of
vertices will be transferred to an ordering of edges by declaring that the
ordinal of $(r,s)$ is $s$.

Let $d(x)$ stand for the degree of a vertex $x$ of $T$, so there are $d(x)$
“directions” from $x$. For a vertex $x$ different from the root, the direction
from $x$ that leads to the root is defined to be the $x$-direction 0;
$x$-directions $1,2,\dots,d(x)-1$ (if any) are then chosen following the
positive orientation coming from the planar embedding. For instance, if $x$ is
not the root and the vertex $y$ incident to $x$ in $x$-direction 0 is not
essential (i.e. $d(y)\leq 2$), then $y=x-1$. Likewise, if $d(x)\geq 2$, then
$x+1$ is the vertex incident to $x$ in $x$-direction 1. It will be convenient
to think of the only direction from the root vertex $0$ as 0-direction 1, in
particular there is no $0$-direction 0. Given an edge $e$ we shall denote by
$\iota(e)$ and $\tau(e)$ its endpoints with $\iota(e)<\tau(e)$.

Fix essential vertices $x_{1}<\cdots<x_{m}$ of T. The complement in $T$ of the
set $\\{x_{1},\ldots,x_{m}\\}$ decomposes into
$1+\sum_{i=1}^{m}\left(d(x_{i})-1\right)$ conected components
$C_{i,\ell_{i}}=C_{i,\ell_{i}}(x_{1},\ldots,x_{m})$, where $0\leq i\leq m$,
$\ell_{0}=1$, and $1\leq\ell_{i}\leq d(x_{i})-1$ for $i>0$. The closure of
each $C_{i,\ell_{i}}$ is a subtree of $T$. $C_{0,1}$ is the component
containing the root $0$, while $C_{i,\ell_{i}}$ (for $i>0$) is the component
whose closure contains $x_{i}$ and is located on the $x_{i}$-direction
$\ell_{i}$. The set $B(C_{i,\ell_{i}})$ of “bounding” vertices of a component
$C_{i,\ell_{i}}$ is defined to be the intersection of the closure of
$C_{i,\ell_{i}}$ with $\\{x_{1},\ldots,x_{m}\\}$. Note that $x_{i}\in
B(C_{i,\ell_{i}})$ for $i>0$, however the root $0$ is not considered to be a
bounding vertex of $C_{0,1}$, just as no leaf of $T$ (i.e., a vertex of degree
1 other than the root) is considered to be a bounding vertex of any
$C_{i,\ell_{i}}$. Furthermore, the set of pruned leaves is
$L_{i,\ell_{i}}:=B(C_{i,\ell_{i}})\setminus\\{x_{i}\\}$.

######  Example 2.1.

Consider the tree of Figure 1(left), we can see in Figure 1(right) the
connected components of $T-\\{x_{1},x_{2},x_{3}\\}$. The only non empty sets
of pruned leaves are $L_{0,1}=\\{x_{1}\\}$ and $L_{1,2}=\\{x_{2},x_{3}\\}$

$x_{1}$$x_{2}$$x_{3}$$C_{0,1}$$C_{1,3}$$C_{1,1}$$C_{2,1}$$C_{2,2}$$C_{2,3}$$C_{1,2}$$C_{3,1}$$C_{3,2}$$C_{3,3}$
Figure 1: The tree $T$ and the connected components of
$T-\\{x_{1},x_{2},x_{3}\\}$.

###  2.1 Discrete Morse theory

A very powefull tool for analyzing configuration spaces of graphs is discrete
Morse theory, since it allows us to reduce the amount of cells in a complex
while preserving the topological properties. Assume throughout this section
that $X$ is a regular complex.

######  Definition 2.2.

A cell $\sigma$ of $X$ is called:

  * •

critical, provided it does not appear as an entry of any pair of $W$;

  * •

redundant, provided there is a cell $\sigma^{\prime}$ such that
$(\sigma,\sigma^{\prime})\in W$;

  * •

collapsible, provided there is a cell $\sigma^{\prime}$ such that
$(\sigma^{\prime},\sigma)\in W$.

$W$ is called a discrete vector field if each cell of $X$ appears as an entry
of at most one pair of $W$. In other words, $W$ is a discrete vector field
provided any cell of $X$ is of one and only one of the three types above.

For a redundant cell $\tau$ of $X$, we shall denote by $W(\tau)$ the unique
cell of $X$ with $(\tau,W(\tau))\in W$.

######  Definition 2.3.

Let $W$ be a discrete vector field on $X$. A sequence of $k$-cells,
$\tau_{1},\ldots,\tau_{n}$ satisfying $\tau_{i}\neq\tau_{i+1}$ for
$i=1,\ldots,n-1$ is called an upper $W$-path of length $n$ if, for each
$i=1,\ldots,n-1$, $\tau_{i}$ is redundant and $\tau_{i+1}$ is a face of
$W(\tau_{i})$. Similarly, if $\tau_{i}$ is collapsible with
$\tau_{i}=W(\sigma_{i})$, and $\sigma_{i}$ is a face of $\tau_{i-1}$ for
$i=2,\dots,n$ then the sequence is called a lower $W$-path of length $n$. The
$W$-path is closed if $\tau_{1}=\tau_{n}$. We say that $W$ is a gradient
vector field provided it does not admit closed $W$-paths.

We can also think of the gradient paths as directed paths in the Hasse diagram
as follows. Let $X$ denote a finite regular cell complex. The Hasse diagram of
$X$, $H_{X}$ is a directed graph, where the vertices are the cells of $X$, and
there exists an arrow from the vertex $v$ to the vertex $w$ if $w$ is a face
of $v$, and $\text{dim}(v)=\text{dim}(w)+1$. Given a discrete vector field $W$
on $X$, the modified Hasse diagram $H_{X}(W)$ is the directed graph obtained
from $H_{X}$ by reversing every arrow belonging to $W$. A $W$-path is a
directed path in $H_{X}(W)$ which alternates reversed arrows with arrows in
$H_{X}$.

We need to recall how gradient paths recover (co)homological information. In
the rest of the section we assume $W$ is a gradient field on $X$.

Start by fixing an orientation on each cell of $X$ and, for cells
$a^{(p)}\subset b^{(p+1)}$, consider the incidence number $\iota_{a,b}$ of $a$
and $b$, i.e. the coefficient ($\pm 1$, since $X$ is regular) of $a$ in the
expression of $\partial(b)$. Here $\partial$ is the boundary operator in the
cellular chain complex $C_{*}(X)$. The Morse cochain complex
$\mathcal{M}^{*}(X)$ is then defined to be the graded $R$-free111Cochain
coefficients are taken in a ground ring $R$, as we are interested in cup
products. module generated in dimension $p\geq 0$ by the duals222We omit the
use of an asterisk for dual elements. of the oriented critical cells $A^{(p)}$
of $X$. The definition of the Morse coboundary map in $\mathcal{M}^{*}(X)$
requires the concept of multiplicity of upper/lower paths. For a path of
length two, multiplicity is given by

$\mu(a_{0}\nearrow b_{1}\searrow
a_{1})=-\iota_{a_{0},b_{1}}\cdot\iota_{a_{1},b_{1}}\mbox{ \ \ and \ \
}\mu(c_{0}\searrow d_{1}\nearrow
c_{1})=-\iota_{d_{1},c_{0}}\cdot\iota_{d_{1},c_{1}},$ (1)

and, in the general case, it is defined to be a multiplicative function with
respect to concatenation of paths. The Morse coboundary is then defined by

$\partial(A^{(p)})=\sum_{B^{(p+1)}}\left(\sum_{b^{(p)}\subset
B}\left(\iota_{b,B}\sum_{\gamma\in\overline{\Gamma}(b,A)}\mu(\gamma)\right)\right)\cdot
B.$ (2)

In other words, the Morse theoretic incidence number of $A$ and $B$ is given
by the number of gradient paths $\overline{\gamma}$ from $B$ to $A$ counted
with multiplicity $\mu(\overline{\gamma}):=\iota_{b,B}\cdot\mu(\gamma)$.

###  2.2 Abrams discrete model and Farley-Sabalka’s gradient field

Since the configuration space of graph is obtain by removing certain points
from the product of the graph with itself, it does not have a CW-complex
structure (nor a cubical or simplicial complex structure). This is why we use
Abrams discrete model. For a tree $T$, think of $T^{n}$ as a cubical set.

Abrams discrete model for $\mathcal{C}^{n}T$ is the largest cubical subset
$\mathcal{D}^{n}T$ of $T^{n}$ inside $\mathcal{C}^{n}T$. In other words,
$\mathcal{D}^{n}T$ is obtained by removing open cubes from $T^{n}$ whose
closure intersect the fat diagonal. As usual, the symmetric group $\Sigma_{n}$
acts on the right of $\mathcal{D}^{n}T$ by permuting factors. The action
permutes in fact cubes, and the quotient complex is denoted by
$U\mathcal{D}^{n}T$.

Thus a cell in $U\mathcal{D}^{n}T$ can be written as
$c=\\{a_{1},a_{2},\dots,a_{n}\\}$ where each $a_{i}$ is either a vertex or an
edge of $T$, $a_{i}\cap a_{j}=\emptyset$ if $i\neq j$ and the dimension $c$ is
$|\\{i\in\\{1,\dots,n\\}:a_{i}\in E(T)\\}|$, that is, the number of edges of
$T$ that are in $c$. Each $a_{i}$ is called an ingredient of $c$ (vertex-
ingredient or edge-ingredient).

######  Theorem 2.4.

[1] Let $\Gamma$ be a graph with at least $n$ vertices. Suppose

  1. 1.

each path between distinct vertices of degree not equal to 2 in $\Gamma$
contains at least $n-1$ edges, and

  2. 2.

each loop at a vertex in $\Gamma$ which is not homotopic to a constant map
contains at least $n+1$ edges.

Then, $\mathcal{C}^{n}\Gamma$ and $U\mathcal{C}^{n}\Gamma$ deformation retract
onto $\mathcal{D}^{n}\Gamma$ and $U\mathcal{D}^{n}\Gamma$, respectively.

Theorem 2.4 allows us to work with the space $U\mathcal{D}^{n}T$ which is much
easier to work with than $U\mathcal{C}^{n}T$.

In [5] Farley and Sabalka gave a discrete gradient vector field for the space
$U\mathcal{D}^{n}T$. For a vertex $x$ of $T$ different from the root $0$, let
$e_{x}$ be the unique edge of $T$ of the form $(y,x)$ with $y<x$. A vertex-
ingredient $x$ of a cell $c$ is said to be blocked in $c$ if $x=0$ or, else,
if $e_{x}\cap c\neq\emptyset$ and $x$ is said to be unblocked in $c$
otherwise. An edge-ingredient $e$ of a cube $c$ is said to be order-
disrespecting in $c$ provided $e$ is of the form $(x,y)$ and there is a vertex
ingredient $z$ in $c$ with $x<z<y$ and $z$ adyacent to $x$ (in particular $x$
must be an essential vertex); $e$ is said to be order-respecting in $c$
otherwise. Blocked vertex-ingredients and order-disrespecting edge ingredients
in $c$ are said to be critical. A cell is critical in Farley and Sablaka’s
gradient vector field if all of its ingredients are critical.

###  2.3 Topological complexity

For $s\geq 2$, the $s$th topological complexity of a path-connected space $X$,
$\operatorname{TC}_{s}(X)$, is defined as the sectional category of the
evaluation map $e_{s}\colon PX\to X^{s}$ which sends a (free) path on $X$,
$\gamma\in PX$, to the $s$-tuple

$e_{s}(\gamma)=\left(\gamma\left(\frac{0}{s-1}\right),\gamma\left(\frac{1}{s-1}\right),\ldots,\gamma\left(\frac{s-1}{s-1}\right)\right).$

A standard estimate for the $s$th topological complexity of a space $X$, which
we will use to obtain our bounds, is given by:

######  Proposition 2.5.

[3] For a $c$-connected space $X$ having the homotopy type of a CW complex,

$\operatorname{zcl}_{s}(X)\leq\operatorname{TC}_{s}(X)\leq
s\operatorname{hdim}(X)/(c+1).$

The notation $\operatorname{hdim}(X)$ stands for the (cellular) homotopy
dimension of $X$, i.e. the minimal dimension of a CW complex having the
homotopy type of $X$. On the other hand (and for our purposes), the $s$th
zero-divisor cup-length of $X$, $\operatorname{zcl}_{s}(X)$, is defined in
purely cohomological terms333All cohomology groups in this paper are taken
with $\mathbb{Z}$-coefficients.. The zero-divisor cup-length,
$\operatorname{zcl}_{s}(X)$ is the largest non-negative integer $\ell$ such
that there are classes $z_{j}\in H^{*}(X^{s})$, each with trivial restriction
under the iterated diagonal inclusion $\Delta_{s}\colon X\hookrightarrow
X^{s}$, and such that the cup product $z_{1}\cdots z_{\ell}\in H^{*}(X^{s})$
is non-zero. Each such class $z_{i}$ is called an $s$th zero-divisor for $X$.
The “zero-divisor” terminology comes from the observation that the map induced
in cohomology by $\Delta_{s}$ restricts to the $s$-fold tensor power
$H^{*}(X)^{\otimes s}$ to yield the $s$-iterated cup product.

##  3 The cohomology ring of $U\mathcal{D}^{n}T$

In [8] we analized the cohomology ring of $U\mathcal{D}^{n}T$, in particular
we showed how to compute cup products. In view of proposition 2.5, this is
particularly useful for obtaining the bounds in section 4.

One of the most important aspects about configuration spaces of trees, is the
following theorem, which allows to obtain cup products easily.

######  Theorem 3.1.

[6] The Morse differential in $U\mathcal{D}^{n}T$ vanishes and therefore for
each $m\geq 0$, a graded basis of $H^{m}(U\mathcal{D}^{n}T)$ is given by the
cohomology classes of the duals of the critical $m$-cells.

Assume $p=(p_{1},\dots,p_{r})$ and $q=(q_{1},\dots,q_{s})$ are integer vectors
such that $p_{i}\geq 0$ for $1\leq i\leq r$, $q_{i}\leq 0$ for $1\leq i\leq s$
and there exists at least one $i\in\\{1,\dots,r\\}$ such that $p_{i}>0$. Let
$x$ be an essential vertex of degree $r+s+1$, we shall denote by
$\\{k|x,p,q\\}$ the critical cell which has $k$ vertices blocked at the root
vertex, the edge $(x,y)$ where $y$ is the vertex lying on the $x$-direction
$r+1$, $p_{i}$ vertices blocked on the $x$-direction $i$ for $1\leq i\leq r$,
and $q_{i}$ vertices blocked on the $x$-direction $i+r$ for $1\leq i\leq s$
(see Figure 2). Similarly we denote a critical $m$-cell by
$\\{k|x_{1},p_{1},q_{1}|x_{2},p_{2},q_{2}|\dots|x_{m},p_{m},q_{m}\\}$ (see for
example Figure 3).

$0$$x$

Figure 2: The critical 1-cell $\\{3|x,(2,3),(1,0,1)\\}$

.

$0$$x$$z$$y$ Figure 3: The critical 3-cell
$c=\\{2|x,(0,1),(0,1)|y,(1,1),(1)|z,(2),(0)\\}$.

Given the factors

$\left\\{k_{1}|x_{1},(p_{1,1},\ldots,p_{1,r_{1}}),(q_{1,1},\ldots,q_{1,s_{1}})\right\\}{\cdots}\left\\{k_{m}|x_{m},(p_{m,1},\ldots,p_{m,r_{m}}),(q_{m,1},\ldots,q_{m,s_{m}})\right\\}$
(3)

we are going to define the interaction parameters as follows, which will help
us decide when a cup product of cells is non zero.

######  Definition 3.2.

The interaction parameters $\mathcal{R}_{0}$,
$\mathcal{P}_{i}:=(\mathcal{P}_{i,1},\ldots,\mathcal{P}_{i,r_{i}})$ and
$\mathcal{Q}_{i}:=(\mathcal{Q}_{i,1},\ldots,\mathcal{Q}_{i,s_{i}})$ of the
factors in $(\ref{aproduct})$ are given by

$\displaystyle\mathcal{R}_{0}$ $\displaystyle:=n\,+\\!\sum_{x_{j}\in
L_{0,1}}(k_{j}-n),$ $\displaystyle\mathcal{P}_{i,\ell_{i}}$
$\displaystyle:=p_{i,\ell_{i}},+\sum_{x_{j}\in L_{i,\ell_{i}}}(k_{j}-n),\mbox{
for }i\in\\{1,\ldots,m\\}\mbox{ and }\ell_{i}\in\\{1,\dots,r_{i}\\},\mbox{ and
}$ $\displaystyle\mathcal{Q}_{i,\ell_{i}}$
$\displaystyle:=q_{i,\ell_{i}}\,+\sum_{x_{j}\in
L_{i,\ell_{i}+r_{i}}}(k_{j}-n),\mbox{ for }i\in\\{1,\ldots,m\\}\mbox{ and
}\ell_{i}\in\\{1,\dots,s_{i}\\}.$

If $\mathcal{R}_{0}\geq 0$, $\mathcal{P}_{i}\geq 0$ and $\mathcal{Q}_{i}\geq
0$ for all $i=1,\ldots,m$, we say that the factors in $(\ref{aproduct})$
interact weakly and, if in addition $\mathcal{P}_{i}>0$ for every $i$, we say
that the factors in $(\ref{aproduct})$ interact strongly. Otherwise, we say
that the factors in $(\ref{aproduct})$ do not interact.

In the above definition $\mathcal{P}_{i},\mathcal{Q}_{i}\geq 0$ means that
every entry is greater than or equal to zero and $\mathcal{P}_{i}>0$ means
that at least one entry is strictly greater than zero.

######  Example 3.3.

Assume we have the tree of Figure 1 sufficiently subdivided for $n=10$ and
consider the cells $\\{1|x_{1},(1,7),(0)\\},\\{7|x_{2},(2,0),(0)\\}$ and
$\\{6|x_{3},(1),(1,1)\\}$. Recall that $L_{0,1}=\\{x_{1}\\}$ and
$L_{1,2}=\\{x_{2},x_{3}\\}$. Then the interaction parameters are
$\mathcal{R}_{0}=10+(9-10)=1\mathcal{P}_{1,2}=7+(7-10)+(6-10)=0$ and
$\mathcal{P}_{i,j}=p_{i,j}$ and $\mathcal{Q}_{i,j}=q_{i,j}$ for the remaining
interaction parameters thus
$\mathcal{P}_{1,1}=1,\mathcal{Q}_{1,1}=0,\mathcal{P}_{2,1}=2,\mathcal{P}_{2,2}=0,\mathcal{Q}_{2,1}=0,\mathcal{P}_{3,1}=1,\mathcal{Q}_{3,1}=1$
and $\mathcal{Q}_{3,2}=1$.

######  Proposition 3.4.

[8] The product $(\ref{aproduct})$ agrees with the critical $m$-cell

$\\{\mathcal{R}_{0}|x_{1},\mathcal{P}_{1},\mathcal{Q}_{1}|\cdots|x_{m},\mathcal{P}_{m},\mathcal{Q}_{m}\\}$

provided the factors of $(\ref{aproduct})$ interact strongly. Recall
$\mathcal{P}_{i}=(\mathcal{P}_{i,1},\mathcal{P}_{i,2},\dots,\mathcal{P}_{i,r_{i}})$
and
$\mathcal{Q}_{i}=(\mathcal{Q}_{i,1},\mathcal{Q}_{i,2},\dots,\mathcal{Q}_{i,s_{i}})$.

######  Example 3.5.

Consider again the cells of Example 3.3. Since every interaction paramenter is
greater or equal than zero, and, for every $i\in\\{1,2,3\\}$ there exists $j$
such that $P_{i,j}>0$ we have that the three factors interact strongly and
thus by Proposition 3.4 their cup product is the 3-cell
$\\{1|x_{1},(1,0),(0)|x_{2},(2,0),(0)|x_{3},(1),(1,1)\\}$.

######  Theorem 3.6.

[8] Any critical $m$-cell
$\\{\mathcal{R}_{0}|x_{1},\mathcal{P}_{1},\mathcal{Q}_{1}|\cdots|x_{m},\mathcal{P}_{m},\mathcal{Q}_{m}\\}$
is the strong interaction product of $m$ critical 1-cells.

Given a critical $m$-cell $c$ with edge-ingredients $(x_{i},y_{i})$ for
$i=1,\dots,m$, we can obtain one of its factors as follows: fix
$i\in\\{1,\dots,m\\}$ and let $d_{i}$ be the cell obtained from $c$ by
substituting every edge $(x_{j},y_{j})$ with the vertex $x_{j}$ for $j\neq i$.
Then $d_{i}$ is a redundant 1-cell and the factor of $c$ is the unique
critical 1-cell $c_{i}$ such that there exists a gradient path from $d_{i}$ to
$c_{i}$.

To be specific, the cell $c_{i}$ is the critical 1-cell (which contains the
edge-ingredient $(x_{i},y_{i})$) $\\{k_{i}|x_{i},p_{i},q_{i}\\}$ where
$p_{i}=(p_{i,1},\dots,p_{i,r})$, $q_{i}=(q_{i,1},\dots,q_{i,s})$ and $p_{i,j}$
denotes the amount of vertex-ingredients in the cell $d_{i}$ that lie on
$x_{i}$-direction $j$. Similarly $q_{i,j}$ denotes the amount of vertex-
ingredients in the cell $d_{i}$ that lie on $x_{i}$-direction $j+r$.

Now we want to see how a weak interaction product looks like. This case is a
bit more complicated than the strong interaction product, since the weak
interaction product yields, in many cases, a large sum of cells instead of
only one cell. Let $\Pi_{1}$ stand for a product (3) whose factors interact
strongly, so Proposition 3.4 applies. Choose an additional 1-dimensional
critical cell
$\\{k_{x}|x,(p_{x,1},\ldots,p_{x,r_{x}}),(q_{x,1},\ldots,q_{x,s_{x}})\\}$ with
$x<x_{1}<\cdots<x_{m}$ and where the standard conditions and conventions are
assumed, namely,

$p_{x}:=(p_{x,1},\ldots,p_{x,r_{x}})>0\ \ \mbox{and}\ \
q_{x}:=(q_{x,1},\ldots,q_{x,s_{x}})\geq 0,$ (4)

where $r_{x}\geq 1\leq s_{x}$, $r_{x}+s_{x}=d_{x}:=d(x)-1$,
$|p_{x}|:=\sum_{\ell=1}^{r_{x}}p_{x,\ell}$,
$|q_{x}|:=\sum_{\ell=1}^{s_{x}}q_{x,\ell}$, $k_{x}+|p_{x}|+|q_{x}|=n-1$ and
$\overline{x}:=x[r_{x}+1]$. Consider the interaction parameters
$P_{i}:=\mathcal{P}_{i}(x_{1},\ldots,x_{m})$ and
$Q_{i}:=\mathcal{Q}_{i}(x_{1},\ldots,x_{m})$ of the factors of $\Pi_{1}$
($i\in\\{1,\ldots,m\\}$), as well as the first three interaction parameters
$R_{0}:=\mathcal{R}_{0}(x,x_{1},\ldots,x_{m})$,
$P_{x}:=\mathcal{P}_{1}(x,x_{1},\ldots,x_{m})$ and
$Q_{x}:=\mathcal{Q}_{1}(x,x_{1},\ldots,x_{m})$ of the factors of
$\Pi_{2}:=\\{k_{x}|x,p_{x},q_{x}\\}\cdot\Pi_{1}$.

######  Theorem 3.7.

[8] In the situation above, if the factors of $\Pi_{2}$ interact but non-
strongly, then

$\displaystyle\Pi_{2}$
$\displaystyle=-\sum_{a}\left\\{R_{0}-|a||x,a,Q_{x}|x_{1},P_{1},Q_{1}|\cdots|x_{m},P_{m},Q_{m}\right\\}$
(5)
$\displaystyle\;\;\;\;{}+\sum_{\ell=1}^{s_{x}-1}\sum_{a,b}\left\\{R_{0}-|a|-b-1|x,Q_{x}^{(\ell,a,b)},Q_{x}^{(\ell,+)}|x_{1},P_{1},Q_{1}|\cdots|x_{m},P_{m},Q_{m}\right\\}$
(6)
$\displaystyle\;\;\;\;{}-\sum_{\ell=1}^{s_{x}-1}\sum_{a,b}\left\\{R_{0}-|a|-b|x,Q_{x}^{(\ell,a,b)},Q_{x}^{(\ell,-)}|x_{1},P_{1},Q_{1}|\cdots|x_{m},P_{m},Q_{m}\right\\}.$
(7)

In the above equation, $a:=(a_{1},\ldots,a_{r_{x}})$,
$|a|:=a_{1}+\cdots+a_{r_{x}}$,
$Q_{x}^{(\ell,+)}:=(Q_{x,\ell+1},\ldots,Q_{x,s_{x}}),$
$Q_{x}^{(\ell,-)}:=(Q_{x,\ell+1}-1,Q_{x,\ell+2},\ldots,Q_{x,s_{x}})\mbox{ and
}Q_{x}^{(\ell,a,b)}:=(a_{1},\ldots,a_{r_{x}},Q_{x,1}+b+1,Q_{x,2},\ldots,Q_{x,\ell}).$
The summation in (5) runs over all $r_{x}$-tuples $a$ of non-negative integer
numbers satisfying $1\leq|a|\leq R_{0}$. The inner summation in (6) runs over
all $r_{x}$-tuples $a$ of non-negative integer numbers and all non-negative
integer numbers $b$ satisfying $|a|+b<R_{0}$. The inner summation in (7) is
empty if $Q_{x,\ell+1}=0$, otherwise it runs over all $r_{x}$-tuples $a$ of
non-negative integer numbers and all non-negative integer numbers $b$
satisfying $|a|+b\leq R_{0}$.

######  Example 3.8.

Let $x$ be a vertex of degree five, in a tree $T$ and assume $y$ is a vertex
of degree three that lies on $x$-direction 1. Take $n=9$, then
$\\{1|x,(2,0),(2,3)\\}\smile\\{7|y,(1),(0)\\}=\\{0|x,(0,1),(2,3)|y,(1),(0)\\}+\\{0|x,(1,0),(2,3)|y,(1),(0)\\}+\\{0|x,(0,0,3),(3)|y,(1),(0)\\}-\\{1|x,(0,0,3),(2)|y,(1),(0)\\}-\\{0|x,(0,1,3),(2)|y,(1),(0)\\}-\\{0|x,(1,0,3),(2)|y,(1),(0)\\}$.
We can visiualize these six cells in Figure 4; the three cells of the top row
have positive sign and the three cells of the bottom row have negatve sign.

Figure 4: The six 2-cells that appear in the product of Example 3.8.

The following corollary will be particularly useful in the next section.

######  Corollary 3.9.

Assume we have a product of cells $c_{0}\smile\dots\smile c_{m}$ as in Theorem
3.7 and let $c$ be a cell which appears as a summand of the product and let
$d$ be the edge-ingredient of $c_{0}$ Then if $e$ is an edge-ingredient of $c$
and is not an edge-ingredient of $c_{i}$ for $0\leq i\leq m$ then
$\iota(e)=\iota(d)$ and $\tau(e)>\tau(d).$

###### Proof.

By Theorem 3.7, since $c$ belongs to one of the three summands, and has $e$ as
an edge-ingredient, it must have one of the following forms:

  * •

$\\{R_{0}-|a|-b-1|x,Q_{x}^{(\ell,a,b)},(Q_{x,\ell+1},\ldots,Q_{x,s_{x}})|\dots\\}$

  * •

$\\{R_{0}-|a|-b|x,Q_{x}^{(\ell,a,b)},(Q_{x,\ell+1}-1,Q_{x,\ell+2},\ldots,Q_{x,s_{x}})|\dots\\}$

where $b$ is a non negative integer, $a:=(a_{1},\ldots,a_{r_{x}})$,
$|a|:=a_{1}+\cdots+a_{r_{x}}$, and
$Q_{x}^{(\ell,a,b)}:=(a_{1},\ldots,a_{r_{x}},Q_{x,1}+b+1,Q_{x,2},\ldots,Q_{x,\ell}).$
It is clear that $\iota(e)=\iota(d)$. Moreover, since the length of $Q_{x}$ is
greater than the length of $(Q_{x,\ell+1},\ldots,Q_{x,s_{x}})$ and
$(Q_{x,\ell+1}-1,Q_{x,\ell+2},\ldots,Q_{x,s_{x}})$ we must have that
$\tau(e)>\tau(d).$ ∎

###  3.1 The simplicial complex $K_{n}T$

In this section $T$ will be a binary tree, this is, a tree where every vertex
has degree one, two or three. Binary trees have a particularly nice cohomology
ring.

Let

$\langle k|x,p,q\rangle=\sum_{i=1}^{k}\\{k-i,x,p+i,q\\},$

notice that since $T$ is a binary tree, $p$ and $q$ are vectors of length one,
thus we can see them as non negative integers.

######  Definition 3.10.

Given a tree $T$, and an integer $n\geq 4$, let $K_{n}T$ denote the simplicial
complex defined as follows:

  * •

The vertices of $K_{n}T$ are the elements $\langle k|x,p,q\rangle$.

  * •

A set of $m+1$ vertices $\langle k_{1}|x_{1},p_{1},q_{1}\rangle,\dots,\langle
k_{m}|x_{m},p_{m},q_{m}\rangle$ is an $m$-simplex if the cells
$\\{k_{1}|x_{1},p_{1},q_{1}\\},\dots,\\{k_{m}|x_{m},p_{m},q_{m}\\}$ interact
strongly.

######  Example 3.11.

Consider the tree $T$ depicted in Figure 5 (left) and assume it is
sufficiently subdivided for $n=4$. Then $K_{4}T$ is the simplicial complex
obtained from the simplicial complex depicted in Figure 5 (right) by adding
twelve isolated vertices. In $K_{4}T$ the three vertices of degree one are
$\langle 2|v_{2},(1,0)\rangle,\langle 0|v_{2},(3,0)\rangle$ and $\langle
0|v_{2},(1,2)\rangle$ and the three vertices of degree one are $\langle
2|v_{3},(1,0)\rangle,\langle 2|v_{4},(1,0)\rangle$ and $\langle
0|v_{3},(3,0)\rangle$.

$v_{1}$$v_{2}$$v_{4}$$v_{3}$ Figure 5: The tree $T$ and part of the simplicial
complex $K_{4}T$.

In [8] we proved a slightly more general version of the following theorem.

######  Theorem 3.12.

[8] Assume $T$ is a binary tree. For a commutative ring $R$ with 1, the
cohomology ring $H^{\ast}(B_{n}T;R)$ is the exterior face ring
$\Lambda_{R}(K_{n}T)$ determined by the simplicial complex $K_{n}T$ .
Explicitly, $H^{\ast}(B_{n}T;R)$ is the quotient $\Lambda/I$, where $\Lambda$
is the exterior graded $R$-algebra generated by the vertex set of $K_{n}T$,
and $I$ is the ideal generated by monomials corresponding to non-faces of
$K_{n}T.$

##  4 The s-topological complexity of $U\mathcal{D}^{n}T$

In this section we are going to give conditions on $T$, depending on the value
of $n$, which assure that the higher topological complexity of
$U\mathcal{D}^{n}T$ is maximal. These conditions are related to the structure
of the tree, and the relation between the number of vertices of degree tree
and the number of vertices of degree higher than three.

Given a $1$-cell $a$, denote by $E(a)$ its unique edge-ingredient. The
following proposition is a bit technical but it will be very helpful later on.

######  Proposition 4.1.

Assume $a_{1},\dots a_{s}$ are critical $m$-cells in $U\mathcal{D}^{n}T$ with
no common edge-ingredient, and let $a_{i}=a_{i}^{1}\smile\dots\smile
a_{i}^{m}$ for $1\leq i\leq s$. Consider $b=\\{b_{1},b_{2},\dots,b_{s}\\}$,
where each $b_{i}=\prod_{k=1}^{s}(\prod_{j\in I_{i,k}}a_{i}^{j}),$ and for
each $i\in\\{1,\dots,s\\}$, $\cup_{k=1}^{s}I_{i,k}=\\{1,2,\dots,m\\}$ and
$I_{1,j}\cap I_{i,k}=\emptyset$ when $j\neq k$. Then $a_{i}$ does not appear
as a summand of $b_{i}$.

###### Proof.

In order to show that each $a_{i}$ does not appear as a summand of the product
$b_{i}$ for $i=1,\dots,s$, we are going to assume it does, and construct a
graph $G_{b}$ associated to $b$ as follows.

The vertices of $G_{b}$ are the edge-ingredients of the cells $a_{i}^{j}$,
which we shall denote by $(i,j)$. The vertices $(i,j)$, which correspond to
edge-ingredients of $a_{i}^{j}$ such that $a_{i}^{j}\in b_{i}$ (this is,
$a_{i}^{j}$ is a factor of $b_{i}$), are isolated vertices in $G_{b}$. Two
vertices $(i,j)$ and $(k,l)$ are adyacent in $G_{b}$ if
$\iota(E(a_{i}^{j}))=\iota(E(a_{k}^{l}))$.

Finally we shall give an orientation to every edge of $G_{b}$ as follows: take
$((i,j),(k,l))$ an edge of $G_{b}$, we orient it from $(i,j)$ to $(k,l)$ if
$\tau(E(a_{i}^{j})>\tau(E(a_{k}^{l}))$.

Now we will show that every non-isolated vertex in $G_{b}$ has indegree and
outdegree at least one. Recall Remark 3.9 and take a non-isolated vertex
$(i,j)$. Since $a_{i}^{j}\notin b_{i}$, there exists $k\in\\{1,\dots,s\\}$,
$k\neq i$ such that $a_{i}^{j}\in b_{k}$. Because we are assuming $a_{k}\in
b_{k}$, there exists $l$ such that $\iota(E(a_{k}^{l}))=\iota(E(a_{i}^{j}))$
and $\tau(E(a_{k}^{l}))>\tau(E(a_{i}^{j}))$. Thus $((k,l),(i,j))$ is an
oriented edge in $G_{b}$, and hence $(i,j)$ has indegree at least one. Now,
since $a_{i}^{j}\notin b_{i}$, there exist $k^{\prime},l^{\prime}$ such that
$a_{k^{\prime}}^{l^{\prime}}\in b_{i}$. This means that
$\iota(E(a_{k}^{l}))=\iota(E(a_{i}^{j}))$ and
$\tau(E(a_{i}^{j}))>\tau(E(a_{k^{\prime}}^{l^{\prime}}))$, thus
$((i,j),(k^{\prime},l^{\prime}))\in G_{b}$. In turn, this means that $(i,j)$
has outdegree at least one.

Thus every vertex in $G_{b}$ has in and out degree at least one. This implies
that $G_{b}$ contains an oriented cycle. Let
$\\{(i_{1},j_{1}),\dots,(i_{r},j_{r})\\}$ be an oriented cycle in $G_{b}$ thus
$((i_{l},j_{l}),(i_{l+1},j_{l+1}))$ and $((i_{r},j_{r}),(i_{1},j_{1}))$ are
oriented edges in $G_{b}$ for $l\in\\{1,\dots,r-1\\}$ but this means that

$\tau(E(a_{i_{1}}^{j_{1}})>\tau(E(a_{i_{2}}^{j_{2}})>\dots>\tau(E(a_{i_{r}}^{j_{r}})>\tau(E(a_{i_{1}}^{j_{1}}),$

a contradiction. ∎

######  Lemma 4.2.

Assume $a_{1},\dots a_{s}$ are critical $m$-cells of maximal dimension in
$U\mathcal{D}^{n}T$ with no common edge-ingredient. Then
$TC(U\mathcal{D}^{n}T)\geq sm$.

###### Proof.

By Theorem 3.6, the critial m-cells $a_{i}$ are the product of $m$ critical
1-cells thus $a_{i}=a_{i}^{1}\smile\dots\smile a_{i}^{m}$ for $i=1,\dots,s$.
Consider the following zero divisors: $A_{i,j}=1_{1}\otimes
1_{2}\otimes\dots\otimes 1_{i-1}\otimes a_{i}^{j}\otimes
1_{i+1}\otimes\dots\otimes 1_{s}-1_{1}\otimes 1_{2}\otimes\dots\otimes
1_{i}\otimes a_{i}^{j}\otimes 1_{i+2}\otimes\dots\otimes 1_{s}$ and
$A_{s,j}=1\otimes 1\otimes\dots\otimes 1\otimes a_{s}^{j}-a_{s}^{j}\otimes
1\otimes\dots\otimes 1$ for $1\leq j\leq m$ and $1\leq i<s$. We will show that
the product

$\prod_{i=1}^{s}(\prod_{j=1}^{m}A_{i,j})$ (8)

is non zero. Notice that (8) contains the terms $\pm a_{1}\otimes
a_{2}\otimes\dots\otimes a_{s}$ and $\pm a_{s}\otimes a_{1}\otimes\dots\otimes
a_{s-1}$. Since every cell $a_{i}$ is of maximal dimension, any product of
more than $s$ factors is zero, thus any other non-zero term which appears in
(8) is of the form

$b_{1}\otimes b_{2}\otimes\dots\otimes b_{s}\mbox{, where each
}b_{i}=\prod_{k=1}^{s}(\prod_{j\in I_{i,k}}a_{i}^{j}),$ (9)

and for each $i\in\\{1,\dots,s\\}$, $\cup_{k=1}^{s}I_{i,k}=\\{1,2,\dots,m\\}$
and $I_{1,j}\cap I_{i,k}=\emptyset$ when $j\neq k$. By Proposition 4.1,
$a_{1}\otimes\dots\otimes a_{s}$ can not appear in any term of the form
$b_{1}\otimes\dots\otimes b_{s}$, thus the product (8) is a non zero product
of $ms$ zero divisors and by Proposition 2.5, $TC_{s}(U\mathcal{D}^{n}T)\geq
ms$. ∎

Notice that if $v$ is a vertex of degree three then there exists a unique
possible critical edge inciding in $v$. Given a vertex $v$ of degree three,
the block $B(v)$ of $v$ is the set consisting of the unique possible critical
edge inciding in $v$ together with the vertex $v+1$.

######  Theorem 4.3.

Let $m$ be the amount of essential vertices and $k$ the amount of vertices of
degree three, thus $k\leq m$ in $T$. Let $n=2(m-k+l)+\varepsilon$ with
$\varepsilon\in\\{0,1\\}$ and $l\leq\lfloor\frac{k}{s}\rfloor(s-1).$ Then
$TC_{s}(U\mathcal{D}^{n}T)\geq s(m-k+l)$.

###### Proof.

We are going to exibit $s$ cells in $U\mathcal{D}^{n}T$ of maximal dimension
which satisfy the hypothesis of Lemma 4.2. Assume first that $k\geq s$.

Let $x_{1},\dots,x_{m-k}$ be the essential vertices of degree greater than
three and let $y_{1},\dots,y_{k}$ be the vertices of degree three. Assume for
now that $\varepsilon=0$. Assume that $w_{i},z_{i},u_{i}\in N(x_{i})$ for
$i=1,\dots m-k$, with $x_{i}<w_{i}<z_{i}<u_{i}$ and $k=sj+r$ with
$r\in\\{0,1,\dots,s-1\\}$.

$U_{1}=\\{B(y_{1}),\dots,B(y_{j})\\},U_{2}=\\{B(y_{j+1}),\dots,B(y_{2j})\\},\cdots,U_{s}=\\{B(y_{(s-1)j+1}),\dots,B(y_{sj})\\}$

and $U_{s+1}=\\{B(y_{sj+1}),\dots,B(y_{sj+r})\\}$, in particular, $U_{s+1}$
can be an empty set.

Let $\Lambda=\cup_{i=1}^{s}U_{i}$, and $V_{i}=\Lambda-U_{i}$ for $1\leq i\leq
s$. Notice that each $V_{i}$ has $(s-1)j\geq l$ blocks of the form $B(y_{j})$,
and that $\cap_{i=1}^{s}V_{i}=\emptyset$.

Let $W_{i}\subseteq V_{i}$ be such that $W_{i}$ contains exactly $l$ blocks of
the form $B(y_{j})$ for some $j$. Then the cells

$c_{i}=\\{(x_{1},u_{1}),z_{1},(x_{2},u_{2}),z_{2},\dots,(x_{m-k},u_{m-k}),z_{m-k},W_{i}\\}$

for $i$ even with $1<i\leq s$ and

$c_{t}=\\{(x_{1},z_{1}),w_{1},(x_{2},z_{2}),w_{2},\dots,(x_{m-k},z_{m-k}),w_{m-k},W_{t}\\}$

for $t$ odd with $1\leq t\leq s$ are $s$ cells such that there is no edge
belonging to all $s$ cells. If $\varepsilon=1$, we take
$c^{\prime}_{l}=c_{l}\cup\\{0\\}$ (where $0$ denotes the root vertex) for
$1\leq l\leq s$. Thus by Lemma 4.2, $TC_{s}(U\mathcal{D}^{n}T)\geq s(m-k+l)$.

Consider now the case when $k<s$. Take $s^{\prime}\leq k$ and construct
$c_{1},\dots,c_{s^{\prime}}$ cells as above. Then
$c_{1}^{1},c_{1}^{2},\dots,c_{1}^{s-s^{\prime}},c_{2},\dots,c_{s^{\prime}}$
are $s$ cells with no edge-ingredient in common, where $c_{1}^{l}=c_{1}$ for
$l\in\\{1,\dots,s-s^{\prime}\\}$. Thus by Lemma 4.2,
$TC_{s}(U\mathcal{D}^{n}T)\geq s(m-k+l)$. ∎

######  Corollary 4.4.

The bound obtained in Theorem 4.3 is sharp

###### Proof.

By Lemma 2.5, $TC_{s}(U\mathcal{D}^{n}T)\leq s(hdim(U\mathcal{D}^{n}T))$ and
notice that since $n=2(m-\lfloor\frac{k}{s}\rfloor+l)+\varepsilon$ with
$l\leq\lfloor\frac{k}{s}\rfloor(s-1)$, we have $n<2m$ and
$hdim(U\mathcal{D}^{n}T)=\frac{n}{2}$ thus $TC_{s}(U\mathcal{D}^{n}T)\leq
s\frac{n}{2}.$ ∎

So far, we have the case where there are many vertices of degree three in
relation to the amount of vertices of degree three. On the other hand, when
there are no vertices of degree three, thus the tree is binary, we know from
Theorem 3.12 that the cohomology ring of $U\mathcal{D}^{n}T$ is an exterior
face ring. This means that every critical $m$-cell has a unique factorization
as the product of $m$ critical 1-cells, which is particular useful if we want
to generalize lemma 4.2.

So, to combine these two results into a more general one, we shall construct a
binary tree $O(T)$ which is relatively similar to $T$ which will help us
construct zero divisors.

Given a tree $T$, we shall construct a binary tree $O(T)$ associated to $T$.
Assume for now that $T$ has no vertices of degree two. Let $x_{1},\dots,x_{m}$
be the essential vertices of $T$ and let $d_{i}$ denote $d(x_{i})-1$ and let
$\\{y_{i}^{0},\dots,y_{i}^{d_{i}}\\}$ be the set of neighbours of $x_{i}$ in
$T$.

  * •

The vertex set of $O(T)$ is

$V(O(T))=\\{v\in
V(T):d(v)=1\\}\cup\bigcup_{i=1}^{m}\\{x_{i}^{1},x_{i}^{2},\dots,x_{i}^{d_{i}-1}\\}.$

  * •

The edge set of $O(T)$ is

$E(O(T))=\bigcup_{i=1}^{m}\left(\\{(y_{i}^{0},x_{i}^{1}),(x_{i}^{d_{i}-1},y_{i}^{d_{i}}),(x_{i}^{d_{i}-1},y_{i}^{d_{i}-1})\\}\bigcup_{j=1}^{d_{i}-2}\\{(x_{i}^{j},y_{i}^{j}),(x_{i}^{j},x_{i}^{j+1})\\}\right).$

In other words, we are substituting every vertex of degree $d>3$ with a path
of length $d-2$ (see Figure 6). Notice that for every vertex of degree three
in $T$, there is a corresponding vertex in $O(T)$. Note also that $O(T)$ does
not depend on the choice of a plannar embedding of $T$, but ofcourse a plannar
embedding of $T$ leads to a plannar embedding of $O(T)$.

Figure 6: The trees $T$ and $O(T)$.

######  Lemma 4.5.

Let $T$ be a tree and consider the cells
$a_{i}=\\{k_{i}|x_{i},p_{i},q_{i}\\}\in U\mathcal{D}^{n}T$ with $d(x_{i})=3$
for $1\leq i\leq m$. With the notation introduced above, let
$b_{i}=\\{k_{i}|x_{i}^{1},p_{i},q_{i}\\}\in U\mathcal{D}^{n}O(T)$ for $1\leq
i\leq m$. Then $a_{1}\smile\dots\smile a_{m}\neq 0$ if and only if
$b_{1}\smile\dots\smile b_{m}\neq 0$. Moreover, $a_{1}\smile\dots\smile a_{m}$
is a strong interaction product if and only if $b_{1}\smile\dots\smile b_{m}$
is a strong interaction product, and if $a_{1}\smile\dots\smile
a_{m}=\\{k|x_{1},P_{1},Q_{1}|\dots|x_{m},P_{m},Q_{m}\\}$ then
$b_{1}\smile\dots\smile
b_{m}=\\{k|x_{1}^{1},P_{1},Q_{1}|\dots|x_{m}^{1},P_{m},Q_{m}\\}$.

###### Proof.

The result follows from Proposition 3.4, and the fact that the interaction
parameters with respect to the factors $a_{1},\dots,a_{m}$ and
$b_{1},\dots,b_{m}$ agree in both trees. ∎

######  Lemma 4.6.

Assume we have $ms$ critical 1-cells $a_{i}^{j}$ for $1\leq i\leq s$ and
$1\leq j\leq m$ in $U\mathcal{D}^{n}T$ with the following properties:

  * •

There exists $k\in\\{1,\dots,s\\}$ such that for every $1\leq i,l\leq s$ and
$1\leq j\leq k$, $E(a_{i}^{j})=E(a_{l}^{j})$ and $\iota(E(a_{i}^{j}))$ is a
vertex of degree three.

  * •

The product $a_{i}^{1}\smile\dots\smile a_{i}^{m}$ is a strong interaction
product for every $1\leq i\leq s$.

  * •

The $(m-k)s$ remaining edges are distinct, this is,
$\bigcap_{i=1}^{s}\bigcap_{j=k+1}^{m}E(a_{i}^{j})=\emptyset$.

  * •

For every $j\in\\{1,\dots,m\\}$, there exist $i,l$ such that $a_{i}^{j}\neq
a_{l}^{j}$.

Then $TC_{s}(U\mathcal{D}^{n}T)\geq sm$.

###### Proof.

Let $a_{i}=\langle a_{i}^{1}\rangle\smile\langle
a_{i}^{2}\rangle\smile\dots\smile\langle a_{i}^{k}\rangle\smile
a_{i}^{k+1}\smile\dots\smile a_{i}^{m}$ and let
$\Lambda_{i,j}=1_{1}\otimes\dots\otimes 1_{i-1}\otimes A_{i}^{j}\otimes
1_{i+1}\otimes\dots\otimes 1_{s}-1_{1}\otimes\dots\otimes 1_{i}\otimes
A_{i}^{j}\otimes 1_{i+2}\otimes\dots\otimes 1_{s}$ for $1\leq i\leq s-1$ and
$\Lambda_{s,j}=1\otimes\dots\otimes 1\otimes a_{s}^{j}-a_{s}^{j}\otimes
1\dots\otimes 1$, where
$A_{i}^{j}=\left\\{\begin{array}[]{rcl}a_{i}^{j}&\mbox{if}&j>k\\\ \langle
a_{i}^{j}\rangle&\mbox{if}&j\leq k\end{array}\right.$

We will show that the product $\prod_{i=1}^{s}\prod_{j=1}^{m}\Lambda_{i,j}$ is
non zero. Notice that this product contains the term $\pm a_{1}\otimes
a_{2}\otimes\dots\otimes a_{s}\pm a_{s}\otimes a_{1}\otimes\dots\otimes
a_{s-1}$. Let $a_{i}=c_{i}\smile d_{i}$ where $c_{i}=\langle
a_{i}^{1}\rangle\smile\langle a_{i}^{2}\rangle\smile\dots\smile\langle
a_{i}^{k}\rangle$ and $d_{i}=a_{i}^{k+1}\smile\dots\smile a_{i}^{m}$. By Lemma
4.5 and Theorem 3.12 each cell $c_{i}$ has a unique factorization and thus can
not be created using different factors. This means that any term
$b=b_{1}\otimes\dots\otimes b_{s}$ as in (9) containing the term $\pm
a_{1}\otimes\dots\otimes a_{s}$ must be such that each $b_{i}$ contains the
term $c_{i}$ as a factor, otherwise we would obtain an other factorization of
$c_{i}$ which is impossible. Thus $b_{i}=c_{i}\smile g_{i}$ for some $g_{i}$.
This means that $d_{1}\otimes\dots\otimes d_{s}$ appears as a term of the
product $g_{1}\otimes\dots\otimes g_{s}$ which, by Proposition 4.1 is
impossible. ∎

In what remains of this section we shall assume $T$ is a tree with $m$
essential vertices and $k$ vertices of degree three thus $k\leq m$.

For a vertex $x\in V(T)$ let $C_{j}(x)$ be the connected components of
$T-\\{x\\}$ for $j=0,1,\dots,d(x)-1$.

######  Theorem 4.7.

Let $n=2(m-\lfloor\frac{k}{s}\rfloor+l)+\varepsilon$ with
$l<\lceil\frac{k}{s}\rceil$ and $\varepsilon\in\\{0,1\\}$. Assume there exists
a set $V$ of $l$ vertices having degree three such that:

  * •

The remaining $k-l$ vertices of degree three can be separated into $s$ sets
$U_{1},\dots,U_{s}$ with $\bigcap_{i=1}^{s}U_{i}=\emptyset$ where each set
$U_{i}$ has cardinality $\lfloor\frac{(s-1)k}{s}\rfloor$ for $1\leq i\leq s$.

  * •

For every $y\in V$ there exists at least one $j\in\\{0,1,2\\}$ and at least
two indices $i_{1},i_{2}\in\\{1,2,\dots,s\\}$ such that $|C_{j}(y)\cap
U_{i_{1}}|\neq|C_{j}(y)\cap U_{i_{2}}|$.

Then $TC_{s}(U\mathcal{D}^{n}T)\geq s(m-\lfloor\frac{k}{s}\rfloor+l)$.

###### Proof.

Assume first that $\varepsilon=0$. Let $x_{1},\dots x_{m-k}$ be the essential
vertices of degree greater than three and let $y_{1},\dots,y_{k}$ be the
vertices of degree exactly three. Let $B(U_{i})=\\{B(u):u\in U_{i}\\}$ and
$B(V)=\\{B(v):v\in V\\}$ for $1\leq i\leq s$. Assume that
$w_{i},z_{i},v_{i}\in N(x_{i})$ for $i=1,\dots,m-k$, with
$x_{i}<w_{i}<z_{i}<v_{i}$.

Then

$c_{i}=\\{(x_{1},v_{1}),z_{1},(x_{2},v_{2}),z_{2},\dots,(x_{m-k},v_{m-k}),z_{m-k},B(V),B(U_{i})\\}$

for $i$ even with $1<i\leq s$ and

$c_{j}=\\{(x_{1},z_{1}),w_{1},(x_{2},z_{2}),w_{2},\dots,(x_{m-k},z_{m-k}),w_{m-k},B(V),B(U_{j})\\}$

for $j$ odd with $1\leq j\leq s$, are $s$ cells of dimension $m$. If
$\varepsilon=1$ we take the cells $c^{\prime}_{l}=c_{l}\cup\\{0\\}$ for $1\leq
l\leq s$.

By Theorem 3.6, each cell $c_{i}$ is the strong interacion product of $m$
1-cells $a_{i}^{1},\dots,a_{i}^{m}$, where each factor is as described in the
discussion following Theorem 3.6. Let $a_{i}^{j}$ be the factor which contains
the edge-ingredient $(x_{j},v_{j})$ or $(x_{j},z_{j})$ (if $i$ is even or odd
respectively) for $1\leq j\leq m-k$, and let
$a_{i}^{m-k+1},\dots,a_{i}^{m-k+l}$ be the factors which contain an edge-
ingredient inciding in a vertex of $V$, and $a_{i}^{m-k+l+1},\dots,a_{i}^{m}$
be the factors which contain an edge-ingredient inciding in a vertex of
$U_{i}$ for $1\leq i\leq s$.

Notice first that for $j\in\\{m-k+1,\dots,m-k+l\\}$ and
$i,g\in\\{1,\dots,s\\}$ we have that $E(a_{i}^{j})=E(a_{g}^{j})$ and
$\iota(E(a_{i}^{j}))\in V$.

Now, since
$\bigcap_{i=1}^{s}\bigcap_{j=1}^{m-k}E(a_{i}^{j})=\bigcap_{i=1}^{s}(x_{i},v_{i})\cap(x_{i},z_{i})=\emptyset,$
and $\bigcap_{i=1}^{s}U_{i}=\emptyset$, we have that

$\bigcap_{i=1}^{s}\bigcap_{\begin{subarray}{c}j\leq m-k,\\\
j>m-k+l\end{subarray}}^{m}E(a_{i}^{j})=\emptyset.$

Finally, for $v\in V$ there exists $g\in\\{0,1,2\\}$ and
$i,l\in\\{1,\dots,s\\}$ such that $|C_{g}(v)\cap U_{i}|\neq|C_{g}(v)\cap
U_{l}|$ thus $a_{l}^{j}\neq a_{i}^{j}$ where $v=\iota(E(a_{i}^{j}))$.

This means that the factors $a_{i}^{1},\dots,a_{i}^{m}$ satisfy the hypothesis
of Lemma 4.6 for $1\leq i\leq s$. ∎

######  Corollary 4.8.

The bound obtained in Theorem 4.7 is sharp

###### Proof.

By Lemma 2.5, $TC_{s}(U\mathcal{D}^{n}T)\leq s(hdim(U\mathcal{D}^{n}T))$ and
notice that since $n=2(m-\lfloor\frac{k}{s}\rfloor+l)+\varepsilon$ with
$l<\lceil\frac{k}{s}\rceil$, we have $n<2m$ and
$hdim(U\mathcal{D}^{n}T)=\frac{n}{2}$ thus $TC_{s}(U\mathcal{D}^{n}T)\leq
s\frac{n}{2}.$ ∎

######  Example 4.9.

Take the tree $T$ of Figure 7 and assume every edge is sufficiently subdivided
for $n=14$. Since $m=8$, $k=7$, $l=1$ and $s=3$, we can see in Figure 7 the
set $V$ consisting of the black vertex, the set $U_{1}\cap U_{2}$ consisting
of light gray vertices, the set $U_{2}\cap U_{3}$ consisting of gray vertices
and the set $U_{3}\cap U_{1}$ consisting of dark gray vertices. By Theorem
4.7, $TC_{3}(U\mathcal{D}^{14}T)\geq 3(8-2+1)=21$.

Figure 7: The tree $T$ and a colouring of the vertices of $F(T)$.

Let $F(T)$ denote the tree obtained from $T$ by removing all leaves and
smoothing all bivalent vertices.

######  Definition 4.10.

Given a tree $T$, let $h_{s}(T)$ denote the minimal integer such that there
exist $s$ sets consisting of vertices which have degree three,
$V_{1},\dots,V_{s}$ such that:

  * •

For every set $|V_{i}|\leq h_{s}(T)$ for $1\leq i\leq s$.

  * •

Every vertex that has degree one in $F(T)$ and degree three in $T$ belongs to
a set $V_{i}$ with $1\leq i\leq s$.

  * •

For every vertex $x$ of degree greater than one in $F(T)$ and degree three in
$T$, there exists $j\leq d(x)-1$ and at least two indices $i_{1},i_{2}$ such
that

$|C_{j}(x)\cap V_{i_{1}}|\neq|C_{j}(x)\cap V_{i_{2}}|.$

Let $V$ be the set of vertices that have degree three in $T$ and degree one in
$F(T)$. Notice that $h_{s}(T)$ always exists, since we can put $V_{i}=V$ for
$i=1,\dots,s-1$ and $V_{s}=\emptyset$ so that for every essential vertex $x$
in $F(T)$ having degree three in $T$, we have that there exists $j$ such that
$0=|C_{j}(x)\cap V_{s}|\neq|C_{j}(v)\cap V_{i}|$ for some $1\leq i<s$.
Obviously this process is not optimal, since in this case the sets $V_{i}=V$
are very large.

######  Theorem 4.11.

Let $n\geq 2m+h_{s}(T)$. Then $TC_{s}(U\mathcal{D}^{n}T)\geq sm$.

###### Proof.

Assume first that $n=2m+h_{s}(T)$. Let $x_{1},\dots,x_{m-k}$ be the vertices
of degree greater than three and let $y_{1},\dots,y_{k}$ be the vertices of
degree three. Assume that $w_{i},z_{i},v_{i}\in N(x_{i})$ for $i=1,\dots m-k$,
with $x_{i}<w_{i}<z_{i}<v_{i}$. Let $U_{i}=\\{y_{i}+2:y_{i}\in V_{i}\\}$ for
$1\leq i\leq s$.

Then

$c_{i}=\\{(x_{1},v_{1}),z_{1},(x_{2},v_{2}),z_{2},\dots,(x_{m-k},v_{m-k}),z_{m-k},B(y_{1}),\dots,B(y_{k}),U_{i}\\}$

for $i$ even with $1<i\leq s$ and

$c_{j}=\\{(x_{1},z_{1}),w_{1},(x_{2},z_{2}),w_{2},\dots,(x_{m-k},z_{m-k}),w_{m-k},B(y_{1}),\dots,B(y_{k}),U_{j}\\}$

for $j$ odd with $1\leq j\leq s$ are $s$ m-cells. If for some $1\leq i\leq s$
we have that $|V_{i}|<h_{s}(T)$ then we can add to the cell $c_{i}$, vertices
blocked at the origin. By Theorem 3.6 every cell $c_{i}$ for $1\leq i\leq s$
is the strong interaction product of $m$ 1-cells $a_{i}^{1},\dots,a_{i}^{m}$.
Let $a_{i}^{j}$ be the factor which contains the edge-ingredient
$(x_{j},v_{j})$ or $(x_{j},z_{j})$ (if $i$ is even or odd respectively) for
$1\leq j\leq m-k$, and let $a_{i}^{l+m-k}$ be the factor which contains
$B(y_{l})$ for $1\leq l\leq k$

We have that $E(a_{i}^{j})=E(a_{l}^{j})$ for $m-k<j\leq m$ and
$\iota(E(a_{i}^{j}))=y_{j}$ with $y_{j}$ a vertex of degree three. Notice also
that

$\bigcap_{i=1}^{s}\bigcap_{j=1}^{m-k}E(a_{i}^{j})=\bigcap_{i=1}^{s}(x_{i},v_{i})\cap(x_{i},z_{i})=\emptyset$

.

Finally consider the cells $a_{i}^{j}$ for $1\leq i\leq s$ which contain
$B(y_{j})$. Since $y_{j}$ is a vertex of degree three, there exist
$i,l\in\\{1,\dots,s\\}$ and $g\in\\{0,1,2\\}$ such that $|C_{g}(y_{j})\cap
V_{i}|\neq|C_{g}(y_{j})\cap V_{l}|$ thus $a_{i}^{j}\neq a_{l}^{j}$.

Thus the factors $a_{i}^{1},\dots,a_{i}^{m}$ satisfy the hypotheisis of Lemma
4.6 $1\leq i\leq s$ and hence $TC_{s}(U\mathcal{D}^{n}T)\geq sm$.

If $n>2m+h_{s}(T)$ we can add to every cell $c_{i}\in
U\mathcal{D}^{2m+h_{s}(T)}T$, $n-(2m+h_{s}(T))$ blocked vertices at the origin
to obtain $c^{\prime}_{i}\in U\mathcal{D}^{n}T.$ ∎

######  Corollary 4.12.

The bound in Theorem 4.11 is sharp.

###### Proof.

By Lemma 2.5, $TC_{s}(U\mathcal{D}^{n}T)\leq s(hdim(U\mathcal{D}^{n}T))$ and
notice that since $n\geq 2m+h_{s}(T)$, $hdim(U\mathcal{D}^{n}T)=m$ thus
$TC_{s}(U\mathcal{D}^{n}T)\leq sm.$ ∎

##  5 Comparison with Schreirer’s results

In this section we are going to compare our results with schreirer’s results
for the case when $s=2$. Since he uses very different tools, we must first
introduce some definitions and notation. We shall continue to assume that our
tree $T$ is sufficiently subdivided (unless otherwise stated) and embedded in
the plane. Recall that an arc in $T$ is a subspace homeomorphic to a non-
trivial closed interval. Given a finite collection of oriented arcs
$\\{A_{i}\\}^{k}{i=1}\in T$, and a vertex $v\in T$ of degree $d$, we will
define integers $\eta_{0}(v),\eta_{1}(v),\dots,\eta_{d-1}(v)$ as follows.
First for $i=1,2,\dots k$ and $j=1,2,\dots,d-1$, if $v$ lies on the arc
$A_{i}$ and $A_{i}$ intersects the interior of the edge $e_{j}$ incident to
$v$ on $v$-direction $j$, then $\eta_{j,i}(v)=1$ if $A_{i}$ is oriented
towards $v$ on $e_{j}$ and $\eta_{j,i}(v)=-1$ if $A_{i}$ is oriented away from
$v$ on $e_{j}$. If $v$ does not fall on $A_{i}$ or $A_{i}$ does not intersect
the interior of $e_{j}$ then $\eta_{j,i}(v)=0$. Then let

$\eta_{j}(v)=\sum_{i=1}^{k}\eta_{j,i}(v).$

We are now ready for the definition of an allowable collection of arcs.

######  Definition 5.1.

Let $A=\\{A_{i}\\}_{i=1}^{k}$ be a collection of oriented arcs in $T$ and $U$
be a set of vertices of $T$. The collection $A$ is said to be allowable for
$U$ if every vertex $v\in U$ of degree $d$ has the property that $v$ is not an
endpoint of any $A_{i}$ and at least one of
$\eta_{0}(v),\eta_{1}(v),\dots,\eta_{d-1}(v)$ is non zero.

Schreirer states the following theorem.

######  Theorem 5.2.

[10] Let $T$ be a tree with $m$ essential vertices.

  1. 1.

Let $p$ be the smallest integer such that there is a collection of oriented
arcs $\\{A_{i}\\}_{i=1}^{p}$ which is allowable for the collection of all
vertices of degree 3 in $T$. If there are no vertices of degree three, let
$p=0$. Let $n\geq 2m+p$ be an integer. Then $TC(U\mathcal{D}^{n}(T))=2m$

  2. 2.

Let $n=2q+\epsilon<2m$, with $\epsilon\in\\{0,1\\}$ and $q\geq 1$, let $(m-k)$
be the number of vertices of degree greater than 3, and let $k$ be the number
of vertices of degree three. Suppose one of these hold:

     * (a)

$k\geq 2(q-(m-k))$

     * (b)

       1. (i)

$k<2(q-(m-k)),\epsilon=0$, and there is some $p\geq 1$ such that there exists
a collection of oriented arcs $\\{A_{i}\\}_{i=1}^{p}$ with the following
properties:

          * (A)

The endpoints of each $A_{l}$ are (distinct) essential vertices, neither of
which is an endpoint of any other $A_{l}^{\prime}$,

          * (B)

There are $r\leq m-k$ vertices of degree greater than 3 which are not the
endpoints of any $A_{l}$,

          * (C)

There is a collection $U$ of vertices of degree 3-vertices, with $|U|\geq
q-r-p$ such that $\\{A_{i}\\}_{i=1}^{p}$ is allowable for $U$.

       2. (ii)

$k<2(q-(m-k)),\epsilon=1$, and there is an arc $A_{0}$ whose endpoints have no
restrictions and whose interior includes a collection $W^{\prime}$ of
$s^{\prime}\leq q$ distinct vertices of degree 3, and if $s<q-(m-k)$ there are
arcs $A_{1},\dots,A_{p}$, as above whose endpoints are also not vertices in
$W^{\prime}$, and there is an other collection of degree-3 vertices, $W$, such
that $W\cap W^{\prime}=\emptyset,|W|\geq q-r-p-s$ and $\\{A_{i}\\}_{i=1}^{p}$
is allowable for $W$, where $r$ is as above.

Then $TC(U\mathcal{D}^{n}T)=2q$.

We are going to focus first on case $2(a)$ and compare it to Theorem 4.3.
Notice first that in Theorem 4.3, we require that $n=2(m-k+l)+\epsilon$ where
$k$ is the amount of vertices of degree three, $m-k$ is the amount of vertices
of degree greater than three and $l\leq\frac{k}{2}$. Subsituting the
hypothesis of Theorem 4.3 $(q=m-k+l)$ in the innequality $k\geq 2(q-(m-k))$ of
Theorem 5.2 $2(a)$, we obtain $k\geq 2l$, thus both Theorem 4.3 and Theorem
5.2 $2(a)$ require the same conditions over $n$ with respect to the amount of
vertices of degree three and the amount of vertices of degree greater than
three. Since both theorems do not have any aditional hypotheisis, we conclude
that they are equivalent.

Consider now case $(1)$ of Theorem 5.2. We are going to show that it is
equivalent to Theorem 4.11. We need to prove that the smallest amount of
oriented arcs which are allowable for the set of degree-3 vertices is
precisely $h_{2}(T)$.

######  Proposition 5.3.

Let $p$ be the smallest integer such that there is a collection of oriented
arcs $\\{A_{i}\\}_{i=1}^{p}$ which is allowable for the collection of all
vertices of degree 3 in $T$. Then $p=h_{2}(T)$.

###### Proof.

Assume first that the hypothesis of Theorem 4.11 hold. Let $U$ be the set of
vertices of degree three in $T$. There exist $V_{1},V_{2}\subset U$ such that
$|V_{i}|=h_{2}(T)$ for $i=1,2$ and all the leaves of $F(T)$ are contained in
$V_{1}\cup V_{2}$. Assume $V_{1}=\\{x_{1},\dots,x_{h_{2}(T)}\\}$ and
$V_{2}=\\{y_{1},\dots,y_{h_{2}(T)}\\}$, and let $Z_{i}$ be the unique
$x_{i}y_{i}$-path in $T$. Denote by $d_{F(T)}(v)$ the degree of a vertex $v$
in $F(T)$. We are going to extend these paths as follows, for $1\leq i\leq
h_{2}(T)$. To make the notation easier, we will assume for now that the tree
is not subdivided, this is, it has no vertices of degree two. If
$d_{F(T)}(x_{i})<3$ , let $a_{i}$ denote a leaf in $T$ adjacent to $x_{i}$,
and similarly, if $d_{F(T)}(y_{i})<3$, let $b_{i}$ denote a leaf in $T$
adjacent to $y_{i}$. If $x_{i}$ is an essential vertex in $F(T)$, let $G_{i}$
be a path with endpoints $x_{i}$ and $g_{i}$ with $g_{i}$ either a leaf in $T$
or a vertex of degree greater than three in $T$ such that $g_{i}\neq
a_{j},b_{j}$ for $j\neq i$. If $y_{i}$ is an essential vertex in $F(T)$, let
$D_{i}$ be a path with endpoints $y_{i}$ and $d_{i}$ with $d_{i}$ either a
leaf in $T$ or a vertex of degree greater than three in $T$ such that
$d_{i}\neq a_{j},b_{j}$ for $i\neq j$. Then we define the set of oriented arcs
as follows:

$A_{i}=\left\\{\begin{array}[]{ccc}(a_{i},x_{i})\cup
Z_{i}\cup(y_{i},b_{i})&\mbox{ if
}&d_{F(T)}(x_{i}),d_{F(T)}(y_{i})\in\\{1,2\\}\\\ (a_{i},x_{i})\cup Z_{i}\cup
D_{i}&\mbox{ if }&d_{F(T)}(x_{i})<3,d_{F(T)}(y_{i})\geq 3\\\ G_{i}\cup
Z_{i}\cup(y_{i},b_{i})&\mbox{ if }&d_{F(T)}(x_{i})\geq 3,d_{F(T)}(y_{i})<3\\\
G_{i}\cup Z_{i}\cup D_{i}&\mbox{ if }&d_{F(T)}(x_{i})\geq
3,d_{F(T)}(y_{i})\geq 3\\\ \end{array}\right.$

The orientation of these arcs is from $a_{i}$ or $g_{i}$ to $b_{i}$ or
$d_{i}$. Notice that if $x_{i}$ is such that $d_{F(T)}(x_{i})<3$ and
$(x_{i},a_{i})=e_{j}$ for some $j\in\\{0,\dots,d_{T}(x_{i})-1\\}$ then
$\eta_{j}(x_{i})=1$ and analogusly we have that $\eta_{j}(y_{i})=-1$ if
$d_{F(T)}(y_{i})<3$. For $v\in U$ an essential vertex of $F(T)$, by the
definition of $h_{2}(T)$ there exists $j\in\\{0,1,2\\}$ such that
$|C_{j}(x)\cap V_{1}|\neq|C_{j}(x)\cap V_{2}|$ thus $\eta_{j}(v)\neq 0$. This
means that the set of oriented arcs $\\{A_{i}\\}_{i=i}^{h_{2}(T)}$ is
allowable for $U$ and $p\leq h_{2}(T)$.

Now assume there exists an allowable collection of arcs
$\\{A_{i}\\}_{i=1}^{p}$ for $U$. We are going to trim every arc just enough so
that its end points are now vertices of degree three $x_{i}$ and $y_{i}$. Let
$V_{1}=\\{x_{1},\dots,x_{p}\\}$ and $V_{2}=\\{y_{1},\dots,y_{p}\\}$. Since
every vertex of $U$ belonged to at least one arc $A_{i}$, the leaves of $F(T)$
must be endpoins of the trimmed arcs, thus belong to $V_{1}$ or $V_{2}$.
Finally consider $v\in U$ an essential vertex of $F(T)$. If $|C_{j}(v)\cap
V_{1}|=|C_{j}(v)\cap V_{2}|$ for every $j\in\\{0,1,2\\}$ then $\eta_{j}(v)=0$
for $j=0,1,2$ which is a contradiction (see for example Figure 8). Thus
$h_{2}(T)\leq p$.

$x_{1}$$y_{3}$$y_{2}$$x_{3}$$y_{1}$$x_{2}$$v$ Figure 8: An example of the
contradiction in the proof of Proposition 5.3

∎

This means that Theorem 4.11 and Theorem 5.2 (1) are equivalent. Thus we only
have one case remaining.

######  Proposition 5.4.

The hypothesis of Theorem 4.7 imply the hypothesis of Theorem 5.2 (2b).

###### Proof.

Assume first that $\epsilon=0$. Let
$l^{\prime}=\lfloor\frac{k}{2}\rfloor-l>0$, since $l>0$ we have
$\lfloor\frac{k}{2}\rfloor-l<\lfloor\frac{k}{2}\rfloor$ thus
$l^{\prime}<\frac{k}{2}$ and $2q=2m-2l^{\prime}>2m-k$ which means that
$k>2m-2q$ and therefore $k=-k+2k<2q-2m+2k=2(q-(m-k))$.

We know there are $U_{1}$ and $U_{2}$ two sets of vertices of degree three
such that $|U_{i}|=\lfloor\frac{k}{2}\rfloor=p$ and a set $V$ of $l$ vertices
of degree three, disjoint from $U_{1}$ and $U_{2}$. Let
$U_{1}=\\{x_{1},\dots,x_{p}\\}$ and $U_{2}=\\{y_{1},\dots,y_{p}\\}$. We are
going to construct arcs in a way similar to the proof of 5.3, but this time we
do want the vertices of $U_{1}$ and $U_{2}$ to be endpoints of the arcs as
long as they are distinct.

Consider, for every $i\in\\{1,\dots,p\\}$, the unique $x_{i},y_{i}$-path in
$T$. Since in $U_{1}\cup U_{2}$ there are only $k-l$ distinct vertices, we
must extend $l$ paths (or less paths if we extend some paths on both sides) to
a vertex of degree higher than tree to obtain the arcs $\\{A_{i}\\}_{i=1}^{p}$
such that they have disctinct essential vertices as endpoints. Then
$\\{A_{i}\\}_{i=1}^{p}$ is allowable for the set $V$ of $l$ vertices of degree
three, and the amount of vertices of degree higher than three which are not an
endpoint of an arc is $r=m-k-l$ thus
$q-r-p=m-\lfloor\frac{k}{2}\rfloor+l-(m-k-l)-\lfloor\frac{k}{2}\rfloor=k-2\lfloor\frac{k}{2}\rfloor\leq
l$. This means that the hypothesis of Theorem 5.2 (2a) hold. ∎

In conclusion, a generalization of Schreirer’s results for $TC_{s}$ in a more
geometric way, would be to cover the set of vertices of degree three, with an
”allowable” collection of $s$-stars instead of arcs, where an $s$-star is a
subdivision of the complete bipartite graph $K_{1,s}$. The problem of this, is
that we can not give the stars an orientation like the arcs and therefore
canot define the numbers $\eta_{j}.$

######  Example 5.5.

Recall the tree $T$ from Figure 7. Then for $s=3$ we can cover it with the
three 3-stars of Figure 9.

Figure 9: The tree $3$-stars covering the tree from Example 4.9.

## References

  * [1] Aaron David Abrams. Configuration spaces and braid groups of graphs. ProQuest LLC, Ann Arbor, MI, 2000\. Thesis (Ph.D.)–University of California, Berkeley.
  * [2] Jorge Aguilar-Guzmán, Jesús González, and Teresa Hoekstra-Mendoza, Farley-Sabalka’s Morse-theory model and the higher topological complexity of ordered configuration spaces on trees, Discrete Comput. Geom. 67 (2022), no 1, 258-286
  * [3] Ibai Basabe, Jesús González, Yuli B. Rudyak y Dai Tamaki, Higher topological complexity and its symmetrization, Algebraic and Geometric Topology. 14 (2014), no. 4, 2103–2124.
  * [4] Michael Farber, Topological Complexity of Motion Planning. Discrete Comput Geom 29, 211–221 (2003)
  * [5] Daniel Farley, and Lucas Sabalka, Discrete Morse theory and graph braid groups, Algebr. Geom. 5 (2005), 1075–1109.
  * [6] Daniel Farley, Homology of tree braid groups, Topological and asymptotic aspects of group theory, Contemp. Math. 394 (2006), 101–112.
  * [7] Robin Forman, Discrete Morse theory and the cohomology ring. Trans. Amer. Math. Soc., 354(12):5063–5085, 2002.
  * [8] Jesús González, Teresa Hoekstra-Mendoza, Cohomology ring of tree braid groups and exterior face rings, Transactions of the American Mathematical Society (to appear)
  * [9] Tomasz Kaczynski and Marian Mrozek, The cubical cohomology ring: an algorithmic approach. Found. Comput. Math., 13(5):789–818, 2013.
  * [10] Steven Scheirer, Topological complexity of $n$ points on a tree, Algebraic and Geometric Topology 18(2) (2016)


# Harmonic generation with topological edge states and electron-electron
interaction

S. Pooyan  D. Bauer  Institute of Physics, Rostock University, 18051 Rostock,
Germany

(August 28, 2024)

###### Abstract

It has been found previously that the presence or absence of topological edge
states in the Su-Schrieffer-Heeger (SSH) model has a huge impact on harmonic
generation spectra. More specifically, the yield of harmonics for harmonic
orders that correspond to photon energies below the band gap is many orders of
magnitude different in the trivial and topological phase. It is shown in this
work that this effect is still present if electron-electron interaction is
taken into account, i.e., if a Hubbard term is added to the SSH Hamiltonian.
To that end, finite SSH-Hubbard chains at half filling are considered that are
short enough to be accessible to exact diagonalization but already showing
edge states in the topological phase. We show that the huge difference in the
harmonic yield between the trivial and the topological phase can be reproduced
with few-level models employing only the many-body ground state and a few
excited many-body states.

##  I Introduction

Condensed-matter high-harmonic spectroscopy stands as a burgeoning field in
strong-field science with ultrashort laser pulses. This technique facilitates
the all-optical, ultrafast examination of both structural and dynamic
properties of materials [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].
Research efforts in condensed matter physics have focused on topological
phases, with a specific emphasis on areas such as topological insulators [16,
17, 18, 19], topological superconductors [20, 21], photonic topological
insulators [22, 23, 24], and topological circuits [25, 26]. It was only
recently that both theoretical investigations [1, 2, 27, 28, 29] and
experimental studies [30, 31] initiated an exploration into the physics
occurring at the intersection of strong-field high-harmonic generation (HHG)
and topological condensed matter physics. Although clear spectral features in
HHG from bulk that unambiguously would pinpoint topological properties are not
yet found [32] it is worthwhile to examine the explicit effects of topological
edge states on HHG (which are not accessible to bulk simulations).

HHG in interacting systems have garnered increasing interest. Already 20 years
ago, Baldea et al. [33] explored HHG in a hexagonal quantum-dot ring using the
Pariser-Parr-Pople model, incorporating Hubbard-onsite and next-nearest
neighbor interactions. Their findings indicated that such a system could
produce higher harmonic intensities compared to natural benzene, highlighting
the potential of engineered quantum structures in enhancing HHG efficiency.
More recently, Silva et al. [34] conducted a theoretical study on HHG
spectroscopy of light-induced Mott transitions within the Fermi-Hubbard model.
Their work demonstrated the feasibility of achieving high time resolution,
which is crucial for studying ultrafast dynamics in correlated materials.
Murakami et al. [35] employed the Hubbard model, including coupling to an
environment, to describe HHG in a Mott insulator. They focused on the roles of
doublons and holons, providing insights into HHG in highly correlated
materials. In another work, Murakami et al. [36] investigated HHG due to
doublon-holon recombination. They developed a three-step model for doublon-
holon pairs and showed that spin dynamics could significantly influence HHG
efficiency, indicating the sensitivity of HHG to spin dynamics in Mott
systems. Tancogne-Dejean et al. [37] investigated the changes in the Hubbard
$U$ parameter under laser excitation using density functional theory
simulations. They demonstrated how laser fields could be used to tune material
properties and drive phase transitions, specifically in NiO. Lysne et al. [38]
extended the analysis to more complex systems, incorporating dynamical mean-
field theory to account for coupling to bosons or local two-orbital models
with Hubbard interaction and Hund coupling. This approach allowed for a more
nuanced understanding of HHG in correlated electron systems. Imai et al. [39]
explored HHG in a spinless-fermion model on a dimer lattice, which can be
mapped to an Ising model at low energies. They interpreted HHG in terms of
recombination of kink-antikink excitations, providing a novel perspective on
the underlying mechanisms. Avchyan et al. [40] used an extended Hubbard model
with longer-range interactions treated within a phenomenological Hartree-Fock
approximation to study two-color HHG in graphene quantum dots, emphasizing the
effects of interaction range and system geometry on HHG. Hansen and colleagues
[41] examined the effect of electron correlation and finite system size on HHG
using a one-band Fermi-Hubbard model. They found that lower-order harmonics
are mainly influenced by finite-size effects, while higher orders are more
affected by electron correlation. In a subsequent study [42] they explored the
impact of doping on HHG, analyzing various Hubbard interaction parameter
values. They interpreted the results in terms of doublon-holon pairs, shedding
light on how different filling levels affect HHG. Valmispild et al. [43]
utilized sub-cycle spectroscopy to investigate highly correlated materials.
They employed a non-equilibrium extension of dynamical mean-field theory and
analyzed the one-particle Keldysh Green’s function, demonstrating the
potential of manipulating strongly-correlated materials with non-resonant
light fields.

In Refs. [1, 2], a huge difference in the harmonic spectra for the trivial and
the topological phase of finite SSH chains was observed. The origin of that
difference in the harmonics yield for photon energies below the (bulk) band
gap could be traced back to the presence of two edge states of which only one
is populated. This result was obtained both for a time-dependent density-
functional theory (TDDFT) treatment [1] and with the simpler tight-binding
description [1, 2] of SSH chains. In both papers very long chains could be
treated because electron-electron (e-e) interaction was neglected in the
tight-binding treatment in [2], and the auxiliary Kohn-Sham particles of TDDFT
used in [1], by construction, interact through an effective potential only.

In this work, we will incorporate a short-range Hubbard interaction and solve
the model for the finite SSH-Hubbard system by exact numerical
diagonalization. As a consequence, we have to restrict ourselves to rather
short chains. However, we will see that clear precursors of the topological
edge states known from long chains without e-e interaction appear already in
short chains with (not too strong) interaction. We find that the huge
difference in the harmonic yield between the trivial and the topological phase
survives modest e-e interaction. For stronger e-e interaction, HHG becomes
inefficient in both phases. Moreover, we find that most of the computational
cost needs to be spent on the field-free electronic structure of the
interacting electron system while the propagation in the laser field is very
cheap. This is because the relevant many-electron states that take part in HHG
are only a small fraction of the total number of states. In fact, the first
harmonic plateau can be calculated accurately with surprisingly few many-body
states.

We want to emphasize that this is not a study of HHG in bulk but takes the
presence of (many-body) edge or surface states self-consistently into account
because the laser will inevitably “see” these states when impinging on the
target. Whether these edge or surface states can be called “topological” in
the interacting case or not is an interesting question that goes well beyond
the specific topic of this work.

The paper is structured as follows. In Sec. II, a brief introduction to the
SSH model with Hubbard term and its coupling to an external field is provided.
Harmonic spectra for both topological and trivial cases for twelve sites at
half filling are presented in Sec. III. In Secs. III.1 and III.2, the
influence of the Hubbard interaction on HHG is studied, and the sufficiency of
a few many-electron states for the time-propagation is demonstrated. In Sec.
III.3, the dominant configurations in the lowest-lying, relevant many-body
states are discussed. Section IV concludes the work and provides an outlook.

##  II Model

Consider a bi-partite chain with interacting spin-1/2 particles, e.g.,
electrons, on it. The corresponding tight-binding Hamiltonian reads

$\displaystyle H_{0}$
$\displaystyle=-v\sum_{i\sigma}(c^{\dagger}_{i1\sigma}c_{i2\sigma}+c^{\dagger}_{i2\sigma}c_{i1\sigma})$
$\displaystyle\quad-w\sum_{i\sigma}(c^{\dagger}_{i+1,1\sigma}c_{i2\sigma}+c^{\dagger}_{i2\sigma}c_{i+1,1\sigma})$
$\displaystyle\quad+\frac{U}{2}\sum_{im\sigma\sigma^{\prime}}c^{\dagger}_{im\sigma}c^{\dagger}_{im\sigma^{\prime}}c_{im\sigma^{\prime}}c_{im\sigma}.$
(1)

Here, we use the usual notation $\sigma=\uparrow,\downarrow$ for a spin,
$i=1,2,3,\ldots$ labels the unit cells, and $m=1,2$ the sites within a unit
cell. The operators $c_{im\sigma}$ and $c^{\dagger}_{im\sigma}$ are fermionic
annihilation and creation operators, respectively, fulfilling the usual anti-
commutator relations
$\\{c_{im\sigma},c^{\dagger}_{i^{\prime}m^{\prime}\sigma^{\prime}}\\}=\delta_{ii^{\prime}}\delta_{mm^{\prime}}\delta_{\sigma\sigma^{\prime}}$
and
$\\{c_{im\sigma},c_{i^{\prime}m^{\prime}\sigma^{\prime}}\\}=\\{c^{\dagger}_{im\sigma},c^{\dagger}_{i^{\prime}m^{\prime}\sigma^{\prime}}\\}=0$.
The first two sums over the hoppings $\propto v,w$ in (1) constitute the SSH
model [44] while the third term $\propto U$ is the short-range Hubbard
interaction. Figure 1 shows a sketch of a finite chain with six unit cells
$i=1,2,\ldots,6$. In this work, we consider half-filling, i.e., as many
electrons as lattice sites, half of the electrons spin-up, half spin-down.

Figure 1: The SSH-Hubbard chain for six unit cells $i=1,2,\ldots,6$. The
intracell hopping amplitude is $-v$, and the intercell hopping amplitude is
$-w$. As an example, the possible positions of six spin-up and six spin-down
electrons are indicated by up and down arrows. For that configuration, two
electrons (of opposite spin) are located at site $i=3$, $m=2$ such that the
Hubbard interaction $U$ contributes.

We couple to an external driver in length gauge, e.g., a laser field in dipole
approximation, polarized along the chain, by adding a time-dependent term

$\displaystyle H_{\mathrm{field}}(t)$
$\displaystyle=E(t)\sum_{im\sigma}x_{im}c^{\dagger}_{im\sigma}c_{im\sigma}$
(2)

where $x_{im}$ is the position of the lattice site $(i,m)$ We considered
equidistant lattice sites separated by one unit of length (i.e., a lattice
constant $a=2$), with the origin in the center of the chain. The total
Hamiltonian then reads

$H(t)=H_{0}+H_{\mathrm{field}}(t).$ (3)

Choosing a particular basis for the many-electron Hilbert space, the field-
free many-electron eigenstates $\mathbf{u}_{j}$, $j=0,1,2,\ldots n-1$ are
calculated by solving the eigenvalue problem

$\mathbf{H_{0}}\mathbf{u}_{j}=\epsilon_{j}\mathbf{u}_{j}.$ (4)

Here, $\mathbf{H_{0}}$ is the matrix representation of $H_{0}$ in the chosen
basis, and
$\epsilon_{0}\leq\epsilon_{1}\leq\epsilon_{2}\leq\ldots\leq\epsilon_{n-1}$ are
the eigenenergies of the many-electron eigenstates in ascending order. For the
case of half-filling, the rank of the matrix $\mathbf{H_{0}}$ is
$n=\binom{N}{N/2}^{2}$. For $N=12$ we have $n=853776$.

The exact diagonalization approach is only feasible for not too large $N$ and
depends on the computational resources available. In this work, we will
discuss results for $N=12$. For vanishing interaction $U$, much larger systems
can be treated [2].

The matrix representation of $H_{\mathrm{field}}(t)$ factorizes in dipole
approximation into $\mathbf{H}_{\mathrm{field}}(t)=E(t)\mathbf{h}$ where
$\mathbf{h}$ is a time-independent matrix. Expanding the time-dependent state
in field-free eigenstates,

$\boldsymbol{\psi}(t)=\sum_{j}b_{j}(t)\mathrm{e}^{-\mathrm{i}\varepsilon_{j}t}\mathbf{u}_{j}$
(5)

including the field-free time evolution
$\mathrm{e}^{-\mathrm{i}\varepsilon_{j}t}$, we obtain

$\displaystyle\mathrm{i}\dot{b}_{k}(t)$
$\displaystyle=E(t)\sum_{j}\mathrm{e}^{-\mathrm{i}(\varepsilon_{j}-\varepsilon_{k})t}\bar{T}_{kj}b_{j}(t)$
(6)

with

$\bar{T}_{kj}=\mathbf{u}^{\dagger}_{k}\mathbf{h}\mathbf{u}_{j}.$ (7)

The expansion (5) transforms from the Schrödinger picture to the interaction
picture. Transitions between states $k$ and $j$ will only take place if the
transition-matrix element $T_{kj}=T_{jk}^{*}$ is non-vanishing.

Collecting the time-dependent coefficients $b_{k}(t)$ in a column vector
$\mathbf{b}(t)$, the time-dependent Schrödinger equation in the interaction
picture (6) can be written in matrix form,

$\mathrm{i}\dot{\mathbf{b}}(t)=\mathbf{M}(t)\mathbf{b}(t)$ (8)

with the matrix elements of $\mathbf{M}(t)$ being

$M_{kj}(t)=E(t)\mathrm{e}^{-\mathrm{i}(\varepsilon_{j}-\varepsilon_{k})t}\bar{T}_{kj}.$
(9)

If we start from the many-body ground state at $t=0$ (where the field $E(t)$
is not yet switched on), the initial condition is $b_{0}(0)=1$ and all other
$b_{k}(0)$ zero. Equation (8) is a set of coupled ordinary differential
equations of first order, which can be solved numerically by standard methods.
The feasibility and computational demand depends on the rank $n$ and on the
sparseness of $\mathbf{M}(t)$.

Harmonic spectra are calculated as
$Y(\Omega)=|\mathrm{FFT}[\mathrm{hann}(t)\ddot{d}(t)]|^{2}$ where FFT denotes
the fast-Fourier transform from the time to the frequency domain $\Omega$,
hann$(t)$ is the Hann window to increase the dynamic range, and $\ddot{d}$ is
the dipole acceleration, which is proportional to the second derivative of the
position expectation value

$\displaystyle x(t)$
$\displaystyle=\boldsymbol{\psi}^{\dagger}(t)\mathbf{h}\boldsymbol{\psi}(t)=\sum_{kj}b^{*}_{k}(t)b_{j}(t)\bar{T}_{kj}=\mathbf{b}^{\dagger}(t)\,\bar{\mathbf{T}}\,\mathbf{b}(t)$
(10)

where $\bar{T}_{kj}$ are the matrix elements of the transition matrix
$\bar{\mathbf{T}}$.

##  III Results

Figure 2 shows harmonic spectra for the $N=12$ chain for the hopping
parameters (chosen to be the same as in [2]) $v=0.18268$, $w=0.10026$ ($v>w$,
trivial) and $w=0.18268$, $v=0.10026$ ($w>v$, topological). The Hubbard
interaction was $U=0.1$ in Fig. 2(a) and $U=0$ in (b). The laser pulse was of
$\sin^{2}$-shape,

$E(t)=E_{0}\sin^{2}\left(\frac{\omega t}{2n_{\mathrm{cyc}}}\right)\cos\omega
t,\qquad 0<t<n_{\mathrm{cyc}}2\pi/\omega,$ (11)

with laser frequency $\omega=0.0049$ (i.e., wavelength $\lambda=9.3\,\mu$m),
electric field amplitude $E_{0}=0.4\omega$ (i.e., laser intensity $13.5\times
10^{10}$ W/cm2), and number of laser cycles in the pulse $n_{\mathrm{cyc}}=5$.
The laser intensity in this work is a hundred times higher than in [2] where
much longer SSH chains were studied. With the same laser intensity as in [2],
no harmonic plateau is observed for the short chains we investigate in this
work.

Figure 2: Logarithm of the harmonic yield $\log Y(\Omega)$ vs the harmonic
order $\Omega/\omega$ for (a) $U=0.1$ and (b) $U=0$. Note the huge difference
between the topological and the trivial phase in the yield up to harmonic
order $\simeq 20$.

For the trivial case $v>w$, there is an exponential drop in the yield over the
first few odd harmonics. This is very similar to the spectra for the
topologically trivial phase in [2]. The next group of harmonics is centered
around harmonic order $\simeq 40$, which corresponds to the energy difference
between the lowest many-electron excited state (to which transitions are
allowed) and the many-electron ground state. This energy difference shifts
with increasing $U$ to higher energies. Other groups of harmonics at higher
harmonic orders are located around energy differences that correspond to
dipole-allowed transitions between higher excited many-electron states and the
many-electron ground state.

For the topological case $w>v$, the first excited many-body state to which
dipole transitions are allowed is at lower energy. Hence the first group of
harmonics occurs for harmonic orders $<20$, which explains the huge difference
in the harmonic yield there. In the trivial case $v>w$ there are simply no
states available that could give rise to harmonic generation at such low
photon energies.

This explanation of the difference in the harmonic yields is simple. What
might be surprising though is the fact that the spectra for such short $N=12$
chains look already very similar to those for the much longer chains in [2].
For the long chains with non-interacting electrons one usually employs (very
successfully) the band structure of the corresponding bulk system to analyze
the spectral features in (high) harmonic generation. There, two edge states
appear in the band gap for the topological phase, one of which is populated.
It was shown in [1, 2] that this presence of edge states explains the high
yield for below-band-gap harmonics in the topological phase. In this work, we
study short chains at half filling with e-e interaction, for which a band
structure does not exist. The first few exponentially dropping harmonics
solely originate from time-dependent populations (so-called Brunel harmonics,
not “intraband harmonic generation,” as there are no bands).

###  III.1 Dependence of HHG spectra on interaction $U$

Figure 3 shows HHG spectra as a function of e-e interaction $U$ for the
trivial and the topological case. In both cases one sees that with increasing
$U$, the emission of high-order harmonics shifts towards higher orders but
with lower yield. This is expected, because in the Mott-insulator limit of
large $U$ the electrons are in the energetically most favorable configuration
$\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow$
(or
$\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow$)
and cannot be polarized by the laser because electrons would have to hop to an
already populated site, which is unlikely for $U\gg v,w$. In the following, we
therefore restrict ourselves to small enough $U$ such that a HHG plateau
exists in the topological case. Of course, the existence of a plateau also
depends on the laser parameters. In this work, we fix laser intensity,
wavelength, and pulse shape to the values given after equation (11).

Figure 3: Contour plots of the harmonic yield $\log Y(\Omega)$ vs the harmonic
order $\Omega/\omega$ and the Hubbard interaction $U$ for (a) the topological
and (b) the trivial twelve-site half-filled chain. Panels (c) and (d) zoom
into the regions of the spectra indicated by the white rectangle in (a) and
(b), respectively. A clear HHG plateau up to harmonic order $\simeq 15$ is
observed in the topological phase [see panel (c)] for $U<0.1$.  Figure 4: The
lowest-lying relevant levels sufficient to reproduce the HHG spectra up to
harmonic order $\simeq 34$ for $U=0.1$ in (a) the topological case, and (b) in
the trivial case. Here, $0,2,3,\ldots$ represent the states
$\mathbf{u}_{0},\mathbf{u}_{2},\mathbf{u}_{3},\ldots$ . Double-headed arrows
indicate allowed transitions. The little red arrows indicate the energy of the
photons in the incoming laser pulse.

###  III.2 Sufficiency of only a few many-electron states

In the case of twelve sites and half filling, the matrix $\mathbf{H}_{0}$ in
(4) is of rank $n=853776$ such that we have $853776$ eigenvalues and
eigenvectors. Starting from the many-body ground state $\mathbf{u}_{0}$, not
all the $853775$ excited many-body states will be populated by the laser. For
many of the excited states, the transition matrix elements $\bar{T}_{kj}$ are
zero, which constitutes selection rules for transitions between many-body
states. Other transitions, which are in principle allowed by
$\bar{\mathbf{T}}$, are just unlikely, given our very small laser frequency,
which is much lower than the transition to the first excited many-body state.
As a consequence, we should obtain the same HHG spectra with a much reduced
matrix $\mathbf{M}(t)$ in (8), taking only a few lowest $b_{k}(t)$ into
account (and excluding those $k$ to which transitions are forbidden). The
number of states necessary to reproduce the HHG spectrum obtained with all
states taken into account depends on the highest harmonic order of interest.
For instance, if we are satisfied with reproducing very well only the first
plateau for the topological case in Fig. 2(a) it is sufficient to take only
$7$ many-electron states into account, namely $k=0,2,3,5,11,16,18$. The
allowed transitions are between states $(0,2),(0,11),(0,18),$
$(2,3),(2,5),(2,16),$ $(3,11),(3,18),(5,18),(11,16)$, and $(16,18)$. Figure
4(a) shows these levels and transitions for the topological case and $U=0.1$.
In this case the many-electron states $\mathbf{u_{2}},\mathbf{u_{3}}$ become
almost degenerate (up to the third digit after the comma in energy) many-body
edge states discussed below in Sec. III.3. Figure 5(a) shows that the first
plateau is indeed well covered by just these seven many-body levels. For the
trivial case, the harmonics in the same range are reproduced with the ten
states $k=0,2,4,11,13,15,17,29,30,34$ and the transitions
$(0,2),(0,11),(0,13),(0,29),(0,30),(0,34),(2,4),(2,15),$
$(2,17),(4,11),(4,13),(4,29),(4,30),(4,34),(11,15),$
$(13,15),(13,17),(15,29),(15,30),(15,34),(17,29),$ $(17,30)$ and $(17,34)$, as
shown in Fig. 5(b). The states and transitions for the trivial case are
depicted in Fig. 4(b). The main difference compared to the topological case in
(a) is that the energy difference between ground and first accessible excited
state is much larger, and that the precursor of degenerate edge states in (a)
(i.e., $\mathbf{u_{2}},\mathbf{u_{3}}$) is absent. It might be surprising that
more states are necessary in the trivial case despite the fact that there is
no plateau but only exponentially dropping Brunel harmonics. The reason is
that, in order to get the yield of these low-order Brunel harmonics right down
to $10^{-25}$ in dynamic range, one needs the accurate population of the
ground state and thus the excited states to which population may go. In the
topological case, there are no Brunel harmonics visible down to $10^{-25}$
because of the plateau.

Figure 5: Logarithm of the harmonic yield $\log Y(\Omega)$ as a function of
the harmonic order $\Omega/\omega$ for $U=0.1$ for (a) topological case and
(b) trivial case. Calculations with the $100$ lowest-lying eigenstates are
shown in blue. They are converged for the harmonic range shown. Calculations
with a reduced number of states ($7$ and $10$ states in (a) and (b),
respectively) are shown in red. This very small number of many-body states is
sufficient to reproduce harmonics up to order $\simeq 25$, covering the first
plateau in (a).

Note that by identifying the lowest relevant many-body states, the calculation
of HHG in a correlated many-electron system has become computationally cheap
because it reduces to solving a few-level time-dependent Schrödinger equation.
However, the numerically demanding task to calculate all the $n$ eigenenergies
and eigenvectors $\mathbf{u}_{j}$ in the Schrödinger equation (4) in the first
place remains. Moreover, the longer the chains, the closer together lie the
eigenenergies $\epsilon_{j}$, and the more states have to be considered in the
reduced matrix $\mathbf{M}$ for the calculation of HHG.

###  III.3 Dominant configurations in the low-lying many-body states

We investigated the dominant configurations in the lowest many-body
eigenvectors $\mathbf{u}_{j}$ for $U=0.1$ and $U=0.2$ in both the trivial and
topological phases of a twelve-site half-filled chain. Note that $U=0.1$ is
similar to the value for the smaller hopping amplitude $0.10026$ ($=v$ in the
topological and $w$ in the trivial case). Hence sacrificing one of these
subdominant hoppings is energetically similarly expensive as paying one $U$
for a doubly occupied site, i.e., a doublon. The situation is different for
$U=0.2$ where paying a $U$ for a doublon is more expensive than sacrificing
even a dominant hopping.

The configuration
$\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow$
(along with its spin or space-inverted counterpart
$\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow$)
is the most energetically favorable and dominates in both the ground state
$\mathbf{u}_{0}$ and the first excited state $\mathbf{u}_{1}$, across both
phases and for both values of $U$. This outcome is anticipated because it
maximizes the number of possible hoppings (twelve possible intracell
$v$-hoppings and ten possible intercell $w$-hoppings), thereby minimizing the
kinetic energy. Additionally, since no two electrons occupy the same site,
there is no energy increase from the e-e interaction $U$. However, as
$\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow$
is not an eigenstate of the Hamiltonian (1) other configurations mix into
$\mathbf{u}_{0}$. The next dominant ones are those with two pairs of adjacent
equal-spin electrons within unit cells (in the topological case) and across
unit cells (in the trivial case). These configurations still allow for all ten
$w$-hoppings (in the topological case) and all twelve $v$-hoppings (in the
trivial case). The first configurations admixed into $\mathbf{u}_{0}$ that
involve a doublon and a holon are of the kind
$\downarrow\uparrow\downarrow\uparrow\downarrow\updownarrow\\!\cdot\\!\uparrow\downarrow\uparrow\downarrow\uparrow$
in the topological case. Here, $\updownarrow$ indicates a doublon (i.e., a
doubly occupied site) and $\\!\cdot\\!$ a holon (i.e., a vacant site). Here
and in the following we show in each case only one of the equivalent spin or
space-inverted configurations. For $U=0.1$ the configuration
$\downarrow\uparrow\downarrow\uparrow\downarrow\updownarrow\\!\cdot\\!\uparrow\downarrow\uparrow\downarrow\uparrow$
has the fourth highest weight in $\mathbf{u}_{0}$, where the weight is
measured as the modulus square of the respective component in the eigenvector
$\mathbf{u}_{0}$. For $U=0.2$ it has only the sixth highest weight because a
doublon is energetically more expensive. In the trivial case, states with the
doublon-holon pair at the edge of the kind
$\updownarrow\\!\cdot\\!\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow$
have the eighth highest weight for $U=0.1$ in $\mathbf{u}_{0}$ but are not
among the top ten dominant configurations for $U=0.2$.

As we know from Fig. 4 that $\mathbf{u}_{2}$ is the first many-body state to
which a dipole-allowed transition can occur it is interesting to look at the
dominant configurations in $\mathbf{u}_{2}$. In the topological case, these
are for both $U$ values many-body edge states with a doublon at one edge and a
holon at the other, e.g.,
$\\!\cdot\\!\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\updownarrow$.
The situation is very different in the trivial case where the dominant
configurations in $\mathbf{u}_{2}$ are of the kind
$\downarrow\uparrow\updownarrow\\!\cdot\\!\updownarrow\\!\cdot\\!\updownarrow\\!\cdot\\!\updownarrow\\!\cdot\\!\downarrow\uparrow$
for $U=0.1$, i.e., several adjacent doublon-holon pairs in the bulk. For
$U=0.2$, the dominant configurations in $\mathbf{u}_{2}$ avoid doublon-holon
pairs altogether but are of the type
$\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow$.

##  IV Conclusion and Outlook

In this work, we studied the effect of e-e interaction on harmonic generation
in half-filled SSH-Hubbard chains. For non-interacting electrons, long but
finite SSH chains show the well-known topological edge states that were found
to play a significant role in the enhancement of the harmonic yield in the
topological phase. Since we used the method of exact diagonalization for the
interacting SSH-Hubbard chains, we were restricted to short chains, no longer
than twelve sites. However, these short chains already showed the precursors
of what would be topological edge states for longer chains without
interaction.

There are two main results of this work: (i) The huge difference in the
harmonic yield between trivial and topological SSH phase observed earlier
survives e-e interaction (unless the interaction is so large that harmonic
generation ceases to exist anyway), and (ii) a few low-lying many-electron
states are sufficient to describe harmonic generation in the small finite
chains considered, including non-perturbative plateaus. With increasing system
size, more and more of such many-electron states will contribute. However, by
examining the smaller, exactly diagonalizable chains like the ones in this
paper, one may be better equipped to make an educated guess about the relevant
states in longer chains. This then may allow us to reduce the many-body
Hilbert space for the electronic-structure calculation in the first place.

Future work is planned to be devoted to a time-dependent Hartree-Fock
treatment of the same chains in order to investigate the role of many-body
correlation, and to 2D topological systems with interaction such that the
polarization properties of the harmonics can be investigated. Further, the
field of topological invariants and robustness for interacting systems is
still in its infancy. Hence it will be of general interest to study how
topological features behave as the interaction between particles increases.
Harmonic generation is a particularly attractive observable because it is
purely optical and non-invasive. Using additional laser fields, one may dress
the system to become Floquet-topological, and thus make topological features
tunable.

## Acknowledgment

Funding by the German Research Foundation - SFB 1477 “Light-Matter
Interactions at Interfaces,” Project No. 441234705, is gratefully
acknowledged.

## References

  * Bauer and Hansen [2018] D. Bauer and K. K. Hansen, Phys. Rev. Lett. 120, 177401 (2018).
  * Jürß and Bauer [2019] H. Jürß and D. Bauer, Phys. Rev. B 99, 195428 (2019).
  * Ghimire  _et al._ [2010] S. Ghimire, A. D. DiChiara, E. Sistrunk, P. Agostini, L. F. DiMauro, and D. A. Reis, Nat. Phys 7, 138–141 (2010).
  * Schubert  _et al._ [2014] O. Schubert, M. Hohenleutner, F. Langer, B. Urbanek, C. Lange, U. Huttner, D. Golde, T. Meier, M. Kira, S. W. Koch, and R. Huber, Nat. Photon 8, 119–123 (2014).
  * Vampa  _et al._ [2015] G. Vampa, T. Hammond, N. Thiré, B. Schmidt, F. Légaré, C. McDonald, T. Brabec, D. Klug, and P. Corkum, Phys. Rev. Lett 115, 10.1103/physrevlett.115.193603 (2015).
  * Hohenleutner  _et al._ [2015] M. Hohenleutner, F. Langer, O. Schubert, M. Knorr, U. Huttner, S. W. Koch, M. Kira, and R. Huber, Nature (London) 523, 572–575 (2015).
  * Luu  _et al._ [2015] T. T. Luu, M. Garg, S. Y. Kruchinin, A. Moulet, M. T. Hassan, and E. Goulielmakis, Nature (London) 521, 498–502 (2015).
  * Ndabashimiye  _et al._ [2016] G. Ndabashimiye, S. Ghimire, M. Wu, D. A. Browne, K. J. Schafer, M. B. Gaarde, and D. A. Reis, Nature (London) 534, 520–523 (2016).
  * Langer  _et al._ [2017] F. Langer, M. Hohenleutner, U. Huttner, S. W. Koch, M. Kira, and R. Huber, Nat. Photon 11, 227–231 (2017).
  * Tancogne-Dejean  _et al._ [2017] N. Tancogne-Dejean, O. D. Mücke, F. X. Kärtner, and A. Rubio, Phys. Rev. Lett 118, 10.1103/physrevlett.118.087403 (2017).
  * You  _et al._ [2017] Y. S. You, Y. Yin, Y. Wu, A. Chew, X. Ren, F. Zhuang, S. Gholam-Mirzaei, M. Chini, Z. Chang, and S. Ghimire, Nat. Commun. 8, 10.1038/s41467-017-00989-4 (2017).
  * Zhang  _et al._ [2018] G. P. Zhang, M. S. Si, M. Murakami, Y. H. Bai, and T. F. George, Nat. Commun. 9, 10.1038/s41467-018-05535-4 (2018).
  * Vampa  _et al._ [2018] G. Vampa, T. J. Hammond, M. Taucer, X. Ding, X. Ropagnol, T. Ozaki, S. Delprat, M. Chaker, N. Thiré, B. E. Schmidt, F. Légaré, D. D. Klug, A. Y. Naumov, D. M. Villeneuve, A. Staudte, and P. B. Corkum, Nat. Photon. 12, 465–468 (2018).
  * Baudisch  _et al._ [2018] M. Baudisch, A. Marini, J. D. Cox, T. Zhu, F. Silva, S. Teichmann, M. Massicotte, F. Koppens, L. S. Levitov, F. J. García de Abajo, and J. Biegert, Nat. Commun. 9, 10.1038/s41467-018-03413-7 (2018).
  * Garg  _et al._ [2018] M. Garg, H. Y. Kim, and E. Goulielmakis, Nat. Photon. 12, 291–296 (2018).
  * Hasan and Kane [2010] M. Z. Hasan and C. L. Kane, Rev. Mod. Phys. 82, 3045–3067 (2010).
  * Ando [2013] Y. Ando, J. Phys. Soc. Jpn. 82, 102001 (2013).
  * Chiu  _et al._ [2016] C.-K. Chiu, J. C. Teo, A. P. Schnyder, and S. Ryu, Rev. Mod. Phys. 88, 10.1103/revmodphys.88.035005 (2016).
  * Moore [2010] J. E. Moore, Nature (London) 464, 194–198 (2010).
  * Qi and Zhang [2011] X.-L. Qi and S.-C. Zhang, Rev. Mod. Phys. 83, 1057–1110 (2011).
  * Viyuela  _et al._ [2018] O. Viyuela, A. Rivas, S. Gasparinetti, A. Wallraff, S. Filipp, and M. A. Martin-Delgado, npj Quantum Inf. 4, 10.1038/s41534-017-0056-9 (2018).
  * Rechtsman  _et al._ [2013] M. C. Rechtsman, J. M. Zeuner, Y. Plotnik, Y. Lumer, D. Podolsky, F. Dreisow, S. Nolte, M. Segev, and A. Szameit, Nature (London) 496, 196–200 (2013).
  * Stützer  _et al._ [2018] S. Stützer, Y. Plotnik, Y. Lumer, P. Titum, N. H. Lindner, M. Segev, M. C. Rechtsman, and A. Szameit, Nature (London) 560, 461–465 (2018).
  * Kruk  _et al._ [2018] S. Kruk, A. Poddubny, D. Smirnova, L. Wang, A. Slobozhanyuk, A. Shorokhov, I. Kravchenko, B. Luther-Davies, and Y. Kivshar, Nat. Nanotechnol. 14, 126–130 (2018).
  * Ningyuan  _et al._ [2015] J. Ningyuan, C. Owens, A. Sommer, D. Schuster, and J. Simon, Phys. Rev. X 5, 10.1103/physrevx.5.021031 (2015).
  * Albert  _et al._ [2015] V. V. Albert, L. I. Glazman, and L. Jiang, Phys. Rev. Lett. 114, 10.1103/physrevlett.114.173902 (2015).
  * Drüeke and Bauer [2019] H. Drüeke and D. Bauer, Phys. Rev. A 99, 10.1103/physreva.99.053402 (2019).
  * Moos  _et al._ [2020] D. Moos, H. Jürß, and D. Bauer, Phys. Rev. A 102, 10.1103/physreva.102.053112 (2020).
  * Koochaki Kelardeh  _et al._ [2017] H. Koochaki Kelardeh, V. Apalkov, and M. I. Stockman, Phys. Rev. B 96, 10.1103/physrevb.96.075409 (2017).
  * Luu and Wörner [2018] T. T. Luu and H. J. Wörner, Nat. Commun. 9, 10.1038/s41467-018-03397-4 (2018).
  * Reimann  _et al._ [2018] J. Reimann, S. Schlauderer, C. P. Schmid, F. Langer, S. Baierl, K. A. Kokh, O. E. Tereshchenko, A. Kimura, C. Lange, J. Güdde, U. Höfer, and R. Huber, Nature (London) 562, 396–400 (2018).
  * Neufeld  _et al._ [2023] O. Neufeld, N. Tancogne-Dejean, H. Hübener, U. De Giovannini, and A. Rubio, Phys. Rev. X 13, 031011 (2023).
  * Baldea  _et al._ [2004] I. Baldea, A. K. Gupta, L. S. Cederbaum, and N. Moiseyev, Phys. Rev. B 69, 245311 (2004).
  * Silva  _et al._ [2018] R. Silva, I. V. Blinov, A. N. Rubtsov, O. Smirnova, and M. Ivanov, Nat. Photonics 12, 266 (2018).
  * Murakami  _et al._ [2018] Y. Murakami, M. Eckstein, and P. Werner, Phys. Rev. Lett. 121, 057405 (2018).
  * Murakami  _et al._ [2021] Y. Murakami, S. Takayoshi, A. Koga, and P. Werner, Phys. Rev. B 103, 035110 (2021).
  * Tancogne-Dejean  _et al._ [2018] N. Tancogne-Dejean, M. A. Sentef, and A. Rubio, Phys. Rev. Lett. 121, 097402 (2018).
  * Lysne  _et al._ [2020] M. Lysne, Y. Murakami, and P. Werner, Phys. Rev. B 101, 195139 (2020).
  * Imai  _et al._ [2020] S. Imai, A. Ono, and S. Ishihara, Phys. Rev. Lett. 124, 157404 (2020).
  * Avchyan  _et al._ [2022] B. Avchyan, A. Ghazaryan, K. Sargsyan, and K. V. Sedrakian, JETP Lett. 116, 428 (2022).
  * Hansen  _et al._ [2022] T. Hansen, S. V. B. Jensen, and L. B. Madsen, Phys. Rev. A 105, 053118 (2022).
  * Hansen and Madsen [2022] T. Hansen and L. B. Madsen, Phys. Rev. B 106, 235142 (2022).
  * Valmispild  _et al._ [2024] V. N. Valmispild, E. Gorelov, M. Eckstein, A. I. Lichtenstein, H. Aoki, M. I. Katsnelson, M. Y. Ivanov, and O. Smirnova, Nature Photonics 10.1038/s41566-023-01371-1 (2024).
  * Su  _et al._ [1979] W.-P. Su, J. R. Schrieffer, and A. J. Heeger, Phys. Rev. Lett. 42, 1698 (1979).