# Imaginary-time Quantum Relaxation Critical Dynamics with Semi-ordered
Initial States

Zhi-Xuan Li  School of Physics and Materials Science, Guangzhou University,
Guangzhou 510006, China  Shuai Yin  School of Physics, Sun Yat-Sen University,
Guangzhou 510275, China  Yu-Rong Shu<EMAIL_ADDRESS>School of Physics and
Materials Science, Guangzhou University, Guangzhou 510006, China

###### Abstract

We explore the imaginary-time relaxation dynamics near quantum critical points
with semi-ordered initial states. Different from the case with homogeneous
ordered initial states, in which the order parameter $M$ decays homogeneously
as $M\propto\tau^{-\beta/\nu z}$, here $M$ depends on the location $x$,
showing rich scaling behaviors. Similar to the classical relaxation dynamics
with an initial domain wall in Model A, which describes the purely dissipative
dynamics, here as the imaginary time evolves, the domain wall expands into an
interfacial region with growing size. In the interfacial region, the local
order parameter decays as $M\propto\tau^{-\beta_{1}/\nu z}$, with $\beta_{1}$
being an additional dynamic critical exponent. Far away from the interfacial
region the local order parameter decays as $M\propto\tau^{-\beta/\nu z}$ in
the short-time stage, then crosses over to the scaling behavior of
$M\propto\tau^{-\beta_{1}/\nu z}$ when the location $x$ is absorbed in the
interfacial region. A full scaling form characterizing these scaling
properties is developed. The quantum Ising model in both one and two
dimensions are taken as examples to verify the scaling theory. In addition, we
find that for the quantum Ising model the scaling function is an analytical
function and $\beta_{1}$ is not an independent exponent.

The understanding of nonequilibrium dynamics in quantum many-body systems is
attracting increasing attentions in recent years inspired by the fast
developments of quantum computers Satzinger  _et al._ (2021); Semeghini  _et
al._ (2021); King  _et al._ (2022) and ultra-cold atom experimental techniques
Bloch  _et al._ (2008). In particular, the study of imaginary-time quantum
critical dynamics is heating up thanks to the recent progresses made by
quantum computers in realizing imaginary-time evolution in quantum systems
Motta  _et al._ (2020); Nishi  _et al._ (2021). Grasping critical properties
on the imaginary-time relaxation avenue down to the critical ground state not
only saves computational efforts but also yields dynamical properties that is
beyond the reach of equilibrium studies. The critical relaxation dynamics is
one of the most simple but important member of the nonequilibrium quantum
critical dynamics family. In the past few years, a scaling theory for the
imaginary-time quantum critical relaxation dynamics has been developed Yin
_et al._ (2014a); Zhang  _et al._ (2014a) in analogy to the critical
relaxation dynamics in classical systems Janssen  _et al._ (2014); Li  _et
al._ (1995, 1996); Zheng (1998); Ying  _et al._ (1998); Zheng (1996). It has
been shown that the initial information can affect the critical relaxation
dynamics in the macroscopic time scale owing to the divergence of the
correlation time at the critical point. Universal behaviors have been found
during the imaginary-time relaxation process with a homogeneous initial state.
For saturated ordered initial state, the order parameter $M$ changes with the
imaginary-time $\tau$ as $M\propto\tau^{-\beta/\nu z}$ Yin  _et al._ (2014a),
in which $\beta$ is the order parameter exponent defined as
$M\propto|g|^{-\beta}$ with $g$ being the distance to the critical point,
$\nu$ is the correlation length exponent defined as $\xi\propto|g|^{-\nu}$
with $\xi$ being the correlation length, and $z$ is the dynamic exponent
defined as $\zeta\propto\xi^{z}$ with $\zeta$ being the correlation time. For
initial state with a small initial order parameter $M_{0}$, the order
parameter increases according to $M\propto M_{0}\tau^{\theta}$ with $\theta$
the critical initial slip exponent in the short-time stage, then decays as
$M\propto\tau^{-\beta/\nu z}$ in the long-time stage. For initial state with
arbitrary order parameter, a universal characteristic function is introduced
to describe the universal effects induced by the initial state Zheng (1996);
Zhang  _et al._ (2014a). These phenomena have been investigated in various
phase transitions within and beyond the Landau paradigm Yin  _et al._ (2014a);
Zhang  _et al._ (2014a); Shu  _et al._ (2017); Shu and Yin (2020); Shu  _et
al._ (2022); Shu and Yin (2022). It has been shown that the imaginary-time
relaxation dynamics of quantum systems can be different from its classical
counterpart. For instance, the critical initial slip exponent $\theta$ is
$0.373$ Yin  _et al._ (2014a) and $0.209$ Shu  _et al._ (2017) for the one-
dimensional ($1$D) and two-dimensional ($2$D) quantum Ising model, while
$\theta$ is $0.191$ Okano  _et al._ (1997) and $0.108$ Jaster  _et al._ (1999)
for their classical counterparts, respectively. Therefore, the imaginary-time
relaxation dynamics deserves special attentions. The flourishing developments
in this issue also inspire us to explore the effects induced by other kinds of
initial states, like the inhomogeneous initial state, in the imaginary-time
evolution.

Critical properties in the presence of the inhomogeneous interfacial regions
have raised long-term attentions in various systems, since phase coexistence
is a common phenomenon in nature Domb and Lebowitz (1986). In particular,
critical relaxation dynamics with a domain interface in a semi-ordered initial
state was studied Zhou and Zheng (2007, 2008). These works showed that
different from the relaxation dynamics with a homogeneous initial state, the
initial domain wall can expand into a growing interfacial region, and in this
region the order parameter decays obeying a distinct scaling relation
$M\propto t^{-\beta_{1}/\nu z}$ with $\beta_{1}$ being an additional dynamic
exponent. In quantum systems, exotic prethermal dynamics induced by the
interface in the $2$D quantum Ising model was discovered Yoshinaga  _et al._
(2022); Hart and Nandkishore (2022); Balducci  _et al._ (2022).

Motivated by the above intriguing issues, we investigate the imaginary-time
relaxation dynamics with a semi-ordered initial state, in which two completely
ordered domains with opposite spin direction sandwich a sharp domain wall, as
shown in Fig. 1. We find that similar to the classical case Zhou and Zheng
(2007, 2008), as the time evolves, the sharp domain wall will blur and expand
into an interfacial region. Let us focus on the behavior of the local
parameter at the position $x$, with $x$ denotes the distance to the initial
domain wall. When $x$ is far away from the interfacial region, the local order
parameter decays as $M(\tau,x)\propto\tau^{-\beta/\nu z}$. As time elapses,
the interfacial region spreads to the position $x$. Accordingly, the order
parameter changes to decay as $M(\tau,x)\propto\tau^{-\beta_{1}/\nu z}$. Here,
$\beta_{1}$ is a purely dynamic exponent, since it has no equilibrium
counterpart, similar to the classical case Zhou and Zheng (2007, 2008). A full
scaling form is then developed to explain this behavior. We take the $1$D and
$2$D quantum Ising models as examples to verify this scaling theory. From the
numerical results, we find that the scaling function is an analytical function
and $\beta_{1}$ seems not an independent critical exponent. Instead, it
satisfies $\beta_{1}/\nu z=\beta/\nu z+1$, in analogy to the classical case
Zhou and Zheng (2007, 2008).

Figure 1: Sketch of the imaginary-time relaxation dynamics from a semi-ordered
initial state. A sharp domain wall separates the spin-up and -down domains in
the initial state. As time evolves, the domain wall extends to an interfacial
region.

For the imaginary-time relaxation dynamics, the evolution of the wave function
$|\psi(\tau)\rangle$ obeys the imaginary-time Schrödinger equation
$-\partial_{\tau}|\psi(\tau)\rangle=H|\psi(\tau)\rangle$ with the
normalization condition $\langle\psi(\tau)|\psi(\tau)\rangle=1$ Yin  _et al._
(2014b); Zhang  _et al._ (2014b). The formal solution of the Schrödinger
equation is given by $|\psi(\tau)\rangle=\exp(-\tau
H)|\psi(\tau_{0})\rangle/Z$, in which $\tau_{0}$ is the initial time of the
evolution and $Z=\|\exp(-\tau H)|\psi(\tau_{0})\rangle\|$, with $\|\cdot\|$
being the modulo operation. Since both the imaginary-time dynamics and the
classical dynamics described by Model A, which refers to a set of models with
no conservation laws Hohenberg and Halperin (1977), are purely dissipative
dynamics, one expects that their dynamic scaling behaviors near the critical
point are similar Yin  _et al._ (2014a). For instance, from the saturated
ordered initial state, the order parameter $M$ follows the same power-law
decay with the evolution time with the exponent $\beta/\nu z$ for both
classical model A dynamics and quantum imaginary-time relaxation dynamics.

Here we study the influence of a different type of initial state to the
quantum imaginary-time relaxation dynamics. The initial state is set as a
semi-ordered state with two fully-ordered domains with opposite spin
directions, separated by a sharp domain wall, as shown in Fig. 1. Since the
translational symmetry is broken by the initial state, it is expected that the
evolution behavior of $M$ depends on the distance to the initial domain wall
$x$. Near the domain wall, the spin at small $x$ feels a stronger spin-flip
intention from the other domain where the spins orientated in the opposite
direction than its homogeneous ordered environment. Accordingly, one
anticipates that at the critical point, for small $x$, the local order
parameter should follows

$M(x,\tau)\propto\tau^{-\beta_{1}/\nu z},$ (1)

with $\beta_{1}$ being an additional critical exponent which is larger than
$\beta$, since the other domain lures the spin at $x$ to flip. Note that
similar to the classical case Zhou and Zheng (2007, 2008), here $\beta_{1}$ is
a purely nonequilibrium critical exponent, since it has no static counterpart.

