Cohomology ring of tree braid groups and exterior face rings

Abstract

For a tree $T$ and a positive integer $n$, let $B_nT$ denote the $n$-strand braid group on $T$. We use discrete Morse theory techniques to show that the cohomology ring $H^*(B_nT)$ is encoded by an explicit abstract simplicial complex $K_nT$ that measures $n$-local interactions among essential vertices of $T$. We show that, in many cases (for instance when $T$ is a binary tree), $H^*(B_nT)$ is the exterior face ring determined by $K_nT$.

1. Main results

For a finite graph $\Gamma$ and a positive integer $n$, let $\operatorname {Conf}_n\Gamma$ denote the configuration space of $n$ ordered points on $\Gamma$,

$$\begin{equation*} \operatorname {Conf}_n\Gamma \coloneq \left\{(x_1,\ldots ,x_n)\in \Gamma ^n\colon x_i\neq x_j \text{ for } i\neq j \right\}. \end{equation*}$$

The usual right action of the $n$-symmetric group $\Sigma _n$ on $\operatorname {Conf}_n\Gamma$ is given by $(x_1,\ldots$, $x_n)\cdot \sigma =(x_{\sigma (1)},\ldots ,x_{\sigma (n)})$, and $\operatorname {UConf}_n\Gamma$ stands for the corresponding orbit space, the configuration space of $n$ unlabelled points on $\Gamma$. Both $\operatorname {Conf}_n\Gamma$ and $\operatorname {UConf}_n\Gamma$ are known to be aspherical 110; 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$.

Besides its central role in geometric group theory, graph braid groups have applications in areas outside pure mathematics such as robotics, topological quantum computing and data science. Yet, there is a relatively limited knowledge of the algebraic topology properties of a graph braid group (or, for that matter, of a tree braid group), particularly concerning its cohomology ring structure.

Using discrete Morse theory techniques on Abrams’ cubical model $\operatorname {UD}_n T$ for $\operatorname {UConf}_nT$ (reviewed below), D. Farley gave in 4 an efficient description of the additive structure of the cohomology of $B_nT$. Later, and in order to get at the multiplicative structure, the Morse theoretic methods were replaced in 5 by the use of a Salvetti complex $\mathcal{S}$ obtained by identifying opposite faces of cells in $\operatorname {UD}_n T$. Being a union of tori, $\mathcal{S}$ has a well understood cohomology ring. Yet more importantly, the projection map $q\colon \operatorname {UD}_n T\to \mathcal{S}$ induces a surjection in cohomology. Farley’s main result in 5 is a description of a set of generators for Ker$(q^*)$, which yields a presentation for the cohomology ring of $B_nT$.

Although 5 includes an algorithm for performing computations mod Ker$(q^*)$, the price of not working at the Morse theoretic level is that Farley’s presentation includes many non-essential generators. As a result, calculations are hard to work with, in concrete examples, as well as in theoretical developments (cf. Remark 1.9). In particular, Farley-Sabalka’s conjecture 7, Conjecture 5.7 that $H^*(B_nT;\mathbb{Z}_2)$ is an exterior face ring, suggested on the basis of extensive concrete calculations, was left open.

In this paper we combine Farley-Sabalka’s original Morse theoretic approach with Forman’s Morse-theoretic description of cup products to prove the integral version of Farley-Sabalka’s conjecture for a large family of trees. The statement in Theorem 1.1, which focuses on binary trees, i.e., on trees all of whose essential vertices have degree three, disproves Conjecture 5.17 in 15 by exhibiting an infinite family of non-linear trees $T$ all of whose braid group cohomology rings are exterior face rings.

Theorem 1.1.

Assume $T$ is a binary tree. For a commutative ring $R$ with 1, the cohomology ring $H^*(B_nT;R)$ is the exterior face ring $\Lambda _R(K_nT)$ determined by a simplicial complex $K_nT$. Explicitly, $H^*(B_nT;R)$ is the quotient $\Lambda /I$, where $\Lambda$ is the exterior graded $R$-algebra generated by the vertex set of $K_nT$, and $I$ is the ideal generated by monomials corresponding to non-faces of $K_nT$.

As noted in 7, p. 68, the isomorphism type of a complex $K_nT$ as the one in Theorem 1.1 is well determined. We refer to $K_nT$ as the $n$-interaction complex of $T$. A description of $K_nT$ as an abstract simplicial complex is given in Definition 1.3. The explicit definition allows us, for instance, to easily deduce a concrete right-angled Artin group presentation for $B_nT$ when $T$ is a linear binary tree (Example 1.6). This complements the inductive method in 3 proving that linearity is a sufficient⁠¹ condition for a tree to have right-angled Artin braid groups.

¹

The condition is known to be necessary and sufficient.

✖

The definition of $K_nT$ applies for any tree and we show that the resulting combinatorial object encodes much of the ring structure of $H^*(B_nT;R)$, whether $T$ is binary or not. Indeed, we generalize Theorem 1.1 in two directions. On the one hand, the ring-isomorphism assertion $H^*(B_nT;R)\cong \Lambda _R(K_nT)$ holds as long as $T$ is a tree with binary core (Theorem 6.4). Furthermore, we show that, for any tree $T$, the vertices of $K_nT$ can be thought of as giving an $R$-basis of $H^1(B_nT;R)$, while the cup-product-based rule $\{v_1,\ldots ,v_m\}\mapsto v_1\cdots v_m$ sets a 1-1 correspondence between the family of ($m-1$)-simplices of $K_nT$ and an $R$-basis of $H^m(B_nT;R)$. More importantly, while cup squares are known to vanish in $H^*(B_nT;R)$, certain (square-free) products $v_1\cdots v_m$ are non-zero even when $\{v_1,\ldots ,v_m\}$ fails to be a face of $K_nT$ (this can happen only if $T$ is not a tree with binary core). In any such case, we give a closed formula (Theorem 5.1) to write any such product $v_1\cdots v_m$ as an $R$-linear combination of basis elements, thus completing a full description of the cup-product structure in the cohomology of $B_nT$ for any tree $T$. Details are summarized in Theorem 1.7.

The techniques used in this work (discrete Morse theoretic approach to cup products) should be a valuable tool in understanding the algebraic topology properties of discrete models for other spaces, such as non-particle configuration spaces, as well as generalized (e.g., no-$k$-equal) configuration spaces.

Remark 1.2.

Ghrist’s pioneering work led to conjecture that any pure braid group $P_n\Gamma$ on a graph $\Gamma$ would be a right-angled Artin group. In the case of full braid groups $B_n\Gamma$, 1314 give two characterizations (one combinatorial and another cohomological) of the right-angled-Artin condition. For instance, for $\Gamma =T$ a tree, $B_nT$ is a right-angled Artin group if and only if $H^*(B_nT)$ is the exterior face ring of a flag complex. Theorem 1.1 and its generalized version in Theorem 6.4 assert that, in the full braid group setting and for trees with binary core, Ghrist’s conjecture is true after removal of the flag requirement.

The description of the complex $K_nT$, as well as an explicit statement of Theorem 1.7, and a couple of explicit illustrations (Examples 1.5 and 1.6) of Theorem 1.1 require a few preparatory constructions. Unless otherwise noted, throughout the rest of the section $T$ stands for an arbitrary tree.

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$. The resulting ordering of vertices and edges will be referred to as the $T$-order.⁠²

²

This of course depends on the embedding and root chosen.

✖

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. See Figure 1. 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.

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)}$ components

$$\begin{equation*} C_{i,{\ell _i}}=C_{i,{\ell _i}}(x_1,\ldots ,x_m), \end{equation*}$$

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 leave 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}$.

Definition 1.3 (The $n$-interaction complex of $T$, $K_nT$).

(a)

The vertex set $V_nT$ of $K_nT$ is the collection of all 4-tuples $\nu =\langle k,x,p,q\rangle$, where $k$ is a non-negative integer number, $x$ is an essential vertex of $T$, and $p=(p_{1},\dots , {p_r})$ and $q=(q_1, \dots , {q_s})$ are tuples of non-negative integer numbers satisfying the three conditions

•

$r+s=d(x)-1$, with $r>0<s;$

•

$k+|p|+|q|=n-1$, where $|p|\coloneq \sum _{j=1}^r p_j$ and $|q|\coloneq \sum _{j=1}^s q_j;$

•

$p_j>0$ for at least one $j\in \{1,\ldots ,r\}$.

We stress that $r$ (i.e., the length of $p$) is one of the parameters determining the 4-tuple $\nu$. For instance, if $d(x)=6$ and $n=4$, then $\langle 1,x,(0,1,0),(1,0) \rangle$ and $\langle 1,x,(0,1),(0,1,0) \rangle$ are two different elements in $V_nT$. The length $s$ of $q$, on the other hand, is determined by $r$ and $d(x)$.

(b)

For $\nu _1,\ldots ,\nu _m\in V_nT$ with $\nu _i=\langle k_i,x_i,p_i,q_i\rangle$, $p_i=(p_{i,1},\dots , p_{i,r_i})$, $q_i=(q_{i,1}, \dots , q_{i,s_i})$ and so that $x_1<\cdots <x_m$, consider the components $C_{0,1}$ and $C_{i,\ell _i}$ $(1\leq i\leq m$ and $1\leq \ell _i\leq d(x_i)-1)$ of $T\setminus \{x_1, \ldots , x_m\}$ as defined above. Then, for $C\in \{C_{0,1},C_{i,\ell _i}\}$, the $C$-local information of $\nu _j$, denoted by $\ell _C(\nu _j)$, is defined by$$\begin{equation*} {\ell _{C_{0,1}}(\nu _j)=\begin{cases} k_j, & \text{if $x_j\in B(C_{0,1})$;} \\ 0, & \text{otherwise,} \end{cases} } \end{equation*}$$

and, for $i>0$,$$\begin{equation} \ell _{C_{i,{\ell _i}}}(\nu _j)=\begin{cases} p_{i,{\ell _i}}, & \text{if $j=i$ and ${\ell _i} \leq {r_i};$} \\ q_{i,{\ell _i-r_i}}, & \text{if $j=i$ and ${\ell _i} > r_i;$} \\ {k_j,} & \text{if $j\neq i$ and ${x_j\in B(C_{i,\ell _i})};$} \\ 0, & \text{in any other case.} \end{cases} {\tag{1}} \end{equation}$$

Note that $\ell _C(\nu _j)=0$ whenever $x_j\not \in B(C)$.

(c)

The $n$-interaction complex of $T$ is the abstract simplicial complex $K_nT$ whose vertex set is $V_nT$ and whose $(m-1)$-simplices are given by families of vertices $\nu _1,\ldots ,\nu _m$ as in item (b) satisfying$$\begin{equation} \sum _{j=1}^m\ell _{C_{i,{\ell _i}}}\left(\nu _j \right)\geq n\left(\operatorname {card}(B(C_{i,{\ell _i}}))-1\right), {\tag{2}} \end{equation}$$

for all $i\in \{0,1,\ldots ,m\}$ and all relevant $\ell _i$, and in such a way that, for every $i>0$, 2 is a strict inequality for at least one $\ell _i\in \{1,\dots , r_i\}$.

It is an easy arithmetic exercise (whose verification is left to the reader) to check that $K_nT$ is indeed a simplicial complex.

Definition 1.3 is dictated by discrete Morse theoretic considerations—reviewed in later sections. Our choice for using angle brackets instead of parentheses for 4-tuples in $V_nT$ will be justified later in the paper (Remark 6.2). More important at this point is to explain the role of $K_nT$ as an object measuring “local interactions” between systems of “local informations” around essential vertices of $T$. For starters, we refer to a vertex $\nu =\langle k,x,{(p_1,\ldots ,p_r),(q_1,\ldots ,q_s)} \rangle \in V_nT$ as a system of local informations around the essential vertex $x$ of $T$. Indeed, as illustrated in Figure 2, we think of:

(i)

$k$ as the local information of $\nu$ in $x$-direction 0,

(ii)

$p_j$ ($1\leq j\leq r$) as the local information of $\nu$ in $x$-direction $j$, and

(iii)

$q_j$ ($1\leq j\leq s$) as the local information of $\nu$ in $x$-direction ${j+r}$.

In these terms, 1 gives a systematic way to spell out the information ingredients on a given family of systems of local informations. Likewise, item (c) in Definition 1.3 asserts that a family $\{\nu _1,\ldots ,\nu _m\}$ of systems of local informations around essential vertices $x_1<\cdots <x_m$ of $T$ assembles a simplex of $K_nT$ if, for each component $C$ of $T\setminus \{x_1,\ldots ,x_m\}$, the sum of the $C$-local informations of vertices $x_j$ bounding $C$ is suitably large, depending on $n$ and on the number of bounding vertices of $C$.

Definition 1.4.

Let $\nu _1,\nu _2,\ldots ,\nu _m\in V_nT$ be a family of systems of local informations around essential vertices $x_1<x_2<\cdots <x_m$ of $T$. We say that $\nu _1,\ldots ,\nu _m$ interact strongly provided $\{\nu _1,\ldots ,\nu _m\}$ is a simplex of $K_nT$. We say that $\nu _1,\ldots ,\nu _m$ interact weakly provided 2 holds for all relevant $i$ and $\ell _i$ but $\{\nu _1,\ldots ,\nu _m\}$ fails to be a simplex of $K_nT$—so that, in fact, 2 is an equality for some $i>0$ and all $\ell _i\in \{1,\ldots ,r_i\}$. In all other cases, we say that $\nu _1,\ldots ,\nu _m$ do not interact.

Example 1.5.

Figure 3 shows three aspects of the smallest possible non-linear tree $T_0$. The four essential vertices are labelled (following the $T_0$-order) in the central picture. The fact that the 4-fold product

$$\begin{equation} \langle 0,x_1,{(1)},{(7)}\rangle \langle 2,x_2,{(4)},{(2)}\rangle \langle 6,x_3,{(1)},{(1)}\rangle \langle 7,x_4,{(1)},{(0)}\rangle \in H^4(B_9T_0;R) {\tag{3}} \end{equation}$$

is a basis element follows from Theorem 1.1, as inspection in the picture on the right of Figure 3 reveals that the factors in 3 interact strongly. Note that $r=s=1$ for each factor in 3, and that the cases with a strict inequality in 2 hold as required in the last clause of item (c) of Definition 1.3. Likewise, interaction analysis in the picture on the left exhibits the well known fact that $K_4T_0$ is not flag (i.e., $B_4T$ is not a right-angled Artin group): the three basis elements $\langle 0,x_1,{(1)},{(2)}\rangle$, $\langle 2,x_3,{(1)},{(0)}\rangle$ and $\langle 2,x_4,{(1)},{(0)}\rangle$ in $H^1(B_4T_0;R)$ have pairwise strong interactions (so their three double products are part of a basis of $H^2(B_4T_0)$), but the three basis elements do not interact (so their triple product vanishes).

Example 1.6.

Let $T$ be a binary tree whose essential vertices lie along a single embedded arc. Choosing the planar embedding shown in Figure 4, we see that $B_nT$ has a right-angled Artin group presentation with generators $\langle k,{x},p,q\rangle$, where ${x}$ is an essential vertex of $T$ and $k,p,q$ are non-negative integer numbers⁠³ satisfying $p>0$ and $k+p+q=n-1$. In these terms, $B_nT$ has a commutativity relation $\langle k,{x},p,q\rangle \langle k',{x'},p',q'\rangle = \langle k',{x'},p',q'\rangle \langle k,{x},p,q\rangle$ whenever ${x<x'}$ and $q+{k'}{{}\geq {}} n$, where the former inequality refers to the $T$-order resulting from the embedding. Note that the chosen planar embedding of $T$ rules out weak interactions.

³

Instead of writing the 1-tuples $(p)$ and $(q)$, we have simply written $p$ and $q$.

✖

Theorem 1.7.

For any tree $T$, any non-negative integer $n$ and any commutative ring $R$ with unit 1, there is a set-theoretic inclusion $V_nT\hookrightarrow H^1(B_nT;R)$ so that the faces of $K_nT$ yield, via cup-product of their vertices, a graded basis of $H^*(B_nT;R)$. For instance, the empty face $\varnothing \in K_nT$ corresponds to the unit $1\in H^0(B_nT;R)=R$. Furthermore, any product $\langle k,x,p,q\rangle \cdot \langle k',x',p',q'\rangle$ with $x=x'$ vanishes (in particular cup-squares vanish), as do cup-products of non-interacting elements in $V_nT$.

The only piece of multiplicative information missing in Theorem 1.7, namely a description of cup-products of weak-interacting basis elements in $V_nT$, is fully addressed in Section 5 (see Theorem 5.1) through the concept of “interaction parameters” introduced in Section 4 (Definition 4.3).

Remark 1.8.

The only obstructions for realizing $H^*(B_nT;R)$ in Theorem 1.7 as the exterior face ring determined by $K_nT$ are the non-vanishing products whose factors interact weakly. For trees with binary core, such weak-interacting non-trivial products are effectively ruled out in the final section of this paper (Theorem 6.4) by means of a suitable change of basis that adjusts the inclusion $V_nT\hookrightarrow H^1(B_nT;R)$ in Theorem 1.7.

Remark 1.9.

The results in this paper allow us to recover and generalize Scheirer’s main technical tool 16, Lemma 3.6 for studying Farber’s topological complexity of $B_nT$. Extensions of Scheirer’s results will be the topic of a future publication.

In the rest of the paper we shall omit writing the coefficient ring $R$ in cohomology groups and associated (co)chain complexes.

2. Preliminaries

We start by collecting the ingredients and facts we need: cup-products in the cubical setting 1112, reviewed in Section 2.1, Forman’s discrete Morse theory 89, reviewed in Subsection 2.2, and Farley-Sabalka’s gradient field on Abrams’ discrete model for (ordered and unordered) graph configuration spaces 12613, reviewed in Subsection 2.3. This will set the notation we use in the rest of the paper.

2.1. Cup products in cubical sets

An elementary cube in $\mathbb{R}^k$ is a cartesian product $c=I_1\times \cdots \times I_k$ of intervals $I_i=[m_i,m_i+\epsilon _i]$, where $m_i\in \mathbb{Z}$ and $\epsilon _i\in \{0,1\}$. For simplicity, we write $[m]\coloneq [m,m]$ for a degenerate interval. We say that $c$ is an $\ell$-cube if there are $\ell$ non-degenerate intervals among the cartesian factors $I_j$ of $c$, say $I_{i_1},\ldots ,I_{i_\ell }$ with $1\leq i_1<\cdots <i_\ell \leq k$. In such a case, the product orientation of $c$ is determined by (a) the orientation (from smaller to larger endpoints) of the non-degenerate intervals $I_{i_1},\ldots ,I_{i_\ell }$, and (b) the order $i_1<\cdots <i_\ell$, i.e., the order of factors in the cartesian product. Under these conditions, and for $1\leq r\leq \ell$, set

$$\begin{equation} \begin{aligned} \delta _{2r}(c)&=I_1\times \cdots \times I_{i_r-1}\times [m_{i_r}+1]\times I_{i_r+1}\times \cdots \times I_{k}, \\ \delta _{2r-1}(c)&=I_1\times \cdots \times I_{i_r-1}\times [m_{i_r}]\times I_{i_r+1}\times \cdots \times I_{k}. \end{aligned}{\tag{4}} \end{equation}$$

Then, for a cubical set $X\subset \mathbb{R}^k$, i.e., a union of elementary cubes in $\mathbb{R}^k$, the boundary map $\partial \colon C_\ell (X)\to C_{\ell -1}(X)$ in the oriented cubical chain complex $C_*(X)$ is determined by

$$\begin{equation} \partial \left(c\right)=\sum _{r=1}^\ell (-1)^{r-1}\left(\delta _{2r}(c)-\delta _{2r-1}(c)\right). {\tag{5}} \end{equation}$$

For instance, the oriented cubical boundary of the square $[0,1]\times [0,1]$ can be depicted as

