Castling tree of tight Dyck nests with applications to odd and middle-levels graphs

1. Introduction

For \(0<k<n\in\mathbb{Z}\), the Kneser graph \(K_{n,k}\) [1, 2] has as its vertices all \(k\)-subsets of the set \([0,n-1]=\{0,1,\ldots,n-1\}\), with any two such vertices adjacent if and only if their intersection as \(k\)-subsets of \([0,n-1]\) is empty. For \(n=2k+1\), \(K(n,k)\) is the odd graph \(O_k\). We represent the vertices of \(O_k\) by the characteristic vectors of those \(k\)-subsets of \([0,n-1]\), so that each such \(k\)-subset is the support of its characteristic vector.

Those vectors represent the members of the \(k\)-level \(L_k\) of the Boolean lattice \(B_{2k+1}\) on \([0,2k]\). The complements of the reversed strings of those vectors are taken to represent the \((k+1)\)-level \(L_{k+1}\) of \(B_{2k+1}\). The union of these two levels, \(L_k\cup L_{k+1}\), is the vertex set of the middle-levels graph \(M_k\) [3], with adjacency given by the inclusion of \(L_k\) in \(L_{k+1}\). This yields a 2-covering graph map \(\Psi_k:M_k\rightarrow O_k\) expressible via the reversed complement bijection \(\aleph:V(M_k)\rightarrow V(M_k)\) given by \(\aleph(v_0v_1\cdots v_{2k-1}v_{2k})=\bar{v}_{2k}\bar{v}_{2k-1}\cdots\bar{v}_1\bar{v}_0\), where \(\bar{0}=1\) and \(\bar{1}=0\), so that \(\aleph(L_k)=L_{k+1}\) and \(\aleph(L_{k+1})=L_k\), and extending to a graph automorphism of \(M_k\), again denoted w.l.o.g. by \(\aleph\). In fact, \(\Psi:M_k\rightarrow O_k\) is characterized by its restriction to the identity map over \(L_k\) and by its restriction to \(\aleph\) over \(L_{k+1}\).

Odd graphs were shown to be Hamiltonian in [2], as an initial step in proving that sparse Kneser graphs were Hamiltonian. And this result was extended in [1] to all Kneser graphs.

More specifically, an investigation of relations of Dyck words [2] controlled by the infinite ordered tree \(T\) of restricted-growth strings ( [4, p. 325]) that are tight (see definitions in §2), to the graphs \(O_k\) and \(M_k\) is undertaken. A definition of \(T\) is developed in §3, while Dyck nests and tight Dyck nests are introduced in §4 associated to corresponding Dyck words and tight Dyck words via their Dyck path heights. As said, a castling procedure assigning tight Dyck nests to the vertices of \(T\) is introduced in §5.

Thus, the main objective of the present work is to apply the tree \(T\) (§3) of tight restricted-growth strings, or TRGSs, (§2) lexicographically ordered by the nonnegative integers \(n\) to the Dyck words and nests of §4, so that to each TRGS \(b(n)\) corresponds a specific Dyck nest \(f(n)\), and to each child of \(T\) corresponds the castling (§5) of its parent node.

§6-§7 introduce how to blow and anchor these words and nests, adapting them as vertex representatives of the graphs \(O_k\) and \(M_k\). In §8, an edge-supplementary arc-factorization [5] of each odd graph based on those representatives is given.

Based on the work of Mütze et al. [2, 6], a permutation is assigned in §9 to each Dyck nest \(F\), leading §10 to establish uniform 2-factors both in the \(O_k\) and the \(M_k\), as in [6]. The said uniform 2-factors yield a partition of \(V(O_k)\) (§11), and thus a partition of \(V(M_k)\), too. However, another partition can be used, instead, based on the action of the cyclic and the dihedral group on \(V(O_k)\) and \(V(M_k)\), respectively.

In §12, we assign a clone to each Dyck nest \(F\). This clone is equivalent to \(F\) (Theorem 2). Moreover, the clone is universally updated along \(T\) (Theorem 1). Thus, it generates an infinite sequence of updates; see also [7].

A convenient set of strings is established in §13, allowing to associate the elements of the graphs \(O_k\) and \(M_k\), as arising from the tree \(T\) (Theorems 6-7 and Corollary 3) based on either of the two mentioned partitions. This allows the cited arc-factorization approach to take to the Hamilton cycles of odd graphs and middle-levels graphs of [2] (§14, Theorem 8).

In sum, our approach differs from that of [2] by reversed complementation, so it constitutes an alternative reinterpretation of [2]. That far can be said as for a comparison of this work with that of [2], as we just have provided a universal treatment for all odd and middle-levels graph that [2] did not. As our treatment differs from that of [2] just by reversed complementation, adapting [2] to our approach did not offer any additional improvement in time complexity. About the time complexity of castling, see after Example 8.

2. Tight restricted-growth strings

Let \({\mathcal S}\) be the lexicographically-ordered sequence of TRGS’s. Then, \({\mathcal S}\) is the infinite extension of the sequence [8, A239903] (finite, as it only uses decimal digit entries \(a_j\), while in \({\mathcal S}\) the digit entries \(a_j\) grow unbounded).

The following definition yields the original notion of restricted-growth string in [4, p.325].

Note that no TRGS starts with 0 if it contains more than one entry. On the other hand, 01 is an RGS, not an TRGS.

3. Tree of tight restricted-growth strings

4. Dyck words, Dyck nests and blowing

We just have seen that to each \(n\in\mathcal{N}\) corresponds a TRGS that constitutes a vertex of the tree \(T\), and that \(V(T)\) is formed by such TRGSs. In §5, we will see that \(V(T)\) is the domain of a castling correspondence whose image is formed by Dyck nests, that we introduce in this section.

Example 4. Figure 1 illustrates Definitions 9–10–11. In fact, for each one of the eight cases in the figure, a piecewise-linear curve \(g_f\) is constructed iteratively that starts at the shown origin O in the Cartesian plane \(\mathbb{R}^2\) by replacing successively the 0-bits and 1-bits of \(f\) by up-steps and down-steps, namely diagonal segments \((x,y)(x+1,y+1)\) and \((x,y)(x+1,y-1)\), respectively. We assign the integers in the interval \([0,k]\) in decreasing order (from \(k\) to 0) to the up-steps, respectively down-steps, of \(g_f\), from the top unit layer of \(g_f\) in \(\mathbb{R}^2\) to the bottom one and from left to right at each pertaining unit layer between contiguous lines \(y,y+1\in\mathbb{Z}\). Then, by reading and successively writing the number entries assigned to the steps of \(g_f\), the \(n\)-tuple \(F(f)\) is obtained. The figure is provided, underneath each instance, with the corresponding \(f\) followed by \(F(f)\) and its (underlined) order of presentation via the castling procedure of §5, below. We assume that all elements of \(V(O_k)\) are represented by means of such piecewise-linear curves, for each fixed integer \(k>0\).