In contrast, for large $x$, the dynamic scaling behavior of $M(x,\tau)$ is
much richer as a result of the spread of the effects induced by the domain
wall, as illustrated in Fig. 1. In the short-time stage, the domain wall
region is too far away to control the spin at $x$ and thus the local order
parameter $M$ decays according to $M(x,\tau)\propto\tau^{-\beta/\nu z}$,
similar to the case with homogeneous ordered initial state. Therefore, this
stage is referred to as the ‘homogeneous region’. As time passes by, the
domain wall extends into an ‘interfacial region’ with growing size. When the
location $x$ is absorbed into this interfacial region, $M$ will evolve
following Eq. (1).

Scaling theory. For the relaxation critical dynamics with homogeneous initial
state, a characteristic scaling behavior is the appearance of the critical
initial slip characterized by an independent critical exponent $\theta$. A
nature question is whether or not $\beta_{1}$ is another independent exponent.
To answer this question, we develop a full scaling form to describe the whole
imaginary-time relaxation process with the semi-ordered initial state. In
analogy with the classical situation Zhou and Zheng (2007, 2008), the scaling
form of the local order parameter $M$ at a quantum critical point is given by

$M(\tau,x)=\tau^{-\beta/\nu z}f(x\tau^{-1/z}),$ (2)

in which $f(x\tau^{-1/z})$ is the scaling function. By comparing Eq. (2) with
the imaginary-time relaxation scaling theory with the homogeneous initial
state Yin  _et al._ (2014a), one finds that the initial order parameter is
absent in Eq. (2). The reason is that the initial state keeps invariant under
the renormalization transformation, as illustrated in Fig. 2. Similarly, the
initial correlation is also not included since both the initial correlation
length and correlation time are zero.

Figure 2: Sketch of renormalization group transformation of the initial state.
After the processes of coarse graining and rescaling, the state keeps
invariant.

It is expected that the scaling behaviors discussed above should be covered by
the full scaling form Eq. (2). This gives some constraints on the scaling
function $f(x\tau^{-1/z})$: (i) $f(x\tau^{-1/z})$ should be an odd function of
$x$ since $M$ should change sign on switching the spin orientation of the
initial spin domains; (ii) in the homogeneous region with large $x$ and small
$\tau$, $M(x,\tau)$ should satisfy $M(x,\tau)\propto\tau^{-\beta/\nu z}$;
(iii) in the interfacial region with small $x$ and large $\tau$, $M(x,\tau)$
should decay as $M(x,\tau)\propto\tau^{-\beta_{1}/\nu z}$. Thus, the scaling
function $f(x\tau^{-1/z})$ must tend to a constant as
$x\tau^{-1/z}\rightarrow\infty$, while for $x\tau^{-1/z}\rightarrow 0$,
$f(x\tau^{-1/z})$ should satisfy
$f(x\tau^{-1/z})\propto|x\tau^{-1/z}|^{\omega}$, in which
$\omega\equiv(\beta_{1}-\beta)/\nu$. Accordingly, we summarize the properties
of $f(x\tau^{-1/z})$ as follows,

$\displaystyle f=$ $\displaystyle C_{1}$ , $x\tau^{-1/z}\gg 1$ (3a)
$\displaystyle f=$ $\displaystyle C_{2}{\rm sgn}(x)(x\tau^{-1/z})^{\omega}$ ,
$x\tau^{-1/z}\ll 1$ (3b)

in which both $C_{1}$ and $C_{2}$ are constants, and ${\rm sgn}(x)$ denotes
the sign function of $x$. In general, without extra information, $\omega$
cannot be determined from the phenomenological scaling analyses. In this
respect, $\beta_{1}$ can be an independent additional exponent. However, for
the special case in which $f(x\tau^{-1/z})$ is an analytical function, the
Taylor expansion of $f(x\tau^{-1/z})$ at $x\tau^{-1/z}\rightarrow 0$, gives
$\omega=1$, which indicates that $\beta_{1}$ is not an independent exponent
but instead satisfies $\beta_{1}/\nu=\beta/\nu+1$. For finite-size system with
$L$ its linear size, by taking into account the finite-size effects, the full
scaling form reads

$M(\tau,x,L)=\tau^{-\beta/\nu z}f_{L}(x\tau^{-1/z},L\tau^{-1/z}),$ (4)

in which $f_{L}$ is another scaling function. When $L\tau^{-1/z}\gg 1$, the
interfacial region is much smaller than the lattice size. Accordingly, the
finite-size effects can be ignored and $f_{L}(x\tau^{-1/z},L\tau^{-1/z})$ can
be approximated as $f(x\tau^{-1/z})$. In contrast, when $L\tau^{-1/z}\ll 1$,
the energy gap induced by the lattice size becomes relevant, the system will
decay exponentially towards the ground state. This is the usual finite-size
scaling region.

Model. The Hamiltonian of the quantum Ising model studied here is Sachdev
(2011)

$H=-J\sum_{\langle
ij\rangle}\sigma^{z}_{i}\sigma^{z}_{j}-h_{x}\sum_{i}\sigma^{x}_{i},$ (5)

in which $J$ is set as $1$ as the unity of energy scale, and $h_{x}$ is the
strength of the transverse field. $\sigma^{z,x}_{i}$ denotes the Pauli matrix
in $z,x$-direction at site $i$, and $\langle ij\rangle$ represents nearest
neighbors. For large $h_{x}$, the system is in the quantum paramagnetic state,
and for small $h_{x}$, the system is in the ferromagnetic state. For the $1$D
case, the critical point locates at $h_{x}=h_{xc}=1$, and the critical
exponents are exactly solved as $\beta=1/8$, $\nu=1$, and $z=1$ Sachdev
(2011); Sondhi  _et al._ (1997); Vojta (2003). For the $2$D case, the critical
point is at $h_{x}=h_{xc}=3.04451$ Shu  _et al._ (2017). The critical
exponents are estimated as $\beta=0.327(1)$, $\nu=0.630(2)$ Jaster  _et al._
(1999), and $z=1$ Sachdev (2011); Sondhi  _et al._ (1997); Vojta (2003).

Figure 3: Local order parameter $M(x,\tau)$ for the $1$D quantum Ising model.
Log-log scale is used. Panel (a): Solid diamonds and open circles represent
results of $L=512$ and $1024$, respectively. Crossover behaviors are shown in
$M(x,\tau)$ for different $x$. Solid lines are power-law fits to the data of
$x=0.5$ and $x=255.5$. The critical exponent $\beta/\nu$ and $\beta_{1}/\nu$
are given by $0.1245(5)$ and $1.121(9)$, respectively. Panel (b): The rescaled
curve shows two different scaling region and the dash line represents a power
law of $(x\tau^{-1/z})^{\omega}$ with $\omega=1$.

To verify the above scaling theory, we perform projector quantum Monte Carlo
Sandvik (2010); Farhi  _et al._ (2012) simulations in both the $1$D and $2$D
quantum Ising model. We compute dependence of the local order parameter on the
position $x$ and the evolution time $\tau$. For simplicity, the periodic
boundary condition is used so that boundary effects can be neglected. At a
given evolution time $\tau$, for $1$D system, the local order parameter is
defined as $M(x)=\langle\sigma^{z}(x)\rangle$. In the $2$D system, since the
$y$ direction is homogeneous, $M(x)$ is taken as the $y$-direction averaged
value for a given $x$, defined as
$M(x)=\left\langle\sum_{y=1}^{L}\sigma^{z}(x)\right\rangle/L$, in which $y$
direction is perpendicular to the $x$ direction. The lattice shape is set to
be $2L\times L$ so that the two domains occupy the same area of $L\times L$.
Note that in Eqs. (2)-(4), $x$ is a continuous variable that represents the
distance to the center of the interfacial region, but here in lattice system,
$x$ is discrete. As shown in Fig. 2, the location of the initial domain wall
is set as $x=0$ and for other positions, $x$ should be among
$\\{\pm\frac{1}{2},\pm\frac{3}{2},...,\pm(\frac{L_{x}}{4}+\frac{1}{2})\\}$
with $L_{x}=L$ for $1$D and $L_{x}=2L$ for $2$D, restricted by the periodic
boundary condition. Besides, due to the spin inversion symmetry, $M(x)$ and
$-M(-x)$ should be equivalent, so that the finial result $M(x)$ is taken as
the average of $|M(x)|$ and $|M(-x)|$.

Numerical results. For the $1$D quantum Ising model, in Fig. 3 (a) we show the
evolution of the order parameter for different $x$. In order to extract the
exponent without the influence of finite-size effect, we plot $M$ for system
of $L=512$ and $1024$ find that up to the time scale considered here, the
dependence of $M$ on $L$ is very weak. Therefore, one can consider the fitted
result represents the effects induced by the initial domain wall only. At the
position $x=0.5$ that is closest to the initial domain wall, we find that
after a transient non-universal stage, the order parameter presents a power-
law decay of $M\propto\tau^{-1.121}$. The exponent $1.121(9)$ (with the number
in the parentheses stands for error bar) is much larger than $\beta/\nu z=1/8$
characterizing the evolution of $M$ relaxed from the homogeneous initial
state. As the scaling theory indicates, close to the initial domain wall, the
local order parameter should decay with an exponent $\beta_{1}/\nu z$, rather
than $\beta/\nu z$. With $\nu=1$ and $z=1$ known, one deduces that
$\beta_{1}=1.121(9)$ and one can find $\omega=0.9965$. In consideration of the
statistical error, these results strongly indicate that $\beta_{1}=9/8$ and
$\omega=1$, suggesting that the scaling function $f(x\tau^{-1/z})$ is an
analytical function.

Figure 4: For fixed $xL^{-1}=1/64$, evolution of $M$ before (a) and after (b)
rescaling for $L=32$ to $992$ in $1$D quantum Ising model. Three different
scaling regions are labeled in (b). The dash line is a power law of $(\tau
L^{-z})^{-\omega}$ with $\omega=1$. Log-log scale is used.