$$\begin{equation*} \vcenter{\img[][172pt][106pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[x=.5cm,y=.5cm] \draw[-&gt;](0,0)--(3,0);\node[below] at (3,0) {\scriptsize${}+[0,1]\times[0]$}; \draw[-&gt;](3,0)--(6,0)--(6,3);\node[right] at (6,3) {\scriptsize${}+[1]\times[0,1]$}; \draw[-&gt;](6,3)--(6,6)--(3,6);\node[above] at (3,6) {\scriptsize${}-[0,1]\times[1]$}; \draw[-&gt;](3,6)--(0,6)--(0,3);\node[left] at (0,3) {\scriptsize${}-[0]\times[0,1]$}; \draw(0,3)--(0,0); \node[left] at (0,0) {\scriptsize$(0,0)$}; \node[left] at (0,6) {\scriptsize$(0,1)$}; \node[right] at (6,6) {\scriptsize$(1,1)$}; \node[right] at (6,0) {\scriptsize$(1,0)$}; \end{tikzpicture}}]{Images/img2fe9158ed19519355d43b4018c33d6c6.svg}} \end{equation*}$$

Example 2.1.

Let $T$ be a tree whose vertices and edges have been ordered as described in the previous section. Think of $T$ as cubical set. In fact, orient the edges of $T$ from the smaller to the larger endpoints and fix an orientation-preserving embedding $T\subset \mathbb{R}^t$ of cubical sets, where elementary cubes in $\mathbb{R}^t$ have product orientation. Thus, a vertex of $T$ becomes a 0-cube $[k_1]\times \cdots \times [k_t]$ in $\mathbb{R}^t$, while an oriented edge in $T$ corresponds in $\mathbb{R}^t$ to an oriented 1-cube $I_1\times \cdots \times I_t$, i.e., an elementary cube whose factors are degenerate, except for one of them.

Cup products in cubical cohomology are fairly similar to their classic simplicial counterparts. At the oriented cubical cochain level, there is a cup product graded map $C^*(X)\times C^*(X)\to C^*(X)$ that is associative, $R$-bilinear and is described on basis elements as follows. Firstly, for intervals $[a,b]$ and $[a',b']$, let

$$\begin{equation*} [a,b]\cdot [a',b']\coloneq \begin{cases}[a,b'] , & \text{if $b=a'$ and either $a=b$ or $a'=b'$ (or both);} \\ 0, & \text{otherwise.}\end{cases} \end{equation*}$$

Then, for elementary cubes $c=I_1\times \cdots \times I_k$ and $d=J_1\times \cdots \times J_k$ in $X$, the cubical cup product $c\cdot d$ of the corresponding basis elements⁠⁴ $c,d\in C^*(X)$ vanishes if either $I_i\cdot J_i=0$ for some $i\in \{1,\ldots ,k\}$ or if $(I_1\cdot J_1)\times \cdots \times (I_k\cdot J_k)$ is not a cube in $X$; otherwise $c\cdot d$ is up to a sign $\epsilon _{c,d}$, the dual of the cube $(I_1\cdot J_1)\times \cdots \times (I_k\cdot J_k)$. Given our product-orientation settings, the sign is given by the usual algebraic-topology convention:

⁴

We shall omit the use of an asterisk for dual elements. The intended meaning will be clear from the context.

✖

$$\begin{equation*} \epsilon _{c,d}=\sum _{j=1}^{k-1}\left(\dim J_j \sum _{i=j+1}^{k}\dim I_i\right). \end{equation*}$$

Remark 2.2.

Particularly agreeable is the fact that a finite cartesian product of cubical sets comes equipped for free with the obvious structure of a cubical set. For instance, in the situation of Example 2.1, the cartesian power $T^n$ is a (product-oriented) cubical set in $\mathbb{R}^{nt}$. In such a setting, an oriented cube $c=c_1\times \cdots \times c_n$ in $T^n$ (where each $c_i$ is either a vertex or an edge of $T$) corresponds in $\mathbb{R}^{nt}$ to an oriented cube $\left(I_{1,1}\times \cdots \times I_{1,t}\right)\times \cdots \times \left(I_{n,1}\times \cdots \times I_{n,t}\right)$ where, for each $i=1,\ldots ,n$, at most one of the intervals $I_{i,1},\ldots ,I_{i,t}$ is non-degenerate. These considerations, coupled with the fact that cubes of a single factor $T$ are at most one-dimensional, yield the next explicit description of cubical cup-products associated to $T$ and $T^n$.

Proposition 2.3.

The cup product in $C^*(T)$ of the duals of a pair of (oriented) cubes $c$ and $d$ in $T$ is given by the dual of

$$\begin{equation*} c\cdot d = \begin{cases} (x,y), & \text{if $c=(x,y)$, an edge of $T$, and $d=y$, a vertex of $T$;} \\ (x,y), & \text{if $c=x$, a vertex of $T$, and $d=(x,y)$, an edge of $T$;} \\ x, & \text{if $c=d=x$, a vertex of $T$;}\\ 0, & \text{otherwise.} \end{cases} \end{equation*}$$

More generally, let $D$ be a (product-oriented) cubical subset of $T^n$. The cup product in $C^*(D)$ of the duals of a pair of cubes $c=c_1\times \cdots \times c_n$ and $d=d_1\times \cdots \times d_n$ in $D$ vanishes provided $c_i\cdot d_i=0$ for some $i\in \{1,\ldots ,n\}$ or, else, provided the cube $c\cdot d\coloneq (c_1\cdot d_1)\times \cdots \times (c_n\cdot d_n)$ is not contained in $D$. Otherwise, the cup product is the multiple $(-1)^{\varepsilon _{c,d}}$ of the dual of $c\cdot d$, where

$$\begin{equation*} \varepsilon _{c,d}=\sum _{j=1}^{n-1}\left(\dim (d_j)\sum _{i=j+1}^n\dim (c_i)\right). \end{equation*}$$

2.2. Discrete Morse theory

Let $X$ denote a finite regular cell complex with face poset $(\mathcal{F},\subset$), i.e., $\mathcal{F}$ is the set of (closed) cells of $X$ partially ordered by inclusion. For a cell $a\in \mathcal{F}$, we write $a^{(p)}$ to indicate that $a$ is $p$-dimensional. We think of the Hasse diagram $H_\mathcal{F}$ of $\mathcal{F}$ as a directed graph: it has vertex set $\mathcal{F}$, while directed edges (called also “arrows”) are given by the family of ordered pairs $(a^{(p+1)},b^{(p)})$ with $b\subset a$. Such an arrow will be denoted as $a^{(p+1)}\searrow b^{(p)}$. Let $W$ be a partial matching on $H_\mathcal{F}$, i.e., a directed subgraph of $H_\mathcal{F}$ whose vertices have degree precisely 1. The modified Hasse diagram $H_\mathcal{F}(W)$ is the directed graph obtained from $H_\mathcal{F}$ by reversing all arrows of $W$. A reversed edge is denoted as $b^{(p)}\nearrow a^{(p+1)}$, in which case $a$ is said to be $W$-collapsible and $b$ is said to be $W$-redundant.

Discrete Morse theory focuses on gradient paths, i.e., directed paths in $H_\mathcal{F}(W)$ given by an alternate chain of up-going and down-going arrows,

$$\begin{equation} a_0\nearrow b_1\searrow a_1\nearrow \cdots \nearrow b_k\searrow a_k \text{ and } c_0\searrow d_1\nearrow c_1\searrow \cdots \searrow d_k\nearrow c_k. {\tag{6}} \end{equation}$$

A gradient path as the one on the left (right) hand-side of 6 is called an upper (respectively, lower) path, and the gradient path is called elementary when $k=1$, or constant when $k=0$. The sets of upper and lower paths that start on a $p$-cell $a$ and end on a $p$-cell $b$ are denoted by $\overline{\Gamma }(a,b)$ and $\underline{\Gamma }(a,b)$, respectively. Concatenation of upper/lower paths $\overline{\Gamma }(a,b)\times \overline{\Gamma }(b,c)\to \overline{\Gamma }(a,c)$ and $\underline{\Gamma }(a,b)\times \underline{\Gamma }(b,c)\to \underline{\Gamma }(a,c)$ is defined in the obvious way; for instance, any upper/lower path is a concatenation of corresponding elementary paths. An upper/lower path is called a cycle if $a_0=a_k$ in the upper case of 6, or $c_0=c_k$ in the lower case. (By construction, the cycle condition can only hold with $k>1$.) The matching $W$ is said to be a gradient field on $X$ if $H_\mathcal{F}(W)$ has no cycles. In such a case, cells of $X$ that are neither $W$-redundant nor $W$-collapsible are said to be $W$-critical or, simply, critical when $W$ is clear from the context. We follow Forman’s convention to use capital letters to denote critical cells.

It is well known that a gradient field on $X$ carries all the homotopy information of $X$. For our purposes, we only 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$-free⁠⁵ module generated in dimension $p\geq 0$ by the duals⁠⁶ 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. In the elementary case, multiplicity is given by

⁵

Cochain coefficients are taken in a ground ring $R$, as we are interested in cup-products.

✖

⁶

Recall we omit the use of an asterisk for dual elements.

✖

$$\begin{equation} \mu (a_0\nearrow b_1\searrow a_1)=-\iota _{a_0,b_1}\cdot \iota _{a_1,b_1}\text{ and } \mu (c_0\searrow d_1\nearrow c_1)=-\iota _{d_1,c_0}\cdot \iota _{d_1,c_1}, {\tag{7}} \end{equation}$$

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

$$\begin{equation} \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. {\tag{8}} \end{equation}$$

In other words, the Morse theoretic incidence number of $A$ and $B$ is given by the number of “mixed” gradient paths $\overline{\gamma }$ from $B$ to $A$ given as the concatenation of an arrow $B\searrow b$ and a path $\gamma \in \overline{\Gamma }(b,A)$, counted with multiplicity $\mu (\overline{\gamma })\coloneq \iota _{b,B}\cdot \mu (\gamma )$.

Gradient paths yield, in addition, a homotopy equivalence between $\mathcal{M}^*(X)$ and the usual cellular cochain complex $C^*(X)$. Indeed, the formulae

$$\begin{equation} \overline{\Phi }(A^{(p)})=\sum _{a^{(p)}}\left(\sum _{\gamma \in \overline{\Gamma }(a,A)}\mu (\gamma )\right)a \qquad \text{and}\qquad \underline{\Phi }(a^{(p)})=\sum _{A^{(p)}}\left(\sum _{\gamma \in \underline{\Gamma }(A,a)}\mu (\gamma )\right)A {\tag{9}} \end{equation}$$

define (on generators) cochain maps $\overline{\Phi }\colon \mathcal{M}^*(X)\to C^*(X)$ and $\underline{\Phi }\colon C^*(X)\to \mathcal{M}^*(X)$ inducing cohomology isomorphisms $\overline{\Phi }^*$ and $\underline{\Phi }^*$ with $(\underline{\Phi }^*)^{-1}=\overline{\Phi }^*$.

2.3. Abrams discrete model and Farley-Sabalka’s gradient field

For a tree $T$, think of $T^n$ as the cubical set described in Remark 2.2. Abrams discrete model for $\operatorname {Conf}_nT$ is the largest cubical subset $\operatorname {D}_n T$ of $T^n$ inside $\operatorname {Conf}_nT$. In other words, $\operatorname {D}_n T$ is obtained by removing open cubes from $T^n$ whose closures intersect the fat diagonal. As usual, the symmetric group $\Sigma _n$ acts on the right of $\operatorname {D}_n T$ by permuting factors. The action permutes in fact cubes, and the quotient complex is denoted by $\operatorname {UD}_n T$. Following Farley-Sabalka’s lead, from now on we use the notation $(a_1,\ldots ,a_n)$, and even $(a)$, for a cube $a_1\times \cdots \times a_n$ in $T^n$ (so each $a_i$ is either a vertex or an edge of $T$), and the notation $\{a_1,\ldots ,a_n\}$, and even $\{a\}$, for the corresponding $\Sigma _n$-orbit. Beware not to confuse the parenthesis notation with a point of $T^n$, or the braces notation with a set of elements of $T$—even if all the $a_i$’s are vertices. The “coordinates” $a_i$ in a cube $(a)$ or in its $\Sigma _n$-orbit $\{a\}$ are referred to as the ingredients of the cube. Closures of ingredients of cubes in $D_nT$ and $\operatorname {UD}_n T$ are therefore pairwise disjoint.

In his Ph.D. thesis, Abrams showed that $\operatorname {D}_n T$ is a $\Sigma _n$-equivariant strong deformation retract of $\operatorname {Conf}_nT$ provided $T$ is $n$-sufficiently subdivided in the sense that each path in $T$ between distinct vertices of degree not equal to 2 passes through at least $n-1$ edges. Such a condition will be in force throughout the paper, although it is not a real restriction because $T$ can be subdivided as needed without altering the homeomorphism type of its configuration spaces. The $\Sigma _n$-equivariance of the strong deformation retraction above implies that $\operatorname {UD}_n T$ is a strong deformation retract of $\operatorname {UConf}_nT$. Consequently, we will switch attention from $\operatorname {Conf}_nT$ and $\operatorname {UConf}_nT$ to their homotopy equivalent discrete models $\operatorname {D}_n T$ and $\operatorname {UD}_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)$—recall this requires $y<x$. Let $c$ be a cube either in $\operatorname {D}_n T$ or $\operatorname {UD}_n T$. A vertex-ingredient $x$ of $c$ is said to be blocked in $c$ if $x=0$ or, else, if replacing in $c$ the ingredient $x$ by the edge $e_x$ fails to render a cube in the corresponding discrete model; $x$ is said to be unblocked in $c$ otherwise. An edge-ingredient $e$ of a cube $c$ is said to be order-disrespectful 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$ adjacent 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-disrespectful edge ingredients in $c$ are said to be critical. Farley-Sabalka’s gradient field (on $\operatorname {D}_n T$ and $\operatorname {UD}_n T$) then works as follows. Order the ingredients of a cube $c$ by their $T$-ordering (as described in Section 1), and look for non-critical ingredients:

(i)

If the first such ingredient is an unblocked vertex $y$ in $c$, then $c$ is redundant, and one sets $c\nearrow c'$, where $c'$ is the cube obtained from $c$ by replacing $y$ by $e_y$. We say that the pairing $c\nearrow c'$ creates the edge $e_y$. In this case $e_y$ is an order-respecting edge in $c'$, and all ingredients of $c'$ smaller than $e_y$ are critical.

(ii)

If the first such ingredient is an order-respecting edge $(w,z)$ in $c$, then $c$ is collapsible, and one sets $c''\nearrow c$, where $c''$ is the cube obtained from $c$ by replacing $(w,z)$ by $z$. Again, we say that the edge $(w,z)$ is created by the pairing $c''\nearrow c$. In this case $z$ is an unblocked vertex in $c''$, and all ingredients of $c''$ smaller than $e_z$ are critical.

(iii)

If all ingredients of $c$ are critical, then $c$ is critical.

Definition 2.4.

For a vertex $x$ and a non-negative integer $t$, let $S_x(t)$ stand for the family of vertices $x,x+1,\ldots ,x+t-1$. We think of $S_x(t)$ as a size-$t$ stack of vertices supported by $x$. Whenever we use such a stack of vertices, the $n$-sufficiently subdivided condition on $T$ will assure the existence of the required $t$ vertices. Furthermore, for $\ell \in \{0,1,\ldots ,d(x)-1\}$, let $x[\ell ]$ denote the vertex adjacent to $x$ that lies in $x$-direction $\ell$. For instance $x[0]=x-1$ and $x[1]=x+1$, if $x$ is essential.

As illustrated in Figures 5 and 6, ingredients of a critical $m$-cube are spelled out through

(a)

a stack $S_0(k)$ of $k$ vertices supported by the root (here $k\geq 0$, i.e., $S_0(k)$ can be empty);

(b)

$m$ pairwise different essential vertices $x_1,\ldots ,x_m$ of $T$ and, for each $i=1,2,\ldots ,m$, an order-disrespectful edge $(x_i,{x_i[r_i+1]})$ with $1\leq r_i< d(x_i)-1$;

(c)

for each $i=1,2,\ldots ,m$ and each $\ell =1,2,\ldots ,d(x_i)-1$, a stack $S_{i,\ell }=S_{y_{i,\ell }}(t_{i,\ell })$ of $t_{i,\ell }$ vertices supported by the vertex$$\begin{equation*} { y_{i,\ell }\coloneq \begin{cases} x_i[\ell ], & \text{if $\ell \neq r_i+1;$} \\ x_i[\ell ]+1, & \text{if $\ell =r_i+1$,} \end{cases} } \end{equation*}$$

subject to the requirements

(d)

some stacks $S_{i,\ell }$ might be empty, i.e., $t_{i,\ell }\geq 0$ for all $i$ and $\ell$. Yet, for each $i$, there must exist an $\ell \in \{1,2,\ldots , r_i\}$ with $t_{i,\ell }>0$ (recall that $(x_i,x_i[r_i+1])$ is order-disrespectful);

(e)

$k+m+\sum _{i,\ell }t_{i,\ell }=n$, i.e., the total number of ingredients is $n$.

The critical cube in the unordered discrete model $\operatorname {UD}_n T$ determined by the above information will be denoted as

$$\begin{equation} \left\{k \vert x_1,p_1,q_{1} \vert \cdots \vert x_m, p_m,q_m \right\}, {\tag{10}} \end{equation}$$

where $p_i={(t_{i,1},\dots , t_{i,r_i})}$ and $q_i ={(t_{i,r_i+1}, \dots , t_{i,d(x_i)-1})}$. Vertical bars are meant to stress the fact that each pair of parameters $p_{i}$ and $q_{i}$ is ordered and attached to $x_i$. Other than that, 10 is indeed a set formed by the triples $(x_i,p_{i},q_{i})$ and the singleton $k$. Figure 6 illustrates a typical critical cube.

Remark 2.5.

In any arrow ${d}\nearrow {c}$ of Farley-Sabalka’s modified Hasse diagram, ${d}$ is an even face of ${c}$, i.e., in the notation of 4, ${d}=\delta _{2r}({c})$ for some $r\in \{1,2,\ldots ,\dim ({c})\}$.

Remark 2.6.

By construction, Farley-Sabalka’s gradient field in $\operatorname {D}_n T$ is $\Sigma _n$-equivariant and, by passing to the quotient, it yields the corresponding gradient field in $\operatorname {UD}_n T$. Consequently, gradient paths can equivalently be analyzed in either the ordered or unordered settings. Indeed, a gradient path in $\operatorname {UD}_n T$ corresponds to a “$\Sigma _n$-orbit” of gradient paths in $\operatorname {D}_n T$. Due to the cup-product descriptions in Subsection 2.1, we find it more convenient to perform the gradient-path analysis at the level of the cubical set $\operatorname {D}_n T$.

3. Gradient-path dynamics

Recall from Subsection 2.1 that the product orientation of a $p$-dimensional cube $(c_1,\ldots ,c_n)$ in $\operatorname {D}_n T$ depends on (the orientation of edges—from the smaller to the larger vertex—in $T$ and on) the coordinate order $c_{i_1},\ldots ,c_{i_p}$, i.e. where $i_1<\cdots <i_p$, of the edge-ingredients. In particular, the quotient cube $\{c_1,\ldots ,c_n\}$ in $\operatorname {UD}_n T$ inherits no well defined orientation. Definition 3.1 avoids the problem and is well suited for the analysis of gradient paths in $\operatorname {D}_n T$.

Definition 3.1 (Gradient orientation, cf. Subsection 2.3 of 5).

The listing $(x_1,y_1)$, $\ldots$, $(x_p,y_p)$ of edge-ingredients of a $p$-cube $c$ in $\operatorname {D}_n T$ or in $\operatorname {UD}_n T$ is said to be in gradient order if $x_1<\cdots <x_p$, where the latter is the $T$-ordering of vertices discussed in Section 1. The gradient orientation of $c$ is defined just as the product orientation, except that the gradient order of the edge-ingredients is used (rather than the coordinate order).

