An Alternate Form of Merino-Mǐcka-Mütze’s Solution to a Knuth’s Combinatorial Generation Problem

1. Introduction

In this survey, an alternate form of Merino-Mička-Mütze’s solution [1] to a combinatorial generation problem of Knuth [2] is given that is compatible with a reinterpretation [3] of the proof by Mütze [4] and Gregor, Mütze and Nummenpalo [5] of existence of Hamilton cycles in the middle-levels graph \(M_n\) [6] (\(0<n\in\mathbb{Z}\)). This graph \(M_n\) is induced by the vertices of the \((2n+1)\)-cube that represent the \(n\)– and \((n+1)\)-subsets of the set \(\{0,\ldots,2n\}\) and is further considered from Section 2 on.

The reinterpretation in question is given in terms of the associated dihedral quotient graph \(N_n\) of \(M_n\) whose vertices (here called necklaces, as in [1], see Definition 2, below) represent the Dyck words of length \(2n\) defined in the following alternate way to that of [1]:

Such words can be linearly ordered via a castling, or lexical, procedure [3,Section 3] (where the term lexical appears in [3] in relation to Kierstead and Trotter [6]).

The castling procedure uses restricted growth strings or RGSs of length \(n\), namely the \(n\)-strings \(a_1a_2\cdots a_n\) such that \(a_1=0\) and \(a_k\le a_{k-1}+1\), for \(1<k\le n\); see [7,page 325]-[8, page 224], that establish that their number is the Catalan number \(C_n=\frac{1}{n+1}{2n\choose n}\) [9, A100108]. By eliminating the initial zero of each such RGS, we say that the resulting \((n-1)\)-string is an \(n\)–germ \(a_2\cdots a_n=b_{n-1}\cdots b_0\), better denoted \(b_{n-1}\cdots b_0\) in what follows.

Those \(n\)-germs form an ordered tree \(\mathcal T^n\) [3,Theorem 1] whose root is the null \(n\)-germ \(\alpha=0^{n-1}\) and such that each non-null \(n\)-germ \(\alpha=a_{n-1}\cdots a_1\) with rightmost nonzero entry \(a_i\) (\(1\le i<n\)) has as parent in \(\mathcal T_n\) the \(n\)-germ \(\beta=b_{n-1}\cdots b_1\) such that \(b_i=a_i-1\) and \(a_j=b_j\), for \(j\ne i\).

To each non-null \(n\)-germ \(\alpha\) corresponds its tight RGS, or irreducible RGS, obtained by removing its largest null prefix. The ordered trees \(\mathcal T^k\) form a chain \({\mathcal T^1}\subset{\mathcal T^2}\subset\cdots\subset{\mathcal T^n}\subset\cdots\) etc. of ordered trees obtained by identifying each \(n\)-germ \(\alpha\) with the \((n+1)\)-germ obtained from \(\alpha\) by prefixing a zero to it. The limit \(\cup_{i=1}^{\infty}{\mathcal T^i}\) of this chain, denoted \(\mathcal T\), will be considered with each vertex \(v\) written as the tight RGS \(\alpha\) associated to the \(n\)-germs \(\alpha,0\alpha,00\alpha,\ldots\) that \(v\) represents, so we have \[V({\mathcal T^1})=\{\emptyset\}, V({\mathcal T^2})=\{0,1\}, V({\mathcal T^2})=\{00,01,10,11,12\},\mbox{ etc.,}\] that, as subsets of \(\mathcal T\), will be expressed as \[V({\mathcal T^1})=\{\emptyset\}, V({\mathcal T^2})=\{\emptyset,1\}, V({\mathcal T^2})=\{\emptyset,1,10,11,12\}\mbox{ etc.}\] The tree \(\mathcal T\) is partially represented on the lower-right of Table 1 by its subtree \({\mathcal T}^4\).

The castling procedure is realized by an inductively defined bijection \(F\) from the set of \(n\)-germs onto \(D_n\). This yields a natural way of designating the participating necklaces.

We “personalize” each necklace of length \(2n+1\) by taking a representation \(f_0f_1\cdots f_{2n}\) of it such that \(f_0=0\) and \(f_1\cdots f_{2n}\in D_n\), and then applying the following procedure: \[\begin{aligned} \label{ifni}\begin{array}{l} g_0:=0;\\ \mbox{begin}\\ \mbox{ for }k=1\mbox{ to }2k\mbox{ do}\\ \mbox{if }f_{k+1}=0\mbox{ then }g_{k+1}=g_k+1\mbox{ else }g_{k+1}=g_k-1;\\ k:=k+1\\ \mbox{end.} \end{array} \end{aligned}\tag{1}\] The procedure (1) replaces each bit \(f_k\) of the necklace \(f_0f_1\cdots f_{2n}\) with a corresponding integer \(g_k\) (\(0\le g_k\le n\)). We say that the resulting \((2n+1)\)-tuple \(g_0g_1\cdots g_{2n}\) is the neck, more specifically the \(n\)–neck, associated to the necklace \(f_0f_1\cdots f_{2n}\), (with the \(2n\)-string \(f_1\cdots f_{2n}\) denoted as an \(n\)–nest in [10,11]). It happens that the necklace \(f_0f_1\cdots f_{2n}\) has each bit \(f_k\) replaced by the height \(g_k\) it determines in its Dyck path [12, Subsection 3.2], so that each 0-bit is replaced either by the null height at the starting point of the Dyck path or the first appearance of each non-null height, and each 1-bit is replaced by the second appearance of that non-null height. See Remark 4 and Figure 2, below. This “personalized” representation of the necklaces, that we call necks here, are shown as an example of Theorem [3,Theorem 2 ] on the left of Table 1, below, generating \(\mathcal T^4\) via the procedure (1), where each row, except the top one, shows an inductively obtained parent correspondence \(F:n\)-germ\(^{parent}\mapsto n\)-neck\(^{parent}\) assigned to its child correspondence \(F:n\)-germ\(^{child}\mapsto n\)-neck\(^{child}\).