Different from the results of $x=0.5$, at positions far away from the initial
domain wall, for instance, $x=255.5$ for $L=1024$, the local order parameter
decays as $M\propto\tau^{-0.1245}$ in the universal short-time stage, as shown
in Fig. 3 (a). The exponent $0.1245(5)$ is close to $\beta/\nu z$,
demonstrating that in the short-time stage, the evolution time is yet too
short for the influence of the other domain to propagate to the positions far
away from the initial domain wall. Thus, the spin at large $x$ only feels its
own homogeneous background, where the homogeneous fluctuations dominate. As
time elapses, $M$ gradually crosses over to the behavior of
$M\propto\tau^{-\beta_{1}/\nu z}$, indicating that the influence induced by
the initial inhomogenity begin to control the dynamics when the interfacial
region spreads over $x$. This crossover behavior can be clearly observed for
intermediate $x$. The crossover time scale depends on the position $x$.

In Fig. 3 (b), we rescale $M$ and $\tau$ as $M\tau^{\beta/\nu z}$ and
$x\tau^{-1/z}$, respectively. We find that the rescaled curves collapse on a
single curve, confirming Eq. (2). This single curve is just the scaling
function $f(x\tau^{-1/z})$. For $x\tau^{-1/z}\gg 1$ the local order parameter
is in the homogeneous region and $f(x\tau^{-1/z})$ tends a constant, while for
$x\tau^{-1/z}\ll 1$ the local order parameter is in the interfacial region and
$f(x\tau^{-1/z})\propto(x\tau^{-1/z})^{\omega}$ with $\omega$ close to $1$.
These results not only verify Eqs. (3a) and (3b), but also indicate that the
scaling function $f(x\tau^{-1/z})$ is an analytical function for
$x\tau^{-1/z}\rightarrow 0$.

Figure 5: Local order parameter $M(x,\tau)$ for the $2$D quantum Ising model.
Log-log scale is used. Panel (a): Solid diamonds and open circles represent
results of lattice size of $256\times 128$ and $512\times 256$. Finite-size
effects are very weak. Crossover behaviors are seen when $x$ changes. The
solid lines are power-law fits to the data of $x=0.5$ and $x=127.5$. The
critical exponent $\beta/\nu$ and $\beta_{1}/\nu$ are given by $0.517(4)$ and
$1.52(6)$, respectively. In panel (b): Rescaled curve of $M$. Different
scaling regions are labeled and the dash line represents a power law of
$(x\tau^{-1/z})^{\omega}$ with $\omega=1$.

Then we explore the finite-size effects. For convenience, a variable
transformation can be implemented in Eq. (4) by replacing $x\tau^{-1/z}$ and
$L\tau^{-1/z}$ with $\tau L^{-z}$ and $xL^{-1}$, respectively, giving the
scaling form $M(\tau,x,L)=L^{-\beta/\nu}g(\tau L^{-z},xL^{-1})$, with $g$
being another scaling function. For fixed $xL^{-1}$, the curves of $M$ for
different lattice sizes are shown in Fig. 4 (a). After rescaling $M$ and
$\tau$ as $ML^{\beta/\nu}$ and $\tau L^{-z}$, respectively, we find in Fig.
(4) (b) the curves collapse on to the single curve of $g(\tau L^{-z})$,
confirming Eq. (4). With $xL^{-1}$ fixed, for small $\tau L^{-z}$, $g(\tau
L^{-z})$ tends to a constant, corresponding to the homogeneous region. For
intermediate $\tau L^{-z}$, $g(\tau L^{-z})\propto(\tau L^{-z})^{-1}$, which
is the interfacial region. For large $\tau L^{-z}$, there exists a finite-size
region in $g(\tau L^{-z})$, where finite-size effect starts to take control of
the scaling function. In the finite-size region, $M$ decays very fast towards
its equilibrium value. The good collapse again verifies the scaling theory
proposed above.

For the $2$D quantum Ising model, in Fig. 5 (a) we show the evolution of the
local order parameter for different $x$. Similarly, here we plot the results
of two different system sizes $256\times 128$ and $512\times 256$, in order to
show finite-size effects are very weak at the time scale considered. For spins
closest to the initial domain wall, namely $x=0.5$, Fig. 5 (a) shows that the
local order parameter decays as $M\propto\tau^{-1.52}$ with the exponent
$1.52(6)$ that is apparently larger than $\beta/\nu=0.518$ Shu  _et al._
(2017), suggesting that the spins at small $x$ are strongly affected by the
initial inhomogenity. Similar to the $1$D case, at $x=0.5$, $M$ should decay
as $\tau^{-\beta_{1}/\nu z}$. Therefore, one finds that $\beta_{1}/\nu
z=1.52(6)$. Differently, for spins far away from the initial domain wall with
large $x$, in the short-time stage, the local order parameter exhibits a
slower power-law decay as $M\propto\tau^{-0.517}$ for the largest value
$x=127.5$. The exponent $0.517(4)$ is close to $\beta/\nu z=0.518$ Shu  _et
al._ (2017). As time passes, $M$ gradually crosses over to a power-law decay
with the exponent $\beta_{1}/\nu z$, indicating that the interfacial region
spreads across $x$ . The crossover time scale increases with $x$ moving away
from the initial domain wall. From the results of $x=0.5$ and $x=127.5$, we
obtain $\omega=1.003$, which is also close to $1$. In analogy to the $1$D
case, taking into account of statistical errors and the possible remaining
finite-size effects, one deduces that $\omega=1$ for the $2$D case as well.

In Fig. 5 (b), we rescale $M$ and $\tau$ as $M\tau^{\beta/\nu z}$ and
$x\tau^{-1/z}$. The rescaled curves collapse onto a single curve of scaling
function $f(x\tau^{-1/z})$, confirming Eq. (2). Similar to the $1$D case, when
$x\tau^{-1/z}\gg 1$, $f(x\tau^{-1/z})$ tends to a constant, representing the
homogeneous region. When $x\tau^{-1/z}\ll 1$, the scaling function is
proportional to $(x\tau^{-1/z})^{\omega}$, with $\omega=1$, corresponding to
the interfacial region. These results verify Eqs. (3a) and (3b) and indicate
that the scaling function is analytical.

Discussions. The agreement between the results of the $1$D and $2$D quantum
Ising model confirms that the scaling theory discussed above is universal. We
find $\omega$ is very close to $1$, which strongly suggests that the scaling
function $f(x\tau^{-1/z})$ is an analytical function when
$x\tau^{-1/z}\rightarrow 0$ and $\beta_{1}$ is not an independent critical
exponent.The analyticity of the scaling function $f(x\tau^{-1/z})$ may
originated from the preparation of the semi-ordered initial state. For the
present case, the spin-up and spin-down domain correspond to the two saturated
initial states, which are both fixed points of the scaling transformation.
Moreover, although the initial state contributes a sharp domain wall, this
non-analyticity can be smeared by the quantum fluctuations in the following
relaxation.

Recent experiments have shown that the quantum imaginary-time evolution can be
implemented in quantum computers Nishi  _et al._ (2021); Motta  _et al._
(2020). The imaginary-time evolution in a small time interval $\Delta\tau$ can
be approximated by the real-time evolution operator with the auxiliary
Hamiltonian $\mathcal{H}$ determined by minimizing the residual norm
$\left\|e^{-\Delta\tau H}|\psi\rangle/Z-e^{-i\Delta
t\mathcal{H}}|\psi\rangle\right\|^{2}$ where $Z=\langle\psi|e^{-2\Delta\tau
H}|\psi\rangle$ Nishi  _et al._ (2021); Motta  _et al._ (2020). It is
promising that the quantum critical relaxation dynamics can be realized during
the process to the ground state in quantum devices. The semi-ordered initial
state considered here has vanishing correlation length and is easy to prepare,
making the issue stuied here a suitable candidate for realizations of
nonequilibrium dynamics in quantum computations.

Here we discuss the relaxation dynamics with semi-ordered initial states of a
generalized quantum Ising model, which includes an additional longitudinal
field term $-h_{z}\sum_{i}\sigma_{i}^{z}$ to the original model (5), described
by $H=H_{0}-h_{z}\sum_{i}\sigma_{i}^{z}$. $H_{0}$ denotes the Hamiltonian in
(5). In the thermodynamic limit, the scaling behavior of the local order
parameter is

$M=\tau^{-\beta/\nu z}f(x\tau^{-1/z},h_{z}\tau^{\beta\delta/\nu z}),$ (6)

in which the exponent $\delta$ is defined by $M\propto h_{z}^{1/\delta}$ at
the critical point and $f$ is a scaling function. Imposing a longitudinal
field aligned along the spin-up direction in Fig. 1, up to linear term of $f$,
one obtains

$M=\tau^{-\beta/\nu z}f^{\prime}(0,0)(x\tau^{-1/z}+h_{z}\tau^{\beta\delta/\nu
z}),$ (7)

in which $f^{\prime}$ denotes the first derivative of the scaling function
$f$. To find out the location of the domain wall, one should let $M=0$ since
the domain wall separates the spin-up and -down domains. For $h_{z}=0$,
enforcing $M=0$ one finds that $x=0$, as shown in Fig. 2. For $h_{z}\neq 0$,
enforcing $M=0$ one arrives at $x\tau^{-1/z}+h\tau^{\beta\delta/\nu z}=0$,
giving $x=-h_{z}\tau^{\beta\delta/\nu z+1/z}$. Therefore, in the presence of
the longitudinal field, the domain wall moves towards the spin-down side and
the stronger $h_{z}$ is, the further $x$ is. The longitudinal field tends to
force all spins align along the spin-up direction homogeneously. As
$\tau\rightarrow\infty$, the order parameter $M\propto h_{z}^{1/\delta}$,
recovering the equilibrium scaling behavior. As a result, the relaxation
dynamics is a superposition of the two effects: the domain wall should shifts
towards the side where spins align opposite to $h_{z}$ and extends into an
interfacial region.