In the rest of the paper, and unless explicitly noted otherwise, we use gradient orientations. In doing so, the definitions of the cubes $\delta _{2r}(c)$ and $\delta _{2r-1}(c)$ in 4 require a corresponding adjustment. Namely, if the edge-ingredients of a $p$-cube $c$ are listed in gradient order as $(x_1,y_1),\ldots ,(x_p,y_p)$, then replacing the edge $(x_r,y_r)$ by the vertex $y_r$ or $x_r$ yields $\delta _{2r}(c)$ or $\delta _{2r-1}(c)$, respectively. Remark 2.5 and the expression in 5 for cubical boundaries then remain unaltered. A first advantage of gradient orientations is that the map induced at the cochain level by the projection $\pi \colon \operatorname {D}_n T\to \operatorname {UD}_n T$ involves no signs,

$$\begin{equation} \pi ^*(\{c\})=\sum _{\sigma \in \Sigma _n}(c)\cdot \sigma . {\tag{11}} \end{equation}$$

(Recall we omit asterisks for duals.) In view of Remark 2.6, the homotopy equivalences in 9 satisfy:

Lemma 3.2.

The following diagram is commutative:

$$\begin{equation*} \vcenter{\img[][210pt][60pt][{$\xymatrix{ \mathcal{M}^*(\DnT)\ar[r] \ar[r]^{\overline{\Phi}} &amp; C^*(\DnT)\ar[r] \ar[r]^{\underline{\Phi}} &amp; \mathcal{M}^*(\DnT) \\ \mathcal{M}^*(\UDnT)\ar[r] \ar[u]^{\pi^*} \ar[r]_{\overline{\Phi}} &amp; C^*(\UDnT)\ar[r] \ar[u]^{\pi^*} \ar[r]_{\underline{\Phi}} &amp; \mathcal{M}^*(\UDnT). \ar[u]^{\pi^*} }$}]{Images/img3d1d38d631ebc9b1b3d886e5935fdce1.svg}} \end{equation*}$$

Remark 3.3.

The Morse differential in $\operatorname {UD}_n T$ is trivial (see 4 or Proposition 3.10). Therefore, for each $m\geq 0$, a graded basis of $H^m(\operatorname {UD}_n T)$ is given by the cohomology classes of the $\overline{\Phi }$-images of the duals of the critical cubes 10. By abuse of notation,⁠⁷ the $\pi ^*$-image⁠⁸ of the cohomology class so determined will also be denoted by the corresponding expression 10. There is no loss of information because vertical maps in the previous diagram are injective and, more importantly, they induce injections in cohomology (the latter assertion follows from a standard transfer argument and the torsion-freeness of $H^*(\operatorname {UD}_n T)$).

⁷

The context clarifies the meaning.

✖

⁸

We prefer to compute products in the ordered setting in view of the explicit descriptions in Subsection 2.1.

✖

This section’s goal is the description of a cocycle in $C^*(\operatorname {D}_n T)$ that represents a given cohomology class $\{k\vert x,p,q\}\in \operatorname {Im}(\pi ^*)$ (Proposition 3.9). This requires the following discussion of dynamics for upper-paths that end at critical cubes.

Definition 3.4.

An edge-ingredient $(x,y)$ of a cube $c$ of $\operatorname {D}_n T$ is said to be

•

edge order-respecting in $c$, written as “$(x,y)$ is $\operatorname {eor}(c)$”, if there are no edge-ingredients $(a,b)$ in $c$ with $x<a<b<y$.

•

strongly order-respecting in $c$, written as “$(x,y)$ is $\operatorname {sor}(c)$”, if $(x,y)$ is $\operatorname {eor}(c)$ and there is no vertex-ingredient $v$ in $c$ with $x<v<y$.

A Farley-Sabalka pairing $\delta _{2i}(c)\nearrow c$ that creates an edge-ingredient that is $\operatorname {sor}(c)$ is said to be of sor type; otherwise, it is said to be of branch type. Likewise, $\delta _{2i}(c)\nearrow c$ is said to be of eor type if the edge-ingredient it creates is $\operatorname {eor}(c)$. An upper elementary path $\delta _{2i}(c)\nearrow c\searrow \delta _j(c)$ is said to be of falling-vertex type (sor type, branch type, respectively) provided $j=2i-1$ ($\delta _{2i}(c)\nearrow c$ is of sor type, $\delta _{2i}(c)\nearrow c$ is of branch type, respectively).

Note that if $y$ is the vertex-ingredient in $\delta _{2i}(c)$ that is responsible for a pairing $\delta _{2i}(c)\nearrow c$, say creating the edge-ingredient $(x,y)$ of $c$, then $\delta _{2i-1}(c)$ is obtained from $\delta _{2i}(c)$ by replacing the vertex $y$ by $x$. In other words, in the falling-vertex type path $\delta _{2i}(c)\nearrow c\searrow \delta _{2i-1}(c)$, the vertex-ingredient $y$ “falls” to its predecessor $x$. In particular, elementary paths of falling-vertex type have multiplicity 1.

Example 3.5.

Any edge-ingredient $(x,x+1)$ of $c$ is $\operatorname {sor}(c)$. On the other hand, for an essential vertex $x$ and a positive direction $\ell \in \{1,2,\ldots ,d(x)-1\}$ from $x$, an edge-ingredient $(x,{x[\ell ]})$ of $c$ is $\operatorname {sor}(c)$ if and only if $c$ has no ingredient, neither vertex nor edge, in any of the components of $T\setminus \{x\}$ lying in $x$-directions $1,2,\ldots ,\ell -1$. Furthermore, if $(x,y)$ is an edge-ingredient of a face $\delta _j(c)$ of some cube $c$ of $\operatorname {D}_n T$, then $(x,y)$ is $\operatorname {sor}(\delta _j(c))$ if and only if $(x,y)$ is $\operatorname {sor}(c)$.

The final observation in Example 3.5 is freely used in the proof of:

Proposition 3.6.

Let $(x_1,y_1),\ldots ,(x_p,y_p)$ be the gradient-order listing of the edge-ingredients of a $p$-cube $c$ in $\operatorname {D}_n T$.

(1)

If an arrow $\delta _{2i}(c)\nearrow c$ in the modified Hasse diagram for $\operatorname {D}_n T$ is of eor type, then $(x_i,y_i)$ is ${\operatorname {sor}(c)}$ and, for any $k>2i$, $\delta _k(c)$ is collapsible.

(2)

If the edge $(x_i,y_i)$ is $\operatorname {sor}(c)$, then there is no upper path starting at a face $\delta _{j}(c)$ with $j<2i-1$ and ending at a critical cube.

Proof.

(1) By definition, $\delta _{2i}(c)\nearrow c$ creates the edge-ingredient $(x_i,y_i)$, which is assumed to be $\operatorname {eor}(c)$. Since ingredients of $\delta _{2i}(c)$ smaller than $y_i$ are critical, $(x_i,y_i)$ is in fact $\operatorname {sor}(c)$. Thus, for $k\neq 2i,2i-1$, $(x_i,y_i)$ is $\operatorname {sor}(\delta _k(x))$ and, therefore, order-respecting in $\delta _k(x)$. On the other hand, for $k>2i$, $\delta _k(c)$ and $c$ have the same ingredients smaller than $y_i$, so that all ingredients in $\delta _k(c)$ smaller than $(x_i,y_i)$ are critical. Thus, by definition, $\delta _k(x)$ is collapsible for $k>2i$.

(2) Under the stated hypothesis, assume (for a contradiction) there is a gradient path

$$\begin{equation} c\searrow \delta _j(c)\eqcolon c_0\nearrow d_1\searrow c_1\nearrow \cdots \nearrow d_m\searrow c_m {\tag{12}} \end{equation}$$

with $j<2i-1$, $m\geq 0$ and $c_m$ critical. Then $(x_i,y_i)$ is $\operatorname {sor}(c_0)$ and, in particular, $(x_i,y_i)$ is order-respecting in $c_0$, which forces $m>0$. Recursively, if $(x_i,y_i)$ is an edge-ingredient of both $c_{\ell -1}$ and $c_\ell$ (and so of $d_\ell$), and $(x_i,y_i)$ is $\operatorname {sor}(c_{\ell -1})$, then $(x_i,y_i)$ is forced to be ($\operatorname {sor}(d_\ell )$ and, thus,) $\operatorname {sor}(c_\ell )$. It is not possible that $(x_i,y_i)$ is an edge-ingredient of all the $c_\ell$’s, for then $(x_i,y_i)$ would be $\operatorname {sor}(c_m)$, which is impossible as $c_m$ is critical. Let $k$ be the first integer ($1\leq k\leq m$) for which $(x_i,y_i)$ is not an ingredient of $c_k$—so that $(x_i,y_i)$ is $\operatorname {sor}(c_\ell )$ for $0\leq \ell <k$. In particular, $(x_i,y_i)$ is order-respecting in $c_{k-1}$. Thus, the vertex-ingredient $v$ of $c_{k-1}$ responsible for the pairing $c_{k-1}\nearrow d_k$ in 12 satisfies $v<y_i$ and, in fact, $v<x_i$, since $(x_i,y_i)$ is $\operatorname {sor}(c_{k-1})$. On the other hand, since the edge $(u,v)$ created by $c_{k-1}\nearrow d_k$ is order-respecting in $d_k$, and since $c_k$ is obtained from $d_k$ by replacing the edge $(x_i,y_i)$ by either $x_i$ or $y_i$, the inequalities $u<v<x_i<y_i$ yield that

$$\begin{equation} \text{$(u,v)$ is order-respecting in $c_k$ too.} {\tag{13}} \end{equation}$$

In particular, $c_k$ is not critical, so $k<m$. Let $w$ be the vertex-ingredient of $c_k$ responsible for the pairing $c_k\nearrow d_{k+1}$. By 13, we get the first inequality in $w<v<x_i<y_i$, so

•

($w$ is an ingredient of $c_k$) $\Rightarrow$ ($w$ is an ingredient of $d_k$ and, therefore, of $c_{k-1}$);

•

($w$ is unblocked in $c_k$) $\Rightarrow$ ($w$ is unblocked in $d_k$ and, therefore, in $c_{k-1}$).

But, by definition, $v$ is the minimal unblocked vertex in $c_{k-1}$, so $v\leq w$, a contradiction.

■

Proposition 3.6 implies that upper paths ending at critical cubes have a forced behavior most of the time:

Corollary 3.7.

Let $\gamma$ be an upper path in $\operatorname {D}_n T$ that ends at a critical cube. Any upper elementary factor of $\gamma$ of sor type is of falling-vertex type.

Example 3.8.

Let us be specific about the dynamics of an upper path $\gamma \colon c_0\nearrow d_1\searrow c_1\nearrow \cdots \searrow c_m$ that ends at a critical 1-cube $c_m$. By the $\Sigma _n$-equivariance of the gradient field, we can assume $c_0=(u_1,\ldots ,u_i,v_1,\ldots ,v_j,(y,{y[d]}),w_1,\ldots ,w_k)$ with $d\in \{1,2,\ldots ,d(y)-1\}$ and

$$\begin{equation*} u_1<\cdots <u_i<y<v_1<\cdots <v_j<{y[d]}<w_1<\cdots < w_k, \end{equation*}$$

i.e., $c_0$ is the $\Sigma _n$-orbit representative whose ingredients appear in the $T$-ordering. By Corollary 3.7, the start of $\gamma$ is forced to consist of falling-vertex elementary paths, where the vertices $u_1,\ldots ,u_i$ fall, each at a time, until they form the stack $S_0(i)$ of $i$ vertices supported (and blocked) by the root. At that point $\gamma$ arrives at the 1-cube $(S_0(i),v_1,\ldots ,v_j,(y,{y[d]}),w_1,\ldots ,w_k),$ and we see that $j$ must be positive, for otherwise $\gamma$ would have reached a collapsible $1$-cube. In particular $y$ must be an essential vertex and $d>1$. Then, again by Corollary 3.7, it is the turn of vertices $v_1,\ldots ,v_j$ that are forced to fall, each at a time, until they form stacks $S_{y[\ell ]}(t_\ell )$ of vertices blocked by $y$ in $y$-directions $\ell =1,\ldots ,d-1$. At that point $\gamma$ arrives at a 1-cube of the form

$$\begin{equation} {\left(S_0(i),S_{y[1]}(t_1),\ldots ,S_{y[d-1]}(t_{d-1}),(y,y[d]),w_1,\ldots ,w_k\right).} {\tag{14}} \end{equation}$$

Not all of the stacks $S_{y[\ell ]}(t_\ell )$ are empty, so 14 has $(y,{y[d]})$ as a critical edge-ingredient. The falling-vertex process is also forced by Corollary 3.7 on those vertices $w_1,\ldots ,w_k$ that are located in positive $y$-directions (if any), and this takes $\gamma$ to a 1-cube of the form

$$\begin{multline*} (S_0(i),S_{y[1]}(t_1),\ldots ,S_{y[d-1]}(t_{d-1}),(y,y[d]),S_{y[d]+1}(t_d),S_{y[d+1]}(t_{d+1}),\\ \ldots ,S_{y[d(y)-1]}(t_{d(y)-1}),w_\rho ,\ldots ,w_k), \end{multline*}$$

with $w_\rho ,\ldots ,w_k$ all lying in $y$-direction 0. Branching starts from this point on, with explicit options discussed in the next paragraph.