In Table 1, from each parent \(n\)-germ to its child \(n\)-germ, the suffix in bold, shows a unit increase at the rightmost nonzero entry of the child’s \(n\)-germ. Such suffix in bold has the same length as both the prefixes and suffixes in bold of both the parent neck and child neck. Both are to be kept unchanged, while a central-string castling takes place on the non-bold central strings. In fact, the one on the parent side is subdivided into a left Italic substring and a right Roman substring, while the other one, on the child side (i.e., inside \(n\)-neck\(^{child}\)), permutes the order of the two substrings, justifying denoting this procedure as “castling”, like in chess. The Roman substring of a central string starts at the first appearance of the integer \(\ell+1\) subsequent to the integer \(\ell\) starting the Italic side.

The upper-right of Table 1 represents how \(n\)-germs and \(n\)-necks fit for each index \(n\) into the case of the subsequent index \(n+1\), where each zero which is added as a prefix (between auxiliary parentheses) of an RGS results in the corresponding neck into an inserted substring (also between auxiliary parentheses) [10]. As a result, the ordered tree \(\mathcal T\) of RGSs yields a bijection into an ordered tree \(\mathcal T'\) covering all tight necks (namely, where all parenthesized substrings as mentioned above are eliminated).

This section is completed by providing some historical motivation and statement of the main results of [1] as Theorems 1 and 2. In the rest of the paper, we adapt the discourse of [1] to our alternate form. In Section 2 we provide additional information about the middle-levels graphs and necklace graphs. In Section 3, basic flip sequences are presented. In Section 4, periodic paths and gluing pairs are introduced. In Section 5, an initial attempt at proving theorem 1 is given. In Sections 6 and 8, sketches of the proofs of Theorems 1 and 2 are given, while Section 7 provides information about involved efficient computations.

Combinatorial generation

An expressed objective of [1] is to generate all \((k,\ell)\)-combinations, i.e. all ways of choosing a subset \(S\) of a fixed size \(k\) from the set \([n]:=\{1,\ldots,n\}\), with \(n=k+\ell\). Each such subset \(S\) is encoded by a bitstring of length \(n\) with exactly \(k\) many 1’s, where the \(i\)-th bit is 1 if and only if the element \(i\) is contained in \(S\).

Buck and Wiedemann conjectured in [13] that all \((n+1,n+1)\)-combinations are generated by star transpositions, for every \(n\ge 1\), i.e. in each step the element 1 either enters or leaves the set. The corresponding flip sequence \(\alpha\) records the position of the bit swapped with the first bit in each step, where positions are indexed in \([2n+1]\) and \(\alpha\) has length \(N:={2n+2\choose n+1}.\) Buck-Wiedemann’s conjecture was independently raised by Havel [14] and became known as the middle-levels conjecture, name coming from an equivalent formulation of the problem, which asks for a Hamilton cycle in the middle-levels graphs, recalled below in Section 2.

Knuth’s conjecture

In [], Knuth conjectured that there is a star transposition that orders the \((n+1,n+1)\)-combinations, for every \(n\ge 1\), such that the flip sequence \(\alpha\) has a block structure \(\alpha=(\alpha_0,\alpha_1,\ldots,\alpha_{2n})\), where each block \(\alpha_i\) has length \(\frac{N}{2n+1}=\frac{1}{2n+1}{2(n+1)\choose n+1}\) and is obtained from \(\alpha_0\) by element-wise addition of \(i\) mod \(2n+1\), where \(i\in[2n]\). As the entries of \(\alpha\) are from \([2n+1]\), the numbers \(1,\ldots,2n+1\) are chosen as addition residue-class representatives, rather than the usual \(0,\ldots,2n\). Note that \(\frac{N}{2n+1}=2C_n\), where \(C_n=\frac{1}{n+1}{2n\choose n}\) is the n-th Catalan number. Then, [1] proves the following.

The proof of Theorem 1 in [1] is constructive and translates into an algorithm that generates all \((n+1,n+1)\)-combinations by star transpositions efficiently, stated in [1] as follows.

Since \(\mathcal T^n\) is an ordered tree, then its vertex set \(V({\mathcal T_n})\) inherits a natural linear order \(\mathcal L^n\). Thus, we have a chain of linear orders \(\mathcal L^1\subset\mathcal L^2\subset\cdots\subset\mathcal L^n\subset\cdots\) etc. The limit \(\cup_{i=1}^\infty\mathcal L^i\) of such a chain, denoted \(\mathcal L\) and consisting of tight RGSs, induces via the castling operation a linear order \(\mathcal L'\) of the tight necks, offering an universal reference point of view [10]–[11] to express and integrate the periodic paths or blocks whose concatenation leads to Hamilton cycles resulting from Remark 1.

\[1_1 0\]

\[12_3 0{\it 1}_2 0{\it 0}_1 10_2 11\]

\[123_3 0{\it 12}_2 0{\it 01}_1 0{\it 00}_2 0{\it 10}_4 0{\it 11}_1 111_3 110_4 100_2 120_4 122_3 112_4 101_0 121\]

\[1234_4 0{\it 123}_3 0{\it 012}_2 0{\it 001}_1 0{\it 000}_2 0{\it 010}_4 0{\it 011}_1 0{\it 111}_3 0{\it 110}_4 0{\it 100}_2 0{\it 120}_4 0{\it 122}_3 0{\it 112}_4 0{\it 101}_0 0{\it 121}_2\]

\[0121_2 1121_5 1221_2 1232_0 1012_5 1123_0 1230_5 1233_1 1231_0 1201_1 1200_3 1000_5 1100_4 1110_5 1111_3\]

\[1111_3 1220_4 1122_5 1112_4 1101_5 1001_0 1011_5 1120_4 1222_5 1211_3 1210_0 1010_1 1212_2 1223\]

2. Middle-levels Graphs and Necklace Graphs

Let \(0<n\in\mathbb{Z}\). Let \(A_n\) (resp. \(B_n\)) be the set of bitstrings of length \(2n+1\) and weight \(n\) (resp. \(n+1\)). The middle-levels graph \(M_n\) can be set as the graph whose vertex set is \(V(M_n)=A_n\cup B_n\) and whose adjacency is given by a single flip. The positions of the bitstrings in \(V(M_n)\) are denoted \(1,2,…,2n+1\) (mod \(2n+1\)), where \(2n+1\) takes the place of additive identity 0. Let \(\sigma^i(x)\) denote the cyclic right-rotation by \(i\) positions ([1] uses left-rotation, while our approach here is compatible with the treatment of [3]). The necklace \(\langle x\rangle\) of \(x\) is defined to be \(\{\sigma^i(x);i\ge 0\}\). For example, if \(x=11000\in A_2\) then \(\langle x\rangle = \{11000, 01100, 00110, 00011, 10001\}\).

Operations on sequences \(x=(x_1,\ldots,x_n)\) of integers \(x+a:=(x_1+a,…,x_k+a)\), (\(a\in\mathbb{Z}\)) and \(|x|=\) length of \(x\); of bitstrings: \(\langle x\rangle=(\langle x_1\rangle,\ldots,\langle x_k\rangle)\mbox{ and } \sigma^i(x)=(\sigma^i(x_1),\ldots,\sigma^i(x_k)).\)

For \(n\ge 1\), let \(PT_n\) be the set of all plane trees with \(n\) vertices. For any rooted tree \(x\), let \([x]\) denote the set of all rooted trees obtained from \(x\) by rotation (that is \([x] = \{\rho^i(x) ; i\ge 0\}\)), to be interpreted as the plane tree underlying \(x\), obtained by “forgetting” the root.

Let \(\lambda(x) = |[x]|\). For \(T=[x]\in PT_n\), define \(\lambda(T) = \lambda(x).\) Note that \[\lambda(x) = \min\{i\ge 1 ; \rho^i(x) = x\},\] the choice of representative of \([x]\) in defining \(\lambda(T)\) being irrelevant, for \(\lambda(T)\) is well defined. Examples for \(\lambda=4,8,2,3\) are given in Figure 2, below, in the notation of [3], meaning that each 0-bit (resp. 1-bit) is represented by the first (resp. second) appearance of each integer, counting appearances rotationally from the red 0 and in the direction indicated by “\(>\)” or by “\(<\)“. See also Remark 4.

Subtrees

Let \(T\in PT_n\). Let \((a,b)\in E(T)\). Let \(T^{(a,b)}\) be \(T\) seen as a rooted tree with root \(a\) and rightmost child \(b\) (not leftmost as in [1]). Let \(T^{(a,b)-}\) be obtained from \(T^{(a,b)}\) by removing all its children and their subtrees except for \(b\) and its descendants. Given \(a\in V(T)\), and all neighbors \(b_i\) of \(a\), (\(i\in[k]\)), let the trees \(t_i=T^{(a,b_i)_-}\) be called the \(a\)-subtrees of \(T\). Then, \(T=[(t_1,\ldots,t_k)]\), where \((t_1,\ldots,t_k)\) is the rooted tree obtained by gluing \(t_1,\ldots,t_k\) at their roots from right to left (in this order, reversed to that of [1]): In terms of bitstrings, \((t_1,\ldots,t_k)\) is obtained by concatenating the bitstring representations of \(t_1,\ldots,t_k\).

Centroids

Given a (rooted or plane) tree \(T\), the potential \(\phi(a)\) of a vertex \(a\) of \(T\) is the sum of the distances from \(a\) to \(V(T)\). The potential \(\phi(T)\) of \(T\) is \(\phi(T)=\)min\(\{\phi(a);a\in V(T)\}\). A centroid of \(T\) is an \(a\in V(T)\) with \(\phi(a)=\phi(T)\). Merino, Mička and Mütze [1]: (i) mention that a centroid of \(T\) is a vertex whose removal splits \(T\) into subtrees with at most \(\frac{|V(T)|}{2}\) vertices each; (ii) prove in [1] that \(T\) has either one centroid or two adjacent centroids, and that if \(|E(T))|\) is even, then \(T\) has just one centroid.

Relation of middle levels to Dyck words

Our objective is to define as in [1] basic flip sequences that visit every necklace exactly once in order to obtain a 2-factor (or cycle factor [1]) in \(N_n\), namely a collection of disjoint cycles that visits every vertex of \(N_n\) exactly once.

Dyck words of \(A_n\) in the notation of Lemma 2

\(\forall x\in A_n\), let \(t(x)\in D_n\) denote the last \(2n\) bits of \(\sigma^\ell(x)\), where \(\ell =\ell(x)\), i.e. \(\sigma^\ell(x) = 0t(x)\), and \(\forall y\in B_n\), let \(t(y)\in D_n\) denote the first \(2n\) bits of \(\sigma^\ell(y)\), where \(\ell =\ell(y)\), i.e. \(\sigma^\ell(y) = t(y)1\). Then, by Lemma 2, every \(x\in A_n\) (resp. \(y\in B_n\)) can be identified uniquely with the pair \((t(x),\ell(x))\) (resp. \((t(y),\ell(y))\)).

3. Basic Flip Sequences

A bijection \(f\) on \(V(M_n)\) is introduced that yields a basic flip sequence visiting every necklace exactly once, however in a different fashion to that of [1] but akin to the treatment of [3].

Let \(x\in A_n\) with \(\ell(x) = 0\), i.e. \(x = 0(u0v1) = 0t(x)\), where \(u,v\in D\). Define \(y:=f(x) = (0u1v)1 = \rho(t(x))1\in B_n\), where \(\ell(y) = 1\) and \(\rho\) is as in Remark 3. Furhter, define \(f(y) = f(f(x)) = (0u1v)0 = \rho(t(x))0\in A_n\), where \(\ell(f(y)) =0\). Extend these definitions of \(f\) for all \(x\in V(M_n)\) via \(f(x) := \sigma^{-\ell}(f(\sigma^\ell))\), where \(\ell := \ell(x)\). Then \(f\) is invertible and \(t(f(f(x)))=t(f(x))=\rho(t(x))\). In our alternate situation (differing from that of [1]), \(\ell(x)=1\), \(\ell(f(x))=0\) and \(\ell(f(f(x)))=0\). Then, for all \(x\in A_n\), \(\ell(f(x))=\ell(x)-1\) and \(\ell(f(f(x)))=\ell(x)-1\).

4. Periodic Paths and Gluing Pairs

Cycle factor of \(N_n\)

For any \(y\in\langle x\rangle\) and any \(0\le i\in\mathbb{Z}\), we have \(\kappa(f^i(y))=\kappa(x)\), so \(\langle P(x)\rangle=\langle P(f^i(y))\rangle\). This yields a 2-factor of \(N_n\), denoted \({\mathcal F}:=\{\langle P(x);x\in V(M_n)\}\).

By Proposition 1 item 3, the number of cycles of \({\mathcal F}_n\) fits the sequence [9, A002995]. Also, [1] mentions that the number of plane trees, or cycles of \({\mathcal F}_n\), grows exponentially.

Gluing pairs

Consider the star \(s_n=0(01)^{n-1}1\in D_n\) for \(n\ge 3\) and the footed-star \(s'_n=01s_{n-1}\in D_n\) for \(n\ge 4\). A gluing pair is a pair \((x,y)\ne(s_n,s'_n)\), with \(x=u0v011\) and \(y=u0v101\), where \(u,v\in D\).