In summary, we study the nonequilibrium imaginary-time quantum critical
dynamics with semi-ordered initial states. We show that in the imaginary-time
relaxation process the domain wall extends to an interfacial region with
growing size. We find that the local order parameters inside and outside of
the interfacial region satisfy different scaling relations. When the location
is outside of the interfacial region, the order parameter evolves as
$M\propto\tau^{-\beta/\nu z}$, similar to the case with homogeneous initial
ordered state. In contrast, when the location is inside the interfacial
region, the order parameter evolves as $M\propto\tau^{-\beta_{1}/\nu z}$. By
analogy with the classical critical dynamics, we develop a scaling theory and
verify it numerically in the $1$D and $2$D quantum Ising model. The numerical
results show that scaling theory is universal and strongly indicate that
$\beta_{1}$ is not an independent exponent but satisfies
$\beta_{1}/\nu=\beta/\nu+1$. We also discuss the relaxation dynamics with
semi-ordered initial states in the presence of an additional longitudinal
field to the quantum Ising model.

Acknowledgements. We gratefully acknowledge helpful discussions with Bo Zheng.
We thank an anonymous referee for his/her suggestions of considering the
relaxation dynamics in the presence of a longitudinal field term of the
quantum Ising model. Z.X.L. and Y.R.S. are supported by the National Natural
Science Foundation of China (Grants No. 12104109) and the Science and
Technology Projects in Guangzhou (202201020222). S.Y. is supported by the
Science and Technology Projects in Guangzhou (202102020367) and the
Fundamental Research Funds for Central Universities, Sun Yat-Sen
University(22qntd3005).

## References

  * Satzinger  _et al._ (2021) K. J. Satzinger, Y.-J. Liu, and A. S. et al., “Realizing topologically ordered states on a quantum processor,” Science 374, 1237–1241 (2021).
  * Semeghini  _et al._ (2021) G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, A. Omran, S. Sachdev, A. Vishwanath, M. Greiner, V. Vuletić, and M. D. Lukin, “Probing topological spin liquids on a programmable quantum simulator,” Science 374, 1242–1247 (2021).
  * King  _et al._ (2022) A. D. King, J. Raymond, and T. L. et al., “Quantum critical dynamics in a 5000-qubit programmable spin glass,” arXiv:2207.13800 (2022).
  * Bloch  _et al._ (2008) I. Bloch, J. Dalibard, and W. Zwerger, “Many-body physics with ultracold gases,” Rev. Mod. Phys. 80, 885–964 (2008).
  * Motta  _et al._ (2020) M. Motta, C. Sun, A. T. K. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. S. L. Brandão, and G. K.-L. Chan, “Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution,” Nature Physics 16, 205–210 (2020).
  * Nishi  _et al._ (2021) H. Nishi, T. Kosugi, and Y.-i. Matsushita, “Implementation of quantum imaginary-time evolution method on NISQ devices by introducing nonlocal approximation,” npj Quantum Information 7, 85 (2021).
  * Yin  _et al._ (2014a) S. Yin, P. Mai, and F. Zhong, “Universal short-time quantum critical dynamics in imaginary time,” Phys. Rev. B 89, 144115 (2014a).
  * Zhang  _et al._ (2014a) S. Zhang, S. Yin, and F. Zhong, “Generalized dynamic scaling for quantum critical relaxation in imaginary time,” Phys. Rev. E 90, 042104 (2014a).
  * Janssen  _et al._ (2014) H. K. Janssen, B. Schaub, and B. Schmittmann, “New universal short-time scaling behaviour of critical relaxation processes,” Zeitschrift für Physik B Condensed Matter 73, 539 (2014).
  * Li  _et al._ (1995) Z. B. Li, L. Schülke, and B. Zheng, “Dynamic monte carlo measurement of critical exponents,” Phys. Rev. Lett. 74, 3396–3398 (1995).
  * Li  _et al._ (1996) Z. Li, L. Schülke, and B. Zheng, “Finite-size scaling and critical exponents in critical relaxation,” Phys. Rev. E 53, 2940–2948 (1996).
  * Zheng (1998) B. Zheng, “Monte carlo simulations of short-time critical dynamics,” International Journal of Modern Physics B 12, 1419–1484 (1998).
  * Ying  _et al._ (1998) H. P. Ying, H. J. Luo, L. Schülke, and B. Zheng, “Dynamic Monte Carlo Study of the Two-Dimensional Quantum XY Model,” Modern Physics Letters B 12, 1237–1243 (1998).
  * Zheng (1996) B. Zheng, “Generalized dynamic scaling for critical relaxations,” Phys. Rev. Lett. 77, 679–682 (1996).
  * Shu  _et al._ (2017) Y.-R. Shu, S. Yin, and D.-X. Yao, “Universal short-time quantum critical dynamics of finite-size systems,” Phys. Rev. B 96, 094304 (2017).
  * Shu and Yin (2020) Y.-R. Shu and S. Yin, “Short-imaginary-time quantum critical dynamics in the $J-{Q}_{3}$ spin chain,” Phys. Rev. B 102, 104425 (2020).
  * Shu  _et al._ (2022) Y.-R. Shu, S.-K. Jian, and S. Yin, “Nonequilibrium dynamics of deconfined quantum critical point in imaginary time,” Phys. Rev. Lett. 128, 020601 (2022).
  * Shu and Yin (2022) Y.-R. Shu and S. Yin, “Dual dynamic scaling in deconfined quantum criticality,” Phys. Rev. B 105, 104420 (2022).
  * Okano  _et al._ (1997) K. Okano, L. Schülke, K. Yamagishi, and B. Zheng, Nucl. Phys. B 485, 727 (1997).
  * Jaster  _et al._ (1999) A. Jaster, J. Mainville, L. Schülke, and B. Zheng, “Short-time critical dynamics of the three-dimensional ising model,” Journal of Physics A: Mathematical and General 32, 1395 (1999).
  * Domb and Lebowitz (1986) C. Domb and J. L. Lebowitz, eds.,  _Phase Transitions and Critical Phenomena_ , Vol. 10 (Academic Press, 1986).
  * Zhou and Zheng (2007) N. J. Zhou and B. Zheng, “Non-equilibrium critical dynamics with domain interface,” Europhysics Letters (EPL) 78, 56001 (2007).
  * Zhou and Zheng (2008) N. J. Zhou and B. Zheng, “Nonequilibrium critical dynamics with domain wall and surface,” Phys. Rev. E 77, 051104 (2008).
  * Yoshinaga  _et al._ (2022) A. Yoshinaga, H. Hakoshima, T. Imoto, Y. Matsuzaki, and R. Hamazaki, “Emergence of hilbert space fragmentation in ising models with a weak transverse field,” Phys. Rev. Lett. 129, 090602 (2022).
  * Hart and Nandkishore (2022) O. Hart and R. Nandkishore, “Hilbert space shattering and dynamical freezing in the quantum ising model,” arXiv:2203.06188 (2022).
  * Balducci  _et al._ (2022) F. Balducci, A. Gambassi, A. Lerose, A. Scardicchio, and C. Vanoni, “Localization and melting of interfaces in the two-dimensional quantum ising model,” Phys. Rev. Lett. 129, 120601 (2022).
  * Yin  _et al._ (2014b) S. Yin, P. Mai, and F. Zhong, “Universal short-time quantum critical dynamics in imaginary time,” Phys. Rev. B 89, 144115 (2014b).
  * Zhang  _et al._ (2014b) S. Zhang, S. Yin, and F. Zhong, “Generalized dynamic scaling for quantum critical relaxation in imaginary time,” Phys. Rev. E 90, 042104 (2014b).
  * Hohenberg and Halperin (1977) P. C. Hohenberg and B. I. Halperin, “Theory of dynamic critical phenomena,” Rev. Mod. Phys. 49, 435–479 (1977).
  * Sachdev (2011) S. Sachdev,  _Quantum Phase Transitions_ , 2nd ed. (Cambridge Univ. Press, 2011).
  * Sondhi  _et al._ (1997) S. L. Sondhi, S. M. Girvin, J. P. Carini, and D. Shahar, “Continuous quantum phase transitions,” Rev. Mod. Phys. 69, 315–333 (1997).
  * Vojta (2003) M. Vojta, “Quantum phase transitions,” Reports on Progress in Physics 66, 2069–2110 (2003).
  * Sandvik (2010) A. W. Sandvik, “Computational studies of quantum spin systems,” AIP Conference Proceedings 1297, 135–338 (2010).
  * Farhi  _et al._ (2012) E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi, “Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs,” Phys. Rev. A 86, 052334 (2012).


# A Gray Code of Ordered Trees

Shin-ichi Nakano
Gunma University

Abstract A combinatorial Gray code for a set of combinatorial objects is a
sequence of all combinatorial objects in the set so that each object is
derived from the preceding object by changing a small part.

In this paper we design a Gray code for ordered trees with $n$ vertices such
that each ordered tree is derived from the preceding ordered tree by removing
a leaf then appending a leaf elsewhere. Thus the change is just remove-and-
append a leaf, which is the minimum.

##  1 Introduction

A classical Gray code for $n$-bit binary numbers is a sequence of all $n$-bit
binary numbers so that each number is derived from the preceding number by
changing exactly one bit. A combinatorial Gray code for a set of combinatorial
objects is a sequence of all combinatorial objects in the set so that each
object is derived from the preceding object by changing a small (constant)
part.

When we generate all combinatorial objects and the number of such objects is
huge if we can compute them as a combinatorial Gray code then we can output
(or store) each object as a small size of the difference from the preceding
object and we may compute each object in a constant time. Also, when we
repeatedly solve some problem for a class of objects, a solution for an object
may help to compute a solution for a similar successive object. See surveys
for combinatorial Gray codes [6, 4].

For binary trees with $n$ vertices one can generate all binary trees so that
each binary tree is derived from the preceding binary tree by a rotation
operation at a vertex [2, 3]. The number of change of edges in a rotation
operation is three [1, p9]. Also one can generate all binary trees with $n$
vertices so that each tree is derived from the preceding tree by removing a
subtree and place it elsewhere [1, Exercise 25]. However the levels of many
vertices may be changed, where the level of a vertex is the number of vertices
on the path from the vertex to the root.