If no vertices $w_\rho ,\ldots ,w_k$ are left, then $\gamma$ would have reached its final critical destination $c_m$. Otherwise, $w_{\rho }$ is forced to fall until $\gamma$ reaches, via some branch type pairing $c_{{\lambda }}\nearrow d_{{\lambda }+1}$, the 2-cube $d_{{\lambda }+1}$ depicted in Figure 7. At this point there are two options for $d_{{\lambda }+1}\searrow c_{{\lambda }+1}$. In the first option, $c_{{\lambda }+1}$ is obtained from $d_{{\lambda }+1}$ by replacing the recently created edge $(x,{x[d']})$ by $x$, i.e., with an upper elementary path $c_{{\lambda }}\nearrow d_{{\lambda }+1}\searrow c_{{\lambda }+1}$ of falling-vertex type. In such a case, $\gamma$ is forced to continue with the vertex $x$ falling until it is added to the stack of vertices blocked by the root 0. This leaves us at a situation similar to the one at the start of this paragraph. In the second option, $c_{{\lambda }+1}$ is obtained from $d_{{\lambda }+1}$ by replacing the edge $(y,{y[d]})$ by either of its end points. In such a case, $\gamma$ is forced to continue:

(1)

with the falling of the vertices that are now unblocked in the neighborhood of $y$ (see Figure 7), until they form a stack of vertices blocked by $x$—thus starting a critical situation around the edge $(x,x[d'])$—and, then,

(2)

with the falling of the vertices (if any) in $x$-directions from $d'$ to $d(x)-1$, which form (possibly empty) stacks of vertices blocked either by $x$ or ${x[d']}$ —thus completing the critical situation around the edge $(x,x[d'])$.

Again, this leaves us at a situation similar to the one at the start of this paragraph, but now with the edge $(x,{x[d']})$ playing the role of the edge $(y,{y[d]})$. The branching process in this paragraph then repeats, necessarily a finite number of times, until all vertices $w_{{\rho }},\ldots ,w_k$ have been considered, when $\gamma$ reaches its critical destination $c_m$.

Proposition 3.9.

A cocycle in $C^*(\operatorname {D}_n T)$ representing a 1-dimensional cohomology class $\{k\vert x,p,q\}$ in $\operatorname {Im}(\pi ^*)$, with $p=(p_1,\ldots ,p_r)$ and $q=(q_1,\ldots ,q_s)$, is given by

$$\begin{equation} \sum \left(u_1,\ldots ,u_k,v_1,\ldots ,v_{|p|},(x,{x[r+1]}),w_1,\ldots ,w_{|q|}\right)\cdot \sigma , {\tag{15}} \end{equation}$$

where the summation runs over

•

all permutations $\sigma \in \Sigma _n$,

•

all possible vertices $u_1<\cdots <u_k$ in the component of $T\setminus \{x\}$ in $x$-direction 0,

•

all possible vertices $v_1<\cdots <v_{|p|}$ in the components of $T\setminus \{x\}$ in $x$-directions from $1$ to $r$ so that, for $i\in \{1,\ldots , r\}$, $p_i$ of the vertices $v_1<\cdots <v_{|p|}$ lie in $x$-direction $i$,

•

all possible vertices $w_1<\cdots <w_{|q|}$ in the components of $T\setminus \{x\}$ in $x$-directions greater than $r$ so that, for $j\in \{r+1,\ldots , d(x)-1\}$, $q_{j-r}$ of the vertices $w_1<\cdots <w_{|q|}$ lie in $x$-direction $j$.

Proof.

By construction, the representing cocycle $z$ we need is obtained by chasing, on the left square of the diagram in Lemma 3.2, the dual of the unordered critical cube $\{c\}$ whose ordered critical representative is

$$\begin{multline*} (c)\coloneq (S_0(k),S_{x[1]}(p_1),\ldots ,S_{x[r]}(p_r),(x,x[r+1]),S_{x[r+1]+1}(q_1),S_{x[r+2]}(q_2),\\ \ldots , S_{x[d(x)-1]}(q_s)). \end{multline*}$$

By 9 and 11,

$$\begin{equation} z=\overline{\Phi }\circ \pi ^*\left({\{c\}}\right)=\sum _{\gamma \in \mathcal{G}}\mu (\gamma )\cdot \mathcal{S}_\gamma , {\tag{16}} \end{equation}$$

where $\mathcal{G}$ is the set of upper paths $\gamma$ that start at a 1-cube $\mathcal{S}_\gamma$ and finish at a 1-cube of the form $c\cdot \sigma$ with $\sigma \in \Sigma _n$. Let $\mathcal{G}'$ be the set of paths $\gamma \in \mathcal{G}$ all of whose upper elementary factors are of falling-vertex type. Since $\mu (\gamma )=1$ for $\gamma \in \mathcal{G}'$, the analysis in Example 3.8 shows that the summands in 15 arise from the summands in 16 with $\gamma \in \mathcal{G}'$. It thus suffices to show

$$\begin{equation} \sum _{\gamma \in \mathcal{G}\setminus \mathcal{G}'}\mu (\gamma )\cdot \mathcal{S}_\gamma =0, {\tag{17}} \end{equation}$$

which will be done by constructing an involution $\iota \colon \mathcal{G}\setminus \mathcal{G}'\to \mathcal{G}\setminus \mathcal{G}'$ such that every pair of paths $\gamma$ and $\iota (\gamma )$ has the same origin but opposite multiplicities, i.e.,

$$\begin{equation} \mathcal{S}_{\iota (\gamma )}=\mathcal{S}_{\gamma }\quad \text{and}\quad \mu (\iota (\gamma ))=-\mu (\gamma ) {\tag{18}} \end{equation}$$

—thus their contributions to 17 cancel each other out. For a path $\gamma \in \mathcal{G}\setminus \mathcal{G}'$, let $\gamma _\text{last}=\left(c\nearrow d\searrow e\right)$ denote the last elementary factor of $\gamma$ that is not of falling-vertex type. In the notation of Example 3.8, $e$ is obtained from $d$ by replacing an edge $(y,{y[d]})$ by either $y$ or ${y[d]}$, and both options are possible. Then $\iota (\gamma )$ is defined so to start with the same factorization of $\gamma$ into elementary paths, except for the elementary factor $\gamma _\text{last}$, for which the other end-point of $(y,{y[d]})$ is taken, and after which the rest of the elementary factors are of falling-vertex type—just like for $\gamma$. Note that the ending 1-cubes of $\gamma$ and $\iota (\gamma )$ lie in the same $\Sigma _n$-orbit, so $\iota (\gamma )\in \mathcal{G}\setminus \mathcal{G}'$. The required properties 18 follow from (the construction and from) the fact that elementary paths of falling-vertex type have multiplicity 1.

■

The cancelation phenomenon in the previous proof allows us to give an easy gradient-path explanation of the main result in 4: the vanishing of the Morse differential in $\operatorname {UD}_n T$. A variant of the cancellation phenomenon will also play an important role in our evaluation of cup products (Theorem 5.1). Thus, in preparation for that argument, we spell out the gradient proof of:

Proposition 3.10.

The Morse differential in $\operatorname {UD}_n T$ vanishes.

Proof.

By Remark 2.6, it suffices to do the gradient path analysis directly at the level of $\operatorname {UD}_n T$. For a pair of unordered critical cubes $c^{(k)}$ and $d^{(k-1)}$, let $\Gamma (c,d)$ be the set of mixed gradient paths ${\gamma }\colon c\searrow \bullet \nearrow \bullet \searrow \cdots \searrow d$. By 8, we only need to construct an involution $\iota \colon \Gamma (c,d)\to \Gamma (c,d)$ so that, for every $\gamma \in \Gamma (c,d)$, $\mu (\iota (\gamma ))=-\mu (\gamma )$. (Recall that the multiplicity of $\gamma \in \Gamma (c,d)$ is the incidence number for $c\searrow \bullet$ multiplied by the multiplicity of the remaining upper path $\bullet \nearrow \bullet \searrow \cdots \searrow d$.) Let $\Gamma (c,d)_{\text{fall}}$ consist of the paths in $\Gamma (c,d)$ all of whose upper elementary factors are of falling-vertex type. The definition of the restricted $\iota _{\text{fall}}\colon \Gamma (c,d)_{\text{fall}}\to \Gamma (c,d)_{\text{fall}}$ uses the two forms of replacing by a vertex the edge-ingredient at the start of the path. Likewise, for $\Gamma (c,d)_{\text{branch}}\coloneq \Gamma (c,d)-\Gamma (c,d)_{\text{fall}}$, the definition of the restricted $\iota _{\text{branch}}\colon \Gamma (c,d)_{\text{branch}}\to \Gamma (c,d)_{\text{branch}}$ uses the two forms of replacing by a vertex the edge ingredient at the last upper elementary factor that is not of falling-vertex type.

■

Propositions 2.3 and 3.9 immediately yield:

Corollary 3.11.

The product of two basis elements $\{k,x,p,q\},\{k',x',p',q'\}\in \operatorname {Im}(\pi ^*)$ vanishes provided $x=x'$. In particular, squares of 1-dimensional elements in $\operatorname {Im}(\pi ^*)$ are trivial.

4. Cup products I: Upper gradient paths

The goal for this section and the next one is to get at a workable description of products

$$\begin{multline} \left\{k_1\Big \vert x_1,(p_{1,1},\ldots ,p_{1,r_1}),(q_{1,1},\ldots ,q_{1,s_1})\right\}{\cdots }\\ \left\{k_m\Big \vert x_m,(p_{m,1},\ldots ,p_{m,r_m}),(q_{m,1},\ldots ,q_{m,s_m})\right\} {\tag{19}} \end{multline}$$

in $\operatorname {Im}(\pi ^*)$. Associated to such a product, from now on we set $p_i\coloneq (p_{i,1},\ldots ,p_{i,r_i})$, $q_i\coloneq (q_{i,1},\ldots ,q_{i,s_i})$, $|p_i|\coloneq \sum _{\ell =1}^{r_i}p_{i,\ell }$, $|q_i|\coloneq \sum _{\ell =1}^{s_i}q_{i,\ell }$, and make free use of (i) the order-disrespectful edge $(x_i,x_i[r_i+1])$ encoded in the $i$-th factor of 19, of (ii) the conditions $k_i+\sum _{j} p_{i,j}+\sum _{j'} q_{i,j'}=n-1$, $r_i+s_i=d(x_i)-1$ and $r_i,s_i\geq 1$, and of (iii) the fact that, for each $i$, $k_i$ and all of the $p_{i,\ell }$ and $q_{i,\ell }$ are non-negative, with not all of the $p_{i,\ell }$ being zero. Additionally, in view of Corollary 3.11, we can safely assume $x_1<\cdots <x_m$. Last, we use the shorthand

$$\begin{equation*} d_i\coloneq d(x_i)-1 \text{ and }\overline{x}_i\coloneq x_i[r_i+1]. \end{equation*}$$

We start by tuning up the definition in Section 1 of the components $C_{i,{\ell _i}}$ of $T\setminus \{x_1,\ldots ,x_m\}$.

Definition 4.1 (Leaves and pruned trees).

Set $T_{0,1}\coloneq C_{0,1}$ and, for $1\leq i\leq m$ and $1 \leq {\ell _i} \leq d(x_i)-1$,

$$\begin{equation*} {T_{i,\ell _i} \coloneq \begin{cases} C_{i,\ell _i}\cup \{x_i\}, & \text{if $\ell _i \neq r_i+1$;} \\ C_{i,\ell _i}\setminus \text{Int}(x_i,\overline{x}_i), & \text{if $\ell _i=r_i+1$,} \end{cases}} \end{equation*}$$

where $\text{Int}(x_i,\overline{x}_i)$ stands for the interior of the edge $(x_i,\overline{x}_i)$. We think of each $T_{i,{\ell _i}}$ $(0\leq i\leq m)$ as a rooted but possibly pruned tree. Namely, in the notation of Section 1 and setting $x_0\coloneq 0$, the root of $T_{i,{\ell _i}}$ is $x_i$, if $i=0$ or if $i>0$ with $\ell _i\neq r_i+1$, whereas the root of $T_{i,r_i+1}$ is $\overline{x}_i$. Furthermore, the set of pruned leaves of $T_{i,{\ell _i}}$ is $L_{i,{\ell _i}}\coloneq B(C_{i,{\ell _i}})\setminus \{x_i\}$.

Remark 4.2.

Just as the sets $L_{i,{\ell _i}}$ give a partition of $\{x_1,\ldots ,x_m\}$, the union of the trees $T_{i,{\ell _i}}$ agrees with the difference $T\setminus \bigcup _{i=1}^m\text{Int}(x_i,\overline{x}_i)$. Actually, each vertex of $T$ other than $x_i$ for $1 \leq i \leq m$, as well as each semi-open edge $(x,y)\setminus \{y\}$ of $T$ not of the form $(x_i,\overline{x}_i)\setminus \{\overline{x}_i\}$ with $1\leq i\leq m$, belongs to a tree $T_{i,{\ell _i}}$ for a unique $\ell _i$.

Definition 1.4 is recast by the second part of:

Definition 4.3.

(1)

For a $\tau$-tuple of integers $t=(t_1,\ldots ,t_\tau )$, we write $t \geq 0$ to mean that $t_j\geq 0$ for all $j\in \{1,\ldots ,\tau \}$, reserving the expression $t>0$ to mean that $t\geq 0$ with $t_j>0$ for at least one $j\in \{1,\ldots ,\tau \}$. Also, when $t\geq 0$, we write $\underline{t}$ to denote a generic tuple of integers $(t'_1, \dots , t'_\tau )\geq 0$ satisfying $t'_j \leq t_j$ for all $j\in \{1,\ldots ,\tau \}$ with in fact $t'_j < t_j$ for at least one $j\in \{1,\ldots ,\tau \}$. We make no distinction between 1-tuples $(t_1)$ and integer numbers $t_1$ so, accordingly, we use $\underline{t_1}$ instead of $\underline{(t_1)}$.

(2)

The interaction parameters $\mathcal{R}_0$, $\mathcal{P}_i\coloneq (\mathcal{P}_{i,1},\ldots ,\mathcal{P}_{i,r_i})$ and $\mathcal{Q}_i\coloneq (\mathcal{Q}_{i,1},\ldots ,\mathcal{Q}_{i,s_i})$ of the factors in 19 are given by$$\begin{align*} \mathcal{R}_0 & \coloneq n+\sum _{x_j\in L_{0,1}}(k_j-n), \\ \mathcal{P}_{i,{\ell _i}} &\coloneq p_{i,{\ell _i}}+\sum _{x_j\in L_{i,{\ell _i}}}(k_j-n),\quad \text{for $i\in \{1,\ldots ,m\}$ and ${\ell _i}\in \{1,\dots , {r_{i}}\}$},\quad \text{and}\\ \mathcal{Q}_{i,{\ell _i}} &\coloneq q_{i,{\ell _i}}+\sum _{x_j\in L_{i,{\ell _i+r_{i}}}}(k_j-n),\quad \text{for $i\in \{1,\ldots ,m\}$ and ${\ell _i}\in \{1,\dots , {s_{i}}\}$.} \end{align*}$$

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 19 interact weakly and, if in addition $\mathcal{P}_i>0$ for some $i$, we say that the factors in 19 interact strongly. Otherwise, we say that the factors in 19 do not interact.

Although not reflected in the notation, pruned trees and leaves depend on the essential vertices $x_i$, while interaction parameters depend on the complete information encoded by the factors in 19. Latter in the paper we will need to use pruned trees, their pruned leaves, as well as interaction parameters of subproducts of 19. In such a case, we will use a notation of the type $T_{i,\ell _i}(x_1,\ldots ,x_m)$, $L_{i,\ell _i}(x_1,\ldots ,x_m)$, $\mathcal{R}_0(x_1,\ldots ,x_m)$, $\mathcal{P}_{i,\ell _i}(x_1,\ldots ,x_m)$, $\mathcal{Q}_{i,\ell _i}(x_1,\ldots ,x_m)$, as well as $\mathcal{P}_i(x_1,\ldots ,x_m)$ and $\mathcal{Q}_i(x_1,\ldots ,x_m)$ in order to clarify the factors under consideration.

Next we adapt the expression in 15 for usage within the $T_{i,{\ell _i}}$-notation. In terms of the cocycle representative

$$\begin{equation} {\sum \left(U_i,V_i,(x_i,\overline{x}_i),W_i\right)\cdot \sigma }\coloneq \sum \left(u_1,\ldots ,u_{k_i},v_1,\ldots ,v_{|p_{i}|},(x_i,{\overline{x}_i}),w_1,\ldots ,w_{|q_{i}|}\right)\cdot \sigma {\tag{20}} \end{equation}$$

in Proposition 3.9 for $\{k_i\vert x_i,p_i,q_i\}$, 19 is represented by the sum of all possible products

$$\begin{equation} \cdots \left((U_i,V_i,(x_i,\overline{x}_i),W_i)\cdot \sigma _i\right)\cdots \left((U_j,V_j,(x_j,\overline{x}_j),W_j)\cdot \sigma _j\right)\cdots . {\tag{21}} \end{equation}$$

A number of vanishing such products can be ruled out as follows. Fix integers $1\leq i<j\leq m$. Proposition 2.3 implies that if a product 21 is non-zero, then $(U_i,V_i,(x_i,\overline{x}_i),W_i)$ must have $x_j$, but cannot have $\overline{x}_j$, as one of its vertex ingredients. Likewise, $(U_j,V_j,(x_j,\overline{x}_j),W_j)$ must have $\overline{x}_i$, but cannot have $x_i$, as one of its vertex ingredients. Actually, together with Remark 4.2, this shows that non-zero products 21 are best organized (and easily evaluated—see below) by replacing each $\Sigma _n$-representative

$$\begin{equation} (u_1,\ldots ,u_{k_i},v_1,\ldots ,v_{|p_{i}|},(x_i,{\overline{x}_i}),w_1,\ldots ,w_{|q_{i}|}) {\tag{22}} \end{equation}$$

in 20 by the one written in a “block” form $(B^i_0,{B^i_1},\ldots ,B^i_m)$. Here each tuple of ingredients $B^i_j$ starts with the relevant $x_j$- or $\overline{x}_j$-information (if $j>0$), and continues with a repacking of the vertex ingredients of 22 that lie in the trees $T_{j,{\ell }}$ for all relevant $\ell$. In detail, for the $i$-th factor in 19 and each of the corresponding summands in 22, let

(a)

$B_0^i\coloneq B_{0,1}^i$ be the tuple of vertex ingredients of 22 that lie in $T_{0,1}$, written in $T$-order;

(b)

$B_i^i\coloneq \left((x_i,{\overline{x}_i}),B^i_{i,1}, \ldots , B^i_{i,{d_i}}\right)$, where $B^i_{i,{\ell }}$ is the tuple of vertex ingredients of 22 that lie in $T_{i,{\ell }}$, written in $T$-order;

(c)

If $i<j$, $B^i_j\coloneq ({x_j}, B^i_{j,1},\ldots , B^i_{j,d_j})$, where $B^i_{j,{\ell }}$ is the tuple of vertex ingredients of 22 that lie in $T_{j,{\ell }}$, written in $T$-order;

(d)

If $j<i$, $B^i_j\coloneq (\overline{x}_j, B^i_{j,1},\ldots , B^i_{j,d_j})$, where $B^i_{j,\ell }$ is the tuple of vertex ingredients of 22 that lie in $T_{j,\ell }$, written in $T$-order.

Thus, summands in 20 that have a chance to contribute with non-vanishing products 21 to a cocycle representative of 19 can be written as

$$\begin{multline*} \Big ({B^i_{0,1}}\Big \vert \cdots \Big \vert \overline{x}_{i'},B^i_{i',1}, \dots ,B^i_{i',{d_{i'}}}\Big \vert \cdots \Big \vert (x_i,\overline{x}_i),B^i_{i,1}, \dots , B^i_{i,d_i}\Big \vert \ldots \\ \Big \vert {x}_{i''},B^i_{i'',1},\dots , B^i_{i'',{d_{i''}}}\Big \vert \cdots \Big )\cdot \sigma , \end{multline*}$$

where vertical bars are used interchangeably by commas, and are intended to make reading easier. Proposition 2.3 then implies that a product 21, written as

$$\begin{multline*} \left(\left({B^1_{0,1}}\Big \vert (x_1,\overline{x}_1),B^1_{1,1},\dots , B^1_{1,d_1}\Big \vert {\cdots }\Big \vert \right.\right.\left.\left.x_m,B^1_{m,1},\dots , B^1_{m,{d_m}}\right)\cdot \sigma _1\right) \\ \cdots \left(\left({B^m_{0,1}}\Big \vert \overline{x}_1,B^m_{1,1},\dots , B^m_{1,{d_1}}\Big \vert {\cdots }\Big \vert (x_m,\overline{x}_m),B^m_{m,1},\dots , B^m_{m,d_m}\right)\cdot \sigma _m\right), \end{multline*}$$

is non-zero if and only if $\sigma _i=\sigma _j\eqcolon \sigma$ and $B^i_{{t,\ell }}=B^j_{{t,\ell }}\eqcolon B_{{t,\ell }}$ for all relevant $i,j,{t,\ell }$, in which case 21 becomes

$$\begin{equation} \operatorname {sign}(\widetilde{\sigma }) \left({B_{0,1}}\vert (x_1,\overline{x}_1),B_{1,1},\cdots , B_{1,d_1}\vert \cdots \vert (x_m,\overline{x}_m),B_{m,1},\cdots ,B_{m,d_m}\right)\cdot \sigma , {\tag{23}} \end{equation}$$

where $\widetilde{\sigma }$ is the permutation determined by the sequence of positions of the edges $(x_1,\overline{x}_1),\ldots ,(x_m,\overline{x}_m)$ in the tuple

$$\begin{equation*} ({B_{0,1}}\vert (x_1,\overline{x}_1),B_{1,1},\dots , B_{1,d_1}\vert \cdots \vert (x_m,\overline{x}_m),B_{m,1},\dots ,B_{m,d_m})\cdot \sigma . \end{equation*}$$

Note that the cube in 23 is product-oriented (as required by Proposition 2.3), and that 23 agrees with the gradient-oriented cube

$$\begin{equation*} \left({B_{0,1}}\vert (x_1,\overline{x}_1),B_{1,1},\cdots ,B_{1,d_1}\vert \cdots \vert (x_m,\overline{x}_m),B_{m,1},\cdots ,B_{m,d_m}\right)\cdot \sigma , \end{equation*}$$

since $x_1<\cdots <x_m$. This proves the first half of the next generalization of Proposition 3.9:

Proposition 4.4.

The product 19 is represented in $C^*(\operatorname {D}_n T)$ by the gradient-oriented cocycle

$$\begin{equation} \sum \left({B_{0,1}}\Big \vert (x_1,\overline{x}_1),B_{1,1},\ldots ,B_{1,d_1}\Big \vert \cdots \Big \vert (x_m,\overline{x}_m),B_{m,1},\ldots ,B_{m,d_m}\right)\cdot \sigma , {\tag{24}} \end{equation}$$

where the summation runs over all permutations $\sigma \in \Sigma _n$ and all possible tuples $B_{{t,\ell }}$ of vertices written in $T$-order, taken from the corresponding pruned trees $T_{{t,\ell }}$, and having the following lengths: Any block ${B_{0,1}}$ must have $\mathcal{R}_0$ ingredients, while any block $B_{{t,\ell }}$ with $t>0$ must have $\mathcal{P}_{{t,\ell }}$ ingredients for $1 \leq {\ell } \leq {r_t}$, and $\mathcal{Q}_{{t,\ell -r_t}}$ ingredients for ${r_t}< {\ell } \leq {d_t}$. In particular, 19 vanishes provided its factors do not interact.

Note that $\mathcal{R}_0+\sum _{i,{\ell }}\mathcal{P}_{i,{\ell }}+\sum _{i,{\ell }}\mathcal{Q}_{i,{\ell }}=n-m$ in Definition 4.3. This is compatible with the fact that cubes in 24, if any, have $n$ ingredients. See also Corollary 4.5.

Proof.

It remains to prove the assertions about the sizes of blocks $B_{t,\ell }$, and that all possible such blocks appear in 24. As for the sizes, proceeding by induction on $m$ (with Proposition 3.9 grounding the argument), it suffices to consider a product $\pi _1\cdot \pi _2$ with

$$\begin{equation} \begin{split} \pi _1&=\left[\left({B_{0,1}}\Big \vert (x_1,\overline{x}_1),B_{1,1},\ldots ,B_{1,d_1}\Big \vert \cdots \Big \vert (x_m,\overline{x}_m),B_{m,1},\ldots ,B_{m,d_m})\right)\cdot \sigma \right],\\ \pi _2&=\left[\left(U\Big \vert (x_{m+1},\overline{x}_{m+1}),V_1,\ldots ,V_{d_{m+1}}\right)\cdot \sigma '\right], \end{split}{\tag{25}} \end{equation}$$

where $x_1<\cdots <x_m<x_{m+1}$, and where the structure of the blocks $B_{{t,\ell }}$ is as specified in the proposition. Here we are assuming (a) that $U$ is a tuple of $k_{m+1}$ vertex ingredients written in $T$-order and lying in $x_{m+1}$-direction 0, (b) that any tuple $V_{{\ell }}$ with $1 \leq {\ell } \leq {r_{m+1}}$ consists of $p_{m+1,{\ell }}$ vertex ingredients written in $T$-order and lying in $x_{m+1}$-direction $\ell$, and (c) that any tuple $V_{{\ell +r_{m+1}}}$ with $1 \leq {\ell } \leq s_{m+1}$ consists of $q_{m+1,{\ell }}$ vertex ingredients written in $T$-order and lying in $x_{m+1}$-direction $\ell +r_{m+1}$. In addition, we make the conventions $d_{m+1}\coloneq d(x_{m+1})-1$ and $\overline{x}_{m+1}\coloneq x_{m+1}[r_{m+1}+1]$, and assume the relations $d_{m+1}=r_{m+1}+s_{m+1}$, $r_{m+1}\geq 1\leq s_{m+1}$ and $k_{m+1}+\sum _{\ell =1}^{r_{m+1}} p_{m+1,\ell }+\sum _{\ell =1}^{s_{m+1}} q_{m+1,\ell }=n-1$. Furthermore, signs and orientations will be ignored in the rest of the proof, as they have been carefully addressed in the discussion previous to this proposition. In particular, we can safely work at the unordered-cube level, thus ignoring the permutations $\sigma$ and $\sigma '$ in 25 and, instead, thinking of tuples of ingredients as sets of ingredients.

Consider the pruned trees $T_{{t,\ell }}\coloneq {T_{t,\ell }(x_1,\ldots ,x_m)}$ and $T'_{{t,\ell }}\coloneq {T_{t,\ell }(x_1,\ldots ,x_{m+1})}$, as well as the pruned leaves $L_{{t,\ell }}\coloneq {L_{t,\ell }(x_1,\ldots ,x_m)}$ and $L'_{{t,\ell }}\coloneq L_{t,\ell }(x_1,\ldots ,x_{m+1})$. There are three cases, depending on whether the edge $(x_{m+1},\overline{x}_{m+1})$ belongs to $T_{0,1}$, or to $T_{{t,\ell }}$ with $1\leq t\leq m$ and $1 \leq {\ell } \leq {r_t}$, or to $T_{{t,\ell }}$ with $1\leq t\leq m$ and ${r_t}<{\ell \leq d_t}$, and the argument is virtually identical in each. We consider only the situation depicted in Figure 8, where the edge $(x_{m+1},\overline{x}_{m+1})$ belongs to $T_{{t,\ell }}$ for some $t\in \{1,2,\ldots ,m\}$ and some $\ell \in \{1,2,\ldots ,r_t\}$. In such a case we have

(i)

$T_{{\tau },{\lambda }}=T'_{{\tau },{\lambda }}$ and $L_{{\tau },{\lambda }}=L'_{{\tau },{\lambda }}$, for $1\leq \tau \leq m$ as long as $\tau \neq t$ or $\lambda \neq \ell$;

(ii)

$T_{{t},{\ell }}\setminus \text{Int}(x_{m+1},\overline{x}_{m+1})=T'_{{t},{\ell }}\bigsqcup \left( \bigcup \limits _{{\lambda }=1}^{d_{m+1}} T'_{m+1,{\lambda }}\right)$;

(iii)

$L'_{{t},{\ell }}=L_{{t},{\ell }}\cup \{x_{m+1}\}$ and $L'_{m+1,{\lambda }}=\varnothing$ for ${\lambda } \in \{1, \dots , d_{m+1}\}$.

By Proposition 2.3, the product $\pi _1\cdot \pi _2$ of the elements in 25 vanishes unless

$$\begin{gather*} \left(\{\overline{x}_1,\ldots ,\overline{x}_m\}\sqcup {B_{0,1}}\sqcup \left(\bigsqcup _{\substack{{1\leq \tau \leq m}\\{1\leq \lambda \leq d_\tau }}} B_{{\tau },{\lambda }}\right) \right) \setminus B_{{t},{\ell }}\subseteq U, \\ \{x_{m+1}\}\sqcup \left( \bigsqcup _{{\lambda =1}}^{d_{m+1}} V_{{\lambda }} \right) \subseteq B_{{t},{\ell }} \end{gather*}$$

and

$$\begin{multline*} U\setminus \left(\left(\{\overline{x}_1,\ldots ,\overline{x}_m\}\sqcup {B_{0,1}}\sqcup \left(\bigsqcup _{\substack{{1\leq \tau \leq m}\\{1\leq \lambda \leq d_\tau }}} B_{{\tau },{\lambda }}\right) \right) \setminus B_{{t},{\ell }} \right)\\ = B_{{t},{\ell }}\setminus \left(\{x_{m+1}\}\sqcup \left( \bigsqcup _{{\lambda =1}}^{d_{m+1}} V_{{\lambda }} \right)\right)\eqcolon B'_{t,\ell }, \end{multline*}$$

in which case

$$\begin{equation*} {\pi _1\cdot \pi _2=(B_{0,1}\vert (x_1,\overline{x}_1),\mathcal{B}_1\vert \cdots \vert (x_m,\overline{x}_m),\mathcal{B}_m\vert (x_{m+1},\overline{x}_{m+1}),V_1,\ldots ,V_{d_{m+1}}),} \end{equation*}$$

where $\mathcal{B}_\tau$ is a shorthand for the sequence $B_{\tau ,1},\ldots ,B_{\tau ,d_{\tau }}$ provided $\tau \neq t$, whereas $\mathcal{B}_t$ stands for the sequence

$$\begin{equation*} B_{t,1},\ldots ,B_{t,\ell -1},B'_{t,\ell },B_{t,\ell +1},\ldots ,B_{t,d_t}. \end{equation*}$$

The induction is complete in view of items (i)–(iii) above and

$$\begin{align*} \vert B'_{{t},{\ell }} \vert &=\vert B_{{t},{\ell }} \vert -\left(1+\sum _{{\lambda }=1}^{{r_{m+1}}}p_{m+1,{\lambda }}+\sum _{{\lambda }=1}^{{s_{m+1}}}q_{m+1,{\lambda }}\right)\\ &=p_{{t},{\ell }}+\sum _{x_{{\lambda }}\in L_{{t},{\ell }}}(k_{{\lambda }}-n)-(n-k_{m+1})=p_{{t},{\ell }}+\sum _{x_{{\lambda }}\in L'_{{t},{\ell }}}(k_{{\lambda }}-n), \end{align*}$$

which shows that $B'_{{t},{\ell }}$ has the prescribed cardinality. The inductive analysis makes it clear also that all blocks $B_{t,\ell }$ with the structure indicated in the proposition indeed appear in 24.

■

Corollary 4.5.

The product 19 agrees with the basis element $\{\mathcal{R}_0\vert x_1,\mathcal{P}_{1},\mathcal{Q}_{1}\vert \cdots \vert x_m,\mathcal{P}_{m},\mathcal{Q}_{m}\}$ provided the factors of 19 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}})$.

Proof.

By the strong interaction hypothesis, a summand in 24 that is the target of a lower gradient path $\gamma$ must actually be critical (and $\gamma$ must be constant) with ingredients equal to those associated to $\{\mathcal{R}_0\vert x_1,\mathcal{P}_{1},\mathcal{Q}_{1}\vert \cdots \vert x_m,\mathcal{P}_{m},\mathcal{Q}_{m}\}$. The conclusion then follows from 9 and 11.

■

Lemma 4.6.

Fix essential vertices $x_1<\cdots <x_m$ and take positive integer numbers $r_i$ and $s_i$ with $r_i+s_i=d(x_i)-1$ for $1\leq i\leq m$. Let $R_0$, $P_{{i,\ell }}$, $Q_{{i,k}}$, with $1 \leq {i} \leq m$, $1 \leq {\ell } \leq r_{{i}}$ and $1 \leq {k} \leq s_{{i}}$, be non-negative integers satisfying $n-{m}=R_0+\sum _{i=1}^m\left(\sum _{{\ell }=1}^{r_{{i}}}P_{i,{\ell }}+\sum _{k=1}^{s_{{i}}} Q_{i,k}\right)$. Then the system

$$\begin{align*} n+\sum _{x_j\in L_{0,1}}(k_j-n)&=R_0,\\ p_{i,{\ell }}+\sum _{x_j\in L_{i,{\ell }}}(k_j-n)&=P_{i,{\ell }}\quad (i=1,\ldots ,m, \;\;{\ell }=1,\dots , r_{{i}}), \\ q_{i,{k}}+\sum _{x_j\in L_{i,{k+r_i}}}(k_j-n)&=Q_{i,{k}}\quad (i=1,\ldots ,m, \;\;{k}=1,\dots , s_{{i}}) \end{align*}$$

has a unique solution of non-negative integer numbers $\{k_i,p_{i,1}, \dots ,p_{i, r_{{i}}}, q_{i,1}, \dots , q_{i, s_{{i}}} \}_{i=1}^m$ satisfying the condition ${n-1}=k_i+\sum _{{\ell }=1}^{r_{{i}}} p_{i,{\ell }}+ \sum _{{k}=1}^{s_{{i}}}q_{i,{k}}$ for each $i\in \{1,\ldots ,m\}$. If, in addition, for each ${i\in \{1,\ldots ,m\}}$ there exists $\ell \in \{1,\ldots ,r_i\}$ with $P_{{i,\ell }}>0$, then the unique solution satisfies that, for each $i\in \{1,\dots ,m\}$, there exists $\ell \in \{1, \dots r_{{i}}\}$ with $p_{{i,\ell }}>0$.

Proof.

The two sets of equations with $i=m$ reduce to $p_{m,{\ell }}=P_{m,{\ell }}$ (${\ell }=1,2, \dots , r_{{m}}$) and $q_{m,{k}}=Q_{m,{k}}$ (${k}=1,2, \dots , s_{{m}}$). This also determines

$$\begin{equation} k_m\coloneq n-\sum _{{\ell }=1}^{r_{{m}}}P_{m,{\ell }}-\sum _{{k}=1}^{s_{{m}}}Q_{m,{k}}-1=R_0+\sum _{j=1}^{m-1}\left(\sum _{{\ell }=1}^{r_{{j}}}P_{j,{\ell }}+\sum _{k=1}^{s_{{j}}}Q_{j,k}+1\right)\geq 0. {\tag{26}} \end{equation}$$

The rest of the equations can be written as

$$\begin{align*} n+\sum _{x_j\in L_{0,1}\setminus \{x_m\}}(k_j-n)&=R'_0\coloneq R_0{{}+{}}\left.\begin{cases} n-k_m, & \text{if $x_m\in L_{0,1}$} \\ 0, & \text{otherwise} \end{cases}\right\},\\ p_{i,{\ell }}+\sum _{x_j\in L_{i,{\ell }}\setminus \{x_m\}}(k_j-n)&=P'_{i,{\ell }}\coloneq P_{i,{\ell }}{{}+{}}\left.\begin{cases} n-k_m, & \text{if $x_m\in L_{i,{\ell }}$} \\ 0, & \text{otherwise} \end{cases}\right\},\\ q_{i,{k}}+\sum _{x_j\in L_{i,{k}+r_{{i}}}\setminus \{x_m\}}(k_j-n)&=Q'_{i,{k}}\coloneq Q_{i,{k}}{{}+{}}\left.\begin{cases} n-k_m, & \text{if $x_m\in L_{i,{k}+r_{{i}}}$} \\ 0, & \text{otherwise} \end{cases}\right\}, \end{align*}$$

for $i=1,\ldots ,m-1$, ${\ell }=1,\dots , r_{{i}}$ and ${k}=1,\dots , s_{{i}}$. The result then follows by induction since

$$\begin{equation*} R'_0+\sum _{j=1}^{m-1}\left(\sum _{{\ell }=1}^{r_{{j}}}P'_{j,{\ell }}+\sum _{k=1}^{s_{{j}}}Q'_{j,k}+1\right)=R_0+\sum _{j=1}^{m-1}\left(\sum _{{\ell }=1}^{r_{{j}}}P_{j,{\ell }}+\sum _{k=1}^{s_{{j}}}Q_{j,k}+1\right){{}+{}}n-{k}_m \end{equation*}$$

$$\begin{equation*} =R_0+\sum _{j=1}^{m}\left(\sum _{{\ell }=1}^{r_{{j}}}P_{j,{\ell }}+\sum _{k=1}^{s_{{j}}}Q_{j,k}+1\right)=n, \end{equation*}$$ where the second equality uses 26.

■

Proof of Theorem 1.7.

Corollary 4.5 and Lemma 4.6 yield a set theoretic identification $\mathcal{S}_m=\mathcal{B}_m$, where $\mathcal{S}_m$ is the set of products 19 whose factors interact strongly, and $\mathcal{B}_m$ is the $m$-dimensional basis of $\operatorname {Im}(\pi ^*)$ with basis elements

$$\begin{multline*} \{R_0\vert x_1,{(P_{1,1},\ldots ,P_{1,r_1})},{(Q_{1,1},\ldots ,Q_{1,s_1})}\vert \cdots \vert x_m,{(P_{m,1},\ldots ,P_{m,r_m})},\\ {(Q_{m,1},\ldots ,Q_{m,s_m})}\}. \end{multline*}$$

Together with Corollary 3.11 and Proposition 4.4, this completes the proof, where $\langle k,x,p,q\rangle \in V_nT$ is identified with (the $\pi ^*$-preimage of) $\{k\vert x,p,q\}\in \operatorname {Im}(\pi ^*)$.

■

Note that the cohomology ring $H^*(\operatorname {UD}_n T)$ is generated by 1-dimensional classes, a fact already known from 7. It is not true that a product 19 vanishes when its factors interact but non-strongly. The description of such products relies on the dynamics of lower gradient paths.

5. Cup products II: Lower gradient paths

Let $\Pi _1$ stand for a product 19 whose factors interact strongly, so Corollary 4.5 applies. Choose an additional 1-dimensional basis element $\{k_x\vert x,(p_{x,1},\ldots ,p_{x,r_x})$, $(q_{x,1},\ldots ,q_{x,s_x})\}$ of $\operatorname {Im}(\pi ^*)$ with $x<x_1<\cdots <x_m$ and where the standard conditions and conventions are assumed, namely,

$$\begin{equation} p_x\coloneq (p_{x,1},\ldots ,p_{x,r_x})>0 \ \ \text{and} \ \ q_x\coloneq (q_{x,1},\ldots ,q_{x,s_x})\geq 0, {\tag{27}} \end{equation}$$

where $r_x\geq 1\leq s_x$, $r_x+s_x=d_x\coloneq d(x)-1$, $|p_x|\coloneq \sum _{\ell =1}^{r_x}p_{x,\ell }$, $|q_x|\coloneq \sum _{\ell =1}^{s_x}q_{x,\ell }$, $k_x+|p_x|+|q_x|=n-1$ and $\overline{x}\coloneq x[r_x+1]$. Consider the interaction parameters $P_{i}\coloneq \mathcal{P}_{i}(x_1,\ldots ,x_m)$ and $Q_{i}\coloneq \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\coloneq \mathcal{R}_0(x,x_1,\ldots ,x_m)$, $P_x\coloneq \mathcal{P}_1(x,x_1,\ldots ,x_m)$ and $Q_x\coloneq \mathcal{Q}_1(x,x_1,\ldots ,x_m)$ of the factors of $\Pi _2\coloneq \{k_x\vert x,p_x,q_x\}\cdot \Pi _1$. This section is devoted to proving:

Theorem 5.1.

In the situation above, if the factors of $\Pi _2$ interact but non-strongly, then

$$\begin{align} \Pi _2&=-\sum _{{a}}\left\{R_0-|{a}|\Big \vert x,{a},Q_x\Big \vert x_1, P_{1},Q_{1}\Big \vert \cdots \Big \vert x_m, P_{m},Q_{m}\right\}{\tag{28}}\\ &\;\;\;\;{}+\sum _{\ell =1}^{s_x-1}\sum _{a,b}\left\{R_0-|a|-b-1\Big \vert x,Q_x^{(\ell ,a,b)},Q_x^{(\ell ,+)}\Big \vert x_1, P_{1},Q_{1}\Big \vert \cdots \Big \vert x_m, P_{m},Q_{m}\right\}{\tag{29}}\\ &\;\;\;\;{}-\sum _{\ell =1}^{s_x-1}\sum _{a,b}\left\{R_0-|a|-b\Big \vert x,Q_x^{(\ell ,a,b)},Q_x^{(\ell ,-)}\Big \vert x_1, P_{1},Q_{1}\Big \vert \cdots \Big \vert x_m, P_{m},Q_{m}\right\}. {\tag{30}} \end{align}$$

In the above expression we set $a\coloneq (a_1,\ldots ,a_{r_x})$, $|a|\coloneq a_1+\cdots +a_{r_x}$, $Q_x^{(\ell ,+)}\coloneq (Q_{x,\ell +1},Q_{x,\ell +2},\ldots ,Q_{x,s_x})$, $Q_x^{(\ell ,-)}\coloneq (Q_{x,\ell +1}-1,Q_{x,\ell +2},\ldots ,Q_{x,s_x})$ and $Q_{x}^{(\ell ,a,b)}\coloneq (a_1,\ldots ,a_{r_x},Q_{x,1}+b+1,Q_{x,2},\ldots ,Q_{x,\ell })$. The summation in 28 runs over all $r_x$-tuples $a$ of non-negative integer numbers satisfying $1\leq |{a}|\leq R_0$. The inner summation in 29 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 30 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$.

Since summands in 28, 29, and 30 are basis elements, Theorem 5.1 and the results in the previous section give a recursive method to effectively assess cup-products in $\operatorname {Im}(\pi ^*)\cong H^*(B_nT)$.

Proof of Theorem 5.1 (Preparation).

We have seen that $\Pi _2$ is represented in $C^*(\operatorname {D}_n T)$ by the gradient-oriented cocycle

$$\begin{multline} \sum \Big ({B_{0,1}}\Big \vert (x,\overline{x}),{B_{x,1},\ldots ,B_{x,d_x}}\Big \vert (x_1,\overline{x}_1),B_{1,1},\ldots ,B_{1,d_1}\Big \vert \cdots \\ \Big \vert (x_m,\overline{x}_m),B_{m,1},\ldots ,B_{m,d_m}\Big )\cdot \sigma , {\tag{31}} \end{multline}$$

where the summation runs over all permutations $\sigma \in \Sigma _n$ and over all possible blocks $B_{\ast ,\ast }$ of vertices written in $T$-order, taken from the corresponding trees $T_{\ast ,\ast }$ determined by the factors of $\Pi _2$, and having sizes as prescribed in Proposition 4.4 in terms of the relevant interaction parameters. The goal now is to identify the $\underline{\Phi }$-image of 31 which, by 9, is the element in $\mathcal{M}^*(\operatorname {D}_n T)$

$$\begin{equation} \sum _{\gamma \in \mathcal{G}}\mu (\gamma )\cdot \mathcal{S}_\gamma . {\tag{32}} \end{equation}$$

Here $\mathcal{G}$ is the set of lower paths $\gamma$ starting at an $(m+1)$-critical cube $\mathcal{S}_\gamma$ and finishing at a summand of 31. We start by identifying (in the next two paragraphs) key characteristics of ending cubes for paths in $\mathcal{G}$.

Firstly, the condition $x<x_1$ forces one of the four configurations depicted in Figure 9. In any of those configurations, vertices $x_i$ with $i>1$ lie either on a component of $T\setminus \{x_1\}$ in positive $x_1$-direction or “below” the horizontal segment joining the root and $x_1$. As a result, the equalities $P_{i}=\mathcal{P}_{i}(x_1,\ldots ,x_m)=\mathcal{P}_{i+1}(x,x_1,\ldots ,x_m)$ and $Q_{i}=\mathcal{Q}_{i}(x_1,\ldots ,x_m)=\mathcal{Q}_{i+1}(x,x_1,\ldots ,x_m)$ hold for $i=1,\ldots ,m$. The interaction hypotheses then yield

$$\begin{equation} P_x=0, {\tag{33}} \end{equation}$$

the $r_x$-tuple consisting of zeros. This and 27 rule out the two configurations on the right of Figure 9, as well as the one on the bottom left, since the equality $P_x=p_x$ is forced for those configurations. The only possible configuration, i.e., the one on the top left of Figure 9, will be assumed in the rest of the section.

Secondly, redundant summands in 31 can be neglected, as none of those can be the destination of a lower path. Furthermore, 33 shows that no summand in 31 is critical. We thus focus on collapsible summands in 31 which (in addition to their size and distribution properties summarized at the start of the proof) are forced to satisfy the following two properties: For one, ingredients of each $B_{0,1}$ that are smaller than ${x}$ form a stack of vertices blocked by the root of $T$. In addition, for any $i\in \{1,2,\ldots ,m\}$ with $\overline{x}_i$ smaller than $\overline{x}$, all ingredients of each $B_{i,{\ell }}$ ($1\leq \ell \leq d_i$) are blocked (this uses the fact that $P_{i}$ is not the zero tuple), so the tuple $((x_i,\overline{x}_i),B_{i,1},\dots , B_{i,d_i})$ assembles a (unique, by block-size limitations) critical situation around $x_i$. It follows that each summand $c\cdot \sigma$ in 31 relevant for 32 is collapsible by a branch-type pairing that creates the edge $(x,\overline{x})$, as depicted in

$$\begin{equation} \vcenter{\img[][387pt][51pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[scale=1.0, rotate = 180, xscale = -1] \node[style={circle, draw, scale=.5}] (1) at ( -5, 1.0) {}; \node at ( -5, 1.3) {$0$}; \node[style={circle, draw, scale=.5}] (2) at ( -3.5, 1) {}; \node[style={circle, draw, scale=.5}] (3) at ( -3.5, 1.9) {}; \node[style={circle, draw, scale=.5}] (4) at (-2.8,0.3) {}; \node[style={circle, draw, scale=.5}] (5) at ( -2.5, 1) {}; \node[fill=black,style={circle, draw, scale=.5}] (6) at ( -3, 1.67) {}; \node[fill=black,style={circle, draw, scale=.5}] (7) at ( -1, 1) {}; \node at ( -1.1, 1.3) {$x_1$}; \node[style={circle, draw, scale=.5}] (8) at ( -.3, .3) {}; \node[fill=black,style={circle, draw, scale=.5}] (9) at ( 0, 1) {}; \node[style={circle, draw, scale=.5}] (10) at ( -.5, 1.67) {}; \node[style={circle, draw, scale=.5}] (41) at ( 3, 1.0) {}; \node at ( 3, 1.3) {$0$}; \node[fill=black,style={circle, draw, scale=.5}] (42) at ( 4.5, 1) {}; \node at ( 4.4, .7) {$x$}; \node[style={circle, draw, scale=.5}] (43) at ( 4.5, 1.9) {}; \node[style={circle, draw, scale=.5}] (44) at (5.2,0.3) {}; \node[style={circle, draw, scale=.5}] (45) at ( 5.5, 1) {}; \node[fill=black,style={circle, draw, scale=.5}] (46) at ( 5, 1.67) {}; \node[fill=black,style={circle, draw, scale=.5}] (47) at ( 7, 1) {}; \node at ( 6.85, .7) {$x_1$}; \node[style={circle, draw, scale=.5}] (48) at ( 7.7, .3) {}; \node[fill=black,style={circle, draw, scale=.5}] (49) at ( 8, 1) {}; \node[style={circle, draw, scale=.5}] (40) at ( 7.5, 1.67) {}; \node(11) at (1.1,1.5){}; \node(12) at (2.35,0.25){}; \draw[thick,-&gt;] (11) -- (12); \draw[very thin, dashed] (42) -- (41); \draw[very thin] (43) -- (42); \draw[very thin] (44) -- (42); \draw[very thick] (46)node[right]{$\overline{x}$} -- (42); \draw[very thin] (45) -- (42); \draw[dashed, very thin] (47) -- (45); \draw[very thin] (48) -- (47); \draw[very thick] (49)node[right]{$\red{\overline{x}_1.}$} -- (47); \draw[very thin] (40) -- (47); \draw[dashed, very thin] (2) -- (1); \draw[very thin] (3) -- (2); \draw[very thin] (4) -- (2); \draw[very thin] (5) -- (2); \draw[very thin] (6)node[right]{$\overline{x}$} -- (2); \draw[dashed, very thin] (7) -- (5); \draw[very thin] (8) -- (7); \draw[very thick] (9)node[right]{\red{$\overline{x}_1$}} -- (7); \draw[very thin] (10) -- (7); \end{tikzpicture}}]{Images/img2dd2e07df3b4aafdd194390c82a19647.svg}} {\tag{34}} \end{equation}$$