Pull/push operations

Let \(G_n\) be the set of all gluing pairs \((x,y)\), where \(x,y\in D_n\). By seeing \(x,y\) as rooted trees, [1] declares that \(y\) is obtained from \(x\) by a pull operation, and calls its inverse a push operation. In our treatment, the right half of our Figure 1 resembles, but differs reflectively, from [1, Figure 9]. We write \(y=\mbox{pull}(x)\) and \(x=\mbox{push}(y)\), say that \(x\) is pullable, \(y\) is pushable and that \(u\) and \(v\) are the left and right subtrees of both \(x\) and \(y\).

Let \((x,y)\in G_n\). Let \(x^i:=f^i(0x)\) and \(y^i:=f^i(0y)\), for \(i\ge 0\). The resulting sequences agree with the first vertices of \(P(x)\) and \(P(y)\), respectively. In such notation, we notice the 6-cycle \(C(x,y)=(x^0,y^1,y^0,x^5,x^6,x^1)\), where:

\[\begin{aligned} \label{6}\begin{array}{c} x^0=0u0v011,\\ y^1=0u0v111,\\ y^0=0u0v101,\\ x^5=0u1v101,\\ x^6=0u1v001,\\ x^1=0u1v011. \end{array} \end{aligned}\tag{2}\] Then, \(P(x)\) and \(P(y)\) are glued together by removing the alternate edges \((y^0,y^1)\), \((x^0,x^1)\) and \((x^5,x^6)\) via the symmetric difference between \(C(x,y)\) and \(P(x)\cup P(y)\).