In this paper we design a Gray code for ordered trees with $n$ vertices such
that each ordered tree is derived from the preceding ordered tree by removing
a leaf then appending a leaf elsewhere. Thus the change is just remove-and-
append a leaf, which is the minimum, and other vertices remain as they were
including their levels. Our Gray code is based on a tree structure among the
ordered trees.

The remainder of this paper is organized as follows. Section 2 gives some
definitions and basic lemmas. In Section 3 we design our algorithm to
construct a Gray code for the ordered trees with $n$ vertices. Finally Section
4 is a conclusion.

##  2 Preliminaries

A tree is a connected graph with no cycle. A rooted tree is a tree with a
designated vertex as the root. The level of a vertex $v$ in a rooted tree is
the number of vertices on the path from $v$ to the root. The level of the root
is $1$. For each vertex $v$ except the root if the neighbor vertex of $v$ on
the path from $v$ to the root is $p$ then $p$ is the parent of $v$ and $v$ is
a child of $p$. The root has no parent. In this paper we always draw each
child vertex below its parent. A vertex with no child is called a leaf. An
ordered tree is a rooted tree in which the left-to-right order of child
vertices of each vertex is defined. The number of ordered trees with exactly
$n+1$ vertices is known as the $n$-th Catalan number ${}_{2n}C_{n}/(n+1)$ [1,
p12].

Given an ordered tree $T$, let $P_{r}(T)=(v_{0},v_{1},\cdots,v_{k})$ be the
path from the root $v_{0}$ to a leaf $v_{k}$ such that, for each
$i=1,2,\cdots,k$, $v_{i}$ is the rightmost child of $v_{i-1}$. $P_{r}(T)$ is
called the rightmost path of $T$ and $v_{k}$ is called the rightmost leaf of
$T$. The number of edges in $P_{r}(T)$ is denoted by $rpl(T)$.

For an ordered tree $T$ if the rightmost child of the root has exactly one
child as a leaf then we say $T$ has the pony-tail.

For two distinct ordered trees $T$ and $T^{\prime}$, if $T^{\prime}$ is
derived from $T$ by appending a new leaf as the rightmost leaf then removing
other leaf, then we say $T$ is copying $T^{\prime}$ (at level
$rpl(T^{\prime})$). When $T$ is copying $T^{\prime}$ if the parent of the
rightmost leaf of $T^{\prime}$ has two or more child vertices then $rpl(T)\geq
rpl(T^{\prime})$ holds, otherwise, the parent of the rightmost leaf of
$T^{\prime}$ has exactly one child vertex, which is the rightmost leaf, and
$rpl(T)=rpl(T^{\prime})-1$ holds. So if $T$ is copying $T^{\prime}$,
$rpl(T)=1$ and $rpl(T^{\prime})>1$ then $T^{\prime}$ has the pony-tail.

Let $S_{k}$ be the set of the ordered trees with exactly $k$ vertices. In this
paper we design, for each $k=1,2,\cdots,n$, a combinatorial Gray code for
$S_{k}$, that is a sequence of all ordered trees in $S_{k}$ such that each
ordered tree is derived from the preceding ordered tree by removing a leaf
then appending a leaf elsewhere. We call the change delete-and-append a leaf.

For an ordered tree $T$ with $n\geq 2$ vertices let $p(T)$ be the ordered tree
derived from $T$ by removing the rightmost leaf. We say $p(T)$ is the parent
of $T$, and $T$ is a child of $p(T)$. For any ordered tree $T$ in $S_{n}$ if
we repeatedly compute the parent of the derived ordered tree we obtain the
sequence $T,p(T),p(p(T)),\cdots$ of ordered trees, which ends with the trivial
ordered tree consisting of exactly one vertex. We call the sequence the
removing sequence of $T$ [5].

Figure 1:  The family tree $F_{n}$ of $S_{n}$.

By merging the removing sequences of the ordered trees in $S_{n}$ one can
obtain an (unordered) tree $F_{n}$ of ordered trees [5] (See an example for
$n=5$ in Fig. 1) in which the root corresponds to the trivial ordered tree
with exactly one vertex, each vertex at level $k$ corresponds to some ordered
tree in $S_{k}$, and each edge corresponds to some ordered tree and its
parent. We call the tree the family tree. Note that we have not decide yet the
left-to-right order of the child ordered trees of each order tree in $F_{n}$.
We have the following three lemmas.

######  Lemma 1.

There is a bijection between the ordered trees in $S_{k}$ and the vertices at
level $k$ in $F_{n}$.

###### Proof.

Given an ordered tree $T$ with exactly $k$ vertices, by repeatedly appending a
new leaf as the rightmost child of the root, one can obtain a descendant tree
$T^{\prime}\in S_{n}$ in $F_{n}$. Thus every order tree in $S_{k}$ appears in
the removing sequence of some tree in $S_{n}$ and so corresponds to a vertex
at level $k$ in $F_{n}$.

Clearly every vertex at level $k$ in $F_{n}$ corresponds to an ordered tree
with exactly $k$ vertices. ∎

Figure 2:  An illustration for Lemma 2.

######  Lemma 2.

Let $T$ be an ordered tree in $S_{k}$ with $k<n$. $T$ has $rpl(T)+1$ child
ordered trees in $F_{n}$.

###### Proof.

For each $i=1,2,\cdots,rpl(T)+1$, by appending a new leaf as the rightmost
child leaf of the vertex on $P_{r}(T)$ at level $i$, one can obtain a distinct
child ordered tree. See Fig.2. ∎

We denote by $C(T,i)$ the child ordered tree of $T$ derived from $T$ by
appending a new leaf as the rightmost child leaf of the vertex on $P_{r}(T)$
at level $i$. Thus $rpl(C(T,i))=i$.

Thus, by Lemma 2, every ordered tree $T$ in $S_{k}$ with $k<n$ except the
ordered tree with exactly one vertex has two or more child ordered trees in
$F_{n}$ since $rpl(T)\geq 1$. Clearly the ordered tree with exactly one vertex
has exactly one child ordered tree in $F_{n}$.

######  Lemma 3.

Any ordered tree is derived from its sibling ordered tree by delete-and-append
a leaf.

###### Proof.

Any ordered tree is derived from its sibling ordered tree by deleting the
rightmost leaf then appending a leaf as the rightmost leaf at the suitable
level. ∎

In this paper we show that by suitably defining the left-to-right order of
child ordered trees of each ordered tree in $F_{n}$, we can define an ordered
tree $F^{O}_{n}$ such that, for each $k$, a Gray code for $S_{k}$ is appeared
as the left-to-right sequence of the ordered trees corresponding to the
vertices at level $k$ of $F^{O}_{n}$. Thus a Gray code for $S_{n}$ is appeared
as the left-to-right sequence of the ordered trees corresponding to the leaves
of $F^{O}_{n}$. See an example for $n=5$ in Fig. 1.

##  3 Algorithm

In this section we design a Gray code for $S_{k}$ for each $k=1,2,\cdots,n$,
where $S_{k}$ is the set of the ordered trees with exactly $k$ vertices.

Induction on levels We proceed by induction on levels. Let $F_{k}$ be the
subtree of $F_{n}$ induced by $S_{1}\cup S_{2}\cup\cdots\cup S_{k}$. The Gray
code for $S_{1}$ is trivial and unique since $|S_{1}|=1$. Simillar for $S_{2}$
since $|S_{2}|=1$. Assume that, for an integer $k<n$, we have defined a left-
to-right order of child ordered trees of each ordered tree in $S_{1}\cup
S_{2}\cup\cdots\cup S_{k-1}$, we have obtained an ordered tree $F^{O}_{k}$
corresponding to $F_{k}$, and we have constructed a Gray code for $S_{k}$ as
the left-to-right sequence of the ordered trees corresponding to the leaves of
$F^{O}_{k}$. Then we are going to define a left-to-right order of child
ordered trees of each ordered tree in $S_{k}$ so that it extends $F^{O}_{k}$
to an ordered tree $F^{O}_{k+1}$ and a Gray code for $S_{k+1}$ is appeared as
the left-to-right sequence of the ordered trees at the leaves of
$F^{O}_{k+1}$.

Basic strategy of algorithm Let ($T_{1},T_{2},\cdots)$ be our Gray code for
$S_{k}$. We are going to define a left-to-right order of child ordered trees
of each $T_{i}$ in $S_{k}$, then we obtain a sequence of ordered trees, which
is a Gray code for $S_{k+1}$, say $(T^{\prime}_{1},T^{\prime}_{2},\cdots)$.

If two consecutive ordered trees $T^{\prime}_{j}$ and $T^{\prime}_{j+1}$ in
the sequence are siblings in $F^{O}_{k+1}$, then one can be derived from the
other by delete-and-append a leaf by Lemma 3. However if two consecutive
ordered trees $T^{\prime}_{j}$ and $T^{\prime}_{j+1}$ are not siblings in
$F^{O}_{k+1}$, that is, $T^{\prime}_{j}$ is the rightmost child ordered tree
of $T_{i}$ and $T^{\prime}_{j+1}$ is the leftmost child ordered tree of
$T_{i+1}$ for some $i$, then we have several cases to consider. We have the
following lemma for $T_{i}$ and $T_{i+1}$.

Figure 3:  Illustration for Lemma 4.

######  Lemma 4.

Assume that $T_{i}$ can be derived from $T_{i+1}$ by delete-and-append a leaf.
Then the followings are hold.

  1. (a)

$C(T_{i},1)$ can be derived from $C(T_{i+1},1)$ by delete-and-append a leaf.

  2. (b)

If $rpl(T_{i})=rpl(T_{i+1})=1$, then $C(T_{i},2)$ can be derived from
$C(T_{i+1},2)$ by delete-and-append a leaf.

  3. (c)