Note that any $(m+1)$-cube $c_0$ that has been identified on the right of 34 as a potential destination of a path $\gamma \in \mathcal{G}$ supports a gradient path $\lambda \colon {c_0}\searrow c_1\nearrow \cdots \searrow c_t$ with $c_t$ a critical $m$-cube. For instance, start by replacing the edge $(x_1,\overline{x}_1)$ in ${c_0}$ by $x_1$, and let the rest of the path consist of falling-vertex elementary factors. It follows that the concatenation of $\gamma$ and $\lambda$ and, therefore, $\gamma$ itself obey the rule in Corollary 3.7: any upper elementary factor of sor type is of falling-vertex type. Such a fact, together with cancellation phenomena similar to the one in the proof of Proposition 3.9, is used in the rest of the argument in order to analyze paths determining 32. As in the proof of Proposition 3.10, the analysis can equivalently be done at the level of $C^*(\operatorname {UD}_n T)$, which means that an ordered cube $c\cdot \sigma$ can be replaced by the corresponding orbit $\{c\}$. Following the lead in Proposition 3.9, we first identify the actual sets of paths whose contributions in 32 give 28 29, and 30.

The summation in 28 arises from a set $\mathcal{L}^-_0\subset \mathcal{G}$ of paths having a single “lock” dynamics. Explicitly, each $r_x$-tuple $a$ of non-negative integer numbers satisfying $0<|a|\leq R_0$ determines a lower gradient path ${\lambda ^-_{a,0}}\in \mathcal{L}^-_0$ that departs from the critical $(m+1)$-cube