Each Dyck word \(f\) as in Definition 8 determines a Dyck path \(g_f\) as in Definition 9 which in turn determines a Dyck nest \(F(f)\) as in Definition 10. If \(f\) is tight, then \(F(f)\) is irreducible, as in Definition 11, or tight as in Definition 12. If not, then reduction takes \(f\) into a tight \(f'\), and \(F= F(f)\) into an irreducible or tight Dyck nest \(F'=F(f')\).

5. Castling procedure

Modifying Theorem 3.2 [11] or Theorem 2 [12] for our present purposes, we assign a Dyck word \(f(n)=f_1f_2\cdots f_{2k}\) to each TRGS \(b(n)=a_{k-1}\cdots a_1\in{\mathcal S}\) as in (1)-(2) in such a way that all such Dyck words become represented (once each) via uniquely corresponding \(F(n)\)’s generated via the procedure contained in the subsequent items (a)-(f), each \(F(n)\) yielding its \(f(n)\) by replacing each first appearance \(j_1\) of an integer \(j\) by a 0-bit and its second appearance \(j_2\) of \(j\) by a 1-bit, and using the function \(\lambda:\mathbb{N}\rightarrow\mathbb{Z}\) given by \(\lambda(n)=k\), (\(n\in\mathbb{N}\)).

1. set \(n=1\) and set \(F(0)=11\), with \(\lambda(0)=k=2\).

2. Let \(\gamma(n)\in\Gamma\) as in (3), let \((c(n),b(n))\in T\) as in (5), let \(0^\ell c(n)=c'(n)=0^\ell b(m)\) as in (4)-(6) (\(0\le m<n\)) and let \(j\) be such that \(\lambda(q^j(F(m)))=\lambda(F(n))\).

3. Set \(q^j(F(m))=W|X|Y|Z\), with \(W\) and \(Z\) of lengths \(\gamma(n)-1\) and \(\gamma(n)\), respectively, and with \(Y\) starting at entry \(x+1\), where \(x\) is the leftmost entry of \(X\).

4. Set \(k=\lambda(n)\) and write \(F^k(n)=F(n)\).

5. Determine \(F^k(n)\) via castling of \(X\) and \(Y\), i.e., transposing: \(X|Y\rightarrow Y|X\). This yields \(F^k(n)=W|Y|X|Z\).

6. Let \(n:=n+1\) and repeat the sequence of items (b)-(f).

The procedure in items (a)-(f) yields the lexicographically-ordered tight Dyck nests \(F(n)=F^k(n)\in{\mathcal N}\) for all \(n\ge 0\), and the corresponding Dyck words \(f(n)=f^k(n)\in{\mathcal W}\).

Example 8. While working with a Dyck word \(f\) or a Dyck nest \(F\), the order \(n\in\mathbb{N}\) of any working tool relating to \(f\) or \(F\) will be indicated by \(ord(\cdot)\). The RGSs of length \(k-1\) conform a tree \(T_k\) controlled by the tree \(T\) of TRGSs by blowing each such TRGS to an RGS of length \(k-1\). Then, \(T_k\) can be considered subtree of \(T\) corresponding to the prefix \([0,{\mathcal C}_k-1]\) of \(\mathbb{N}\), where \({\mathcal C}_k=\frac{(2k)!}{k!(k+1)!}\) is the \(k\)-th Catalan number [8, A000108], [13]. Figure 2 contains representations of the effects of the castling operation on the trees \(T_k\) (\(k=1,2,3,4\), with \({\mathcal C}_k=1,2,5,14\)), each such tree with its root \(0^{k-1}\) represented in a box containing the order \(ord(0^{k-1})=0\in\mathbb{N}\), the root \(0^{k-1}\) and \(F(0^{k-1})\). Each other node \(f\) of \(T_k\) is represented by a box of two levels: the top level contains the order \(ord(\rho(f))\in\mathbb{N}\), the parent \(\rho(f)\) and \(F(\rho(f))\); the lower level contains the order \(ord(f)\in\mathbb{N}\), \(f\) and \(F(f)\). In these two levels, the entry at which parent \(c\) and child \(b\) differ in (4), namely at position \(\gamma(n)\), is in red in contrast with the remaining entries, in black. In all boxes, \(F(\rho(f))=“W|X|Y|Z"\) and \(F(f)=“W|Y|X|Z"\) have \(X\) and \(Y\) colored blue and red, respectively, while \(W\) and \(Z\) are left black. In addition, the edge leading from \(\rho(f)\) to \(f\) is labeled with its subindex \(i\).

The computational complexity of the castling operation is determined by the value \(k=\lambda(n)\) in item (d) in time \(O(1)\) and includes: the determination of \(\gamma(n)\) and \(j\) in item (b), both of time \(O(k)\); \(W,X,Y,Z\) in item (c), again \(O(k)\); the string transposition \(XY\rightarrow YX\) of item (e), again \(O(k)\); so in sum the time of the castling procedure is \(O(k)\), for any particular \(n\in\mathbb{N}\), where \(k=\lambda(n)\). Considered over all of \(T_k\), the complexity amounts to \(O(k{\mathcal C}_k)\), where the time complexity of \({\mathcal C}_k\) can be obtained by Dynamic Programming via recursiont \({\mathcal C}_0=1\) and \({\mathcal C}_{k+1}=\sum\limits_{j=0}^{k}{\mathcal C}_j{\mathcal C}_{k-j}\), yielding time \(O(k^2)\), a total time \(O(k^3)\). Space complexity is \(O(k)\).

6. Dyck nests blown to a specific length

7. Anchoring Dyck words to odd graphs

The characteristic vectors of the vertices of \(O_k\) in the upper half of Table 1 also represent the elements of \(L_k\subset V(M_k)\). The complements of their reversed strings represent \(L_{k+1}\) so their union \(L_k\cup L_{k+1}\) forms \(V(M_K)\), where adjacency is given by inclusion of \(L_k\) into \(L_{k+1}\).

8. Arc factorizations of odd graphs

Let \(^0\!F=0F_1\cdots F_{2k}\) be an anchored Dyck nest representing a \(\mathbb{Z}_{2k+1}\)-class of \(V(O_k)\) (\(F_i\in[1,k]\), for \(i\in[1,2k]\)). Then, such a class can be expressed (Example 11, Table 1) as \[\begin{aligned} \label{^0F} [^0\!F]=\{^0\!F\!=\!0F_1\cdots F_{2k},\;\; ^1\!\!F\!=\!F_1\cdots F_{2k}0,\;\; ^2\!F\!=\! F_2\cdots F_{2k}0F_1,\; \ldots,\;\; ^{2k}\!F\!=\!F_{2k}0F_1\cdots F_{2k-1}\}. \end{aligned} \tag{10}\] Each entry of value \(j\in[0,k]\) in a \((2k+1)\)-tuple \(\chi=\,^\ell\!F\) as in (10) (\(\ell\in[0,2k]\)) is either the first, \(j_1\), or second, \(j_2\), appearance of \(j\) in \(\chi\) counting from the entry of value 0, from left to right and cyclically mod \(2k+1\), e.g., \(^2\!F\) has value 0 in the penultimate entry (see (10)).

Let \(\ell\in[0,2k]\). Given the entry of value \(j=0\) in \(^\ell\!F\) or the first appearance \(j_1\) of an integer \(j\in[1,k]\) in \(^\ell\!F\), there exists just one anchored \(k\)-blown Dyck nest \(_{j+\ell}^{\ell}\!F\ne\,^\ell\!F\) (with \(j+\ell\) taken mod \(n\)) adjacent as a vertex of \(O_k\) to \(^\ell\!F\) via one of the two arcs forming an edge \(e\) of \(O_k\), namely the arc \(\overrightarrow{e}=(^\ell\!F,\) \(_{j+\ell}^{\ell}\!F)\), and having:

1. \((k-j)_1\) as first appearance of \(k-j\) in the same position as \(j_1\) in \(^0\!F\), and

2. the other \(j=0\) or first (resp., second) appearance positions of integers \(j\in[1,k]\) in \(^\ell\!F\) as second (resp., \(j=0\) or first) appearance positions of integers \(j\in[1,k]\) in \(_{j+\ell}^{\ell}\!F\).

We use the following notation for the vertices \(v\in V(O_k)\): \(v=n_k^j\), where \(n\) is the order of the TRGS \(b(n)\in{\mathcal S}\) yielding the \(\mathbb{Z}_{2k+1}\)-class of \(v\), and \(j\) is taken by expressing \(v\) as \(^j\!F\) in (10).

Thus, for each \(k\in\mathbb{N}\), the arcs of \(O_k\) form an arc factorization \(\mathcal F\) composed by the arc factors \(\mathcal F_j\) formed by those arcs \((n^j_k,\ell^{j'}_k)\) with fixed \(j\in[0,k]\) and adequate \(n\), \(\ell\) and \(j'\).

Lifting \(\mathcal F\) via pull-back from \(O_k\) to \(M_k\) via the 2-covering graph map \(\Psi_k:M_k\rightarrow O_k\) yields the so-called modular arc factorization of \(M_k\) [2, 6, 14], again mentioned in relation to item 2 in §11.

9. Permutations associated to Dyck words

Let us associate a \(2k\)-permutation \(\pi\) to each anchored \(k\)-blown Dyck nest \(F\), or word \(f\), (and to the \(\mathbb{Z}_{2k+1}\)-class of \(V(O_k)\) they represent), via the following procedure (compare [2, 5]):

1. Set parentheses or commas between each two entries of \(f\), so that the four substrings \[\begin{array}{rrrrrrrrl} “01"&,&“10"&,&“00"&\mbox{and}&“11"&&\mbox{ are transformed into the substrings}\\ “0,1"&,&“1)(0"&,&“0(0"&\mbox{and}&“1)1"&,&\mbox{ respectively, resulting in a string }f'. \end{array}\] Add a terminal parenthesis to \(f'\), so that the last “\(1\)” in \(f'\) is transformed into “\(1)\)“. Denote by \(g\) the string resulting from such addition of a closing parenthesis to \(f'\).

2. By proceeding from left to right, replace the bits of \(g\) by the successive integers from 1 to \(|g|\), keeping all pre-inserted parentheses and commas of \(g\) in their position. This yields a version \(h_0\) of \(g\).

3. Set \(h_0\) as a concatenation \((w_1)|(w_2)|\cdots|(w_t)\) of expressions \((w_i)\), (\(1\le i\le t\)), the terminal “)” of each \((w_i)\) being the closing “)” nearest to its opening “(“. Let \(w'_i\) be the number string obtained from \(w_i\) by removing parentheses and commas. For \(i=1,\ldots,t\), perform a recursive step \({\mathcal R}\) consisting in transforming \(w'_i\) into its reverse substring \(w''_i\) and then resetting \(w''_i\) in place of \(w'_i\) in \((w_i)\), with the parentheses and commas of \((w_i)\) kept in place. Denote the resulting expression by \({\mathcal R}(w_i)\). This yields a string \(h_1={\mathcal R}(w_1)|{\mathcal R}(w_2)|\cdots|{\mathcal R}(w_t).\)

4. For \(i\in[1,t]\), let \({\mathcal R}(w_i)=(a_{i,1}^1\eta_{i,1}^1b_{i,1}^1)|(a_{i,2}^1\eta_{i,2}^1b_{i,2}^1)|\cdots|(a_{i,t_i}^1\eta_{i,t_i}^1b_{i,t_i}^1)\), where \(a_{i,j},b_{i,j}\in\mathbb{N}\) and \(\eta_{i,j}^1=(w_{i,j})\) has terminal “)” being the closing “)” nearest to its opening “(“. Apply the treatment of the \((w_i)\)’s in item 3 to each \(\eta_{i,j}=(w_{i,j})\ne\)“(,)”, for \(j\in[1,t_i]\). Replace the resulting strings \({\mathcal R}(w_{i,j})\) in place of the corresponding \((w_{i,j})\) in \({\mathcal R}(w_i)\), yielding a modified version \({\mathcal R}^2(w_i)\) of \({\mathcal R}(w_i)\). Let \(h_2={\mathcal R}^2(w_1)|{\mathcal R}^2(w_2)|\cdots|{\mathcal R}^2(w_t)\).

5. Each \({\mathcal R}(w_{i,j})\) is a concatenation of terms of the form \(a^2_I\eta^2_Ib^2_I\) with \(I=\{i,j_1,j_2\}\), where \(j_1:=j\). In each such concatenation, the strings \(\eta^2_I\ne\)“(,)” are of the form \((w_I)\) and must be treated as \((w_{i,j})\) is in item 4 (or \((w_i)\) in item 3), producing a modified string \({\mathcal R}(w_I)\) that forms part of the subsequent string \(h_3\). Eventually ahead, to pass from \(h_{\ell-1}\) to \(h_\ell\) (\(\ell>3\)), each \({\mathcal R}(w_I)\) in \(h_{\ell-1}\) with \(I=\{i,j_1,\ldots,j_{\ell-2}\}\) would be a concatenation of terms of the form \(a^{\ell-1}_{I'}|\eta^{\ell-1}_{I'}|b^{\ell-1}_{I'}\) with \(I'=\{i,j_1,\ldots,j_{\ell-1}\}\). In each such concatenation, those \(\eta^{\ell-1}_{I'}\ne\)“(,)” would be of the form \((w_{I'})\), to be treated again as in items 3-4.

6. A sequence \((h_0,\ldots,h_{s+1})\) is eventually obtained for some \(s\ge 0\) when all innermost expressions \((w_I)=(a,a\pm 1)\) with \(a,a\pm 1\in[1,2k]\) have been processed. Disregarding parentheses and commas in \(h_{s+1}\) yields a \(2k\)-string \(g'\) and an assignment \(i\rightarrow p(i)\), (\(i\in[1,2k]\)), by making correspond the places \(i\in[1,2k]\) of \(g'\) to the values in the places of \(g'\). Define \(\pi=p^{-1}\), the inverse \(2k\)-permutation of \(p=(p(1)p(2)\cdots p(2k))\).

10. Uniform 2-factors of the odd graphs

Departing from each anchored \(k\)-blown Dyck word taken as a vertex \(v\) of \(O_k\), an oriented path \(\overrightarrow{P^{2k}_{\!v}}\) of length \(2k\) is grown in \(2k\) stages \(v=v_0\), \(\overrightarrow{P_v^1}=v_0v_1\), \(\overrightarrow{P_v^2}=v_0v_1v_2\), \(\ldots\), \(\overrightarrow{P^{2k}_{\!v}}=v_0v_1\cdots v_{2k}\) by traversing successively from \(v_i\) (\(i\in[0,2k-1]\)) the edge arc whose assigned color, according to Remark 1, is the corresponding entry of the reversed permutation \(rev(\pi)\) of \(\pi\). Now, the terminal vertex \(v_{2k}\) of \(\overrightarrow{P^{2k}_{\!v}}\) is at distance 1 from \(v\) by means of an arc \(\overrightarrow{e_v}\) in the arc factor \(\mathcal F_0\). An oriented \((2k+1)\)-cycle \(\overrightarrow{C_v^k}\) in \(O_k\) is created by adding \(\overrightarrow{e_v}\) to \(\overrightarrow{P^{2k}_{\!v}}\). Lifting such \(\overrightarrow{C_v^k}\) to \(M_k\) via \(\Psi_k^{-1}\) yields an oriented \(2(2k+1)\)-cycle \(\overrightarrow{_MC_v^k}\) in \(M_k\) containing all pairs of opposite vertices \((w,\aleph(w)\)) (i.e, at distance \(k\) from each other along \(\overrightarrow{_MC_v^k}\) via two internally disjoint paths, one oriented, the other one anti-oriented). This provides \(O_k\) (resp., \(M_k\)) with a 2-factor of \({\mathcal C}_k\) components, all as oriented cycles of uniform length \(2k+1\) (resp., \(2(2k+1)\)) [2, 5, 6].

11. Partitions of odd-graph vertex sets

So far, we have two different partitions of \(V(O_k)\) into \((2k+1)\)-subsets. In terms of anchored \(k\)-blown Dyck nests, these partitions are:

1. the \(\mathbb{Z}_{2k+1}\)-classes \([0F^k(n)]\) of \(V(O_k)\), for \(0\le n<{\mathcal C}_k\) in Sections 7-9;

2. the vertex sets \(V\left(\overrightarrow{C_v^k}\right)\), where \(v=0F^k(n)\), for \(0\le n<{\mathcal C}_k\) in §10, from [6].

Item 1 refers to the algebraic partition of \(V(O_k)\) that leads to the determination of Hamilton cycles in \(M_k\) via the lexical 1-factorization of \(M_k\) [9– 12]. Here, the \(\mathbb{Z}_{2k+1}\)-classes of \(O_k\) correspond via the inverse image \(\Psi_k^{-1}\) to the dihedral classes, or \({\mathbb D}_{2k+1}\)-classes, of \(M_k\), where \({\mathbb D}_{2k+1}\) is the dihedral group with \(2(2k+1)\) elements in which the cyclic group \({\mathbb Z}_{2k+1}\) appears as a subgroup of index 2.

In fact, each anchored \(k\)-blown Dyck word \(0f^k(n)\) is a binary \((2k+1)\)-string of weight \(k\) whose support is a vertex of \(O_k\) as well as an element of \(L_k\), while \(\aleph(0f(n))\) is an element of \(L_{k+1}\). Note that both the pair \(\{0f(n),\aleph(0f(n))\}\) and the \({\mathbb Z}_{2k+1}\)-class of \(0f(n)\) in \(L_k\) (\(=V(O_k)\)) generate together the \(\mathbb{D}_{2k+1}\)-class of \(0f(n)\) of \(V(M_k)\). Thus, \(0f(n)\) represents both a \({\mathbb Z}_{2k+1}\)-class of \(V(O_k)\) and a \({\mathbb D}_{2k+1}\)-class of \(V(M_k)\).

Item 2 refers to the graph-theoretical partition of \(V(O_k)\) that leads to the determination of Hamilton cycles both in \(O_k\) and \(M_k\) (\(k>3\)) [2] via the modular arc factorization of \(M_k\) mentioned at the end of §8. Note that the Petersen graph \(M_3\) is hypo-hamiltonian, a constraint for §14 and its Theorem 8 that reformulate those determinations.

Let \((P^0,P^1,P^2,\ldots)\) be a partition of \(V(T)\) into threads \(P^i\), each thread inducing a path \(T[P^i]\) with an initial vertex \(b(n_0^i)\) such that \(\gamma(n_0^i)>1\) and its remaining vertices \(b(n_j^i)=b(n_0^i+j)\) such that \(\gamma(n_j^i)=\gamma(n_0^i+j)=1\), for \(0<j\le s^i\), where the length \(s^i\) of \(P^i\) is maximal. Here, the indices \(n_0^i\) form an integer sequence \((n_0^0,n_0^1,n_0^2,\ldots)\), as shown vertically on the second, sixth and tenth columns on the triptych left of Table 5.

Table 5. Table of initial values of n\(_{0,s}\) and γ(n\(_0\)). Final data of Table 6

\[\begin{array}{|r|r|r|r||r|r|r|r||r|r|r|r|}\hline i&n_0^i&s^i&\gamma^i&i&n_0^i&s^i&\gamma^i&i&n_0^i&s^i&\gamma^i\\\hline 0& 0&1&*&14&42&1&5&28&84&1&4\\ 1& 2&2&2&15&44&2&2&29&86&2&2\\ 2&5&1&3&16&47&1&3&30&89&1&3\\ 3& 7&2&2&17&49&2&2&31&91&2&2\\ 4&10&3&2&18&52&3&3&32&94&3&2\\ 5&14&1&4&19&56&1&4&33&98&1&3\\ 6&16&2&2&20&58&2&2&34&100&2&2\\ 7&19&1&3&21&61&1&3&35&103&3&2\\ 8&21&2&2&22&63&2&2&36&107&4&2\\ 9&24&3&2&23&66&3&2&37&112&1&3\\ 10&28&1&3&24&70&1&3&38&114&2&2\\ 11&30&2&2&25&72&2&2&39&117&3&2\\ 12&33&3&2&26&75&3&2&40&121&4&2\\ 13&37&4&2&27&79&4&2&41&126&5&2\\\hline \end{array} \qquad \begin{array}{|r|r|r|r|r||r|}\hline \;\;\;3&\;\;\;2&\;\;\;2&\;\;\;2&\;\;\;2&\;\;\;2\\\hline 0&-3&-4&-5&-6&0\\ 0&1&2&3&4&-2\\ &0&1&2&3&-3\\ &&0&1&2&-4\\ &&&0&1&-5\\ &&&&0&-6\\ &&&&&0\\\hline \end{array}\]

Table 6. Disposition of threads of T

\[\begin{array}{|r|r||r|}\hline \;\;\;*&\;\;\;2&\\\hline *&0&\\ 0&-2&\\ &0&\\\hline\hline 3&2&2\\\hline *&-3&\;\;\;0\\ 0&1&-2\\ &0&-3\\ &&0\\\hline \end{array} \qquad \begin{array}{|r|r|r|r|r||r|r|r||r|}\hline \;\;\;* &2 &\;\;\;3 &\;\;\;2 &\;\;\;2 & & & &\\\hline \;\;\;* &\;\;\;0 &\;\;\;0 &-3 &\;\;\;0 & & & &\\ \;\;\;0 &-2 &\;\;\;0 &\;\;\;1 &-2 & & & &\\ &\;\;\;0 & &\;\;\;0 &-3 & & & &\\ & & & &\;\;\;0 & & & &\\\hline\hline \;\;\;4 &2 &\;\;\;3 &\;\;\;2 &\;\;\;2 &\;\;\;3&\;\;\;2&\;\;\;2&\;\;\;2\\\hline \;\;\;0 &\;\;\;0 &-4 &\;\;\;1 &\;\;\;0 &\;\;\;0&-3 &-4 &0\\ \;\;\;0 &-2 &\;\;\;0 &-3 &-2 &\;\;\;0&\;\;\;1&\;\;\;2&-2\\ &\;\;\;0 & &\;\;\;0 &\;\;\;1 & &\;\;\;0 &\;\;\;1&-3\\ & & & &0 & & &\;\;\;0&\;\;\;1\\ & & & & & & &\;\;\; &\;\;\;0\\\hline \end{array}\] \[\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r||r|r|r|r||r|} \hline *\!&\!2\!&\!3\!&\!2\!&\!2\!&\!4\!&\!2\!&\!3\!&\!2\!&\!2\!&\!3\!&\!2\!&\!2\!&\!2\!&\!\!&\!\!&\!\!&\!\!&\!\\\hline \;\;\;*\!&\!\;\;\;0\!&\!\;\;\;0\!&\!-3\!&\!0 \!&\!0\!&\!0\!&\!-4\!&\!1\!&\!0\!&\!\;\;\;0\!&\!-3\!&\!-4\!&\!0\!&\!\!&\!\!&\!\!&\!\!&\!\\ \;\;\;0\!&\!-2\!&\!0\!&\!1\!&\!-2\!&\!\;\;\;0\!&\!-2\!&\!0\!&\!-3\!&\!-2\!&\!0\!&\!1\!&\!2\!&\!-2\!&\!\!&\!\!&\!\!&\!\!&\!\\ \!&\!0 \!&\! \!&\!0\!&\!-3 \!&\!\!&\!0\!&\! \!&\!0\!&\!1\!&\!\!&\!0\!&\!1\!&\!-3\!&\!\!&\!\!&\!\!&\!\!&\!\\ \!&\! \!&\! \!&\! \!&\!0 \!&\!\!&\!\!&\! \!&\!\!&\!0\!&\!\!&\!\!&\!0\!&\!-4\!&\!\!&\!\!&\!\!&\!\!&\!\\ \!&\! \!&\! \!&\! \!&\! \!&\!\!&\!\!&\! \!&\!\!&\!\!&\!\!&\!\!&\!\!&\!0\!&\!\!&\!\!&\!\!&\!\!&\!\\\hline\hline 5\!&\!2\!&\!3\!&\!2\!&\!2\!&\!4\!&\!2\!&\!3\!&\!2\!&\!2\!&\!3\!&\!2\!&\!2\!&\!2\!&\!\!&\!\!&\!\!&\!\!&\!\\\hline \;\;\;0\!&\!\;\;\;0\!&\!\;\;\;0\!&\!-3\!&\!0 \!&\! 5\!&\! 0\!&\! 1\!&\!-4\!&\!0\!&\!\;\;\;0\!&\!-3\!&\!1\!&\!0\!&\!\!&\!\!&\!\!&\!\!&\!\\ \;\;\;0\!&\! -2\!&\! 0\!&\!1\!&\!-2\!&\!\;\;\;0\!&\!-2\!&\!0\!&\!2\!&\!-2\!&\!0\!&\!1\!&\!-3\!&\!-2\!&\!\!&\!\!&\!\!&\!\!&\!\\ \!&\! 0\!&\! \!&\!0\!&\!-3 \!&\! \!&\! 0\!&\! \!&\!0\!&\!-4\!&\!\!&\!0\!&\!-4\!&\!-3\!&\!\!&\!\!&\!\!&\!\!&\!\\ \!&\! \!&\! \!&\! \!&\! 0 \!&\! \!&\!\!&\! \!&\!\!&\!0\!&\!\!&\!\!&\!0\!&\!1\!&\!\!&\!\!&\!\!&\!\!&\!\\ \!&\! \!&\! \!&\! \!&\! \!&\!\!&\!\!&\! \!&\!\!&\!\!&\!\!&\!\!&\!\!&\!0\!&\!\!&\!\!&\!\!&\!\!&\!\\\hline\hline \!&\! \!&\! \!&\! \!&\! \!&\!4\!&\!2\!&\!3\!&\!2\!&\!2\!&\!3\!&\!2\!&\!2\!&\!2\!&\!3\!&\!2\!&\!2\!&\!2\!&\!2\\\hline \!&\! \!&\!\; \;\; \!&\! \!&\! \!&\! 0\!&\! 0\!&\!-4\!&\! 1\!&\!0\!&\! -5\!&\! 2\!&\!1\!&\!0\!&\!\;\;\;0\!&\!-3\!&\!-4\!&\!-5\!&\!0\\ \!&\! \!&\! \!&\! \!&\! \!&\!\;\;\;0\!&\!-2\!&\!0\!&\!-3\!&\!-2\!&\!0 \!&\!-4\!&\!-3\!&\!-2\!&\!0\!&\!1\!&\!2\!&\!3\!&\!-2\\ \!&\! \!&\! \!&\! \!&\! \!&\! \!&\! 0\!&\! \!&\! 0\!&\! 1\!&\! \!&\!0 \!&\! 1\!&\! 2\!&\!\!&\!0\!&\!1\!&\!2\!&\!-3\\ \!&\! \!&\! \!&\! \!&\! \!&\! \!&\! \!&\! \!&\! \!&\! 0\!&\! \!&\! \!&\!0 \!&\!1\!&\!\!&\!\!&\!0\!&\!1\!&\!-4\\ \!&\! \!&\! \!&\! \!&\! \!&\!\!&\!\!&\! \!&\!\!&\!\!&\!\!&\!\!&\!\!&\!0\!&\!\!&\!\!&\!\!&\!0\!&\!-5\\ \!&\! \!&\! \!&\! \!&\! \!&\!\!&\!\!&\! \!&\!\!&\!\!&\!\!&\!\!&\!\!&\!0\!&\!\!&\!\!&\!\!&\!\!&\!0\\\hline \end{array}\]

The induced paths \(T[P^i]\) have respective lengths \(s^i\) and values \(\gamma^i=\gamma(n_0^i)\) shown subsequently in the triptych.

Table 7 shows the first 42 TRGS \(b(n)=b(n^i_j)\), with the columns (divided again as in a triptych) headed \(n^i_j\), \(b(n^i_j)\), \(\rho(n^i_j)\), \(\gamma(n^i_j)\) and \(h(n^i_j)\), where \(h(.)\) is introduced in Observation 3.

Table 7. The first 42 TRGS’s \(b(n^i_j)\) of \({\mathcal S}\) with associated data \(n^i_j\), \(\rho(n^i_j)\), \(\gamma(n^i_j)\) and \(h(n^i_j)\)

\[\begin{array}{|r|r|r|r|r||r|r|r|r|r||r|r|r|r|r|}\hline n^i_j&b()&\rho()&\gamma()&h()&n^i_j&b()&\rho()&\gamma()&h()&n^i_j&b()&\rho()&\gamma()&h()\\\hline 0^0_0&0&-&-&-&14^5_0&1000&0&4&0&28^{10}_0&1200&19&3&0\\ 1^0_1& 1&0&1&0&15^5_1&1001&14&1&0&29^{10}_1&1201&28&1&0\\ 2^1_0&10&0&2&0&16^6_0&1010&14&2&0&30^{11}_0&1210&28&2&-3\\ 3^1_1&11&2&1&-2&17^6_1&1011&16&1&-2&31^{11}_1&1211&30&1&1\\ 4^1_2&12&3&1&0&18^6_2&1012&17&1&0&32^{11}_2&1212&31&1&0\\ 5^2_0&100&0&3&0&19^7_0&1100&14&3&-4&33^{12}_0&1220&30&2&-4\\ 6^2_1&101&5&1&0&20^7_1&1101&19&1&0&34^{12}_1&1221&33&1&2\\ 7^3_0&110&5&2&-3&21^8_0&1110&19&2&1&35^{12}_2&1222&34&1&2\\ 8^3_1&111&7&1&1&22^8_1&1111&21&1&-3&36^{12}_3&1223&35&1&0\\ 9^3_2&112&8&1&0&23^8_2&1112&22&1&0&37^{13}_0&1230&33&2&0\\ 10^4_0&120&7&2&0&24^9_0&1120&21&2&0&38^{13}_1&1231&37&1&-2\\ 11^4_1&121&10&1&-2&25^9_1&1121&24&1&-2&39^{13}_2&1232&38&1&-3\\ 12^4_2&122&11&1&-3&26^9_2&1122&25&1&1&40^{13}_3&1233&39&1&-4\\ 13^4_3&123&12&1&0&27^9_3&1123&26&1&0&41^{13}_4&1234&40&1&0\\\hline \end{array}\]

We reunite the threads \(P^i\) into braids, which are subsets \(Q^\ell\) (\(0\le \ell\in\mathbb{N}\)) of \(V(T)\), each inducing a maximal connected ordered subtree with initial vertex \(b(m_0^\ell)\) such that \(\gamma(m_0^\ell)>2\) and its remaining vertices \(b(m_j^\ell)\) such that \(\gamma(m_j^\ell)=\gamma(m_0^\ell+j)\in\{1,2\}\), for \(0<j\le \sum\limits_{P^i\subseteq Q^\ell}s^i\). This yields a partition \(\{Q^\ell\}\) of \(V(T)\) coarser than \(\{P^i\}\).

12. Clones of Dyck nests

Each anchored \(k\)-blown Dyck nest \(0F(n)\) (arising from its anchored \(k\)-blown Dyck word \(0f(n)\)) is encoded by its clone or signarture, defined as the vector \(\sigma(n)=(\sigma_{k-1}(n),\ldots,\sigma_2(n),\)
\(\sigma_1(n))\) of halfway-distance floors \(\sigma_j(n)\) between the first, \(j_1\), and second, \(j_2\), appearances of each integer \(j\) assigned to the respective up- and down-steps of the path \(g_f\), where \(k>j>0\).

For example, if \(j_1k_1k_2j_2\), (or \(j_1(k-1)_1k_1k_2(k-1)_2j_2\)), is a substring of \(0F(n)\), (resp., \(0F(n')\)), then the halfway-distance floor of \(j\) is \(\lfloor d(j_1,j_2)\rfloor=\lfloor 3/2\rfloor=1\), (resp. \(\lfloor d(j_1,j_2)\rfloor=\lfloor 5/2\rfloor=2\)), engaged as the \(j\)-th entry of \(\sigma(n)\), (resp., \(\sigma(n')\)), where \(0\le n<{\mathcal C}_k\), (resp., \(0\le n'<{\mathcal C}_k\)). We will write \(\sigma(n)=\sigma_{k-1}(n)\cdots \sigma_2(n)\sigma_1(n)\).

The growth of the tree \(T\) of Dyck nests \(F(n)\) will be simplified further from that given in the procedure of §5 by recursively updating just one entry of the parent clone \(\sigma(\rho(n))\) to obtain the clone \(\sigma(n)\). This uses an equivalence of the set of anchored \(k\)-blown Dyck nests \(F(n)\) and that of their clones \(\sigma(n)\), provided in Theorem 2, below.

Table 8 exemplifies how the procedure in §5 is solely determined by the integer entries \(\sigma_{\gamma(n)}(n)\) of the corresponding permutation \(\sigma(n)\) in Theorem 1, supplying in the

1. first column: the value of \(k\) that depends on the value of \(n\) in the third column;

2. second and third columns: the values of the parent index \(\rho(n)\) and \(n\) itself;

3. fourth and fifth columns: the TRGS \(b(n)\) and the value of \(\gamma(n)\), respectively;

4. sixth column: \(0F(\rho(n))=0|Z|X|Y|W\); with \(X\) underlined and \(Y\) in Italics;

5. seventh column: \(0F(n)=0|Z|Y|X|W\), with \(X,Y\) as in the sixth column;

6. last three columns: the values of \(\sigma(\rho(n))\), \(\sigma(n)\) and \(\sigma_{\gamma(n)}(n)\), this last value given in terms of \(k\) via Observation 3.

Table 8. Development of clone updates \(\sigma_{\gamma(n)}(n)\) expressed in terms of k

\[\begin{array}{|c||r|r||r|r||c||r|r||r|r||r|}\hline k&\rho(n)&n&b(\rho(n))&b(n)&\gamma(n)&0F(\rho(n))&0F(n)&\sigma(\rho(n))&\sigma(n)&\sigma_{\gamma(n)}(n)\\\hline 1&*&0&*&0&*&0&011&*&1&\\\hline 2&0&1&0&1&1&0\underline{1}\textit{22}1&0\textit{22}\underline{1}1&1&0&0\\\hline 3&0&2&00&10&2&01{\underline 2}\textit{33}21&01\textit{33}{\underline 2}21&12&02&0\\ 3&2&3&10&11&1&0{\underline{133}}\textit{22}1&0\textit{22}{\underline{133}}1&02&01&k-2\\ 3&3&4&11&12&1&0{\underline{221}}\textit{33}1&0\textit{33}{\underline{221}}1&01&00&0\\\hline 4&0&5&000&100&3&012{\underline 3}\textit{44}321&012\textit{44}{\underline 3}321&123&023&0\\ 4&5&6&100&101&1&0\underline{1}\textit{244332}1&0\textit{244332}\underline{1}1&023&020&0\\ 4&5&7&100&110&2&01{\underline{244}}\textit{33}21&01\textit{33}{\underline{244}}21&023&013&k-3\\ 4&7&8&110&111&1&0{\underline{133}}\textit{2442}1&0\textit{2442}{\underline{133}}1&013&011&1\\ 4&8&9&111&112&1&0{\underline{24421}}\textit{33}1&0\textit{33}{\underline{24421}}1&011&010&0\\ 4&7&10&110&120&2&01{\underline{332}}\textit{44}21&01\textit{44}{\underline{332}}21&013&003&0\\ 4&10&11&120&121&1&0{\underline{14433}}\textit{22}1&0\textit{22}{\underline{14433}}1&003&002&k-2\\ 4&11&12&121&122&1&0{\underline{22144}}\textit{33}1&0\textit{33}{\underline{22144}}1&002&001&k-3\\ 4&12&13&122&123&1&0{\underline{33221}}\textit{44}1&0\textit{44}{\underline{33221}}1&001&000&0\\\hline \end{array}\]

We introduce a family \(\{\Phi_j| j>0\}\) of subsequences of \(\mathbb{N}\) defined by the following properties:

1. \(\gamma(\Phi_1)\) is the subsequence of \(\gamma(\mathbb{N})\) formed by all indices \(\gamma(n)\) larger than 1.

2. The first term of \(\Phi_j\) is 1 if j=1; and \(n\) such that \(b(n)\) is the smallest TRGS having suffix \((j-1)(j-1)\) for \(j>1\).

3. Assume \(n\in\Phi_j\), \(b(n)=a_{k-1}\cdots a_1\) and either \(a_1=0\) or \(n'\notin\Phi_j\;\forall n'\in\mathbb{N}\) with \(b(n')=a_{k-1}\cdots a_2a'_1\), (\(a'_1<a_1\)). Then, \(b(n)|j=b(n'')\) has \(n''\in\Phi_j\; \forall j\in[0,a_1]\). If so and \(b(m)=a_{k-1}\cdots a_2(a_1+j')\) has \(m\in\Phi_j\; \forall j'\ge1\), then \(b(m)|j=b(m')\) has \(m'\in\Phi_j\).

4. Each braid \(Q^\ell=\{P^i\}_{i=u_\ell}^{t_\ell}\) has associated subsequence \(\Gamma^\ell=(\iota,2,\ldots,2)\) in \(\Gamma=\gamma(\mathbb{N})\), where \(\iota>2\). If there exist \(z\) penultimate terms \(\gamma(n)=2\) in \(\Gamma^\ell\) yielding maximal prefixes of common fixed length \(y>0\) in the threads of \(Q^\ell\setminus P^{t_\ell}\) with associated images in \(h(\Phi_j)\) ending at \(h(m)\), where \(b(m)=a_{k-1}\cdots a_3(y+j)y)\) \(\forall j\in[0,z-1]\), then \(m'\in\Phi_j\) \(\forall b(m')=a_{k-1}\cdots a_3(y+z)j'\) with \(j'\in(y,y+z]\), which yields a suffix of \(P^{t_\ell}\) with \(h\)-image \(\{h(\alpha_{j'})|j'\in(y,y+z]\}\).

13. Controlling odd and middle-levels graphs via T

Table 10. Introduction of strings \(\xi_\gamma^b\), for all pairs \((\gamma,b)\in\mathbb{N}^2\) such that \(1<\gamma\le b\)

\[\begin{array}{|l|}\hline {\xi_2^2=2_1|1_1|1_2;}\\ {\xi_2^3=2_2|1_1|1_2|1_3;}\\ {\xi_2^4=2_3|1_1|1_2|1_3|1_4;}\\ {\xi_2^5=2_4|1_1|1_2|1_3|1_4|1_5;}\\ {\cdots;}\\ {\xi_3^3=3_1|1_1|\xi_2^2|\xi_2^3=3_1|1_1|2_11_11_2|2_21_11_21_3;}\\ {\xi_3^4=3_2|1_1|\xi_2^2|\xi_2^3|\xi_2^4=3_2|1_1|2_11_11_2|2_21_11_21_3|2_31_11_21_31_4;}\\ {\xi_3^5=3_3|1_1|\xi_2^2|\xi_2^3|\xi_2^4|\xi_2^5=3_2|1_1|2_11_11_2|2_21_11_21_3|2_31_11_21_31_4|2_41_11_21_31_41_5;}\\ {\cdots;}\\ {\xi_4^4=4_1|1_1|\xi_2^2|\xi_3^3|\xi_3^4=4_1|1_1|2_11_11_2|3_11_12_11_11_22_21_11_21_3|3_21_12_11_11_2|2_21_11_21_3|2_31_11_21_31_4;}\\ {\xi_4^5=4_2|1_1|\xi_2^2|\xi_3^3|\xi_3^4|\xi_3^5;}\\ {\cdots}\\ {\xi_5^5=5_1|1_1|\xi_2^2|\xi_3^3|\xi_4^4|\xi_4^5;}\\ {\xi_5^6=5_2|1_1|\xi_2^2|\xi_3^3|\xi_4^4|\xi_4^5|\xi_4^6;}\\ {\cdots}\\ {\xi_a^{a+b}=a_{a+b}|1_1|\xi_2^2|\cdots|\xi_{a-1}^{a-1}|\xi_{a-1}^a|\cdots|\xi_{a-1}^{a+b}, \; \forall 0<a\in\mathbb{N}, \forall 0<b\in\mathbb{N}.}\\\hline \end{array}\]

We introduce strings \(\xi_\gamma^b\), for all pairs \((\gamma,b)\in\mathbb{N}^2\) with \(1<\gamma\le b\). The entries of each \(\xi_\gamma^b\) are integer pairs \((\alpha,\beta)\), denoted \(\alpha_\beta\), starting with \(\alpha_\beta=1_1\), initial case of the more general notation \(1_\beta\), for \(\beta\ge 1\). The strings \(\xi_\gamma^b\) are determined following Table 10. The components \(\alpha\) in the entries \(\alpha_\beta\) represent the indices \(\gamma=\gamma(b(n))\) (see §3) in their order of appearance in \({\mathcal S}\), and \(\beta\) is an indicator to distinguish different entries \(\alpha_\beta\) with \(\alpha\) locally constant.

Next, consider the infinite string \(J\) of integer pairs \(\alpha_\beta\) formed as the concatenation \[\begin{aligned} \label{J(2)} J=\xi_1^1|\xi_2^2|\cdots|\xi_\gamma^\gamma|\cdots=*|1_1|\xi_2^2|\cdots|\xi_\gamma^\gamma|\cdots, \end{aligned} \tag{11}\] with \(\xi_1^1=*|1_1\) standing for the first two lines of Tables 7 and 8, where \(*\), representing the root of \(T\), stands for the first such line, and \(\xi_1^1\) for the second line.

A partition of a string \(A\) is a sequence of substrings \(\sigma_1,\sigma_2,\ldots,\sigma_n\) whose concatenation \(\sigma_1|\sigma_2|\cdots|\sigma_n\) is equal to \(A\).

We recur to Catalan’s reversed triangle \(\Delta'\), whose lines are obtained from Catalan’s triangle \(\Delta\) (see [11]) by reversing its lines, so that they may be written as in Table 11 that shows the first eight lines \(\Delta'_k\) of \(\Delta'\), for \(k\in[0,7]\). Each \(\xi_\gamma^b\) in the statement of Theorem 6 is presented in the Tables 7-8 in \(\gamma(n)\)-columnwise disposition.

Table 11. An initial detailed portion of Catalan’s reversed triangle ∆′

\[\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline &&&&&&&&\tau_0^0=1\\ &&&&&&&\tau_1^1=1&\tau_0^1=1\\ &&&&&&\tau_2^2=2&\tau_1^2=2&\tau_0^2=1\\ &&&&&\tau_3^3=5&\tau_2^3=5&\tau_1^3=3&\tau_0^3=1\\ &&&&\tau_4^4=14&\tau_3^4=14&\tau_2^4=9&\tau_1^4=4&\tau_0^4=1\\ &&&\tau_5^5=42&\tau_4^5=42&\tau_3^5=28&\tau_2^5=14&\tau_1^5=5&\tau_0^5=1\\ &&\tau_6^6=132&\tau_5^6=132&\tau_4^6=90&\tau_3^6=48&\tau_2^6=20&\tau_1^6=6&\tau_0^6=1\\ &\tau_7^7=429&\tau_6^7=429&\tau_5^7=297&\tau_4^7=165&\tau_3^7=75&\tau_2^7=27&\tau_1^7=7&\tau_0^7=1\\ \cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots\cdots\\\hline \end{array}\]

14. Hamilton cycles in odd and middle-levels graphs

A flippable tuple [2] in a vertical list \(L(n)\) is a pair \(FT(n,j)\) of contiguous lines in \(L(n)\) having its \(k\)-supplementary entry pair at the \(j\)-th position counted from the right (\(j\in[0,2k]\)). Let \(2<\kappa\in\mathbb{Z}\). A flipping \(\kappa\)-cycle [2] is a finite sequence of pairwise different vertical lists \(L(n_j)\), (\(n=1,\ldots,\kappa)\) determining a \(2\kappa\)-cycle in \(O_k\) containing successive pairwise disjoint edges whose endvertex pairs \(\{\chi_0^j,\chi_1^j\}\) are flippable tuples in their corresponding vertical lists \(L(n_j)\) (\(n=1,\ldots,\kappa\)), with the vertical pairs of number \(k\)-supplementary entries happening at pairwise different coordinate positions.

Consider the following Dyck-word collections (triples, quadruples, etc.): \[\begin{aligned} \label{!}\left\{\begin{array}{lllllr} S_1(w)&=&\{\xi_{1^w}^1=0w001\underline{1}1,&\xi_{1^w}^2=0w\underline{0}1101,&\xi_{1^w}^3=0w0101\underline{1}\},&\\ S_2&=& \{\xi_2^1=0\underline{0}110011,&\xi_2^2=0010011\underline{1},&\xi_2^3=00010\underline{1}11\},&\\ S_3&=& \{\xi_3^1=00011\underline{1},&\xi_3^2=0100\underline{1}1,&\xi_3^3=\underline{0}10101\},&\\ S_4&=&\{\xi_4^1=00011\underline{1},&\xi_4^2=0010\underline{1}1,&\xi_4^3=01\underline{0}011,&\xi_4^4=\underline{0}10101\}, \end{array}\right. \end{aligned} \tag{13}\]

(based on [2, display (4.2)]) where \(w\) is any (possibly empty) Dyck word. Consider also the sets \(\underline{S}_1(w)\), \(\underline{S}_2\), \(\underline{S}_3\), \(\underline{S}_4\) obtained respectively from \(S_1(w)\), \(S_2\), \(S_3\), \(S_4\) by having their component Dyck paths \(\underline{\xi}_{1^w}^j\), \(\underline{\xi}_2^j\), \(\underline{\xi}_3^j\), \(\underline{\xi}_4^j\) defined as the complements of the reversed strings of the corresponding Dyck paths \(\xi_{1^w}^j\), \(\xi_2^j\), \(\xi_3^j\), \(\xi_4^j\). Note that each Dyck word in the subsets of display (13) has just one underlined entry. By denoting \[\begin{aligned} \label{denot}\xi_{1^w}^j=x_sx_{s-1}\cdots x_2x_1x_0\;\mbox{ and }\;\xi_i^j=x_sx_{s-1}\cdots x_2x_1x_0,\mbox{ for }i=2,3,4, \end{aligned} \tag{14}\] where \(j=1,2,3\) for \(i=1,2,3\) and \(j=1,2,3,4\) for \(i=4\) and adequate \(s\) in each case, the barred positions in (13) are the targets of the following correspondence \(\Phi\): \[\begin{aligned} \label{!!}\left\{\begin{array}{llll} \Phi(\xi_{1^w}^1)=1,&\Phi(\xi_{1^w}^2)=4,&\Phi(\xi_{1^w}^3)=0,&\\ \Phi(\xi_2^1)=6,&\Phi(\xi_2^2)=0,&\Phi(\xi_2^3)=2,&\\ \Phi(\xi_3^1)=0,&\Phi(\xi_3^1)=1,&\Phi(\xi_3^3)=5,&\\ \Phi(\xi_4^1)=0,&\Phi(\xi_4^2)=1,&\Phi(\xi_4^3)=3,&\Phi(\xi_4^4)=5.\\ \end{array}\right. \end{aligned} \tag{15}\] The correspondence \(\Phi\) is extended over the Dyck words \(\underline{\xi}_{1^w}^j\), \(\underline{\xi}_2^j\), \(\underline{\xi}_3^j\), \(\underline{\xi}_4^j\) with their barred positions taken reversed with respect to the corresponding barred positions in \(\xi_{1^w}^j\), \(\xi_2^j\), \(\xi_3^j\), \(\xi_4^j\), respectively.

Adapting from [2], we define an hypergraph \(H_k\) with \(V(H_k)\) formed by the lists \(L(i)\) with \(b(i)\in V(T)\cap b([0,{\mathcal C}_k-1])\) and as hyperedges the subsets

\[\{L(i_j)|j\in\{1,2,3\}\}\subset V(H_k)\mbox{ and }\{L(i_j)|j\in\{1,2,3,4\}\}\subset V(H_k)\]

whose member lists \(L(i_j)\) have the Dyck words \(f(i_j)\) corresponding to their initial rows, the Dyck nests \(F(i_j)\), for \(j=1,2,3\mbox{ or }j=1,2,3,4\), containing respective Dyck subwords as members in the collection (indexed by \(j\)) \[\{\xi_{1^w}^j, \xi_2^j, \xi_3^j, \xi_4^j, \underline{\xi}_{1^w}^j, \underline{\xi}_2^j, \underline{\xi}_3^j, \underline{\xi}_4^j\}\] in the same 6 or 8 fixed positions \(x_i\) (for specific indices \(i\in\{0,1,\ldots,s\}\) in (14)) and forming respective subsets \[\{\xi_{1^w}^j|j=1,2,3\},\; \{\underline{\xi}_{1^w}^j|j=1,2,3\},\; \{\xi_4^j|j=1,2,3,4\},\; \{\underline{\xi}_4^j|j=1,2,3,4\},\] \[\{\xi_i^j|j=1,2,3\}\;\mbox{ and }\;\{\underline{\xi}_i^j|j=1,2,3\},\;\mbox{ for both }i=2\mbox{ and }3.\]

Table 12. Uniform 2-factors provided by permutations π for k = 4.