If $rpl(T_{i})$ has the pony-tail, $rpl(T_{i+1})=1$, $T_{i}$ is copying
$T_{i+1}$ at level $1$ and $T_{i+1}$ is copying $T_{i}$ at level $2$, then
$C(T_{i},2)$ can be derived from $C(T_{i+1},2)$ by delete-and-append a leaf.

  4. (d)

If $rpl(T_{i})=1$, $rpl(T_{i+1})>1$, and $T_{i+1}$ has no pony-tail (so
$T_{i+1}$ is copying $T_{i}$ at level $1$), then $C(T_{i},2)$ can not be
derived from $C(T_{i+1},2)$ by delete-and-append a leaf (See Fig.3 (d1) and
(d3)), however $C(T_{i},2)$ can be derived from $C(T_{i+1},1)$ by delete-and-
append a leaf. (See Fig.3 (d2) and (d4).)

  5. (e)

If $rpl(T_{i})=1$, $rpl(T_{i+1})>1$, $T_{i+1}$ has the pony-tail, and $T_{i}$
is copying $T_{i+1}$ at level $2$, then $C(T_{i},2)$ can be derived from
$C(T_{i+1},2)$ by delete-and-append a leaf. (See Fig. 3 (e).)

  6. (e’)

If $rpl(T_{i})>1$, $rpl(T_{i+1})=1$, $T_{i}$ has the pony-tail, and $T_{i+1}$
is copying $T_{i}$ at level $2$, then $C(T_{i+1},2)$ can be derived from
$C(T_{i},2)$ by delete-and-append a leaf.

  7. (f)

If $rpl(T_{i})=1$, $rpl(T_{i+1})>1$, $T_{i+1}$ has the pony-tail, $T_{i+1}$ is
copying $T_{i}$ at level $1$, then $C(T_{i},2)$ can not be derived from
$C(T_{i+1},2)$ by delete-and-append a leaf (See Fig.3 (f1)), however
$C(T_{i},2)$ can be derived from $C(T_{i+1},1)$ by delete-and-append a leaf.
(See Fig.3 (f2).)

  8. (g)

If $rpl(T_{i})\geq rpl(T_{i+1})\geq 2$, then $C(T_{i},rpl(T_{i+1}))$ can be
derived from $C(T_{i+1},rpl(T_{i+1}))$ by delete-and-append a leaf. (See Fig.3
(g).)

If $rpl(T_{i})=rpl(T_{i+1})\geq 2$, then $C(T_{i},rpl(T_{i}))$ can be derived
from $C(T_{i+1},rpl(T_{i}))$ by delete-and-append a leaf, and
$C(T_{i},rpl(T_{i})+1)$ can be derived from $C(T_{i+1},rpl(T_{i})+1)$ by
delete-and-append a leaf.

  9. (g’)

If $rpl(T_{i+1})\geq rpl(T_{i})\geq 2$, then $C(T_{i+1},rpl(T_{i}))$ can be
derived from $C(T_{i},rpl(T_{i}))$. Also if $rpl(T_{i+1})>rpl(T_{i})\geq 2$,
then $C(T_{i},1)$ can be derived from $C(T_{i+1},rpl(T_{i}))$ by delete-and-
append a leaf.

###### Proof.

(a) (b) We have the following two cases. Case 1: $T_{i}$ is derived from
$T_{i+1}$ by removing the rightmost leaf then appending a new leaf elsewhere.
Case 2: $T_{i}$ is derived from $T_{i+1}$ by removing a leaf which is not the
rightmost leaf then appending a new leaf elsewhere. For both cases the claim
holds.

(c) Assume that $T_{i+1}$ is derived from $T_{i}$ by appending the rightmost
leaf at level $1$ then deleting a leaf $v$ (since $T_{i}$ is copying
$T_{i+1}$), and $T_{i}$ is derived from $T_{i+1}$ by appending the rightmost
leaf at level $2$ then deleting a leaf $v^{\prime}$ (since $T_{i+1}$ is
copying $T_{i}$).

We can show that exactly one of $v$ or $v^{\prime}$ is a child of the root, as
follows. If $v$ is a child of the root of $T_{i}$ and $v^{\prime}$ is a child
of the root of $T_{i+1}$ then, since $T_{i}$ is copying $T_{i+1}$, the degree
of the root of $T_{i}$ is equal to the degree of the root of $T_{i+1}$, and,
since $T_{i+1}$ is copying $T_{i}$, the degree of the root of $T_{i+1}$ minus
$1$ is equal to the degree of the root of $T_{i}$, a contradiction. Also if
$v$ is not a child of the root of $T_{i}$ and $v^{\prime}$ is not a child of
the root of $T_{i+1}$ then, since $T_{i}$ is copying $T_{i+1}$, the degree of
the root of $T_{i}$ plus $1$ is equal to the degree of the root of $T_{i+1}$,
and, since $T_{i+1}$ is copying $T_{i}$, the degree of the root of $T_{i+1}$
is the degree of the root of $T_{i}$, a contradiction. Thus exactly one of $v$
or $v^{\prime}$ is a child of the root.

Assume first that $v$ is a child of the root of $T_{i}$. Let
$x_{1},x_{2},\cdots,x_{d}$ be the child vertices of the root in $T_{i}$ except
$v$ in right-to-left order, and $y_{1},y_{2},\cdots,y_{d+1}$ the child
vertices of the root in $T_{i+1}$ in right-to-left order. Since $T_{i}$ is
copying $T_{i+1}$, after removing $v$ from $T_{i}$, the subtrees rooted at
$x_{1},x_{2},\cdots,x_{d}$ are identical to the subtrees rooted at
$y_{2},y_{3},\cdots,y_{d+1}$, respectively. Also since $T_{i+1}$ is copying
$T_{i}$, after removing $v^{\prime}$ from $T_{i+1}$, the subtrees rooted at
$y_{2},y_{3},\cdots,y_{d+1}$ except one (corresponding to the trivial subtree
rooted at $v$) are identical to the subtrees rooted at
$x_{2},x_{3},\cdots,x_{d}$, respectively. If $v^{\prime}$ belong to a subtree
rooted at, say $y_{j}$, then, since $T_{i}$ is copying $T_{i+1}$, the subtree
rooted at $x_{j-1}$ is identical to the subtree rooted at $y_{j}$ and also,
since $T_{i+1}$ is copying $T_{i}$, after removing $v^{\prime}$ from the
subtree rooted at $y_{j}$, if it is identical to the subtree rooted at
$x_{j-1}$, then, a contradiction. Thus $v^{\prime}$ belong to the subtree
corresponding to the subtree rooted at $v$, that is $v^{\prime}$ is the only
child of a child (corresponding to $v$) of the root. See Fig.3 (c). Now
$C(T_{i},2)$ is derived from $C(T_{i+1},2)$ by delete-and-append a leaf.

Simillar for the case where $v^{\prime}$ is a child of the root of $T_{i+1}$.

(d) Since $T_{i+1}$ has no pony-tail, either (Case 1) the rightmost child
vertex of the root of $T_{i+1}$ has two or more child vertices (See Fig.3
(d1)), or (Case 2) the rightmost child vertex of the rightmost child vertex of
the root of $T_{i+1}$ has one or more child vertices (See Fig.3 (d3)). Since
$rpl(T_{i})=1$ the rightmost child vertex of the root of $T_{i}$ has no child
vertex. For Case 1, the rightmost child vertex of the root of $C(T_{i+1},2)$
has three or more child vertices, while the rightmost child vertex of the root
of $C(T_{i},2)$ has exactly one child vertex. Thus $C(T_{i},2)$ can not be
derived from $C(T_{i+1},2)$ by delete-and-append a leaf. See Fig.3 (d1). For
Case 2 we need to remove at least two vertices and append at least two
vertices to obtain $C(T_{i},2)$ from $C(T_{i+1},2)$. Thus $C(T_{i},2)$ can not
be derived from $C(T_{i+1},2)$ by delete-and-append a leaf. See Fig.3 (d3).
However $C(T_{i},2)$ can be derived from $C(T_{i+1},1)$ by delete-and-append a
leaf. See Fig.3 (d2) and (d4).

(e) See Fig.4 (e).

(e’) Similar to (e).

(f) See Fig.3 (f1) and (f2).

(g) See Fig.3 (g).

(g’) Similar to (g). ∎

Step of algorithm Let $(T_{1},T_{2},\cdots)$ be a Gray code for $S_{k}$
corresponding to the leaves of $F^{O}_{k}$ and we are going to define a left-
to-right order of child ordered trees of each ordered tree in $S_{k}$ and
construct a Gray code $(T^{\prime}_{1},T^{\prime}_{2},\cdots)$ for $S_{k+1}$
corresponding to the leaves of $F^{O}_{k+1}$. When we start step $i$ assume
that we have already defined the left-to-right order of the child ordered
trees of $T_{1},T_{2},\cdots,T_{i-1}$ and the leftmost child ordered tree of
$T_{i}$, and in step $i$ we are going to define the left-to-right order of the
child ordered trees of $T_{i}$ except the leftmost one, and the leftmost child
ordered trees of $T_{i+1}$. See Fig.4. The part we are going to define in the
current step $i$ is depicted as a grey rectangle. We proceed with several
cases based on $rpl(T_{i}),rpl(T_{i+1})$ and the leftmost child of $T_{i}$, as
explained later.

Figure 4:  An illustration for step $i$ of the algorithm.

Loop invariants

Our algorithm satisfies the following two conditions at each step $i$. (Note
that (co1) is independent of $i$.)

  1. (co1)

For consecutive three ordered trees $T_{u-1},T_{u},T_{u+1}$ at level $k$, if
$rpl(T_{u-1})=rpl(T_{u+1})=1$ and $rpl(T_{u})>1$ then $T_{u}$ has the pony-
tail and $T_{u+1}$ is copying $T_{u}$ at level $2$. Also if
$rpl(T_{u-1})=rpl(T_{u+1})\geq 2$ then $rpl(T_{u-1})>rpl(T_{u})$.

  2. (co2)