$$\begin{equation*} \left\{R_0-|{a}| \Big \vert x,{a},Q_{x}\Big \vert x_1,P_{1},Q_{1}\Big \vert \ldots \Big \vert x_m,P_{m},Q_{m}\right\} \end{equation*}$$

by replacing the edge $(x,\overline{x})$ by $\overline{x}$—this opens the lock. Then ${\lambda ^-_{a,0}}$ continues with the falling of the $|{a}|$ vertices that were blocked by $x$, after which ${\lambda ^-_{a,0}}$ ends with the pairing that closes the lock by creating the edge $(x,\overline{x})$ required in 34. Since both opening and closing locks are associated to the same face (the gradient-orientated $\delta _2$-face), and since falling-vertex elementary paths have multiplicity 1, we see from 7 that $\mu ({\lambda ^-_{a,0}})=-1$. Thus, $\mathcal{L}^-_0\subseteq \mathcal{G}$ yields 28.

The set of paths ${\mathcal{L}_0^-}$ is contained in a slightly larger subset $\mathcal{L}^{-}\subset \mathcal{G}$ which consists of paths $\lambda _{a,b}^-$, where $a$ runs over $r_x$-tuples of non-negative integer numbers and $b$ runs over non-negative integers numbers satisfying $|a|>0$ and $|a|+{b}\leq R_0$. Explicitly, $\lambda _{a,b}^-$ starts by taking face $\delta _2$ (lock opening) of the critical $(m+1)$-cube

$$\begin{equation*} \left\{R_0-|a|-{b}\Big \vert x,a,{Q_{x}+{(b,0,\ldots ,0)}}\Big \vert x_1,P_{1},Q_{1}\Big \vert \ldots \Big \vert x_m,P_{m},Q_{m}\right\}. \end{equation*}$$

Here and below we take the coordinate-wise sum of tuples. Then $\lambda _{a,b}^-$ continues with the falling of the $|a|$ vertices that were blocked by $x$, followed (if $b>0$) by the falling of the $b$ vertices $S_b(\overline{x})$, to finish with the falling of $\overline{x}+b$ until it creates the required branch-type pairing 34—which closes the lock. As in the case of ${\mathcal{L}^-_0},$ paths in $\mathcal{L}^{-}$ have multiplicity $-1$. Likewise, there is the family $\mathcal{L}^{+}\subset \mathcal{G}$ consisting of paths $\lambda _{a,b}^+$, with $a$ and $b$ as above, except that the inequality $|a|+b\leq R_0$ is replaced by the strict inequality $|a|+b<R_0$. Explicitly, $\lambda _{a,b}^+$ starts by taking face $\delta _1$ (inverse lock opening) of the critical $(m+1)$-cube

$$\begin{equation*} \left\{R_0-|a|-{b-1}\Big \vert x,{a},Q_{x}+({b+1,0,\ldots ,0})\Big \vert x_1,P_{1},Q_{1}\Big \vert \ldots \Big \vert x_m,P_{m},Q_{m}\right\}. \end{equation*}$$

Then $\lambda _{a,b}^+$ continues with the falling of $x$, followed by the falling of the $|a|$ vertices that were blocked by $x$, followed (if $b>0$) by the falling of the ${b}$ vertices $S_{\overline{x}+1}(b)$, to finish with the falling of $\overline{x}+b+1$ until it creates the required branch-type pairing 34—which closes the lock. Note that paths in $\mathcal{L}^{+}$ have multiplicity $+1$.

Figure 10 summarizes dynamics of paths in $\mathcal{L}^-$ (top) and paths in $\mathcal{L}^+$ (bottom), with lock opening/closing represented by arrows. Note the shifting on the $b$ vertices falling from $x$-direction $r_x+1$, as well as on the vertices that make up $B_{x,r_x+1}$ at the end of the path. The key point is that if $b>0$, the paths $\lambda ^-_{a,b}$ and $\lambda ^+_{a,b-1}$ share origin, so their contributions in 32 cancel each other out. The only unmatched paths are those in $\mathcal{L}^{-}$ with parameter $b=0$, i.e., paths in ${\mathcal{L}^-_0,}$ whose contribution in 32 has been shown to yield (28).

By construction, $\mathcal{L}^-\cup \mathcal{L}^+$ consists of those paths in $\mathcal{G}$ that start by taking a face $\delta _i$ with $i=1,2$ of a critical $(m+1)$-cube with edges

$$\begin{equation*} (x,\overline{x}), (x_1,\overline{x}_1),\ldots ,(x_m,\overline{x}_m), \end{equation*}$$

and that evolve exclusively though falling-vertex elementary paths before reaching the required pairing 34. Next we describe similar sets of paths contributing in 32 with 29 and 30. In such sets of paths, an edge

$$\begin{equation} (x,x[r+1]) \text{ with }r\neq r_x {\tag{35}} \end{equation}$$

plays the role of the edge $(x,\overline{x})=(x,x[r_x+1])$ in $\mathcal{L}^\pm$.

Paths $\mathcal{K}_\ell ^-$ with $1\leq \ell \leq s_x-1$ ($r=r_x+\ell$, in the notation of 35): If $Q_{x,\ell +1}=0$, set $\mathcal{K}^-_\ell =\varnothing$, otherwise $\mathcal{K}^-_\ell$ consists of paths $\kappa ^-_{\ell ,a,b}\in \mathcal{G}$, where $a$ runs over $r_x$-tuples of non-negative integer numbers and $b$ runs over non-negative integer numbers satisfying $|a|+b\leq R_0$. Explicitly, if $a=(a_1,\ldots ,a_{r_x})$, then $\kappa ^-_{\ell ,a,b}$ starts by taking face $\delta _2$ of the critical $(m+1)$-cube

$$\begin{multline*} \left\{R_0-|a|-{b}\Big \vert \right.x,(a_1,\ldots ,a_{r_x},Q_{x,1}+b+1,Q_{x,2},\ldots ,Q_{x,\ell }),\\ (Q_{x,\ell +1}-1,Q_{x,\ell +2},\ldots ,Q_{x,s_x})\Big \vert x_1,P_{1},Q_{1}\Big \vert \ldots \left.\Big \vert x_m,P_{m},Q_{m}\right\}, \end{multline*}$$

and evolves through falling-vertex elementary paths as depicted by the chart⁠⁹

⁹

As in the case of $\mathcal{L}^\pm$, the $|a|$ vertices falling from $x$-directions 1 through $r_x$ are not shown in the chart.

✖

$$\begin{align*} \overrightarrow {(x,x[r+1])},\underbrace{\overline{x},\ldots ,\overline{x}+b-1}_{\text{$b$ falling vertices}},&\;\overbrace {\;\overline{x}+b,\;}^{\text{closing-lock vertex}}\;\underbrace{\overline{x}+b+1,\ldots ,\overline{x}+b+Q_{x,1}}_{\text{vertices in $B_{x,r_x+1}$ at the end of $\kappa _{\ell ,a,b}^-$}} \end{align*}$$

before reaching the required pairing 34. Both opening and closing locks of $\kappa ^-_{\ell ,a,b}$ are associated to a (gradient-oriented) $\delta _2$ face, so that $\mu (\kappa ^-_{a,b})=-1$. The contribution in 32 of the paths in $\mathcal{K}^-_1\cup \cdots \cup \mathcal{K}^-_{s_x-1}$ thus gives raise to 30. Note that no path that starts from the origin of a given $\kappa ^-_{a,b}$ by taking face $\delta _1$—instead of $\delta _2$—and that evolves through falling-vertex elementary paths can arrive at a summand of 31. This is why the contribution to 32 of the set of paths in the next paragraph does not cancel out terms in 30.

Paths $\mathcal{K}_\ell ^+$ with $1\leq \ell \leq s_x-1$ ($r=r_x+\ell$, in the notation of 35): $\mathcal{K}^+_\ell$ consists of paths $\kappa ^+_{\ell ,a,b}\in \mathcal{G}$, where $a$ runs over $r_x$-tuples of non-negative integer numbers and $b$ runs over non-negative integer numbers satisfying $|a|+b<R_0$. Explicitly, if $a=(a_1,\ldots ,a_{r_x})$, then $\kappa ^+_{\ell ,a,b}$ starts by taking face $\delta _1$ of the critical $(m+1)$-cube

$$\begin{multline*} \left\{R_0-|a|-b-1\Big \vert \right.x,(a_1,\ldots ,a_{r_x},Q_{x,1}+b+1,Q_{x,2},\ldots ,Q_{x,\ell }),\\ (Q_{x,\ell +1},Q_{x,\ell +2},\ldots ,Q_{x,s_x})\Big \vert x_1,P_{1},Q_{1}\Big \vert \ldots \left.\Big \vert x_m,P_{m},Q_{m}\right\}, \end{multline*}$$

and evolves through falling-vertex elementary paths as depicted by the chart

$$\begin{align*} \underbrace{\overleftarrow {(x,x[r+1])},\overline{x},\ldots ,\overline{x}+b-1}_{\text{$b+1$ falling vertices}},&\;\overbrace {\;\overline{x}+b,\;}^{\text{closing-lock vertex}}\;\underbrace{\overline{x}+b+1,\ldots ,\overline{x}+b+Q_{x,1}}_{\text{vertices in $B_{x,r_x+1}$ at the end of $\kappa _{\ell ,a,b}^+$}} \end{align*}$$

before reaching the required pairing 34. Now $\mu (\kappa ^+_{a,b})=1$, so the contribution in 32 of the paths in $\mathcal{K}^+_1\cup \cdots \cup \mathcal{K}^+_{s_x-1}$ gives raise to 29. Again, no path that starts from the origin of a given $\kappa ^+_{a,b}$ by taking face $\delta _2$—instead of $\delta _1$—and that evolves through falling-vertex elementary paths can arrive at a summand of 31.

■

Remark 5.2.

Since the closing-lock pairing 34 must come from $x$-direction $r_x+1$, paths corresponding to cases with $r<r_x$ in 35 have no contribution in 32. Specifically, any path $\gamma \in \mathcal{G}$ that starts from a critical cell with edges $(x,x[r+1]),(x_1,\overline{x}_1),\ldots ,(x_m,\overline{x}_m)$, where $r<r_x$, by taking a face $\delta _i$ with $i=1,2$, and that reaches the pairing 34 through falling-vertex elementary paths, has a companion path $\gamma '$ that starts from the same critical cell by taking the face $\delta _{3-i}$, and that also evolves through falling-vertex elementary paths until it reaches the closing-lock pairing 34—so that $\mu (\gamma ')=-\mu (\gamma )$ and $(\gamma ')'=\gamma$. Note that, in the ordered setting, $\gamma$ and its companion path $\gamma '$ arrive at summands of 31 whose ingredients differ only by a permutation (so $\gamma '\in \mathcal{G}$ as well). The phenomenon noticed in this remark is in fact the key to finishing the proof of the main result in this section.

Proof of Theorem 5.1 (Conclusion). Let $\mathcal{J}$ stand for the set of paths analyzed up to this point, i.e., the paths in $\mathcal{G}$ that (I) depart from a critical $(m+1)$-cube with gradient-ordered edges $(x,{x[\ell ]}),(x_1,\overline{x}_1),\ldots ,(x_m,\overline{x}_m)$, (II) start by taking the face $\delta _1$ or $\delta _2$ and (III) reach the ending branch-type pairing 34 exclusively through falling-vertex elementary paths. It suffices to construct an involution $\iota \colon \mathcal{G}'\to \mathcal{G}'$, with $\mathcal{G}'\coloneq \mathcal{G}\setminus \mathcal{J}$, such that each pair of paths $\gamma$ and $\iota (\gamma )$ shares origin and has opposite multiplicity. With this in mind, we first note that condition (II) is forced by conditions (I) and (III). Indeed, in any gradient path $e\searrow e'\nearrow \cdots$ all of whose upper elementary factors are of falling-vertex type,