Modifying the proof of Lemma 9 in [1], we get for our Lemma 5 now that \[\alpha(C(x,y))=(|u|+|v|+3,|u|+|v|+4,|u|+2,|u|+|v|+3,|u|+|v|+4,|u|+2).\] On the other hand, if \((x,y)=(s_n,s'_n)\), then \(\kappa(x^0)=4\), so \(\langle x^0\rangle = \langle x^4\rangle\), \(\langle x^2\rangle = \langle x^6\rangle\), and Lemma 5 does not hold.

If \([x]\ne[y]\), then \(\langle P(x)\rangle\) and \(\langle P(y)\rangle\) are distinct cycles in \(N_n\) by Proposition 1, so we have that the grafted path \[P(x^0)\nabla P(y^0):=(x^0,y^1,y^2,\ldots,y^{2\lambda(y)-1},\sigma^{-\lambda(y)}(y^0,x^5,x^4,x^3,x^2,x^1,x^6,x^7,\ldots,x^{2\lambda(x)-1}))\] is a periodic path in \(M_n\).

The \(2n+1\) periodic paths \(\sigma^i(P(x^0)\nabla P(y^0))\) form \[\cup_{i\ge0}(\sigma^i(P(x^0)\nabla P(y^0))),\mbox{ that visits all vertices of }\cup_{i\ge 0}(\sigma^i(P(x^0)\cup P(y^0))).\] Indeed, \(|P(x^0)|=2\lambda(x)\), \(|P(y^0)|= 2\lambda(y)\) and \(\sigma^{\lambda(i)}(y^{2\lambda(y)})=y^0\), by Proposition 1, item 2. Then, \(E(\cup_{i\ge0}(\sigma^i(P(x^0)\nabla P(y^0))))\) is the symmetric difference of \[E(\cup_{i\ge 0}(\sigma^i(P(x^0)\cup P(y^0))))\mbox{ with the gluing cycles }\cup_{i\ge 0}\sigma^i(C(x,y)).\]

Additional notation

For all \(i\ge0\), the subpath \(\sigma^i(x^1,\ldots,\sigma^5)\) of \(\sigma^i(P(x^0))\) is said to be reversed by \(\sigma^i(C(x,y))\). Two gluing cycles \(\sigma^i(C(x,y))\) and \(\sigma^j(C(x',y'))\) are compatible if they have no \(f\)-edges in common. They are nested if the edge \(\sigma^i(y^0,y^1))\) of \(\sigma^i(C(x,y))\) belongs to the path reversed by \(\sigma^j(C(x',y'))\) (see Figure 4). They are interleaved if the \(f\)-edge \(\sigma^j(x'^0,x'^1)\) of \(\sigma^j(C(x',y'))\) belongs to the path that is reversed by \(\sigma^i(C(i,j))\).

Item 3 here can be interpreted as follows: Starting at the tree \(x\), pull an edge \(e\) towards the root to reach the tree \(y=\)pull\((x)\), then perform an inverse tree rotation \(x'=\rho^{-1}(y)\) which makes \(e\) pullable, and pull it again to reach \(y'=\)pull\((x')\). Thus, nested gluing cycles occur if and only if the same edge of the underlying plane trees is pulled twice in succession.

Some pairs of nodes in \({\mathcal H}_n\) may be connected by multiple arcs similarly oriented but with different labels, e.g. \(([0011001101],[0101001101])\) and \(([0011010011],[0101010011])\); oppositely oriented, e.g. \(([00101011],[01001011])\) and \(([00110101],[01010101])\). There may be also loops in \({\mathcal H}_n\), e.g. \(([00101101],[01001101])\).

Pullable/pushable trees

Let \(T\) be a tree, let \(a,c\in V(T)\) and let \(d(a,c)\) be the distance between \(a\) and \(c\). Let \(p^i(a,c)\) be the \(i\)-th vertex in the path from \(a\) to \(c\), (\(i=0,1,\ldots,d(a,c)\)). In particular, \(p^0(a,c)=0\) and \(p^{d(a,c)}(a,c)=c\). (See Figure 5).

Let \(c,a\in V(T)\), where \(a\) is a leaf of \(T\) and \(d(a,c)\ge 2\). Then \(a\) is pullable to \(c\) if \(p^1(a,c)\) has no neighbors between \(p^2(a,c)\) and \(a\) in the clockwise ordering of neighbors. (This and the next concepts differ from the couterclockwise stance in [1]). Also, \(a\) is pushable to \(c\) if \(p^1(a,c)\) has no neighbors between \(a\) and \(p^2(a,c)\) in the clockwise ordering of neighbors.

Let \(d(a,c)\ge 1\). Then, \(a\) is pullable from \(c\) if \(d(a,c)\ge 2\) and \(p^1(a,c)\) has at least one neighbor between \(p^2(a,c)\) and \(a\) in its clockwise ordering of neighbors or if \(c\) is not a leaf and \(d(a,c)=1\). Also, \(a\) is pushable from \(c\) if \(d(a,c)\ge 2\) and \(p^1(a,c)\) has at least one neighbor between \(a\) and \(p^2(a,c)\) in its clockwise ordering of neighbors or if \(c\) is not a leaf and \(d(a,c)=1\).

For odd \(n\ge 5\), consider the dumbbells \(d_n:=(01)^{\frac{n-1}{2}}0(01)^{\frac{n-1}{2}}1\) and \(d'_n:=\rho^{2}(d_n)=010(01)^{(n-1)/2}0(01)^{(n-3)/2}\). Each dumbbell has two centroids of degree \(\frac{n+1}{2}\), while all the remaining vertices are leaves.

If \(T\) has just one centroid \(c\), every \(c\)-subtree of \(T\) is said to be active. If \(T\) has two centroids \(c,c'\), every \(c\)-subtree except the one containing \(c'\) and every \(c'\)-subtree except the one containing \(c\) are also said to be active. For \(n\ge 4\), if \(T\ne[s_n]\) and \(T\ne[d_n]\) for odd \(n\), then \(T\) has a centroid with an active subtree that is not a single edge.

A leaf of \(T\) is thin if its unique neighbor in \(T\) has degree \(\le 2\); otherwise, it is thick.

5. Initial Attempt at Proving Theorem 1

Scaling trick

[1] presents a scaling trick consisting in the construction of a flip sequence \(\alpha_0\) for one particular shift \(s\) coprime to \(2n+1\). From such a shift \(s\), a transformation \(\Upsilon\) yields every shift \(s'\) coprime to \(2n+1\), where \(\Upsilon\) consists in multiplying all entries of \(\alpha_0\) by \(s^{-1}s'\) mod \(2n+1\), with \(s^{-1}\) equal to the multiplicative inverse of \(s\).

Define \(\label{rev}\mbox{rev}(P):=(x_1,\sigma^{\lambda(\alpha)}(x_k,x_{k-1},\ldots,x_2))\) and \(\mbox{rev}(\alpha):=(a_k,a_{k-1},\ldots,a_1)-\lambda(\alpha)\), with indices taken mod \(2n+1\). Note that rev\((\alpha)\) is a flip sequence for the periodic path rev\((P)\) satisfying \(\lambda(\)rev\((\alpha))=-\lambda(\alpha)\).

Define mov\((P):=(x_2,\ldots,x_k,\sigma^{-\lambda(\alpha)}(x_1))\) and mov\((\alpha):=(a_2,\ldots,a_k,a_1+\lambda(\alpha))\), this being a flip sequence for the periodic path mov\((P)\) satisfying \(\lambda(\)mov\((\alpha))=\lambda(\alpha)\), which means that the shift is independent of the choice of the starting vertex along the path. Similarly, \(\alpha +i\) is a flip sequence for \(\sigma^{-i}(P)\) satisfying \(\lambda(\alpha +i)=\lambda(\alpha)\), \(\forall i\in{\mathbb Z}\).

For any \(x\in V(M_n)\), let \(\alpha(x)\) be the sequence of positions at which \(f^{i+1}(x)\) differs from \(f^i(x)\), \(\forall i=0,\ldots,\kappa(x)-1\). Clearly, \(\alpha(x)\) is a flip sequence for \(P(x)\) (Definition 5). By Proposition 1 item 2, \(\lambda(\alpha(x))=\lambda(t(x))\).

For any subtree \({\mathcal T}\) of \({\mathcal H}_n\) with \(G:=G({\mathcal T})\) interleaving-free as in Remark 6, define the set of necklaces \(N({\mathcal T}):=\cup_{[x]\in{\mathcal T}}\langle P(0x)\rangle\). By Proposition 1 item 1, this is the set of necklaces visited by those cycles \(\langle P(0x)\rangle\) in \(N_n\) for which \([x]\in\mathcal T\).

For any \(z\in N({\mathcal T})\) and any \(x\in z\), there is a pair \({\mathcal P}_G(X)=\{P,P'\}\) of two periodic paths \(P\) and \(P'\), both starting at \(x\in V(M_n)\) with flip sequences \(\alpha(P)\) and \(\alpha(P')\) such that \(P'=\)rev\((P)\) and \(\alpha(P')=\)rev\((\alpha(P))\). Moreover, \(\langle P\rangle\) and \(\langle P'\rangle\) are oppositely oriented in the subgraph of \(N_n\) whose vertex set is \(N({\mathcal T})\).

The node set of \({\mathcal T}_n\) is \(PT_n\). By Lemma 9, \(G({\mathcal T}_n)\) is interleaving-free. Fix \(x_1:=0^{n+1}1^n\in V(M_n)\). The pair \({\mathcal P}_{G({\mathcal T}_n)}(x_1)\) contains a periodic path \(P\) with starting vertex \(x_1\) and second vertex \(f(x_1)\) in \(M_n\) such that \(\langle P\rangle\) has vertex set \(N({\mathcal T}_n)=\cup_{[x]\in PT_n}\langle P(0x)\rangle=\{\langle x\rangle |x\in V(M_n)\}\), i.e. \(\langle P\rangle\) is Hamilton cycle in \(N_n\). The corresponding flip sequence \(\alpha(P)\) has a shift \[\begin{aligned} \label{la}\lambda(\alpha(P))=\sum_{T\in PT_n}\gamma_T.\lambda(T), \end{aligned}\tag{3}\] for numbers \(\gamma_T\in\{1,-1\}\) that are determined by which gluing cycles encoded by \({\mathcal T}_n\) are nested.

With \(s:=\lambda(\alpha(P))\), define \(\alpha_0:=\alpha(P)\) and \(\alpha_i:=\alpha_0+i.s\), for \(i\in[2n]\). If we apply the entire flip sequence \((\alpha_0,\alpha_1,\ldots,\alpha_{2n})\) to \(x_1\) in \(M_n\), then the vertex \(\sigma^{i.s}(x_1)\) is reached after applying all flips in \((\alpha_0,\alpha_1,\ldots,\alpha_{i-1})\), \(\forall i\in[2n+1]\). If \(s\) and \(2n+1\) are coprime, then \(x_1\) is reached only after applying the entire flip sequence. Since \(\alpha_0\) is the flip sequence of the Hamilton cycle \(\langle P\rangle\) in \(N_n\), the resulting sequence of bitstrings is a Hamilton cycle in \(M_n\). However, this approach requires that \(s=\lambda(\alpha(P))\) and \(2n+1\) be coprime. A technique is needed to modify \(\alpha(P)\) into another flip sequence \(\alpha'\) such that \(s':=\lambda(\alpha')\) is coprime to \(2n+1\).

Switches and their shifts

Let \(p(x,y)\) indicate a pair \(x,y\in V(M_n)\) that differ in just one position. A triple of vertices \(\tau=(x,y,y')\), where \(x\in A_n\), \(\{y,y'\}\subseteq B_n\) and \(y\ne y'\), is a switch if \(x\) differs from \(y\), (resp. \(y'\)) in a single bit, and \(\langle y\rangle=\langle y'\rangle\). In \(N_n\), a switch may be considered as a multiedge \((\langle x\rangle,\langle y\rangle)=(\langle x\rangle,\langle y'\rangle)\). The shift of a switch \(\tau=(x,y,y')\), denoted \(\lambda(\tau)\), is the integer \(i\) such that \(y=\sigma^i(y')\). Denote a switch \(\tau=(x,y,y')\) compactly by writing \(x\) with the 0-bit at position \(p(x,y)\) underlined and the 0-bit at position \(p(x,y')\) overlined. This way, we write \(\tau=(0000111,1000111,0001111)=\underline{0}00\overline{0}111\). For any switch \(\tau=(x,y,y')\), the inverted switch \(\tau^{-1}=(x,y',y)\) has shift \(\lambda(\tau^{-1})=-\lambda(\tau)\). Clearly, cyclically rotating a switch yields another switch with the same shift. Also, reversing a switch yields another switch with the negated shift. For example, \(\sigma(\tau)=11\overline{0}00\underline{0}1\) has shift 1 while its reversed switch \(1\underline{0}00\overline{0}11\) has shift \(-1\).

Consider a flip sequence \(\alpha=(a_1,\ldots,a_k)\) with shift \(\lambda(\alpha)\) for a periodic path \(P=(x_1,\ldots,x_k)\) and let \(x_{k+1}\) be the vertex obtained from \(x_k\) by flipping the bit at position \(a_k\). If \((x_i,x_{i+1})=(x,y)\) for some \(i\in[k]\), then the modified flip sequence \[\begin{aligned} \label{25a} \alpha'=(a_1,\ldots,a_{i-1},p(x,y'),a_{i+1}+\lambda(\tau),\ldots,a_k+\lambda(\tau)) \end{aligned}\tag{4}\] yields a periodic path \(P'=(x'_1,\ldots,x'_k)\) that visits necklaces in the same order as does \(P\), i.e. \(\langle x_i\rangle=\langle x'_i\rangle\), for \(i\in[a_k]\), and \(\lambda(\alpha')=\lambda(\alpha)+\lambda(\tau)\). The situation where \((x_i,x_{i+1})=(x,y')\) is symmetric and considers the inverted switch \(\tau^{-1}\), with \(\lambda(\tau^{-1})=-\lambda(\tau)\).

Similarly, if \((x_i,x_{i+1})=(y',x)\) for some \(i\in[k]\), then the modified sequence \[\begin{aligned} \label{25c}\alpha':=(a_1,\ldots,a_{i-1},p(x,y)+\lambda(\tau),a_{i+1}+\lambda(\tau),\ldots,a_k+\lambda(\tau)) \end{aligned}\tag{5}\] produces a periodic path \(P'=(x'_1,\ldots,x'_k)\) that visits necklaces in the same order as \(P\), and \(\lambda(\alpha')=\lambda(\alpha)+\lambda(\tau)\). The situation \((x_i,x_{i+1})=(y,x)\) is symmetric and goes to the inverted switch \(\tau^{-1}\), with \(\lambda(\tau^{-1})=-\lambda(\tau)\).

In particular, if \(\langle P\rangle\) is a Hamilton cycle in \(N_n\), then \(\langle P'\rangle\) is also a Hamilton cycle in \(N_n\) with shift \(\lambda(\alpha')=\lambda(\alpha)+\lambda(\tau)\).

Construction of switches out of \(\tau_{n,1}=\underline{0}0^{n-1}\overline{0}1^n\), with \(\lambda(\tau)=1\)

For any integers \(n\ge 1\), \(d\ge 1\) and \(1\le s\le d\), make the \((s,d)\)-orbit to be the maximal prefix of the sequence \(s+id\), \(i\ge0\), modulo \(2n+1\), in which all the numbers are distinct. Then, the number of distinct \((s,d)\)-orbits for fixed \(d\) and \(s\ge 1\) is \(n_d:=\)gcd\((2n+1,d)\), and the length of each orbit is \(\ell_d:=\frac{2n+1}{n_d}\), where both \(n_d\) and \(\ell_d\) are odd. For example, let \(n=10\) and \(d=6\), so \(n_d=3\), \(\ell_d=7\) and the \((1,6)\)-orbit is \((1,7,13,19,4,10,16)\), the \((2,6)\)-orbit is \((2,8,14,20,5,11,17)\) and the \((3,6)\)-orbit is \((3,9,15,21,6,12,18)\).

For any integer \(d\) (\(2\le d\le n\)) that is coprime to \(2n+1\), let \(\tau_{n,d}\) denote the sequence whose entries at the positions given by the \((1,d)\)-orbit equal \(\tau_{n,1}=\underline{0}0^{n-1}\overline{0}1^n\), including the overlined and underlined entries.

For any \(n\ge 1\), let \(Z_n\) be the set of bitstrings of length \(2n\) and weight \(n\). For any integers \(d\) (\(3\le d\le n\)) not coprime to \(2n+1\), select an arbitrary bitstring \(z=(z_2,\ldots,z_{n_d})\in Z_{(n_d-1)/2}\). Let \(\tau_{n,d,z}\) be the sequence: (a) whose entries at the positions given by the \((1,d)\)-orbit form the sequence \(\tau_{(\ell_d-1)/2,1}\), including the underlined and overlined entries, and (b) for \(j=2,\ldots,n_d\), all entries at the positions given by the \((j,d)\)-orbit form the sequence \(z_j\). Then, the number of choices for \(z\) in such a construction is \({n_d-1\choose (n_d-1)/2}\).

Interactions

Given a flip bijection \(f\) of \(V(M_n)\) as in Section 3, a switch \(\tau=\tau(x,y,y')\) is said to be \(f\)-conformal if either \(y=f(x)\) or \(x=f(y')\); in such cases, \((x,y)\) or \((y',x)\), respectively, is said to be the \(f\)-edge of \(\tau\). We say that \(\tau\) is \(f^{-1}\)–conformal if \(\tau^{-1}\) is conformal and we refer to the \(f\)-edge of \(\tau^{-1}\) also as an \(f\)-edge of \(\tau\). That a switch is \(f\)-conformal means that its \(f\)-edge belongs to a periodic path, as in Definition 5.

Given a subset \(G\subseteq G_n\), an \(f\)-conformal or \(f^{-1}\)-conformal switch \(\tau\) is usable with respect to \(G\) if for every \((x',y')\in G\) and all \(i\ge 0\), the three \(f\)-edges of \(\sigma^i(C(x',y'))\) in Remark 5 are distinct from the \(f\)-edges of \(\tau\). Those three \(f\)-edges are removed when joining periodic paths.

Number theory

Let \(n\ge 1\). Let \({\mathcal P}(n)\) be the set of prime factors of \(n\). For any \(s\in\{0,1,\ldots,n-1\}\), define \({\mathcal P}(n,s):={\mathcal P}(n)\setminus{\mathcal P}(s)\), if \(s>0\), and \({\mathcal P}(n,0):=\emptyset\).

6. Sketch of Proof of Theorem 1

The switches \(\tau_{n,1}\) and \(\tau_{n,2}\) are not sufficient alone for the proof of Theorem 1, starting with \(n=52\) and \(2n+1=105=3\dot 5\dot 7\) and \(s=5\), for which none of the three numbers \(s-2=3\), \(s+1=6\) and \(s+2=7\) is coprime to \(2n+1\), so Lemma 15 cannot be applied and it is necessary to use switches \(\tau_{n,s,z}\).

7. Efficient Computation: Redefinition of \({\mathcal T}_n\)

In [1], ten rooted trees are distinguished, that in our alternate viewpoint are expressed as: \[\begin{aligned} \label{eqn}\begin{array}{llll} q_0:=01,&q_1:=0011,&q_2:=001011,&q_3:=00100111,\\ q_4:=00101011,&q_5:=0010010111,&q_6:=0010100111,&q_7:=0001100111,\\ q_8:=00011010111,&q_9:=0010101011.&& \end{array} \end{aligned}\tag{10}\]

For \(n\ge 4\), let \({\mathcal T}_n\) be a subgraph of \({\mathcal H}_n\) given as follows: For each plane tree \(T\in PT_n\) with \(T\ne[s_n]\), consider a gluing pair \((x,y)\in G_n\) with either \(T=[x]\) or \(T=[y]\). Let \({\mathcal T}_n\) be the spanning subgraph of \({\mathcal H}_n\) given by the union of the arcs \(([x],[y])\), labeled \((x,y)\), for all gluing pairs \((x,y)\) obtained this way. The definition of the gluing pair \((x,y)\) for a given plane tree \(T\ne[s_n]\) proceeds as in the following three steps (T1)-(T3), unless \(n\) is odd and \(T=[d_n]\), in which case the special rule (D) is applied.

(D) Dumbbell rule

If \(n\) is odd and \(T=[d_n]\), let \(c\) be one of the centroids of \(T\) having exactly one \(c\)-subtree that is not a single edge, namely the subtree \(s_{(n+1)/2}\). Its leftmost leaf \(a\) is thick and pushable to \(c\) in \(T\), so we define \(y:=y(T,c,a)=d'_n\) and \(x:=push(y)\), as in Lemma 8.

(T1) Fix the centroid and subtree ordering

If \(T\) has two centroids, we let \(c\) be a centroid of \(T\) whose active \(c\)-subtrees are not all single edges. If this is true for both centroids, we let \(c\) be the one for which its clockwise-ordered active \(c\)-subtrees \(t_1,\ldots,t_k\) give the lexicographically minimal string \((t_1,\ldots,t_k)\), with \(t_1\) as the first \(c\)-subtree found after the \(c\)-subtree containing the other centroid.

If \(T\) has a unique centroid, we denote it by \(c\) and consider all \(c\)-subtrees of \(T\), denoting them \(t_1,\ldots,t_k\), i.e. \(T=[(t_1,\ldots,t_k)]\) such that among all possible clockwise orderings around \(c\), the string \((t_1,\ldots,t_k)\) is lexicographically minimal.

(T2) Select \(c\)-subtree of \(T\)

If \(T\) has two centroids, we let \(t_{i'}\) be the first of the trees \(t_1,\ldots,t_k\) that differs from \(q_0\), in display (10).

If \(T\) has a unique centroid, then for each of the following conditions (i)-(iv), we consider all trees \(t_i\) (\(i\in[k]\)) and determine the first subtree \(t_i\) satisfying the condition, i.e. only check one of these conditions once all trees failed all previous conditions:

1. \(t_i=q_1\) and \(t_{i-1}=q_0\);

2. \(t_i\in\{q_2,q_4\}\) and \(t_{i+1}\in\{q_0,q_1,q_2\}\);

3. \(t_i\notin\{q_0,q_1,q_2,q_4\}\);

4. \(t_i\neq q_0\).

Conditions (i) and (ii) refer to the previous tree \(t_{i-1}\) and the next tree \(t_{i+1}\) in the clockwise ordering of \(c\)-subtrees, and those indices are considered modulo \(k\). Note that \(T\ne[s_n]\). Thus, at least one \(c\)-subtree is not \(q_0\) and satisfies condition (iv), so this rule to determine \(t_i\) is well defined. Let \(t_{i'}\) be the \(c\)-subtree determined in this way. Clearly, \(t_{i'}\) has at least two edges.

(T3) Select a leaf to push/pull

If \(t_{i'}=0^lq_j1^l\), for some \(l\ge 0\) and \(j\in\{1,\ldots,8\}\), i.e. \(t_{i'}\) is a path with one of the trees \(q_j\) attached to it. Then, four cases are distinguished:

• (q137) If \(j\in\{1,3,7\}\), let \(a\) be the rightmost leaf of \(t_{i'}\), which is thin, and define \(x:=x(T,c,a)\) and \(y:=\mbox{pull}(x)\), as in Lemma 7. Clearly, \((j=1)\Rightarrow(y=0^{l-1}q_21^{l-1}\), if \(l>0\), and \(y=q_0^2\), if \(l=0)\); also, \((j=3)\Rightarrow (y=0^lq_41^l)\); and \((j=7)\Rightarrow (t=0^lq_81^l)\).

• (q24) If \(j\in\{2,4\}\), let \(a\) be the leftmost leaf of \(t_{i'}\), which is thick, and define \(y:=y(T,c,a)\) and \(x:=\mbox{push}(y)\), as in Lemma 8. Clearly, \((j=2)\Rightarrow(x=0^{l-1}q_31^{l-1}\), if \(l>0\), and \(x=q_2q_0\), if \(l=0)\); also, \((j=4)\Rightarrow(x=0^{l-1}q_51^{l-1}\), if \(l>0\), and \(x=q_2q_0\), if \(l=0)\).

• (q5) If \(j=5\), let \(a\) be the unique leaf of \(t_{i'}\) that is neither the rightmost nor the leftmost leaf of \(t_{i'}\), where \(a\) is thick, and define \(y:=y(T,c,a)\) and \(y=\mbox{push}(x)\), as in Lemma 8. Clearly, \(x=0^lq_61^l\).

• (q8) If \(j=8\), let \(a\) be the leftmost leaf of \(t_{i'}\), which is thin, and define \(x:=x(T,c,a)\) and \(y:=\mbox{pull}(x)\), as in Lemma 7. Clearly, \(y=0^lq_01^l\).

Otherwise, there are three cases to be distinguished:

• (e) If the potential \(\phi(T)=\phi(c)\) is even, we let \(a\) be the rightmost leaf of \(t_{i'}\) and define \(x:=x(T,c,a)\) and \(y=\mbox{pull}(x)\), as in Lemma 7.

• (o1) If the potential \(\phi(T)=\phi(c)\) is odd and the leftmost leaf \(a\) of \(t_{i'}\) is thin, define \(x:=x(T,c,a)\) and \(y:=\mbox{pull}(y)\), as in Lemma 7.

• (o2) If the potential \(\phi(T)=\phi(c)\) is odd and the leftmost leaf \(a\) of \(t_{i'}\) is thick, define \(y:=y(T,c,a)\) and \(x:=\mbox{push}(y)\), as in Lemma 8.

This completes the definition of \({\mathcal T}_n\). [1] refers to rules (q137), (q8), (e) and (o1) in step (T3) as pull rules and to rules (q24), (q5) and (o2) as push rules. The leaf to which one of the pull rules (q137), (q8) or (o1) is applied is always thin, whereas the leaf to which any push rule is applied is always thick.

Illustrations for the spanning trees \({\mathcal T}_i\) for \(i=4,5,6,7\) are in Figures 7-8, the versions of [1, Figures 15-16] for the alternate viewpoint in this survey.

Interaction with switches

Assume \(G\subseteq G_n\) is nesting-free. A usable switch \(\tau\) is reversed if the \(f\)-edge of \(\tau\) lies on the reversed path of one of the gluing cycles \(\sigma^i(C(x',y'))\), \((x',y')\in G\), for some \(i\ge 0\), i.e. on the path \(\sigma^i(x'^1,\ldots,x'^5)\).

8. Sketch of Proof of Algorithmic Theorem 2

The algorithm in Theorem 2 is a faithful implementation of the constructive proof of Theorem 1 sketched in Section 6 which also works with the spanning tree \({\mathcal T}_n\) of Section 7. In particular, the switch \(\tau_{n,d,z}\) is usable by Lemma 18. The effective shifts of the switches \(\tau_{n,1}\), \(\tau_{n,2}\) and \(\tau_{n,d,z}\) used in the proof, i.e. the signs \(\gamma_1\), \(\gamma_2\) and \(\gamma_d\) in displays (6)-(8), can now be computed explicitly. Specifically, from Lemmas 12, 13 and 18, it is obtained: \[\begin{aligned} \label{gam}\gamma_1=(-1)(-1)=+1,\gamma_2=(+1)(+1)=(+1),\gamma_d=(-1)(+1)=-1. \end{aligned}\tag{11}\] In each product in (11), the first factor is \(-1\) if and only if the switch is \(f^{-1}\)-conformal and the second factor is \(-1\) if and only if the switch is reversed.

Declaration of competing interest

The author declares no conflicts of interest to this work.