For consecutive three ordered trees
$T^{\prime}_{u^{\prime}-1},T^{\prime}_{u^{\prime}},T^{\prime}_{u^{\prime}+1}$
at level $k+1$ with $u^{\prime}+1\leq i^{\prime}$, where
$T^{\prime}_{i^{\prime}}$ is the leftmost child ordered tree of $T_{i}$, if
$rpl(T^{\prime}_{u^{\prime}-1})=rpl(T^{\prime}_{u^{\prime}+1})=1$ and
$rpl(T^{\prime}_{u^{\prime}})>1$ then $T^{\prime}_{u^{\prime}}$ has the pony-
tail and $T^{\prime}_{u+1}$ is copying $T^{\prime}_{u}$ at level $2$. Also if
$rpl(T^{\prime}_{u^{\prime}-1})=rpl(T^{\prime}_{u^{\prime}+1})\geq 2$ then
$rpl(T^{\prime}_{u^{\prime}-1})>rpl(T_{u}^{\prime})$.

Figure 5:  Illustrations for the loop invariants.

The intuitive reason why we need those condition is as follows.

Assume that there are $T_{u-1},T_{u},T_{u+1}$ with
$rpl(T_{u-1})=rpl(T_{u+1})=1$, $rpl(T_{u})>1$, $T_{u}$ has no pony-tail, and
$C(T_{u},1)$ is the leftmost child of $T_{u}$ (see Fig.5(a)), and if we try to
set $C(T_{u},1)$ at the rightmost child of $T_{u}$, then we fail to construct
a Gray code for $S_{k+1}$ since the same tree appear twice. (See Fig.5(b).) So
our algorithm try to exclude any occurrence of such consecutive three ordered
trees. Note that even when $rpl(T_{u-1})=rll(T_{u+1})=1$, $rpl(T_{u})>1$ and
$C(T_{u},1)$ is the leftmost child of $T_{u}$, if $T_{u}$ has the pony-tail
and $T_{u+1}$ is copying $T_{u}$ (see Fig.5(c)), then we can set $C(T_{u},2)$
at the rightmost child of $T_{i}$ and $C(T_{u+1},2)$ at the leftmost child of
$T_{i+1}$ (by Lemma 4(e’)) and we can proceed successfully. (See an example in
Fig.5(d).)

Algorithm First we set $C(T_{1},1)$ as the leftmost child of $T_{1}$.

Assume that we have done each step $1,2,\cdots,i-1$. Now we execute the next
step $i$ of our algorithm if $T_{i+1}$ exists. (If $T_{i}$ is the last ordered
tree in the Gray code of $S_{k}$ then we order the remaining child of $T_{i}$
with decreasing order of $rpl$ from left to right. See Fig. 1. Note that if
$rpl(T_{i})\geq 3$ then $C(T_{i},1)$ never appear at the second leftmost child
of $T_{i}$.)

We have the following four cases for step $i$.

Case 1: $rpl(T_{i})=1$ and $rpl(T_{i+1})=1$.

Case 1a: If $C(T_{i},1)$ is the leftmost child of $T_{i}$ then we set
$C(T_{i},2)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},2)$ as the
lefttmost child of $T_{i+1}$ (by Lemma 4(b)).

Case 1b: Otherwise, $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we
set $C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
lefttmost child of $T_{i+1}$ (by Lemma 4(a)).

Case 2: $rpl(T_{i})=1$ and $rpl(T_{i+1})>1$.

We have two subcases.

Case 2a: $T_{i+1}$ has no pony-tail. (So $T_{i+1}$ is copying $T_{i}$.)

Case 2a1: If $C(T_{i},1)$ is the leftmost child of $T_{i}$ then we set
$C(T_{i},2)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(d)).

Case 2a2: If $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we set
$C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(a)).

Case 2b: $T_{i+1}$ has the pony-tail and $T_{i}$ is copying $T_{i+1}$.

Case 2b1: If $C(T_{i},1)$ is the leftmost child of $T_{i}$ then we set
$C(T_{i},2)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},2)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(e)).

Case 2b2: If $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we set
$C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(a)).

Case 2c: $T_{i+1}$ has the pony-tail and $T_{i+1}$ is copying $T_{i}$.

Case 2c1: If $C(T_{i},1)$ is the leftmost child of $T_{i}$ then we set
$C(T_{i},2)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(f)).

Case 2c2: If $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we set
$C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(a)).

Case 3: $rpl(T_{i})>1$ and $rpl(T_{i+1})=1$.

We have two subcases.

Case 3a: $T_{i}$ has no pony-tail. (So $T_{i}$ is copying $T_{i+1}$.)

Case 3a1: If $C(T_{i},1)$ is the leftmost child of $T_{i}$ then we can prove
that this case never occur, as follows.

We have set $C(T_{i},1)$ as the leftmost child of $T_{i}$ with $rpl(T_{i})>1$
in the preceding step of either Case 2a1, 2a2, 2b2, 2c1 or 2c2. In those cases
$rpl(T_{i-1})=1$ holds, and in Case 3a1 $rpl(T_{i})>1$ and $rpl(T_{i+1})=1$
hold and $T_{i}$ has no pony-tail. This contradicts to (co1).

Case 3a2: If $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we set
$C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(a)). Set other child ordered trees of
$T_{i}$ between the leftmost child and the rightmost child with decreasing
order of $rpl$ from left to right.

Case 3b: $T_{i}$ has the pony-tail and $T_{i+1}$ is copying $T_{i}$.

Case 3b1: If $C(T_{i},1)$ is the leftmost child of $T_{i}$ then we set
$C(T_{i},2)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},2)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(e’)). Set the remaining child
$C(T_{i},3)$ of $T_{i}$ as the middle child of $T_{i}$.

Case 3b2: If $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we set
$C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(a)). Set the remaining child as the
middle child of $T_{i}$.

Case 3c: $T_{i}$ has the pony-tail and $T_{i}$ is copying $T_{i+1}$.

Case 3c1: $C(T_{i},1)$ is the leftmost child of $T_{i}$. If $T_{i+1}$ is also
copying $T_{i}$ then we set $C(T_{i},2)$ as the rightmost child of $T_{i}$ and
$C(T_{i+1},2)$ as the leftmost child of $T_{i+1}$ (by Lemma 4(c)) and set the
remaining child as the middle child of $T_{i}$. Otherwise one can prove that
this case never occur. Similar to Case 3a1.

Case 3c2: If $C(T_{i},1)$ is not the leftmost child of $T_{i}$ then we set
$C(T_{i},1)$ as the rightmost child of $T_{i}$ and $C(T_{i+1},1)$ as the
leftmost child of $T_{i+1}$ (by Lemma 4(a)). Set the remaining child as the
middle child of $T_{i}$

Case 4: $rpl(T_{i})>1$ and $rpl(T_{i+1})>1$.

Case 4a: $C(T_{i},1)$ is the leftmost child of $T_{i}$.

Case 4a1: $rpl(T_{i})\leq rpl(T_{i+1})$.

We set $C(T_{i},rpl(T_{i}))$ as the rightmost child of $T_{i}$ and
$C(T_{i+1},rpl(T_{i}))$ as the leftmost child of $T_{i+1}$ (by Lemma 4(g’)).

Set other child ordered trees of $T_{i}$ between the leftmost child
$C(T_{i},1)$ and the rightmost child $C(T_{i},rpl(T_{i}))$ with increasing
order of $rpl$ from left to right.

Case 4a2: $rpl(T_{i})>rpl(T_{i+1})$.

We set $C(T_{i},rpl(T_{i+1}))$ as the rightmost child of $T_{i}$ and
$C(T_{i+1},rpl(T_{i+1}))$ as the leftmost child of $T_{i+1}$ (by Lemma 4(g)).

Set other child ordered trees of $T_{i}$ between the leftmost child
$C(T_{i},1)$ and the rightmost child $C(T_{i},rpl(T_{i+1}))$ with increasing
order of $rpl$ from left to right.

Case 4b: $C(T_{i},1)$ is not the leftmost child of $T_{i}$.

Let $T$ be the leftmost child of $T_{i}$.

Case 4b1: $rpl(T_{i})\leq rpl(T_{i+1})$.

If $rpl(T_{i})<rpl(T_{i+1})$ then we set $C(T_{i},1)$ as the rightmost child
of $T_{i}$ and $C(T_{i+1},rpl(T_{i}))$ as the leftmost child of $T_{i+1}$ (by
Lemma 4(g’)).

Otherwise $rpl(T_{i})=rpl(T_{i+1})$ holds. If $rpl(T)=rpl(T_{i})$ then we set
$C(T_{i},rpl(T_{i})+1)$ as the rightmost child of $T_{i}$ and
$C(T_{i+1},rpl(T_{i})+1)$ as the leftmost child of $T_{i+1}$, and if
$rpl(T)\neq rpl(T_{i})$ then we set $C(T_{i},rpl(T_{i}))$ as the rightmost
child of $T_{i}$ and $C(T_{i+1},rpl(T_{i}))$ as the leftmost child of
$T_{i+1}$ (by Lemma 4(g)).

Set other child ordered trees of $T_{i}$ between the leftmost child and the
rightmost child with decreasing order of $rpl$ from left to right. (Note that
if $rpl(T_{i})\geq 3$ then $C(T_{i},1)$ never appear at the second leftmost
child of $T_{i}$.)

Case 4b2: $rpl(T_{i})>rpl(T_{i+1})$ and $rpl(T)\neq rpl(T_{i+1})$.

We set $C(T_{i},rpl(T_{i+1}))$ as the rightmost child of $T_{i}$ and
$C(T_{i+1},rpl(T_{i+1}))$ as the leftmost child of $T_{i+1}$ (by Lemma 4(g)).
Set other child ordered trees of $T_{i}$ between the leftmost child and the
rightmost child with decreasing order of $rpl$ from left to right. (Note that
$C(T_{i},1)$ never appear at the second leftmost child of $T_{i}$ since
$rpl(T_{i})\geq 3$ holds.)