$$\begin{equation} \text{the edge ingredients of $e'$ are present in all steps of the path.} {\tag{36}} \end{equation}$$

Therefore $\mathcal{G}'$ is partitioned into two sets, ${\mathcal{G}'}_\text{fall}$ and ${\mathcal{G}'}_\text{branch}$, where the former set consists of the paths in $\mathcal{G}$ that satisfy (III) without satisfying (I), and the latter set consists of the paths in $\mathcal{G}$ that do not satisfy (III). We construct involutions $\iota _\text{fall}\colon {\mathcal{G}'}_\text{fall}\to {\mathcal{G}'}_\text{fall}$ and $\iota _\text{branch}\colon {\mathcal{G}'}_\text{branch}\to {\mathcal{G}'}_\text{branch}$ with the required properties.

For a path ${\gamma }=a_0\searrow b_1\nearrow a_1\searrow \cdots \searrow b_k\nearrow a_k$ in ${\mathcal{G}'}_\text{fall}$, the observation in 36 and the form of the closing-lock pairing $b_k\nearrow a_k$ imply that all edges $(x_i,\overline{x}_i)$, $1\leq i\leq m$, must be ingredients of $a_0$. The additional edge of the critical $(m+1)$-cube $a_0$ must then have the form $(y,y[d])$, with $y\not \in \{x,x_1,\ldots ,x_m\}$, which is then replaced by either $y$ or $y[d]$ at the beginning of $\gamma$. Given the form of $b_k\nearrow a_k$, $y$ must lie in $x$-direction $r_x+1$. Then, as in the proof of Proposition 3.10, the definition of $\iota _{\text{fall}}$ is based on the two options for $a_0\searrow b_1$, as both lead to summands of 31—unlike the situation in Remark 5.2, the ending cube of $\iota _{\text{fall}}(\gamma )$ might fail to be in the $\Sigma _n$-orbit of the ending cube of $\gamma$. Likewise, the definition of $\iota _{\text{branch}}$ is based on the two forms of replacing by a vertex the edge ingredient at the last upper elementary factor that is not of falling-vertex type.

6. Exterior-face basis for trees with binary core

We have made a careful distinction between $\operatorname {Im}(\pi ^*)$ and $H^*(\operatorname {UD}_n T;R)$ in the previous sections so as to provide clear proof arguments. In this section we use the resulting algebro-combinatorial description of cup-products and have no need to make any further distinction between these isomorphic rings. Accordingly, we transfer the notation and descriptions of elements in $\operatorname {Im}(\pi ^*)$ back to $H^*(\operatorname {UD}_n T;R)$. In particular, the notation and conventions in the paragraph containing 19 will be carried over this final section, directly in the context of $H^*(\operatorname {UD}_n T;R)$, with the simplifications discussed below.

Definition 6.1.

A tree $T$ is said to have binary core provided that, for each essential vertex $x$ of $T$, at most two of the components of $T\setminus \{x\}$ in $x$-directions $1,2,\ldots ,d_x$ carry essential vertices (recall $d_x\coloneq d(x)-1$).

Throughout this section, $T$ stands for a tree with binary core (e.g. an actual binary tree). In addition, we assume that the chosen planar embedding of $T$ has been adjusted so that, for any essential vertex $x$ of $T$,

$$\begin{multline} \text{\textit{no component of $T\setminus \{x\}$ in $x$-direction $j$ with $1\leq j\leq d_x-2$}} \\ \text{\textit{carries an essential vertex}.} {\tag{37}} \end{multline}$$

There are two reasons for sticking to such a hypothesis. For one, the existence of non-vanishing products whose factors are given by weak-interacting basis elements

$$\begin{equation*} \{k_i\vert x_i,(p_{i,1},\ldots ,p_{i,r_i}),(q_{i,1},\ldots ,q_{i,s_i})\} \end{equation*}$$

with $x_1<\cdots <x_m$, i.e., the obstructions in Remark 1.8, is somehow restricted (cf. Example 1.6), while our description of the corresponding product is greatly simplified. Explicitly, in the setting and notation of Theorem 5.1, since the top left configuration in Figure 9 holds, 37 forces $s_x=1$, i.e., the edge $(x,\overline{x})$ must lie in the largest $x$-direction, with $x_1$ then lying in the second largest $x$-direction $r_x=d_x-1$. In particular, the product $\Pi _2$ takes the simpler form

$$\begin{equation} \Pi _2=-\sum \left\{R_0-|{a}|\Big \vert x,{a},Q_x\Big \vert x_1, P_{1},Q_{1}\Big \vert \cdots \Big \vert x_m, P_{m},Q_{m}\right\}, {\tag{38}} \end{equation}$$

where the sum runs over all $r_x$-tuples of integer numbers $a=(a_1,\ldots , a_{r_x})$ with $a>0$ and $|a|\leq R_0$.

The second advantage for working under the situation in 37 is that, for $1\leq i\leq m$ and $j\leq d_i-2$, any set of pruned leaves $L_{i,j}$ associated to a product 19 is empty. As a result, the corresponding $C_{i,j}$-local interaction is “vacuous” in the sense that the $C_{i,j}$-instance of 2 simplifies to $\ell _{C_{i,j}}(\nu _i)\geq 0$—a condition which is certainly true. In fact, still in the context of 19, there will be no local interactions in the positive $x_i$-directions leading to a weak interaction situation as long as $p_{i,j}>0$ for some $j\leq \min \{r_i,d_i-2\}$ (cf. 33). In particular, it makes sense to reset the notation for pruned leaves in the presence of 37: we shall set $L_1(x_i)\coloneq L_{i,d_i-1}$ and $L_2(x_i)\coloneq L_{i,d_i}$ when $i>0$, and $L_1(x_0)\coloneq L_{0,1}$ (recall from Definition 4.1 that $x_0$ stands for the root of $T$).

Expression 38 suggests redefining some of the basis elements $\langle k,x,(p_1,\ldots ,p_r)$, $(q_1,\ldots ,q_s)\rangle \in H^1(B_nT)$ in the proof of Theorem 1.7. Namely, for the purposes of this section, if $p_1=\cdots =p_{r-1}=0$ and $s=1$, we set

$$\begin{equation} \langle k,x,(p_1,\ldots ,p_r),(q_1,\ldots ,q_s)\rangle \coloneq \sum \left\{k-|a|\Big \vert x,(a_1,\ldots ,a_{r-1},p_r+a_r),(q_1)\right\}, {\tag{39}} \end{equation}$$

where the summation runs over all $r$-tuples $a=(a_1,\ldots ,a_r)\geq 0$ with $|a|\leq k$, otherwise we keep

$$\begin{equation*} \langle k,x,(p_1,\ldots ,p_r),(q_1,\ldots ,q_s)\rangle \coloneq \left\{k\Big \vert x,(p_1,\ldots ,p_r),(q_1,\ldots ,q_s)\right\}. \end{equation*}$$

Remark 6.2.

We use the angle-bracket notation $\left\langle k,x,p,q\right\rangle$ since we have reserved the parenthesis notation for cubes in $\operatorname {D}_n T$ (as tuples of their ingredients). Additionally, the angle-bracket notation is intended to stress the change of basis in 39.

A central task in this section is the analysis of the relationship between ordered⁠¹⁰ products

¹⁰

In the sense that $x_1<\cdots <x_m$.

✖

$$\begin{equation} \langle k_1,x_1,p_{1},q_{1}\rangle \cdots \langle k_m,x_m,p_{m},{q}_{m}\rangle \text{ and } \{ k_1\vert x_1,p_{1},q_{1}\}\cdots \{ k_m\vert x_m,p_{m},q_{m}\}. {\tag{40}} \end{equation}$$

We say that any of these products is a strong interaction product if the factors of the product on the right hand-side of 40 interact strongly (in the sense of Definition 4.3).

Remark 6.3.

Corollary 4.5, Proposition 4.4 and Theorem 5.1 show that both products in 40 are (possibly empty) linear combinations of basis elements

$$\begin{equation*} \{\smblkcircle \vert x_1,\smblkcircle ,\smblkcircle \vert \cdots \vert x_m,\smblkcircle ,\smblkcircle \}. \end{equation*}$$

Such a linear combination will be written as

$$\begin{equation*} \mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\smblkcircle \vert x_1,\smblkcircle ,\smblkcircle \vert \cdots \vert x_m,\smblkcircle ,\smblkcircle \}. \end{equation*}$$

Here and below, a dot ‘$\smblkcircle$’ stands for either an unspecified ring coefficient or an unspecified tuple⁠¹¹ of integer numbers, $t=(t_1,t_2,\ldots )\geq 0$, satisfying $t>0$ when the tuple immediately follows an essential vertex $x_i$ (the context clarifies the option).

¹¹

As in Definition 4.3, we make no distinction between integer numbers and 1-tuples.

✖

Theorem 6.4.

Let $T$ be a tree with binary core, $R$ be a commutative ring with 1, and $n\geq 1$. Then $H^*(B_nT;R)\cong \Lambda _R(K_nT)$. In detail: (i) An ordered product $\langle k_1,x_1,p_{1},q_{1}\rangle \cdots \langle k_m,x_m,p_{m},q_{m}\rangle$ is non-zero if and only if it is a strong interaction product. (ii) Two ordered strong interaction products agree if and only if they have the same factors. (iii) A graded basis of $H^*(\operatorname {UD}_n T)$ is given by the set of ordered strong interaction products.

The crux of the matter in the proof of Theorem 6.4 is getting at a precise description of the conditions that have to be satisfied by some of the unspecified dot ingredients in

$$\begin{equation} \langle k_1,x_1,p_{1},q_{1}\rangle \cdots \langle k_m,x_m,p_{m},q_{m}\rangle =\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\smblkcircle \vert x_1,\smblkcircle ,\smblkcircle \vert \cdots \vert x_m,\smblkcircle ,\smblkcircle \}. {\tag{41}} \end{equation}$$

With this in mind, the product in 41 will be denoted by $\varpi$ throughout the section, setting

$$\begin{equation*} R_0\coloneq \mathcal{R}_0(x_1,\ldots ,x_m),\; P_{i,j}\coloneq \mathcal{P}_{i,j}(x_1,\ldots ,x_m),\; Q_{i,j}\coloneq \mathcal{Q}_{i,j}(x_1,\ldots ,x_m), \end{equation*}$$

$P_i\coloneq (P_{i,1}, \dots , P_{i,r_i})$ and $Q_i\coloneq (Q_{i,1}, \dots , Q_{i,s_i})$, $1\leq i\leq m$, for the corresponding interaction parameters. Furthermore, we set

$$\begin{equation} B_i\coloneq (x_i,P_{i},Q_{i})\ \ \text{and} \ \ \dot{B}_i\coloneq (x_i,\smblkcircle ,\smblkcircle ), {\tag{42}} \end{equation}$$

where the latter expression stands for any triple with unspecified tuples in the second and third coordinates (subject to the usual restrictions). Additionally, the $i$-th factor on the left hand-side of 41 will denoted by $\phi _i$. For instance, in terms of the notation set forth in Definition 4.3,

$$\begin{equation*} \phi _i=\{k_i\vert x_i,p_{i},q_{i}\}+\sum \{\underline{k_i}\vert x_i,\smblkcircle ,q_{i}\}, \end{equation*}$$

with a possibly empty summation, whereas Corollary 4.5 asserts that the second product in 40 is trivial or agrees with $\{R_0\vert B_1\vert \ldots \vert B_m\}$ under, respectively, the no-interaction or strong-interaction condition of the factors.

In the following results, some of which are true for general trees, we make free use of the notation and considerations above. Likewise, the use of cup-product descriptions in Sections 4 and 5, with the simplification in 38, we will refer to generically as “interaction reasons”.

Lemma 6.5.

(1)

Assume $L_1(x_0)=\{x_1,x_2,\ldots ,x_m\}$ (left configuration in Figure 11), then$$\begin{equation*} \varpi =\begin{cases} \{R_0\vert B_1\vert \cdots \vert B_m\} +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}_1\vert \cdots \vert \dot{B}_m\}, & \text{if $R_0\geq 0$;} \\ 0, & \text{otherwise.} \end{cases} \end{equation*}$$

(2)

Assume $L_{1}(x_1)=\{x_2,x_3,\ldots ,x_u\}$ and $L_{2}(x_1)=\{x_{u+1},\ldots ,x_{m-1},x_m\}$ with $1\leq u\leq m$ (right configuration in Figure 11) with $u=1$ (i.e. $L_1(x_1)=\varnothing$ and $L_2(x_1)=\{x_2,\ldots ,x_m\})$ if $s_1=1$, then$$\begin{equation*} \varpi =\begin{cases} \begin{aligned} \{R_0\vert B_1\vert \cdots \vert B_m\}& + \mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}_1\vert \cdots \vert \dot{B}_m\}\\ &+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert x_1,P_{1},\underline{Q_{1}}\vert \dot{B}_2\vert \cdots \vert \dot{B}_m\}, \end{aligned} & \text{if $Q_1\geq 0;$} \\ 0, & \text{otherwise.} \end{cases} \end{equation*}$$

Proof.

The first assertion follows by direct inspection of the expression

$$\begin{equation*} \left(\{k_1\vert x_1,p_{1},q_{1}\} +\sum \{\underline{k_1}\vert x_1,\smblkcircle ,\smblkcircle \}\right)\cdots \left(\{k_m\vert x_m,p_{m},q_{m}\}+\sum \{\underline{k_m}\vert x_m,\smblkcircle ,\smblkcircle \}\right), \end{equation*}$$

noticing that the only non-vacuous interaction occurs in the tree $T_{0,1}$ (so that $P_i=p_i$ and $Q_i= q_i$ for $1\leq i\leq m$). The second assertion is proved in a similar way, noticing that this time non-vacuous interactions occur only either on $T_{1,d_1}$ or $T_{1,d_1-1}$ (or both). In any case, $R_0=k_1$, $P_{i}=p_{i}$ for $1\leq i \leq m$, while $Q_{i}=q_i$ for $2\leq i\leq m$.

■

A key situation with $L_1(x_1)\cup L_2(x_1)=\{x_2,x_3,\ldots ,x_m\}$ not covered by Lemma 6.5(2) is:

Lemma 6.6.

Assume $L_{1}(x_1)=\{x_2,x_3,\ldots ,x_m\}$. Then the product of $\langle k_1, x_1,(p_{1,1},\ldots ,p_{1,d_1-1}),(q_{1,1})\rangle$ with $\{R\vert x_2,p_{2},q_{2}\vert \cdots \vert x_m,p_{m},q_{m}\}$ vanishes provided $p_{1,1}=\cdots =p_{i,d_1-2}=0$ and $p_{1,d_1-1}+R\leq n$.

Proof.

We proceed by induction on $p_{1,d_1-1}+R-n=p_{1,d_1-1}+\sum _{j=2}^m(t_j-n)\in \{0,-1,-2,\ldots \}$, where

$$\begin{equation*} \{R\vert x_2,p_{2},q_{2}\vert \cdots \vert x_m,p_{m},q_{m}\}=\{t_2\vert x_2,p_{2},q_{2}\}\cdots \{t_m\vert x_m,p_{m},q_{m}\} \end{equation*}$$

is the unique strong-interaction factorization of $\{R\vert x_2,p_{2},q_{2}\vert \cdots \vert x_m,p_{m},q_{m}\}$ noted in the proof of Theorem 1.7. Since $p_{1,j}=0$ for $j=1,\ldots ,d_1-2$, the induction is grounded for $p_{1,d_1-1}+R-n=0$ by

$$\begin{align*} \{k_1\vert \, & x_1,(p_{1,1},\ldots ,p_{1,d_1-1}),(q_{1,1})\}\cdot \left(\{t_2\vert x_2,p_{2},q_2\}\cdots \{t_m\vert x_m,p_{m},q_{m}\}\right)\\ &=-\sum \{ k_1-|a|\vert x_1,a,(q_{1,1})\vert x_2,p_2,q_2\vert \cdots \vert x_m,p_m,q_m\}\\ &=-\sum \{k_1-|a|\vert x_1,(a_1,\ldots ,a_{d_1-2},p_{1,d_1-1}+a_{d_1-1}),(q_{1,1})\} (\{t_2\vert x_2,p_{2},q_{2}\}\\ &\qquad \cdots \{t_m\vert x_m,p_{m},q_{m}\}), \end{align*}$$

where both summations run over tuples $a=(a_1,\ldots ,a_{d_1-1})>0$ with $|a|\leq k_1$. The inductive step then follows by noticing that, for $p_{1,d_1-1}+R-n<0$,

$$\begin{align*} \langle k_1, x_1,&\,(p_{1,1},\ldots ,p_{1,d_1-1}),(q_{1,1})\rangle \cdot \left(\{t_2\vert x_2,p_2,q_2\}\cdots \{t_m\vert x_m,p_m,q_m\}\right)\\ =&\langle k_1-1, x_1, (p_{1,1},\ldots ,p_{1,d_1-2},p_{1,d_1-1}+1),(q_{1,1})\rangle \\ & \cdot \left(\{t_2\vert x_2,p_2,q_2\}\cdots \{t_m\vert x_m,p_m,q_m\}\right), \end{align*}$$

as

$$\begin{multline*} \{k_1-|a|\vert x_1, (p_{1,1}+a_1,\ldots ,p_{1,d_1-2}+a_{d_1-2},p_{1,d_1-1}),(q_{1,1})\}\\ \cdot \left(\{t_2\vert x_2,p_2,q_2\}\cdots \{t_m\vert x_m,p_m,q_m\}\right) \end{multline*}$$

vanishes for $a=(a_1,\ldots ,a_{d_1-2},0)\geq 0$ with $|a|\leq k_1$ by interaction reasons.

■

Corollary 6.7.

If the factors on the left of 41 do not yield a strong interaction product, then $\varpi =0$.

Proof.

By focusing on the factors $\phi _i$ of $\varpi$ that are involved in a faulty interaction parameter, it suffices to consider three cases: $L_1(x_0)=\{x_1,\ldots ,x_m\}$, $L_{2}(x_1)=\{x_2,\ldots ,x_m\}$ and $L_{1}(x_1)=\{x_2,\ldots ,x_m\}$. The first two cases are covered by Lemma 6.5. On the other hand, there are two options for the instances of the third case that are not covered by Lemma 6.5(2): either $p_{1,j}>0$ for some $j\in \{1,2,\ldots ,d_1-2\}$ or $p_{1,j}=0$ for all $j\in \{1,2,\ldots ,d_1-2\}$—in both cases $s_1=1$. In the latter option, the result follows from Lemma 6.6; in the former option we have $\langle k_1,x_1,p_1,q_1\rangle =\{k_1 \vert x_1,p_1,q_1\}$ while the condition $p_{1,d_1-1}+\mathcal{R}_0(x_2,\ldots ,x_m)<n$ is forced by the no-strong-interaction hypothesis, so that the result follows by interaction reasons in view of Lemma 6.5(1).

■

The proof of Theorem 6.4 will be complete once we set a one-to-one correspondence between the set of ordered strong interaction products $\varpi$ and the graded basis of $H^*(B_nT;R)$ formed by the elements in 10. With this in mind, we start with a two-step approach to the missing case in Lemma 6.5(2):

Lemma 6.8.

Assume $L_{1}(x_1)=\{x_2,x_3,\ldots ,x_m\}$ with $s_1=1$. Then

$$\begin{equation} \varpi =\begin{cases} \begin{aligned} \{R_0\vert B_1\vert \cdots \vert B_m\}&+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}_1\vert \cdots \vert \dot{B}_m\}\\ & +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \, \{R_0\vert x_1,\underline{P_{1}},Q_{1}\vert \dot{B}_2\vert \cdots \vert \dot{B}_m\}, \end{aligned} & \text{if $P_{1}>0;$} \\ 0, & \text{otherwise.} \end{cases} {\tag{43}} \end{equation}$$

Proof.

Interactions occur only in $T_{1,d_1-1}$, so $R_0=k_1$, $Q_i=q_{i}$ for $1\leq i\leq m$, and $P_{i}=p_{i}$ for $2\leq i\leq m$. By Corollary 6.7, only the case $P_{1}>0$ needs to be argued. Use Lemma 6.5(1) to write $\varpi =\phi _1\cdot (\phi _2\cdots \phi _m)$ as

$$\begin{equation*} \left(\{R_0\vert x_1,p_{1},Q_{1}\} +\sum \{\underline{R_0}\vert x_1,\smblkcircle ,Q_{1}\}\right) \left(\{R'_0\vert B_2\vert \cdots \vert B_m\}+\sum \{\underline{R'_0}\vert \dot{B}_2\vert \cdots \vert \dot{B}_m\}\right), \end{equation*}$$

where $R'_0=\mathcal{R}_0(x_2,\ldots ,x_m)$ (so $P_{1,d_1-1}=p_{1,d_1-1}+R'_0-n$). The result then follows by direct inspection, though this time 38 needs to be used in the analysis of the products giving rise to the terms in both summations of 43.

■

Proposition 6.9.

Assume $L_{1}(x_1)=\{x_2,x_3,\ldots ,x_u\}$ and $L_{2}(x_1)=\{x_{u+1},\ldots , x_{m-1},x_m\}$, with $1<u<m$ and $s_1=1$. Then

$$\begin{equation*} \varpi =\begin{cases} \begin{aligned} \{R_0\vert B_1\vert \cdots \vert B_m\}&+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}_1\vert \cdots \vert \dot{B}_m\}\\ &+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert x_1,\underline{P_{1},Q_{1}}\vert \dot{B}_2\vert \cdots \vert \dot{B}_m\}, \end{aligned} &\text{if $P_{1}>0\leq Q_{1}$;}\\ 0,&\text{otherwise.} \end{cases} \end{equation*}$$

Here and below each expression $\underline{P_{1},Q_{1}}$ is meant to represent a pair $V_1,W_1$ of unspecified tuples of integer numbers with $V_1=(V_{1,1},\ldots ,V_{1,d_1-1})$, $W_1=(W_{1,1})$ and such that $V_1>0\leq W_1$ and $(V_1,W_1)<(P_{1},Q_{1})$ in the product ordering, i.e., $V_{1,j}\leq P_{1,j}$ for $j=1,2,\ldots , d_1-1$ and $W_{1,1}\leq Q_{1,1}$, with at least one of the last $d_1$ inequalities being strict.

Proof.

By Corollary 6.7, it suffices to consider the case $P_1>0\leq Q_1$. Lemmas 6.5(1) and 6.8 allow us to write $\varpi =(\phi _1\cdots \phi _u)\cdot (\phi _{u+1}\cdots \phi _m)$ as the product of

$$\begin{multline*} \{R_0\vert x_1,P_{1},q_{1}\vert B_2\vert \ldots \vert B_u\} +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}_1\vert \dot{B}_2\vert \ldots \vert \dot{B}_u\}\\ +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert x_1,\underline{P_{1}},q_{1}\vert \dot{B}_2\vert \ldots \vert \dot{B}_u\} \end{multline*}$$

with

$$\begin{equation*} \{R'_0\vert B_{u+1}\vert \ldots \vert B_m\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R'_0}\vert \dot{B}_{u+1}\vert \ldots \vert \dot{B}_m\}, \end{equation*}$$

where $R'_0=\mathcal{R}_0(x_{u+1},\ldots ,x_m)$ (so $Q_{1,1}=q_{1,1}+R'_0-n$). The result follows by inspection.

■

We are now ready to set up the strategy for completing the proof of Theorem 6.4. By Lemma 4.6, Remark 6.3 and Corollary 6.7, the goal reduces to describing, for fixed essential vertices $x_1<\cdots <x_m$, a partial ordering $\preceq$ on the set of basis elements $\{t_0\vert x_1,u_{1},v_{1}\vert \cdots \vert x_m,u_{m},v_{m}\}$ of $H^m(\operatorname {UD}_n T)$ such that any strong interaction product 41 can be expressed by a congruence

$$\begin{equation} \langle k_1,x_1,p_{1},q_{1}\rangle \cdots \langle k_m,x_m,p_{m},q_{m}\rangle \equiv \{R_0\vert B_1\vert \cdots \vert B_m\} {\tag{44}} \end{equation}$$

modulo basis elements that are $\preceq$-smaller than $\{R_0\vert B_1\vert \cdots \vert B_m\}$. The partial ordering $\preceq$ we need becomes apparent by writing either of the triples $(x_1,\underline{P_1,Q_1})$, $(x_1,\underline{P_1},Q_1)$ and $(x_1,P_1,\underline{Q_1})$ in Proposition 6.9 and Lemmas 6.8 and 6.5(2), respectively, as $\underline{B_1}$. Indeed, in such terms, the ($P_1>0\leq Q_1$)-conclusions in those results can be written as

$$\begin{equation} \varpi =\{R_0\vert B_1\vert \cdots \vert B_m\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}_1\vert \cdots \vert \dot{B}_m\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert \underline{B_1}\vert \dot{B}_2\vert \cdots \vert \dot{B}_m\}. {\tag{45}} \end{equation}$$

Definition 6.10.

The $\ell$-th level of pruned leaves $\mathcal{L}_\ell$ of the essential vertices $x_1<\cdots <x_m$ is

$$\begin{equation*} \mathcal{L}_\ell =\mathcal{L}_\ell (x_1,\ldots ,x_m)\coloneq \begin{cases} \;L_1(x_0), & \text{if $\ell =1$;}\\ \;\bigcup _{x_i\in \mathcal{L}_{\ell -1}}\left(L_1(x_i)\cup L_2(x_i)\right), & \text{if $\ell >1$.} \end{cases} \end{equation*}$$

The interaction level of the vertices $x_1<\cdots <x_m$ is the largest $\ell$ such that $\mathcal{L}_\ell \neq \varnothing$. Furthermore, extending the notation introduced in 42 and 45, let $B^{(\ell )}$ denote the collection of blocks $B_i$ with $x_i\in \mathcal{L}_\ell$, and let $\dot{B}^{(\ell )}$ stand for any collection of blocks $\dot{B}_i$ with $x_i\in \mathcal{L}_\ell$. On the other hand, $\underline{B^{(\ell )}}$ stands for any collection of blocks $(x_i,V_{i},W_{i})$, with $x_i\in \mathcal{L}_\ell$, satisfying:

•

$V_i>0\leq W_i$ and $(V_i,W_i)\leq (P_{i},Q_{i})$ (the latter in the product ordering) for all $x_i\in \mathcal{L}_\ell$, and

•

$(V_i,W_i)\neq (P_{i},Q_{i})$ for at least one $x_i\in \mathcal{L}_\ell$.

Note that the definition of $\underline{B^{(\ell )}}$ is less restrictive than actually requiring $\underline{B^{(\ell )}}$ to be a collection of blocks $\underline{B_i}$ with $x_i\in \mathcal{L}_\ell$. As in Proposition 6.9, the condition we want for $\underline{B^{(\ell )}}$ is based on a strict product-order inequality. The reason for this becomes apparent in the proof of Proposition 6.12.

Example 6.11.

Lemma 6.5(1) gives $\varpi =\{R_0,B^{(1)}\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R}_0,\dot{B}^{(1)}\}$ in interaction level 1 (under a strong condition hypothesis). Likewise, 45 becomes

$$\begin{equation} \varpi =\{R_0\vert B^{(1)}\vert B^{(2)}\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}^{(1)}\vert \dot{B}^{(2)}\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert \underline{B^{(1)}}\vert \dot{B}^{(2)}\} {\tag{46}} \end{equation}$$

in interaction level 2 (with $\mathcal{L}_1=\{x_1\}$, so $B^{(1)}$ consist of $B_1$ alone). In full generality:

Proposition 6.12.

Let $x_1<\cdots <x_m$ be essential vertices having interaction level $\ell$. If $\varpi$ is a strong interaction product, then

$$\begin{equation} \begin{split} \varpi \,=&\,\,\{R_0\vert B^{(1)}\vert \cdots \vert B^{(\ell )}\}+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{\underline{R_0}\vert \dot{B}^{(1)}\vert \cdots \vert \dot{B}^{(\ell )}\}\\ &+\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert \underline{B^{(1)}}\vert \dot{B}^{(2)}\vert \cdots \vert \dot{B}^{(\ell )}\}+\cdots \\ & +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\{R_0\vert B^{(1)}\vert \cdots \vert B^{(\ell -2)}\vert \underline{B^{(\ell -1)}}\vert \dot{B}^{(\ell )}\}. \end{split} {\tag{47}} \end{equation}$$

Proof of Theorem 6.4 (Conclusion).

Partially order the set of basis elements

$$\begin{equation*} \{v_0\vert x_1,v_{1},w_{1}\vert \cdots \vert x_m,v_{m},w_{m}\} \end{equation*}$$

by means of a level-wise lexicographical comparison of their $v$- and $w$-ingredients. Then 47 yields the required congruence 44.

■

Proof of Proposition 6.12.

The argument is by direct computation, proceeding by induction on $\ell$ and with Example 6.11 grounding the induction. The real challenge consists of setting a suitable notation so arguments can be seen clearly. With this in mind, we start by checking the situation in the special case $\mathcal{L}_1=\{x_1\}$ (so $R_0=k_1$), i.e., the generalization of 46 to higher interaction levels. In such a situation

$$\begin{equation} \mathcal{L}_\lambda (x_2,\ldots ,x_m)=\mathcal{L}_{\lambda +1}(x_1,\ldots ,x_m),\text{ for $\lambda \geq 2$.} {\tag{48}} \end{equation}$$

Accordingly, we reset notation and start level-number counting at 2 (rather than at 1) for $x_2<\cdots <x_m$, so as to make it compatible with that for $x_1<\cdots <x_m$. Thus, 48 gets replaced by

$$\begin{equation} \mathcal{L}_\lambda (x_2,\ldots ,x_m)=\mathcal{L}_\lambda (x_1,\ldots ,x_m),\text{ for $\lambda \geq 3$.} {\tag{49}} \end{equation}$$

Let $x_2,x_3,\ldots ,x_t$ be the essential vertices lying on the component of $T\setminus \{x_1\}$ in $x_1$-direction $d_1-1$, while $x_{t+1},x_{t+2},\ldots ,x_m$ be the vertices lying on the component of $T\setminus \{x_1\}$ in $x_1$-direction $d_1$ ($1\leq t\leq m$). Then, if $B^{(\lambda )}$, $\dot{B}^{(\lambda )}$ and $\underline{B^{(\lambda )}}$ stand for collections defined by all the vertices $x_1,\ldots ,x_m$, we write

$$\begin{equation} B^{(\lambda )}_{[\epsilon ]}, \;\; \dot{B}^{(\lambda )}_{[\epsilon ]} \;\;\text{or}\;\; \underline{B^{(\lambda )}_{[\epsilon ]}}, {\tag{50}} \end{equation}$$

with $\varepsilon =1$, to denote the corresponding parts coming only from the vertices $x_2,\ldots ,x_t$. Likewise, the case $\epsilon =2$ in 50 stands for the parts that come from the vertices $x_{t+1},\ldots ,x_m$. For instance, $B^{(\lambda )}=B^{(\lambda )}_{[1]}\cup B^{(\lambda )}_{[2]}$. In these terms, we use induction to write $\varpi =\phi _1\cdot (\phi _2\cdots \phi _t)\cdot (\phi _{t+1}\cdots \phi _m)$ as the product of the three expressions

$$\begin{equation*} \{R_0\vert x_1,p_{1},q_{1}\}+\sum \{\underline{R_0}\vert x_1,\smblkcircle ,q_{1}\}, \end{equation*}$$

$$\begin{multline*} \left\{R'_0\Big \vert B_{[1]}^{(2)}\Big \vert \cdots \Big \vert B_{[1]}^{(\ell )}\right\}+ \mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\left\{\underline{R'_0}\Big \vert \dot{B}_{[1]}^{(2)}\Big \vert \cdots \Big \vert \dot{B}_{[1]}^{(\ell )}\right\}\\ +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits _{3\leq j\leq \ell }\,\left\{R'_0\Big \vert B_{[1]}^{(2)}\Big \vert \cdots \Big \vert B_{[1]}^{(j-2)}\Big \vert \underline{B_{[1]}^{(j-1)}}\Big \vert \dot{B}_{[1]}^{(j)}\Big \vert \cdots \Big \vert \dot{B}_{[1]}^{(\ell )}\right\}, \end{multline*}$$ and

$$\begin{multline*} \left\{R''_0\Big \vert B_{[2]}^{(2)}\Big \vert \cdots \Big \vert B_{[2]}^{(\ell )}\right\}+ \mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\left\{\underline{R''_0}\Big \vert \dot{B}_{[2]}^{(2)}\Big \vert \cdots \Big \vert \dot{B}_{[2]}^{(\ell )}\right\} \\ +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits _{3\leq j\leq \ell }\,\left\{R''_0\Big \vert B_{[2]}^{(2)}\Big \vert \cdots \Big \vert B_{[2]}^{(j-2)}\Big \vert \underline{B_{[2]}^{(j-1)}}\Big \vert \dot{B}_{[2]}^{(j)}\Big \vert \cdots \Big \vert \dot{B}_{[2]}^{(\ell )}\right\}, \end{multline*}$$

where $R'_0=\mathcal{R}_0(x_2,\ldots ,x_t)$ and $R''_0=\mathcal{R}_0(x_{t+1},\ldots ,x_m)$. Note the compactified notation for the two summations running over $j$, each of which really stands for sums of summations as in 47. Note also that the interaction level of the vertices $x_2,\ldots ,x_t$ (or $x_{t+1},\ldots ,x_m$) could be smaller than $\ell$, in which case some of the corresponding collections of blocks are empty. Then, by direct inspection and interaction reasons (using 38 when $s_1=1$ and the interaction parameter under consideration lies in $x_1$-direction $d_1-1$), the product of the three expressions above takes the form 47. This completes the proof when $\mathcal{L}_1$ is a singleton.

In general, $\mathcal{L}_1$ consists of, say, vertices $x_1=x_{i_1}<\cdots <x_{i_k}$, and we evaluate $\varpi$ as the length-$k$ product

$$\begin{equation} (\phi _1\cdots \phi _{i_2-1})(\phi _{i_2}\cdots \phi _{i_3-1})\cdots (\phi _{i_k}\cdots \phi _m). {\tag{51}} \end{equation}$$

(This time there is no need to reset notation so as to get the analogue of 49 to hold.) We have just seen that the $w$-th factor in 51 takes the form

$$\begin{multline*} \left\{r_{i_w}\Big \vert B_{[w]}^{(1)}\Big \vert {\cdots }\Big \vert B_{[w]}^{(\ell )}\right\}+ \mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits \,\left\{\underline{r_w}\Big \vert \dot{B}_{[w]}^{(1)}\Big \vert {\cdots }\Big \vert \dot{B}_{[w]}^{(\ell )}\right\}\\ +\mathop{ \vcenter{\img[][14pt][11pt][{$\sum\raisebox{.6mm}{$\centerdot$}$}]{Images/img3e04cb397c31108057dd343a03dfe5bb.svg}} }\limits _{2\leq j\leq \ell }\,\left\{r_{i_w}\Big \vert B_{[w]}^{(1)}\Big \vert {\cdots }\Big \vert B_{[w]}^{(j-2)}\Big \vert \underline{B_{[w]}^{(j-1)}}\Big \vert \dot{B}_{[w]}^{(j)}\Big \vert {\cdots }\Big \vert \dot{B}_{[w]}^{(\ell )}\right\}, \end{multline*}$$

where

$$\begin{equation*} B_{[w]}^{(1)}\coloneq B_{i_w}, \ \ \dot{B}_{[w]}^{(1)}\coloneq \dot{B}_{i_w}, \ \ \underline{B_{[w]}^{(1)}}\coloneq \underline{B_{i_w}} \end{equation*}$$

and, for interaction levels larger than 1, a subindex ‘[$w$]’ in a collection of blocks indicates that only blocks in positive $x_{i_w}$-directions are to be taken. The required form 47 for the product of all these expressions follows again from direct inspection—this time without requiring the use of 38.

■

Figure 1.

The $d(x)$ $x$-directions from an essential vertex $x$

Figure 2.

The local information given by a vertex $\langle k,x,{(p_1,\ldots ,p_r), (q_1,\ldots ,q_s)} \rangle$ of $K_nT$

Figure 3.

Three different aspects of the minimal non-linear tree $T_0$

$$\begin{equation*} \vcenter{\img[][377pt][97pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[x=.51cm,y=.51cm] \draw(0,0)--(0,2);\draw(0,0)--(1.4,-1.4);\draw(0,0)--(-1.4,-1.4); \draw(0,2)--(1.3,3.3);\draw(0,2)--(-1.3,3.3); \draw(1.4,-1.4)--(3,-1.4);\draw(1.4,-1.4)--(1.4,-2.8); \draw(-1.4,-1.4)--(-3,-1.4);\draw(-1.4,-1.4)--(-1.4,-2.8); \node[below] at (-1.4,-2.8) {\scriptsize\red{root}}; \node[above] at (1.6,-1.45) {\scriptsize{$x_4$}}; \node[below] at (.05,-.1) {\scriptsize{$x_2$}}; \node[above] at (-1.6,-1.45) {\scriptsize{$x_1$}}; \node[above] at (0,2.2) {\scriptsize{$x_3$}}; \par\draw(-10,0)--(-10,2);\draw(-10,0)--(-8.6,-1.4);\draw(-10,0)--(-11.4,-1.4); \draw(-10,2)--(-8.7,3.3);\draw(-10,2)--(-11.3,3.3); \draw(-8.6,-1.4)--(-7,-1.4);\draw(-8.6,-1.4)--(-8.6,-2.8); \draw(-11.4,-1.4)--(-13,-1.4);\draw(-11.4,-1.4)--(-11.4,-2.8); \node[below] at (-8,-1.3) {\scriptsize{$\red{1}$}}; \node[below] at (-8.8,-1.55) {\scriptsize{$\red{0}$}}; \node[below] at (-8.8,-.43) {\scriptsize{$\red{2}$}}; \node[below] at (-10.85,-.8) {\scriptsize{$\red{2}$}}; \node[below] at (-11.6,-1.6) {\scriptsize{$\red{0}$}}; \node[below] at (-11.85,-.72) {\scriptsize{$\red{1}$}}; \node[below] at (-10.2,2) {\scriptsize{$\red{2}$}}; \node[below] at (-10.25,3.05) {\scriptsize{$\red{1}$}}; \node[below] at (-9.4,2.65) {\scriptsize{$\red{0}$}}; \node[below] at (8.6,-2.8) {\scriptsize\red{root}}; \par\draw(10,0)--(10,2);\draw(10,0)--(11.4,-1.4);\draw(10,0)--(8.6,-1.4); \draw(10,2)--(11.3,3.3);\draw(10,2)--(8.7,3.3); \draw(11.4,-1.4)--(13,-1.4);\draw(11.4,-1.4)--(11.4,-2.8); \draw(8.6,-1.4)--(7,-1.4);\draw(8.6,-1.4)--(8.6,-2.8); \node[below] at (12,-1.2) {\scriptsize{$\red{1}$}}; \node[below] at (11.2,-1.55) {\scriptsize{$\red{0}$}}; \node[below] at (11.2,-.43) {\scriptsize{$\red{7}$}}; \node[below] at (9.1,-.85) {\scriptsize{$\red{7}$}}; \node[below] at (8.4,-1.55) {\scriptsize{$\red{0}$}}; \node[below] at (8.15,-.72) {\scriptsize{$\red{1}$}}; \node[below] at (9.8,2) {\scriptsize{$\red{6}$}}; \node[below] at (9.75,3.1) {\scriptsize{$1$}}; \node[below] at (10.6,2.65) {\scriptsize{$\red{1}$}}; \node[below] at (10.25,-.15) {\scriptsize{$2$}}; \node[left] at (9.8,-.15) {\scriptsize{$2$}}; \node[below] at (10.25,.9) {\scriptsize{$4$}}; \node[below] at (-11.37,-2.8) {\scriptsize\red{root}}; \node at (0,3.5) {\rule{4mm}{0mm}}; \end{tikzpicture}}]{Images/img842af35c5972df63b12a5d58f5c03cd2.svg}} \end{equation*}$$

Figure 4.

A planar embedding of a binary linear tree

Figure 5.

Critical ingredients blocked by the root ($k=2$) and by an order-disrespectful edge $(x_i,x_i[3])$ ($r_i=2$, $t_{i,1}=1$, $t_{i,2}=3$, $t_{i,3}=2$ and $t_{i,4}=1$)

Figure 6.

A critical 3-cell $\{2 \vert x_1,{(2),(0)} \vert x_2,{(1,0),(1)} \vert x_3,{(1),(1,1)}\}$

Figure 7.

A portion of the 1-cube $d_{{\lambda }+1}$ with its recently created edge $(x,{x[d']})$

Figure 8.

The edge $(x_{m+1},\overline{x}_{m+1})$ belongs to $T_{{t},3}$, so the path from $x_t$ to $x_{m+1}$ does not pass through an essential vertex $x_j$

Figure 9.

The four possible configurations with $x<x_1$

Figure 10.

Dynamics of paths in $\mathcal{L}^-$ (top) and $\mathcal{L}^+$ (bottom)

$$\begin{align*} \underbrace{\overrightarrow {(x,\overline{x})},\overline{x}+1,\ldots ,\overline{x}+b-1}_{\text{$b$ falling vertices}},&\;\overbrace {\;\overline{x}+b,\;}^{\text{closing-lock vertex}}\;\underbrace{\overline{x}+b+1,\ldots ,\overline{x}+b+Q_{x,1}}_{\text{vertices in $B_{x,r_x+1}$ at the end of $\lambda _{a,b}^-$}} \\ \overleftarrow {(x,\overline{x})},\underbrace{\overline{x}+1,\ldots ,\overline{x}+b}_{\text{$b$ falling vertices}},\;&\overbrace {\overline{x}+b+1,}^{\text{closing-lock vertex}}\;\underbrace{\overline{x}+b+2,\ldots ,\overline{x}+b+Q_{x,1}+1}_{\text{vertices in $B_{x,r_x+1}$ at the end of $\lambda _{a,b}^+$}} \end{align*}$$

Figure 11.

Configurations of essential vertices in Lemma 6.5