Case 4b3: $rpl(T_{i})>rpl(T_{i+1})$ and $rpl(T)=rpl(T_{i+1})$.

We show this case never occur in the lemma below.

The description of the four cases for step $i$ is completed.

We have the following three lemmas.

######  Lemma 5.

Case 4b3 never occur.

###### Proof.

Assume for a contradiction that the case occurs. (In Case 4b we have defined
$T$ as the leftmost child of $T_{i}$.)

If $rpl(T)>2$, then we have set $T$ in Case 4 of the preceding setp $i-1$. If
$rpl(T_{i-1})\leq rpl(T_{i})$ and we set $C(T_{i},rpl(T_{i-1}))$ as $T$ in
either Case 4a1 or Case 4b1, then
$rpl(T_{i-1})=rpl(T)=rpl(T_{i+1})<rpl(T_{i})$ holds, which contradicts to
(co1). Otherwise if $rpl(T_{i-1})=rpl(T_{i})$ and we set $C(T_{i},rpl(T_{i}))$
or $C(T_{i},rpl(T_{i})+1)$ as $T$ in Case 4b1, then it contradict to the
condition $rpl(T_{i})>rpl(T_{i+1})$ and $rpl(T)=rpl(T_{i+1})$ of Case 4b3.
Otherwise, $rpl(T_{i-1})>rpl(T_{i})$ holds, then we set $C(T_{i},rpl(T_{i}))$
as $T$ in either Case 4a2 or Case 4b2, so $rpl(T)=rpl(T_{i})$ holds, which
contradicts to Case 4b3.

If $rpl(T)=2$, then we set $T$ in either Case 2b1, 4a1, 4a2, 4b1 or 4b2 of the
preceding step $i-1$. If we set $T$ in Case 2b1 then $T_{i}$ has the pony-tail
and $rpl(T_{i})=2$, which contradicts to $rpl(T_{i})>rpl(T_{i+1})>1$. If we
set $T$ in Case 4a1 or Case 4b1 then
$rpl(T_{i-1})=rpl(T)=rpl(T_{i+1})<rpl(T_{i})$, which contradicts to (co1). If
we set $T$ in either Case 4a2 or Case 4b2 then
$rpl(T_{i-1})>rpl(T_{i})=rpl(T)$ which contradicts to Case 4b3. ∎

######  Lemma 6.

(a) If $rpl(T)=1$, $T^{\prime}$ has no pony-tail and $T^{\prime}$ is copying
$T$, then $C(T^{\prime},1)$ is copying $C(T,2)$.

(b) If $rpl(T)=1$, $T^{\prime}$ has the pony-tail and $T^{\prime}$ is copying
$T$, then $C(T^{\prime},1)$ is copying $C(T,2)$.

###### Proof.

(Sketch.) See Fig. 6. ∎

We need above lemma in the proof of the next lemma.

Figure 6:  Illustrations for Lemma 6.

######  Lemma 7.

Assume that (co1) is satisfied. If (co2) is satisfied for $i=1,2,\cdots,s$
then, after executing step $i=s$, (co2) is satisfied for $i=s+1$.

###### Proof.

First part of (co2) We have the following three cases to consider. For each
case we can prove (co2) is satisfied for $i=s+1$, as follows.

Case 1: $T^{\prime}_{u^{\prime}-1}$ is the rightmost child of $T_{s-1}$,
$T^{\prime}_{u^{\prime}}$ is the lefhtmost child of $T_{s}$ and
$T^{\prime}_{u^{\prime}+1}$ is the second lefhtmost child of $T_{s}$.

If those three ordered trees violate (co2) then
$rpl(T^{\prime}_{u^{\prime}-1})=rpl(T^{\prime}_{u^{\prime}+1})=1<rpl(T^{\prime}_{u^{\prime}})$
holds.

Only Case 4b1 with $rpl(T_{s-1})<rpl(T_{s})$ sets $T^{\prime}_{u^{\prime}-1}$
and $T^{\prime}_{u^{\prime}}$ so that
$rpl(T^{\prime}_{u^{\prime}-1})=1<rpl(T^{\prime}_{u^{\prime}})$. If so
$rpl(T_{s})\geq 3$ holds. However no case set (the second leftmost child of
$T_{s}$) $T^{\prime}_{u^{\prime}+1}$ with $rpl(T^{\prime}_{u^{\prime}+1})=1$
since if $rpl(T_{s})\geq 3$ then no case set $C(T_{s},1)$ as the second
leftmost child of $T_{s}$. Thus (co2) is satisfied.

Case 2: $T^{\prime}_{u^{\prime}-1}$, $T^{\prime}_{u^{\prime}}$ and
$T^{\prime}_{u^{\prime}+1}$ are children of $T_{s}$.

Those three ordered trees never violate (co2) since they are children of
$T_{s}$ and have distinct $rpl$’s.

Case 3: $T^{\prime}_{u^{\prime}-1}$ is the second rightmost child of
$T_{s-1}$, $T^{\prime}_{u^{\prime}}$ is the rightmost child of $T_{s-1}$ and
$T^{\prime}_{u^{\prime}+1}$ is the leftmost child of $T_{s}$.

If those three ordered trees violate (co2) then
$rpl(T^{\prime}_{u^{\prime}-1})=rpl(T^{\prime}_{u^{\prime}+1})=1<rpl(T^{\prime}_{u^{\prime}})$
holds. This occurs only when we set $T^{\prime}_{u^{\prime}}$ and
$T^{\prime}_{u^{\prime}+1}$ in either Case 2a1 or Case 2c1. For those cases
$rpl(T_{s-1})=1$ holds, and
$rpl(T^{\prime}_{u^{\prime}-1})=rpl(T^{\prime}_{u^{\prime}+1})=1$,
$T^{\prime}_{u^{\prime}}$ has the pony-tail and $T^{\prime}_{u^{\prime}+1}$ is
copying $T^{\prime}_{u^{\prime}}$ by Lemma 6(a) and (b). Thus (co2) is
satisfied.

Second part of (co2) If $T^{\prime}_{u^{\prime}-1},T^{\prime}_{u^{\prime}}$
and $T^{\prime}_{u^{\prime}+1}$ are siblings, since each child ordered tree
has a distinct $rpl$, the claim is satisfied. So assume otherwise, that is
$T^{\prime}_{u^{\prime}-1}$ and $T^{\prime}_{u^{\prime}+1}$ are not siblings.
We have the following two cases.

Case 1: $T^{\prime}_{u^{\prime}}$ and $T^{\prime}_{u^{\prime}+1}$ are not
siblings.

Now $T^{\prime}_{u^{\prime}-1}$ and $T^{\prime}_{u^{\prime}}$ are siblings. If
$T^{\prime}_{u^{\prime}-1},T^{\prime}_{u^{\prime}},T^{\prime}_{u^{\prime}+1}$
violate (co2) then $2\leq
rpl(T^{\prime}_{u^{\prime}-1})<rpl(T^{\prime}_{u^{\prime}})$ and
$rpl(T^{\prime}_{u^{\prime}})>rpl(T^{\prime}_{u^{\prime}+1})\geq 2$ hold. No
case set $T^{\prime}_{u^{\prime}}$ and $T^{\prime}_{u^{\prime}+1}$ with
$rpl(T^{\prime}_{u^{\prime}})>rpl(T^{\prime}_{u^{\prime}+1})\geq 2$. Thus this
case never occur.

Case 2: $T^{\prime}_{u^{\prime}-1}$ and $T^{\prime}_{u^{\prime}}$ are not
siblings.

Now $T^{\prime}_{u^{\prime}}$ and $T^{\prime}_{u^{\prime}+1}$ are siblings. If
$T^{\prime}_{u^{\prime}-1},T^{\prime}_{u^{\prime}},T^{\prime}_{u^{\prime}+1}$
violate (co2) then $2\leq
rpl(T^{\prime}_{u^{\prime}+1})<rpl(T^{\prime}_{u^{\prime}})$ and
$rpl(T^{\prime}_{u^{\prime}})>rpl(T^{\prime}_{u^{\prime}-1})\geq 2$ hold. No
case set $T^{\prime}_{u^{\prime}-1}$ and $T^{\prime}_{u^{\prime}}$ with
$rpl(T^{\prime}_{u^{\prime}})>rpl(T^{\prime}_{u^{\prime}-1})\geq 2$. Thus this
case never occur. ∎

Now we have the following theorem.

######  Theorem 8.

There is a Gray code for ordered trees with $n$ vertices such that each
ordered tree is derived from the preceding ordered tree by removing a leaf
then appending a leaf.

By constructing the necessary part of $F^{O}_{n}$ on the fly one can generate
each ordered tree in a Gray code for $S_{n}$ in $O(n^{2})$ time for each
ordered tree.

##  4 Conclusion

In this paper we have designed a Gray code for ordered trees with $n$ vertices
such that each ordered tree is derived from the preceding ordered tree by
removing a leaf then appending a leaf.

Can we design a Gray code for binary trees with $n$ vertices such that each
binary tree is derived from the preceding binary tree by removing a leaf then
appending a leaf?

## References

  * [1] Donald E. Knuth.  The Art of Computer Programming, Volume 4, Generating All Trees, History of Combinatorial Generation.  Addison-Wesley, 2006.
  * [2] Joan M. Lucas.  The rotation graph of binary trees is hamiltonian.  J. Algorithms, 8(4):503–535, 1987.
  * [3] Joan M. Lucas, Dominique Roelants van Baronaigien, and Frank Ruskey.  On rotations and the generation of binary trees.  J. Algorithms, 15(3):343–366, 1993.
  * [4] Torsten Mütze.  Combinatorial gray codes - an updated survey.  CoRR, abs/2202.01280, 2022.
  * [5] Shin-Ichi Nakano.  Efficient generation of plane trees.  Inf. Process. Lett., 84(3):167–172, 2002.
  * [6] Carla D. Savage.  A survey of combinatorial gray codes.  SIAM Rev., 39(4):605–629, 1997.