# Thermalization in the Lenard-Jones gas

Rauoof Wani  Indian Institute of Technology Jammu, Department of Physics,
Jammu, 181221, India  Vimal Kumar  Department of Physics, Indian Institute of
Technology Kanpur, Kanpur, 208016, India  Mahendra Verma  Department of
Physics, Indian Institute of Technology Kanpur, Kanpur, 208016, India  Sanat
Tiwari<EMAIL_ADDRESS>Indian Institute of Technology Jammu,
Department of Physics, Jammu, 181221, India

###### Abstract

In this letter, using energy transfers, we demonstrate a route to
thermalization in an isolated ensemble of realistic gas particles. We
performed a grid-free classical molecular dynamics simulation of two-
dimensional Lenard-Jones gas. We start our simulation with a large-scale
vortex akin to a hydrodynamic flow and study its non-equilibrium behavior till
it attains thermal equilibrium. In the intermediate phases, small wavenumbers
($k$) exhibit $E(k)\propto k^{-3}$ kinetic energy spectrum whereas large
wavenumbers exhibit $E(k)\propto k$ spectrum. Asymptotically, $E(k)\propto k$
for the whole range of $k$, thus indicating thermalization. These results are
akin to those of Euler turbulence despite complex collisions and interactions
among the particles.

A system with billions of randomly colliding spheres forms a Boltzmann gas
(Huang, 2008). A Lenard-Jones (LJ) gas with particles interacting through the
short-range LJ potential is a realization of the Boltzmann gas. These systems
provide the platform for studying the classical kinetic theory (Bellomo and
Schiavo, 1997), statistical mechanics, and thermodynamics (Reif, 1965;
Goldstein, 2001). According to the kinetic theory, these systems reach
equilibrium after a sufficiently long time (several collision timescales),
whose behaviour is described by thermodynamic laws (Grad, 1958; Loeb, 2004).
We report the energy transfers and thermalization characteristics in a
realistic fluid modeled using LJ gas.

A realistic fluid, which is composed of a large number of particles, exhibits
a variety of hydrodynamic structures like waves, shear, and vortices at a
macroscopic scale. The properties and dynamics of such structures are
described by either Navier-Stokes or Euler equations. At present, significant
research is focused on a comprehensive understanding of the dynamics of real
fluids from microscopic scales to hydrodynamic scales (Gallis  _et al._ ,
2017; Bell  _et al._ , 2022; Bandak  _et al._ , 2022; McMullen  _et al._ ,
2022). This research is of paramount importance to nano- and microfluidics,
plasma turbulence, astrophysical turbulence, quantum turbulence, etc. In this
letter, we explore the full range of length scales of the two-dimensional (2D)
LJ gas using molecular dynamics (MD) simulation. We study the evolution of a
large hydrodynamic vortex superposed on a thermal background in an isolated
system with total energy conserved. We report thermalization in a manner
similar to three-dimensional (3D) Euler turbulence Cichowlas  _et al._
(2005a).

Euler turbulence is studied using an inviscid, incompressible fluid equation
given as:

${\partial_{t}}{\bf u}+{\bf u\cdot\nabla u}=-\nabla p;~{}~{}~{}{\bf\nabla\cdot
u}=0,$ (1)

where ${\bf u},p$ are the velocity and pressure fields respectively. An Euler
flow conserves total kinetic energy ($\int d{\bf x}u^{2}/2$). In addition, 2D
and 3D Euler equations conserve, respectively, the total enstrophy ($\int
d{\bf x}\omega^{2}/2$) and total kinetic helicity ($\int d{\bf x}({\bf
u}\cdot\boldsymbol{\omega})$), where $\boldsymbol{\omega}=\nabla\times{\bf
u}$. Lee (1952) and Kraichnan (1973a) showed that Euler turbulence admits
equilibrium solutions that exhibit approximately $k^{2}$ energy spectrum for
3D and $k$ energy spectrum for 2D (also see Onsager (1949)).

For the 3D Euler turbulence, Cichowlas  _et al._ (2005a) showed the Taylor-
Green vortex evolves to $k^{-5/3}$ spectrum with positive energy flux at the
small and intermediate wavenumbers, and $k^{2}$ spectrum with zero energy flux
at large wavenumbers. Eventually, the system thermalizes and exhibits $k^{2}$
spectrum for all wavenumbers. Note that $k^{-5/3}$ spectrum and constant
energy flux are the predictions by Kolmogorov Kolmogorov (1941a, b); Frisch
(1995) for fully-developed hydrodynamic turbulence. Gross-Pitaevskii equation
and quantum turbulence too exhibit similar behavior as Euler turbulence (Davis
_et al._ , 2001; Proment  _et al._ , 2009; Barenghi  _et al._ , 2014).

Bell  _et al._ (2022) and Bandak  _et al._ (2022) studied 3D Navier-Stokes
equation coupled with fluctuating hydrodynamics. They showed that such systems
exhibit Kolmogorov’s $k^{-5/3}$ energy spectrum in the inertial range.
However, the dissipation range spectrum starts with $\exp(-k\eta)$, and then
it transitions to the $k^{2}$ energy spectrum midway, which corresponds to a
thermalized region. Betchov (1957) reported a similar crossover to the $k^{2}$
spectrum in his experiment on a turbulent jet.

Some researchers support equilibrium behaviour of two-dimensional Euler
turbulence (Robert and Sommeria, 1991; Kraichnan, 1973b; Lee, 1952; Onsager,
1949), while others argue for its non-equilibrium behaviour (Pakter and Levin,
2018; Bouchet and Simonnet, 2009; Seyler  _et al._ , 1975; Verma and
Chatterjee, 2022). Further, the initial condition of 2D Euler turbulence
affects the asymptotic states considerably; some states are in equilibrium,
but many of them are out of equilibrium. (Bouchet and Simonnet, 2009; Bouchet
and Venaille, 2012; Verma  _et al._ , 2020; Verma and Chatterjee, 2022). In
the present work, we show that a 2D LJ gas with a large-vortex thermalizes.

Kinetic approaches such as the Lattice Boltzmann Method (LBM) (Martinez  _et
al._ , 1994; Chen and Doolen, 1998), the Direct Simulation Monte Carlo (DSMC)
(Bird, 1976; Gallis  _et al._ , 2017; McMullen  _et al._ , 2022) and MD
simulations (Kadau  _et al._ , 2004; Ashwin and Sen, 2015; Wani  _et al._ ,
2022) have been employed to study flows, instabilities, and turbulence in
fluids. Gallis  _et al._ (2017) simulated 3D decaying turbulence using DSMC
and showed the spectrum to be a combination of $k^{-5/3}$ and exponential
components, as observed for the Navier-Stokes equation. McMullen  _et al._
(2022) further observed an energy spectrum with $k^{-5/3}$ and $k^{2}$
components, similar to fluctuating hydrodynamics (Betchov, 1957; Bell  _et
al._ , 2022; Bandak  _et al._ , 2022). These results align with those of 3D
Euler turbulence Cichowlas  _et al._ (2005b). Such simulations also shed light
on the foundations of statistical physics, e.g., thermalization, the arrow of
time, measure of entropy for hydrodynamics, etc. Frisch (1995); Bandak  _et
al._ (2022); Gallis  _et al._ (2017); Verma (2019a, 2020); Verma and
Chatterjee (2022). Here we demonstrate the thermalization features of Euler
turbulence in a LJ gas that includes realistic interactions, gas density, and
intrinsic transport properties of the medium.

In this letter, we report the results of a MD simulation with $2.5\times
10^{5}$ particles using the open-source code LAMMPS (Large-scale
Atomic/Molecular Massively Parallel Simulator) (Plimpton, 1995). We employ
MPI-based parallel LAMMPS with a maximum of 400 CPU cores. The particles,
confined in a periodic 2D (x-y geometry) square box, interact among each other
via pairwise LJ potential of the form
$\phi_{ij}(r_{ij})=4\epsilon\left[\left(\sigma/r_{ij}\right)^{12}-\left(\sigma/r_{ij}\right)^{6}\right]$,
where $r_{ij}$ is the separation between the particles, $\sigma$ is the
distance at which $\phi_{ij}$ is zero, and $\epsilon$ is the depth of the
potential. In this letter, we choose a small $\sigma$ and isolate the system
from the heat bath. Also, the kinetic energy dominates the potential energy
for our chosen temperature.

In the present simulation, we employ the standard LJ units, in which $\sigma$
is the unit of length, and $\epsilon$ is the unit of energy. For our
simulation, the box size $L$ is 500 LJ units, and the mean free path is $0.9$
LJ units, which is significantly shorter than the box size. Hence, our
simulation satisfies the continuum approximation, as well as effectively
includes the impact of thermal fluctuations at hydrodynamic scales.

At $t=0$, particles have random velocity (white noise) whose rms value is
$u_{\mathrm{th}}=\sqrt{2T}$, where $T$ is the temperature in LJ units (here,
the particle mass $m=1$, and the Boltzmann constant $k_{B}=1$). In addition,
we provide each particle with a coherent velocity given by

${\bf
u(x},t=0)=A\left[\sin(k_{0}x)\cos(k_{0}y)\hat{x}+\cos(k_{0}x)\sin(k_{0}y)\hat{y}\right],$
(2)

where $k_{0}=\pi/L$, and $A=u_{\mathrm{th}}$ is a constant amplitude chosen so
that the initial coherent and incoherent kinetic energies have similar
magnitudes. Figure 1 illustrates the initial condition and its evolution. The
above initial condition mimics realistic terrestrial flows that have large-
scale macroscopic velocity and small-scale thermal velocity. For present
simulations, we take $T=100$ LJ units. Hence, rms velocity
$U=\sqrt{200}\approx 14.1$ LJ units, and the eddy turnover time at $t=0$ is
$L/U\approx 35.5$ LJ units. Our simulation can be related to inert Ar gas in a
box of size 0.17 $\mu m$ whose average inter-particle separation is 0.19 nm
and the associated mean free path is 0.304 nm. We also remark that our
numerical results are independent of particle numbers as long as it is more
than tens of thousands.

Figure 1: Snapshots of the velocity (represented by arrows) and vorticity
(represented by colors) fields at $t=0,1000$, and $2000$ LJ units in our MD
simulation with a vortex structure embedded in a noisy environment as an
initial condition. The system evolves from an ordered structure ($t=0$) to a
thermalized state ($t=2000$).

##

We start with randomly and homogeneously distributed particles with random
velocities corresponding to 100 LJ temperature units. During the evolution, we
solve the equation of motion for each particle, $m\ddot{\textbf{r}}_{i}=\
-\nabla\sum\phi_{ij}$, using the velocity-verlet algorithm with a time step of
$dt=0.001$ LJ unit. We attach the system of particles to a Nosé-Hoover
thermostat and let the particles attain thermal equilibrium, which takes
around 100 LJ time units. We then remove the thermostat and allow the system
to evolve as a micro-canonical ensemble for another 100 time units to remove
the possibilities of any available free energy due to numerical or
equilibration issues. The energy fluctuations in the asymptotic state are
approximately $10^{-4}\%$. In the above thermalized state, we add the velocity
of the coherent vortex of Eq. (2). This is the initial condition ($t=0$) for
the non-equilibrium MD run.

After applying the vortex velocity profile, we let the LJ gas evolve from
$t=0$ to $2000$ LJ units, approximately 56 eddy turnover time. In Figure 1, we
illustrate three snapshots of the flow using the velocity and vorticity fields
at $t=0$, 1000, and 2000 LJ time units. These plots illustrate the evolution
from an ordered state to a thermalized state, consistent with the numerical
results of 3D Euler turbulence Cichowlas  _et al._ (2005b); Verma and
Chatterjee (2022). We quantify the thermalization process using the kinetic
energy spectrum and flux related to the hydrodynamic velocity. For the same,
we compute the coarse-grained flow velocity ${\bf u(x},t)$ for a given
snapshot by averaging over several hundred particles over a 40x40 grid. We
Fourier transform ${\bf u(x},t)$ and compute ${\bf u(k},t)$, and subsequently,
the modal energy $E({\bf k},t)=|{\bf u(k},t)|^{2}/2$. After this, we compute
the 1D shell spectrum $E(k,t)=\sum_{k-1\leq k^{\prime}\leq k}E({\bf
k}^{\prime},t)$ (Frisch, 1995). Our spectral plots exclude $E(k,t)$ at
$k={k_{0},2k_{0}}$. However, all the available wavevectors are considered for
the computation of nonlinear transfer, energy fluxes, and enstrophy.

Figure 2 illustrates the energy spectra at $t=10,15$, and $25$ LJ units,
whereas Fig. 3 at $t=20,50,500$, and $2000$ LJ units. In these plots, the
smallest wavenumber corresponding to the large-scale vortex is
$k_{0}=2\pi/L\approx 0.0125$, whereas $k_{\mathrm{max}}=40k_{0}\approx 0.5$.
For the initial evolution, Fig. 2 exhibits $E(k,t)\propto k^{-3}$ for small
wavenumbers, and $E(k,t)\propto k$ at large wavenumbers. The $k^{-3}$ energy
spectrum is related to the vortex structure, as explained later. The latter
energy spectrum ($\propto k$) illustrates thermalization of the system at
large wavenumbers. At around $t=25$, $E(k,t)$ at small $k$’s starts to deviate
from $k^{-3}$ scaling because of the energy transfers from the vortex
structure to the fluctuations. We observe that $E(k,t)\propto k$ at $t=500$
(or $\sim 14$ eddy turnover time) and beyond, which is consistent with the
thermalization time for 3D Euler turbulence Cichowlas  _et al._ (2005b).

Figure 2: The shell spectra $E(k,t)$ of the LJ gas at $t=10,15$, and 25 LJ
time units. Here, $E(k,t)\propto k^{-3}$ at small wavenumbers, and
$E(k,t)\propto k$ at large wavenumbers. The latter $E(k,t)$ represents the
thermalized component of the fluid. Figure 3: The shell spectra $E(k,t)$ of
the LJ gas at $t=20,50,500$, and 2000 LJ time units. Here, $E(k,t)\propto k$
at 500 time units and beyond, indicating complete thermalization of the fluid.
The inset shows that the amplitude of the thermalized $E(k,t)$ increases with
time.

Figures 2 and 3 illustrate that the region of $k^{-3}$ spectrum shrinks with
time, whereas that of $k$ spectrum increases with time. In addition, the
magnitude of $E(k,t)$ decreases for small and intermediate wavenumbers, but it
increases for large wavenumbers, similar to the evolution of 3D Euler
turbulence Cichowlas  _et al._ (2005a) (refer to the inset of Fig. 3). We
denote the transition wavenumber between the $k^{-5/3}$ and $k$ regimes by
$k_{c}$ and quantify the coherent and incoherent energies of the hydrodynamic
component using $\sum_{k_{\mathrm{min}}}^{k_{c}}E(k,t)$ and
$\sum^{k_{\mathrm{max}}}_{k_{c}}E(k,t)$ respectively. We illustrate these
quantities in Fig. 4. Clearly, $k_{c}$ decreases with time because of the
expansion of the $k$ spectrum at the cost $k^{-3}$ spectrum. Here, the system
exhibits nonequilibrium behavior at large scales and equilibrium features at
small scales. At $t=500$ LJ units, the coherent energy is nearly over,
indicating nearly complete thermalization of the system. Note that the
velocity follows the Maxwell-Boltzmann distribution; thus, local thermal
equilibrium is always maintained. This feature deviates from the Euler
turbulence that lacks the thermal component.

Figure 4: The time evolution of the transition wavevector $k_{c}$ that
separates the coherent hydrodynamic energy (with $k^{-3}$ spectrum) and
incoherent hydrodynamic energy (with $k$ spectrum). Note that $k_{c}$
decreases with time, as in Figs. 2 and 3. The inset exhibits a decrease in the
total coherent energy $\sum_{k_{\mathrm{min}}}^{k_{c}}E(k,t)$ (black curve)
and a growth in the total incoherent energy
$\sum^{k_{\mathrm{max}}}_{k_{c}}E(k,t)$ (blue curve).

##

Next, we compute the energy and enstrophy transfers and the corresponding
fluxes. Using the energy equation we derive that $dE(k,t)/dt=T^{E}(k,t)$,
where $T^{E}(k,t)=\sum_{\bf p}\Im[\\{{\bf k}\cdot{\bf u(k-p},t)\\}\\{{\bf
u(p},t)\cdot{\bf u^{*}(k},t)\\}]$ is the nonlinear energy transfer term, and
that $\Pi^{E}(k)=-\int_{0}^{k}T^{E}(k^{\prime})dk^{\prime}$ Dar  _et al._
(2001); Verma (2019b). In addition, the enstrophy,
$\Omega=\int_{0}^{\infty}dk^{\prime}k^{\prime 2}E(k^{\prime})$, is conserved
in Euler turbulence. Hence,
$dE^{\Omega}(k,t)/dt=T^{\Omega}(k,t)=k^{2}T^{E}(k,t)$ and
$\Pi^{\Omega}(k,t)=-\int_{0}^{k}T^{\Omega}(k^{\prime},t)dk^{\prime}=-\int_{0}^{k}k^{\prime
2}T^{E}(k^{\prime},t)dk^{\prime}$ Verma (2019b). Note that $\Pi^{E}(k,t)$
[$\Pi^{\Omega}(k,t)$] represents the net energy [enstrophy] transfer from the
modes inside the wavenumber sphere of radius $k$ to the modes outside the
sphere.

##

We compute $T^{E}(k,t)$, $T^{\Omega}(k,t)$, $\Pi^{E}(k,t)$, and
$\Pi^{\Omega}(k,t)$ for our system. We estimate
$T^{E}(k,t)\approx[E(k,t=25)-E(k,t=10)]/(2\times 7.5)$ with an optimum value
of $\Delta t=7.5$ LJ units or 0.2 eddy turnover time. The above $\Delta t$
appears large, but it is reasonable considering large fluctuations in MD
simulations. In Fig. 5, we plot $T^{E}(k,t)$, $T^{\Omega}(k,t)$,
$\Pi^{E}(k,t)$, and $\Pi^{\Omega}(k,t)$. As shown in the figure,
$T^{E}(k,t),T^{\Omega}(k,t)<0$, indicating energy and enstrophy transfers from
smaller wavenumbers to larger wavenumbers. This feature leads to positive
energy and enstrophy fluxes, with $\Pi^{E,\mathrm{max}}\approx 166$, and
$\Pi^{\Omega,\mathrm{max}}\approx 1.05$. Note that our MD simulation has an
interesting feature that deviates from Euler turbulence. For Euler turbulence,
$\int_{0}^{\infty}T^{E}(k^{\prime},t)dk^{\prime}=0$ and
$\Pi^{E}(k,t)\rightarrow 0$ as $k\rightarrow\infty$. However, for MD
simulations, $\int_{0}^{\infty}T^{E}(k^{\prime},t)dk^{\prime}<0$ and
$\Pi^{E}(k,t)$ is finite at $k=k_{\mathrm{max}}$. This is because in MD
simulations, the hydrodynamic modes at the grid level transfer energy to the
thermal particles, which is absent in Euler turbulence that has no thermal
particles.

Figure 5: (a) Nonlinear energy transfer $T^{E}(k,t)$ and (b) nonlinear
enstrophy transfer $T^{\Omega}(k,t)=k^{2}T^{E}(k,t)$. (c,d) The energy flux
$\Pi^{E}(k,t)$ and the enstrophy flux $\Pi^{E}(k,t)$.

##

Lastly, we discuss the $k^{-3}$ energy spectrum exhibited in Figs. 2 and 3.
The hydrodynamic velocity field till $t\lessapprox 20$ LJ units is reasonably
well described by Eq. (2) with some added noise. For such a field
configuration, the two-point correlation function $C({\bf r},t)=\langle{\bf
u(x+r},t){\bf u(x},t)\rangle\propto\alpha-\beta r^{2}$, with $\alpha$ and
$\beta$ as constants. Therefore, $C({\bf k},t)=\int d{\bf r}C({\bf
r},t)\exp(i{\bf k\cdot r})\propto k^{-4}$, and hence $E(k,t)=C({\bf k},t)2\pi
k\sim k^{-3}$. Interestingly, the above $k^{-3}$ spectrum is related to the
Nastrom-Gage spectrum of Earth’s atmosphere at synoptic scales (1000-3000 km),
which is coupled with $k^{-5/3}$ spectrum at mesoscales (10-500 km) Nastrom
_et al._ (1984); Gage and Nastrom (1986). We remark that the above $k^{-3}$
spectrum is not directly related to Kraichnan’s predictions based on the
constancy of enstrophy flux Kraichnan (1973a). Rather, it is connected to the
large-scale 2D structures, as described above.

##

Researchers have constructed a variety of arguments to explain the Nastrom-
Gage spectrum of Earth’s atmosphere Lindborg and Alvelius (2000); Tung and
Orlando (2003); Gkioulekas and Tung (2006). Among the proposed theories, our
results match best with the double cascade theory of Gkioulekas and Tung
(2006). According to this theory, $E(k)\propto k^{-3}$ for $k<k_{t}$, whereas
$E(k)\propto k^{-5/3}$ for $k>k_{t}$, where
$k_{t}\approx\sqrt{\Pi^{\Omega,\mathrm{max}}/\Pi^{E,\mathrm{max}}}$ separates
the two power law regimes. For our MD simulations, $k_{t}\approx 0.08$.
Therefore, according to Gkioulekas and Tung (2006), we expect $k^{-3}$ energy
spectrum for $k<k_{t}$ and $k^{-5/3}$ spectrum for $k>k_{t}$. Our simulation
exhibits only the $E(k)\propto k^{-3}$ for $k<k_{t}$ because $k_{t}$ is close
to the dissipation scale.

##

We summarize our results as follows. We simulate thermalization of a realistic
fluid system containing a large number of weakly interacting particles that
are also part of a large hydrodynamic vortex. We isolate our system from the
heat bath so as to conserve the total energy. Thus, our system resembles Euler
turbulence with energy-conserving noise. In the early phase, the system
exhibits $E(k)\propto k^{-3}$ and $E(k)\propto k$ at small and large
wavenumbers, respectively. The system gets fully thermalized at $t\gtrsim 500$
LJ units, at which point the coherent hydrodynamic energy is fully transferred
to the incoherent hydrodynamic component ($E(k)\propto k$) and thermal noise.
We strengthen our arguments using the energy and enstrophy transfers. Our MD
simulation clearly demonstrates how large-scale kinetic energy cascades to
small scales in a realistic turbulent system.

Our results are consistent with the route to thermalization observed earlier
in Euler turbulence Cichowlas  _et al._ (2005a), in Navier-Stokes equation
with fluctuating hydrodynamics Bell  _et al._ (2022); Bandak  _et al._ (2022),
and in DSMC simulations McMullen  _et al._ (2022). However, there are some
subtle differences. In our simulation, some of the hydrodynamic energy is
transferred to the thermal particles at the microscopic level, which is absent
in 3D Euler turbulence. We also remark that our MD simulations represent the
particle dynamics more realistically than DSMC.

In our system, the large-scale initial structure generates $k^{-3}$ energy
spectrum, as well as forward energy and enstrophy fluxes. Such dynamics
resemble that in Earth’s atmosphere at the synoptic scales Gage and Nastrom
(1986). A difference, however, is that the atmospheric vortex structures are
maintained by large-scale forcing. However, the vortex structure in our system
breaks down and thermalizes due to a lack of external forcing. Interestingly,
in earlier simulations of 2D Euler systems with large-scale structures as
initial conditions exhibit nonequilibrium behaviour Bouchet and Simonnet
(2009); Bouchet and Venaille (2012); Verma and Chatterjee (2022). In contrast,
the initial vortex structure in our 2D MD simulation thermalizes. However, we
also found similar thermalization for other initial conditions such as sheared
flow, wave excitation, Rayleigh-Taylor instability, and four-vortex during the
validation process.

Thus, our MD simulations of hydrodynamic structures embedded in a noisy
environment provide valuable insights into the thermalization process in a
realistic fluid system. The work also sheds light on the connection between
hydrodynamics and thermodynamics, which are active at macroscopic and
microscopic scales, respectively.

##

Acknowledgements. The authors acknowledge the use of AGASTYA HPC for present
studies. RW and ST also acknowledge the support for this work through SERB
Grant No. CRG/2020/003653, and MKV the support of SERB Grant Nos.
SERB/PHY/20215225 and SERB/PHY/2021473.

## References

  * Huang (2008) K. Huang,  _Statistical mechanics_ (John Wiley & Sons, 2008).
  * Bellomo and Schiavo (1997) N. Bellomo and M. L. Schiavo, Mathematical and Computer Modelling 26, 43 (1997).
  * Reif (1965) F. Reif,  _Fundamentals of Statistical and Thermal Physics_ (McGraw-Hill, New York, 1965).
  * Goldstein (2001) S. Goldstein, in  _Chance in physics: Foundations and perspectives_ (Springer, 2001) pp. 39–54.
  * Grad (1958) H. Grad, “Principles of the kinetic theory of gases,” (Springer Berlin Heidelberg, 1958).
  * Loeb (2004) L. B. Loeb,  _The kinetic theory of gases_ (Courier Corporation, 2004).
  * Gallis  _et al._ (2017) M. A. Gallis, N. P. Bitter, T. P. Koehler, J. R. Torczynski, S. J. Plimpton, and G. Papadakis, Phys. Rev. Lett. 118, 064501 (2017).
  * Bell  _et al._ (2022) J. B. Bell, A. Nonaka, A. L. Garcia, and G. Eyink, J. Fluid Mech. 939, A12 (2022).
  * Bandak  _et al._ (2022) D. Bandak, N. Goldenfeld, A. A. Mailybaev, and G. Eyink, Phys. Rev. E 105, 065113 (2022).
  * McMullen  _et al._ (2022) R. M. McMullen, M. C. Krygier, J. R. Torczynski, and M. A. Gallis, Phys. Rev. Lett. 128, 114501 (2022).
  * Cichowlas  _et al._ (2005a) C. Cichowlas, P. Bonaïti, F. Debbasch, and M. Brachet, Phys. Rev. Lett. 95, 264502 (2005a).
  * Lee (1952) T. D. Lee, Quart. Appl. Math. 10, 69 (1952).
  * Kraichnan (1973a) R. H. Kraichnan, J. Fluid Mech. 59, 745 (1973a).
  * Onsager (1949) L. Onsager, Il Nuovo Cimento 6, 279 (1949).
  * Kolmogorov (1941a) A. N. Kolmogorov, Dokl Acad Nauk SSSR 30, 301 (1941a).
  * Kolmogorov (1941b) A. N. Kolmogorov, Dokl Acad Nauk SSSR 32, 16 (1941b).
  * Frisch (1995) U. Frisch,  _Turbulence: The Legacy of A. N. Kolmogorov_ (Cambridge University Press, Cambridge, 1995).
  * Davis  _et al._ (2001) M. J. Davis, S. A. Morgan, and K. Burnett, Phys. Rev. Lett. 87, 160402 (2001).
  * Proment  _et al._ (2009) D. Proment, S. Nazarenko, and M. Onorato, Phys. Rev. A 80, 051603 (2009).
  * Barenghi  _et al._ (2014) C. F. Barenghi, L. Skrbek, and K. R. Sreenivasan, Proceedings of the National Academy of Sciences 111, 4647 (2014).
  * Betchov (1957) R. Betchov, J. Fluid Mech. 3, 205 (1957).
  * Robert and Sommeria (1991) R. Robert and J. Sommeria, J. Fluid Mech. 229, 291–310 (1991).
  * Kraichnan (1973b) R. H. Kraichnan, J. Fluid Mech. 59, 745–752 (1973b).
  * Pakter and Levin (2018) R. Pakter and Y. Levin, Phys. Rev. Lett. 121, 020602 (2018).
  * Bouchet and Simonnet (2009) F. Bouchet and E. Simonnet, Phys. Rev. Lett. 102, 094504 (2009), 0804.2231 .
  * Seyler  _et al._ (1975) C. E. Seyler, Y. Salu, D. Montgomery, and G. Knorr, Physics of Fluids 18, 803 (1975).
  * Verma and Chatterjee (2022) M. K. Verma and S. Chatterjee, Phys. Rev. Fluids 7, 114608 (2022).
  * Bouchet and Venaille (2012) F. Bouchet and A. Venaille, Phys. Rep. 515, 227 (2012).
  * Verma  _et al._ (2020) M. K. Verma, S. Bhattacharya, and S. Bhattacharya, arXiv , arXiv:2004.09053 (2020).
  * Martinez  _et al._ (1994) D. O. Martinez, W. H. Matthaeus, S. Chen, and D. C. Montgomery, Phys. Fluids 6, 1285 (1994).
  * Chen and Doolen (1998) S. Chen and G. D. Doolen, Annual review of fluid mechanics 30, 329 (1998).
  * Bird (1976) G. A. Bird, NASA STI/Recon Technical Report A 76, 40225 (1976).
  * Kadau  _et al._ (2004) K. Kadau, T. C. Germann, N. G. Hadjiconstantinou, P. S. Lomdahl, G. Dimonte, B. L. Holian, and B. J. Alder, Proc. Natl. Acad. Sci. 101, 5851 (2004).
  * Ashwin and Sen (2015) J. Ashwin and A. Sen, Phys. Rev. Lett. 114, 055002 (2015).
  * Wani  _et al._ (2022) R. Wani, A. Mir, F. Batool, and S. Tiwari, Scientific Reports 12 (2022).
  * Cichowlas  _et al._ (2005b) C. Cichowlas, P. Bonaïti, F. Debbasch, and M. E. Brachet, Phys. Rev. Lett. 95, 264502 (2005b).
  * Verma (2019a) M. K. Verma, Eur. Phys. J. B 92, 190 (2019a).
  * Verma (2020) M. K. Verma, Phil. Trans. R. Soc. A. 378, 20190470 (2020).
  * Plimpton (1995) S. Plimpton, Journal of Computational Physics 117, 1 (1995).
  * Dar  _et al._ (2001) G. Dar, M. K. Verma, and V. Eswaran, Physica D 157, 207 (2001).
  * Verma (2019b) M. K. Verma,  _Energy transfers in Fluid Flows: Multiscale and Spectral Perspectives_ (Cambridge University Press, Cambridge, 2019).
  * Nastrom  _et al._ (1984) G. Nastrom, K. Gage, and W. Jasperson, Nature 310, 36 (1984).
  * Gage and Nastrom (1986) K. S. Gage and G. D. Nastrom, J. Atmos. Sci. 43, 729 (1986).
  * Lindborg and Alvelius (2000) E. Lindborg and K. Alvelius, Phys. Fluids 12, 945 (2000).
  * Tung and Orlando (2003) K.-K. Tung and W. W. Orlando, J. Atmos. Sci. 60, 824 (2003).
  * Gkioulekas and Tung (2006) E. Gkioulekas and K.-K. Tung, Journal of Low Temperature Physics 145, 25 (2006).


The Universal Steiner tree, and Oblivious buy-at-bulk problem sound very
similar. Indeed, one might be tempted to think that the Universal Steiner tree
problem is a special case where there is only a single source, and the
canonical function gets only the values $\\{0,1\\}$. However, in the universal
Steiner tree we have additional demand- the solution has to be a tree! Indeed,
at present, there are significant gaps between the best solutions for this
problems on both general, and $K_{r}$-minor free graphs.

###  7.4 Name-Independent Routing

A _compact routing scheme_ in a network is a mechanism that allows packets to
be delivered from any node to any other node. The network is represented as a
undirected graph, and each node can forward incoming data by using local
information stored at the node, called a _routing table_ , and the (short)
packet’s _header_. The stretch of a routing scheme is the worst-case ratio
between the length of a path on which a packet is routed to the shortest
possible path. When designing a compact routing scheme our goal is to optimize
the trade-off between the stretch and the size of the routing table and
header. Here we focus on the name-independent model where each node is
assigned an arbitrary unique network identifier, which cannot be chosen by the
routing scheme designer. In addition, each edge will have an arbitrary port
(that also cannot be changed). Note that there is a different regime of
labeled routing, where the designer can choose the node labels and edge ports,
see e.g. [TZ01, Tho04a, AG06, Che13, ACE+20, Fil21, FL21]. The labeled routing
regime admits much better compact routing schemes. Indeed for general graphs,
for every $k\in\mathbb{N}$ one can construct labeled routing scheme with
stretch $3.68k$, routing table size $O(k\cdot n^{\frac{1}{k}})$, and label
size $O(k\cdot\log n)$ (see also [ACE+20, FL21] for different trade-off’s). In
$K_{r}$-minor free graphs one can even construct labeled routing scheme with
stretch $1+\varepsilon$ and and label and table size of $\varepsilon^{-1}\cdot
f(r)\cdot\mathrm{polylog}(n)$ ${}^{\ref{foot:RS}}$ [AG06].

The name-independent regime is considered more practical, as it does not
assumes that the sender knows the artificially chosen label of the
destination. Further, it can cope much better with changes in the network.
There are also applications that pose constrains on nodes addresses that are
not easily satisfied by the artificial smartly chosen labels (such as
distributed hash tables). However, the name-independent regime is much more
challenging. Indeed, any name-independent routing scheme on unweighted stars
(trees of depth $1$) requires table size of $\Omega(n\cdot\log n)$ bits to get
stretch bellow $3$ [AGM+08]. The situation in weighted stars is even more
dire, as every name-independent routing scheme with stretch bellow $2k+1$ (for
$k\geq 1)$ requires routing tables of at least $\Omega((n\cdot\log
n)^{\frac{1}{k}})$ bits [AGM06]. We will thus focus on unweighted graphs.

Abraham et al. [AGMW10] used their strong sparse covers, as well as name-
independent routing scheme for trees [AGM04], to design a name-independent
routing scheme for $K_{r}$-minor free graphs. We can use our new strong sparse
cover to improve the various parameters in this routing scheme. In the
following we elaborate on that.

A hereditary graph family is a family ${\cal F}$ such that for every
$G\in{\cal F}$, every subgraph $H$ of $G$ also belongs to $H\in{\cal F}$. A
graph posses an $\alpha$-orientation if it is possible to direct all edges
such that every vertex has out-degree at most $\alpha$. A family ${\cal F}$
has an $\alpha$-orientation if every $G\in{\cal F}$ has $\alpha$-orientation.
[AGMW10] implicitly proved the following meta theorem: consider a hereditary
graph family ${\cal F}$ that has an $\alpha$-orientation, and let $G\in{\cal
F}$ be an unweighted graph with diameter $D$ that admits a strong
$(\tau,\beta)$-sparse cover scheme. Then there is a polynomial time
constructible name-independent routing seheme, in the fixed port model with
stretch $O(\beta)$, and using $O(\log n+\log\tau)$-bit headers, in which every
node requires tables of $O(\frac{\log^{3}n}{\log\log n}+\alpha\cdot\log
n)\cdot\tau\cdot\log D$ bits.

It is well known that the hereditary graph family of $K_{r}$ minor free graphs
has an $O(r\sqrt{\log r})$-orientation (see e.g. [AGMW10]). Combining it with
our Theorem 1 we conclude

######  Corollary 6.

For every $n$ vertex unweighted $K_{r}$-minor free graph $G$ with diameter
$D$, there is a polynomial time constructible name-independent routing scheme,
in the fixed port model, with:

  * •

Stretch $O(r)$, $O(\log n)$ bit headers, and $O(\frac{\log^{3}n}{\log\log
n}+r\sqrt{\log r}\cdot\log n)\cdot r^{2}\cdot\log D$ bit table.

  * •

Stretch $O(1)$, $O(r+\log n)$ bit headers, and
$O(1)^{r}\cdot\frac{\log^{3}n}{\log\log n}\cdot\log D$ bit table.

See Table 3 for comparison of Corollary 6 with previous results.

| Stretch | Header | Table | Ref
---|---|---|---|---
(1) | $O(r^{2})$ | $O(\log n+r\log r)$ | $O(1)^{r}\cdot r!\cdot\frac{\log^{3}n}{\log\log n}\cdot\log D$ | [AGMW10]
(2) | $O(1)$ |  | $O(f(r)\cdot\log^{3}n)$ | [BLT14]
(3) | $O(r)$ | $O(\log n)$ | $O(\frac{\log^{3}n}{\log\log n}+r\sqrt{\log r}\cdot\log n)\cdot r^{2}\cdot\log D$ | Corollary 6
(4) | $O(1)$ | $O(r+\log n)$ | $O(1)^{r}\cdot\frac{\log^{3}n}{\log\log n}\cdot\log D$ | Corollary 6
Table 3: Summery of new and previous work on name-independent routing schemes
in $K_{r}$-minor free graphs in the fixed parameter model. The input graph are
unweighted, and $D$ denotes it’s diameter. $f(r)$ is an extremely fast growing
function ${}^{\ref{foot:RS}}$. In [BLT14], the header size is not explicitly
stated, and the bound on the table is only in expectation. Comparing our
result (3) with [AGMW10] we quadratically improved the stretch, and
exponentially improved the dependence on $r$ in the routing table size.
Comparing [AGMW10] with (4) we improved the stretch from $O(r^{2})$ to
constant, and somewhat improved the dependence on $r$ in both table size and
header. Comparing (4) with [BLT14], we very significantly improved the table
size, and improved the size bound to hold in the worst case.

###  7.5 Path-Reporting Distance Oracle

Given a weighted graph $G=(V,E,w)$, a path-reporting distance oracle (PRDO) is
a succinct data structure that given a query $\\{u,v\\}\in{V\choose 2}$
quickly returns a $u-v$ path which is an approximate $u-v$ shortest path.
Formally we say that a distance oracle has stretch $k$ if on query
$\\{u,v\\}$, it returns a $u-v$ path $P$ of weight at most $k\cdot
d_{G}(u,v)$. We say that the query time is $t$, if the time it takes the
distance oracle to return a path $P$ is at most $O(|P|)+t$. In the study of
PRDO’s [EP16, ENW16, ES23], the goal is to optimize the trade-off between
stretch, query time, and space.

Elkin, Neiman and Wulff-Nilsen [ENW16] constructed a PRDO using strong sparse
covers with very small query time. Given a weighted graph $G=(V,E,w)$ with
aspect ratio $\Phi$ that admits a strong $(\beta,s)$-sparse cover scheme,
[ENW16] implicitly constructed a PRDO with stretch $O(\beta)$, space
$O(s\cdot\log\Phi)$ (in machine words), and query time $O(\log\log\Phi)$. In
fact, by decreasing the gap between the different scales in their construction
to $1+\varepsilon$, their proof will lead to a PRDO with stretch
$(1+\varepsilon)\cdot\beta$, space $O(\frac{s}{\varepsilon}\cdot\log\Phi)$,
and query time $O(\log\log\Phi+\log\frac{1}{\varepsilon})$.

Elkin et al. [ENW16] used the strong $(O(r^{2}),O(\log n))$-sparse cover
scheme that follows from the padded decomposition of [AGG+19] to construct
their PRDO for $K_{r}$-minor free graphs with stretch $O(r^{2})$, size
$O(n\cdot\log n\cdot\log\Phi)$ and query time $O(\log\log\Phi)$. Later,
Filtser [Fil19a] used his improved strong padded decomposition to obtain a
strong $(O(r),O(\log n))$-sparse cover scheme, and plugged it into the PRDO
construction of [ENW16], improving the stretch parameter from $O(r^{2})$ to
$O(r)$. Using our strong $(O(r),O(r^{2}))$-sparse cover scheme (Theorem 1), we
can get a further improvement, reducing the space to $O(n\cdot
r^{2}\cdot\log\Phi)$. Furthermore, using our strong
$(4+\varepsilon,O(\frac{1}{\varepsilon})^{r})$-sparse cover scheme (Theorem
1), and the observations made in the proof of the contraction argument in
Lemma 10, we can obtain a PRDO with stretch $3+\varepsilon$, size $n\cdot
O(\frac{1}{\varepsilon})^{r+1}\cdot\log\Phi$ and query time
$O(\log\log\Phi+\log\frac{1}{\varepsilon})$.

######  Corollary 7.

Every $n$-vertex $K_{r}$-minor free weighted graph $G$ with aspect ratio
$\Phi$, admits a path-reporting distance oracle with:

  * •

Stretch $O(r)$, size $O(n\cdot r^{2}\cdot\log\Phi)$ and query time
$O(\log\log\Phi)$.

  * •

Stretch $3+\varepsilon$, size $n\cdot
O(\frac{1}{\varepsilon})^{r+1}\cdot\log\Phi$ and query time
$O(\log\log\Phi+\log\frac{1}{\varepsilon})$.

##  8 Conclusion and Open Problems

This paper is mainly concerned with sparse covers for minor free graphs. Our
first contribution is to transform from the recently introduced notion of
buffered cop decomposition [CCL+24] to sparse covers. As a result, we obtain a
strong $\left(O(r),O(r^{2})\right)$-SPCS, and strong
$\left(4+\varepsilon,O(\frac{1}{\varepsilon})^{r}\right)$-SPCS for
$K_{r}$-minor free graphs (Theorem 1). This significantly improves both
sparsity and padding parameters compared to previous work, obtains the strong
diameter guarantee, and the “partition based” property. We then use this new
covers to construct low distortion and dimension $\ell_{\infty}$ embedding of
$K_{r}$ minor free graphs (Corollary 1, and Theorem 2), improving
significantly over the previous work [KLMN05] in both dimension and
distortion. Next, three decades after the notions of sparse covers and padded
decompositions were introduced [AP91, KPR93], we observe that sparse covers
imply padded decomposition (Theorem 3), and recover the state of the art
padded decomposition for minor free graphs [AGG+19]. Finally, we show several
applications of our new sparse covers. Specifically, we obtained better sparse
partitions, and as a result get an exponential improvement in the dependence
on $r$ for both universal TSP, and metric universal Steiner tree problems. We
also get a similar exponential improvement for the oblivious buy-at-bulk
problem. For the name independent routing scheme in $K_{r}$-minor free graphs,
we get quadratic improvement in the stretch and exponential improvement in the
space (in the dependence on $r$) compared with previous work [AGMW10] (or just
ginormous improvement in the space compared with [BLT14]). We also obtain
similar improvements for path reporting distance oracles.

Our work leaves several open questions:

  1. 1.

The main open question is to obtain improve sparse covers for $K_{r}$-minor
free graphs. Note that we don’t have any lower bound beyond what follows from
general graphs. In particular, it might be possible to obtain $(O(\log
r),O(\log r))$-sparse cover scheme, or $(O(1),\mathrm{poly}(r))$-sparse cover
scheme. Due to our Theorem 3, such sparse covers will imply padded
decomposition with parameter $\tilde{O}(\log r)$, solving the conjecture from
[AGG+19].

  2. 2.

Metric embeddings into $\ell_{\infty}$. In Theorem 2 we got distortion
$3+\varepsilon$ which looks like a natural barrier for sparse cover based
techniques. It is very interesting to see if we can get bellow $3$, even for
planar graphs. Optimally, we would like to see an embedding with distortion
$1+\varepsilon$ and $g(r,\varepsilon)\cdot\log n$ coordinated, for an
arbitrary function $g$.

  3. 3.

Universal Steiner tree. In this paper, using the reduction from [JLN+05] we
obtain a solution for the metric UST problem in $K_{r}$-minor free graphs with
stretch $O(\frac{r^{4}}{\log r})\cdot\log n$. However, for the usual (non-
metric) UST problem, the state of the art for $K_{r}$-minor free (or even
planar) graphs is $O(\log^{7}n)$ [BCF+23], the same as for general graphs. It
is interesting to see if we can use the topological structure to get an
improved stretch.

## Acknowledgments

The author would like to thank James R Lee for helpful discussions regarding
the embedding of planar graphs into $\ell_{\infty}$ from [KLMN05]. The author
would also like to thank Shmuel Tomi Klein for the reference to [KN76].

## References

  * [ABN11] I. Abraham, Y. Bartal, and O. Neiman.  Advances in metric embedding theory.  Advances in Mathematics, 228(6):3026–3126,  2011, doi:https://doi.org/10.1016/j.aim.2011.08.003.
  * [ACE+20] I. Abraham, S. Chechik, M. Elkin, A. Filtser, and O. Neiman.  Ramsey spanning trees and their applications.  ACM Trans. Algorithms, 16(2):19:1–19:21, 2020.  preliminary version published in SODA 2018, doi:10.1145/3371039.
  * [AFGN22] I. Abraham, A. Filtser, A. Gupta, and O. Neiman.  Metric embedding via shortest path decompositions.  SIAM J. Comput., 51(2):290–314, 2022.  a priliminary version apperared in the proceedings of STOC 18, doi:10.1137/19m1296021.
  * [AG06] I. Abraham and C. Gavoille.  Object location using path separators.  In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, pages 188–197, 2006.  Full version: https://www.cse.huji.ac.il/~ittaia/papers/AG-TR.pdf, doi:10.1145/1146381.1146411.
  * [AGG+14] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ‘14, page 79–88,  2014, doi:10.1145/2591796.2591849.
  * [AGG+19] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  SIAM J. Comput., 48(3):1120–1145, 2019.  preliminary version published in STOC 2014, doi:10.1137/17M1112406.
  * [AGM04] I. Abraham, C. Gavoille, and D. Malkhi.  Routing with improved communication-space trade-off.  In R. Guerraoui, editor, Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings, volume 3274 of Lecture Notes in Computer Science, pages 305–319. Springer,  2004, doi:10.1007/978-3-540-30186-8\\_22.
  * [AGM05] I. Abraham, C. Gavoille, and D. Malkhi.  Compact routing for graphs excluding a fixed minor.  In P. Fraigniaud, editor, Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings, volume 3724 of Lecture Notes in Computer Science, pages 442–456. Springer,  2005, doi:10.1007/11561927\\_32.
  * [AGM06] I. Abraham, C. Gavoille, and D. Malkhi.  On space-stretch trade-offs: lower bounds.  In P. B. Gibbons and U. Vishkin, editors, SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30 - August 2, 2006, pages 207–216. ACM,  2006, doi:10.1145/1148109.1148143.
  * [AGM+08] I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup.  Compact name-independent routing with minimum stretch.  ACM Trans. Algorithms, 4(3):37:1–37:12,  2008, doi:10.1145/1367064.1367077.
  * [AGMW10] I. Abraham, C. Gavoille, D. Malkhi, and U. Wieder.  Strong-diameter decompositions of minor free graphs.  Theory of Computing Systems, 47(4):837–855,  2010, doi:10.1007/s00224-010-9283-6.
  * [AKP94] B. Awerbuch, S. Kutten, and D. Peleg.  On buffer-economical store-and-forward deadlock prevention.  IEEE Trans. Commun., 42(11):2934–2937,  1994, doi:10.1109/26.328973.
  * [AKPW95] N. Alon, R. M. Karp, D. Peleg, and D. B. West.  A graph-theoretic game and its application to the k-server problem.  SIAM J. Comput., 24(1):78–100, 1995.  preliminary version published in On-Line Algorithms 1991, doi:10.1137/S0097539792224474.
  * [And86] T. Andreae.  On a pursuit game played on graphs for which a minor is excluded.  J. Comb. Theory, Ser. B, 41(1):37–47,  1986, doi:10.1016/0095-8956(86)90026-2.
  * [AP90a] B. Awerbuch and D. Peleg.  Network synchronization with polylogarithmic overhead.  In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 514–522,  1990\.
  * [AP90b] B. Awerbuch and D. Peleg.  Sparse partitions.  In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (FOCS), pages 503–513,  1990, doi:10.1109/FSCS.1990.89571.
  * [AP91] B. Awerbuch and D. Peleg.  Concurrent online tracking of mobile users.  In L. Chapin, editor, Proceedings of the Conference on Communications Architecture & Protocols, SIGCOMM 1991, Zürich, Switzerland, September 3-6, 1991, pages 221–233. ACM,  1991, doi:10.1145/115992.116013.
  * [AW04] H. Attiya and J. L. Welch.  Distributed computing - fundamentals, simulations, and advanced topics (2. ed.).  Wiley series on parallel and distributed computing. Wiley,  2004\.
  * [Bar96] Y. Bartal.  Probabilistic approximations of metric spaces and its algorithmic applications.  In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193,  1996, doi:10.1109/SFCS.1996.548477.
  * [BCF+23] O. Busch, D. Q. Chen, A. Filtser, D. Hathcock, D. E. Hershkowitz, and R. Rajaraman.  One tree to rule them all: Poly-logarithmic universal steiner tree.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 60–76,  2023, doi:10.1109/FOCS57990.2023.00012.
  * [BDR+12] C. Busch, C. Dutta, J. Radhakrishnan, R. Rajaraman, and S. Srivathsan.  Split and join: Strong partitions and universal steiner trees for graphs.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 81–90. IEEE Computer Society,  2012, doi:10.1109/FOCS.2012.45.
  * [BFN19a] Y. Bartal, N. Fandina, and O. Neiman.  Covering metric spaces by few trees.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 20:1–20:16,  2019, doi:10.4230/LIPIcs.ICALP.2019.20.
  * [BFN19b] Y. Bartal, A. Filtser, and O. Neiman.  On notions of distortion and an almost minimum spanning tree with constant average distortion.  J. Comput. Syst. Sci., 105:116–129, 2019.  preliminary version published in SODA 2016, doi:10.1016/j.jcss.2019.04.006.
  * [BFT24] S. Bhore, A. Filtser, and C. D. Toth.  Online duet between metric embeddings and minimum-weight perfect matchings.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4564–4579,  2024, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.162, doi:10.1137/1.9781611977912.162.
  * [BG19] Y. Bartal and L. Gottlieb.  Approximate nearest neighbor search for $\ell_{p}$-spaces ($2<p<\infty$).  Theor. Comput. Sci., 757:27–35,  2019, doi:10.1016/J.TCS.2018.07.011.
  * [BLT14] C. Busch, R. LaFortune, and S. Tirthapura.  Sparse covers for planar graphs and graphs that exclude a fixed minor.  Algorithmica, 69(3):658–684,  2014, doi:10.1007/S00453-013-9757-4.
  * [Bou85] J. Bourgain.  On lipschitz embedding of finite metric spaces in hilbert space.  Israel Journal of Mathematics, 52(1-2):46–52,  1985, doi:10.1007/BF02776078.
  * [CCL+23] H.-C. Chang, J. Conroy, H. Le, L. Milenkovic, S. Solomon, and C. Than.  Covering planar metrics (and beyond): O(1) trees suffice.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2231–2261,  2023, doi:10.1109/FOCS57990.2023.00139.
  * [CCL+24] H.-C. Chang, J. Conroy, H. Le, L. Milenković, S. Solomon, and C. Than.  Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5300–5331,  2024, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.191, doi:10.1137/1.9781611977912.191.
  * [CFJ+22] A. Czumaj, A. Filtser, S. H. Jiang, R. Krauthgamer, P. Veselý, and M. Yang.  Streaming facility location in high dimension via new geometric hashing.  CoRR, abs/2204.02095, 2022.  conference version published in STOC 2022, arXiv:2204.02095, doi:10.48550/ARXIV.2204.02095.
  * [CFKL20] V. Cohen-Addad, A. Filtser, P. N. Klein, and H. Le.  On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs.  CoRR, abs/2009.05039, 2020.  To appear in FOCS 2020,https://arxiv.org/abs/2009.05039, arXiv:2009.05039.
  * [Che13] S. Chechik.  Compact routing schemes with improved stretch.  In P. Fatourou and G. Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013, pages 33–41. ACM,  2013, doi:10.1145/2484239.2484268.
  * [Che18] Y. K. Cheung.  Steiner point removal - distant terminals don’t (really) bother.  In A. Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1353–1360. SIAM,  2018, doi:10.1137/1.9781611975031.89.
  * [CLPP23] V. Cohen-Addad, H. Le, M. Pilipczuk, and M. Pilipczuk.  Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1*.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2262–2277,  2023, doi:10.1109/FOCS57990.2023.00140.
  * [EFN17] M. Elkin, A. Filtser, and O. Neiman.  Terminal embeddings.  Theoretical Computer Science, 697:1 – 36,  2017, doi:https://doi.org/10.1016/j.tcs.2017.06.021.
  * [EFN18] M. Elkin, A. Filtser, and O. Neiman.  Prioritized metric structures and embedding.  SIAM J. Comput., 47(3):829–858,  2018, doi:10.1137/17M1118749.
  * [EN22] M. Elkin and O. Neiman.  Lossless prioritized embeddings.  SIAM J. Discret. Math., 36(3):1529–1550,  2022, doi:10.1137/21M1436221.
  * [ENW16] M. Elkin, O. Neiman, and C. Wulff-Nilsen.  Space-efficient path-reporting approximate distance oracles.  Theor. Comput. Sci., 651:1–10,  2016, doi:10.1016/j.tcs.2016.07.038.
  * [EP16] M. Elkin and S. Pettie.  A linear-size logarithmic stretch path-reporting distance oracle for general graphs.  ACM Trans. Algorithms, 12(4):50:1–50:31,  2016, doi:10.1145/2888397.
  * [Erd64] P. Erdős.  Extremal problems in graph theory.  In in “Theory of Graphs and Its Applications,” Proc. Sympos. Smolenice, pages 29–36,  1964\.
  * [ES23] M. Elkin and I. Shabat.  Path-reporting distance oracles with logarithmic stretch and size o(n log log n).  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2278–2311,  2023, doi:10.1109/FOCS57990.2023.00141.
  * [FGK23] A. Filtser, L. Gottlieb, and R. Krauthgamer.  Labelings vs. embeddings: On distributed and prioritized representations of distances.  Discret. Comput. Geom.,  2023, doi:10.1007/s00454-023-00565-2.
  * [FGN23] A. Filtser, Y. Gitlitz, and O. Neiman.  Light, reliable spanners.  CoRR, abs/2307.16612,  2023, arXiv:2307.16612, doi:10.48550/ARXIV.2307.16612.
  * [FI99] M. Farach-Colton and P. Indyk.  Approximate nearest neighbor algorithms for hausdorff metrics via embeddings.  In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA, pages 171–180. IEEE Computer Society,  1999, doi:10.1109/SFFCS.1999.814589.
  * [Fil19a] A. Filtser.  On strong diameter padded decompositions.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, pages 6:1–6:21,  2019, doi:10.4230/LIPIcs.APPROX-RANDOM.2019.6.
  * [Fil19b] A. Filtser.  Steiner point removal with distortion ${O}(logk)$ using the relaxed-voronoi algorithm.  SIAM J. Comput., 48(2):249–278,  2019, doi:10.1137/18M1184400.
  * [Fil20a] A. Filtser.  A face cover perspective to $\ell_{1}$ embeddings of planar graphs.  In S. Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1945–1954. SIAM,  2020, doi:10.1137/1.9781611975994.120.
  * [Fil20b] A. Filtser.  Scattering and sparse partitions, and their applications.  In A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 47:1–47:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,  2020, doi:10.4230/LIPIcs.ICALP.2020.47.
  * [Fil21] A. Filtser.  Hop-constrained metric embeddings and their applications.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 492–503. IEEE,  2021, doi:10.1109/FOCS52979.2021.00056.
  * [Fil23] A. Filtser.  Labeled nearest neighbor search and metric spanners via locality sensitive orderings.  In E. W. Chambers and J. Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 33:1–33:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,  2023, doi:10.4230/LIPIcs.SoCG.2023.33.
  * [FKS19] E. Fox-Epstein, P. N. Klein, and A. Schild.  Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ‘19, page 1069–1088,  2019, doi:10.1137/1.9781611975482.66.
  * [FKT19] A. Filtser, R. Krauthgamer, and O. Trabelsi.  Relaxed voronoi: A simple framework for terminal-clustering problems.  In J. T. Fineman and M. Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 10:1–10:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,  2019, doi:10.4230/OASICS.SOSA.2019.10.
  * [FL21] A. Filtser and H. Le.  Clan embeddings into trees, and low treewidth graphs.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 342–355. ACM,  2021, doi:10.1145/3406325.3451043.
  * [FL22a] A. Filtser and H. Le.  Locality-sensitive orderings and applications to reliable spanners.  In S. Leonardi and A. Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1066–1079. ACM,  2022, doi:10.1145/3519935.3520042.
  * [FL22b] A. Filtser and H. Le.  Low treewidth embeddings of planar and minor-free metrics.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 1081–1092. IEEE,  2022, doi:10.1109/FOCS54457.2022.00105.
  * [FN22] A. Filtser and O. Neiman.  Light spanners for high dimensional norms via stochastic decompositions.  Algorithmica,  2022, doi:10.1007/s00453-022-00994-0.
  * [FRT04] J. Fakcharoenphol, S. Rao, and K. Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  J. Comput. Syst. Sci., 69(3):485–497, November 2004.  preliminary version published in STOC 2003, doi:10.1016/j.jcss.2004.04.011.
  * [FT03] J. Fakcharoenphol and K. Talwar.  An improved decomposition theorem for graphs excluding a fixed minor.  In RANDOM-APPROX, pages 36–46,  2003\.
  * [GHR06] A. Gupta, M. T. Hajiaghayi, and H. Räcke.  Oblivious network design.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 970–979. ACM Press,  2006\.
  * [GNRS04] A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair.  Cuts, trees and l${}_{\mbox{1}}$-embeddings of graphs.  Comb., 24(2):233–269,  2004, doi:10.1007/S00493-004-0015-X.
  * [HIS13] S. Har-Peled, P. Indyk, and A. Sidiropoulos.  Euclidean spanners in high dimensions.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 804–809,  2013, doi:10.1137/1.9781611973105.57.
  * [HMO23] S. Har-Peled, M. Mendel, and D. Oláh.  Reliable spanners for metric spaces.  ACM Trans. Algorithms, 19(1):7:1–7:27,  2023, doi:10.1145/3563356.
  * [Huf52] D. A. Huffman.  A method for the construction of minimum-redundancy codes.  Proceedings of the IRE, 40(9):1098–1101,  1952, doi:10.1109/JRPROC.1952.273898.
  * [Hwa76] F. K. Hwang.  On steiner minimal trees with rectilinear distance.  SIAM Journal on Applied Mathematics, 30(1):104–114,  1976, arXiv:https://doi.org/10.1137/0130013, doi:10.1137/0130013.
  * [IMSZ10] P. Indyk, A. Magen, A. Sidiropoulos, and A. Zouzias.  Online embeddings.  In M. J. Serna, R. Shaltiel, K. Jansen, and J. D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 246–259. Springer,  2010, doi:10.1007/978-3-642-15369-3\\_19.
  * [Ind98] P. Indyk.  On approximate nearest neighbors in non-euclidean spaces.  In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA, pages 148–155. IEEE Computer Society,  1998, doi:10.1109/SFCS.1998.743438.
  * [Ind02] P. Indyk.  Approximate nearest neighbor algorithms for Fréchet distance via product metrics.  In Proceedings of the 8th Symposium on Computational Geometry, pages 102–106, Barcelona, Spain, June 2002.  ACM Press, doi:10.1145/513400.513414.
  * [IW91] M. Imase and B. M. Waxman.  Dynamic steiner tree problem.  SIAM J. Discret. Math., 4(3):369–384,  1991, doi:10.1137/0404033.
  * [JL84] W. Johnson and J. Lindenstrauss.  Extensions of Lipschitz mappings into a Hilbert space.  Contemporary Mathematics, 26:189–206, 1984.  see here.
  * [JLN+05] L. Jia, G. Lin, G. Noubir, R. Rajaraman, and R. Sundaram.  Universal approximations for tsp, steiner tree, and set cover.  In H. N. Gabow and R. Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 386–395. ACM,  2005, doi:10.1145/1060590.1060649.
  * [Joh87] D. S. Johnson.  The NP-completeness column: An ongoing guide (column 19).  Journal of Algorithms, 8(3):438–448,  1987\.
  * [KKN15] L. Kamma, R. Krauthgamer, and H. L. Nguyen.  Cutting corners cheaply, or how to remove steiner points.  SIAM J. Comput., 44(4):975–995,  2015, doi:10.1137/140951382.
  * [Kle02] P. N. Klein.  Preprocessing an undirected planar network to enable fast approximate distance queries.  In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 820–827, 2002.  see here.
  * [KLMN05] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor.  Measured descent: a new embedding method for finite metrics.  Geometric and Functional Analysis, 15(4):839–858, 2005.  preliminary version published in FOCS 2004, doi:10.1007/s00039-005-0527-6.
  * [KLR19] R. Krauthgamer, J. R. Lee, and H. Rika.  Flow-cut gaps and face covers in planar graphs.  In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 525–534. SIAM,  2019, doi:10.1137/1.9781611975482.33.
  * [KN76] G. O. H. Katona and T. O. H. Nemetz.  Huffman codes and self-information.  IEEE Trans. Inf. Theory, 22(3):337–340,  1976, doi:10.1109/TIT.1976.1055554.
  * [KPR93] P. Klein, S. A. Plotkin, and S. Rao.  Excluded minors, network decomposition, and multicommodity flow.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, STOC ’93, pages 682–690, New York, NY, USA, 1993.  ACM, doi:http://doi.acm.org/10.1145/167088.167261.
  * [Kum22] N. Kumar.  An approximate generalization of the okamura-seymour theorem.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 1093–1101. IEEE,  2022, doi:10.1109/FOCS54457.2022.00106.
  * [LLR95] N. Linial, E. London, and Y. Rabinovich.  The geometry of graphs and some of its algorithmic applications.  Comb., 15(2):215–245, 1995.  preliminary version published in FOCS 1994, doi:10.1007/BF01200757.
  * [LR10] J. R. Lee and P. Raghavendra.  Coarse differentiation and multi-flows in planar graphs.  Discret. Comput. Geom., 43(2):346–362,  2010, doi:10.1007/S00454-009-9172-4.
  * [LS23] H. Le and S. Solomon.  A unified framework for light spanners.  In B. Saha and R. A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 295–308. ACM,  2023, doi:10.1145/3564246.3585185.
  * [Lyn96] N. A. Lynch.  Distributed Algorithms.  Morgan Kaufmann,  1996\.
  * [Mat96] J. Matoušek.  On the distortion required for embedding finite metric spaces into normed spaces.  Israel Journal of Mathematics, 93(1):333–344,  1996, doi:10.1007/BF02761110.
  * [MPX13] G. L. Miller, R. Peng, and S. C. Xu.  Parallel graph decompositions using random shifts.  In G. E. Blelloch and B. Vöcking, editors, 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’13, Montreal, QC, Canada - July 23 - 25, 2013, pages 196–203. ACM,  2013, doi:10.1145/2486159.2486180.
  * [Nei16] O. Neiman.  Low dimensional embeddings of doubling metrics.  Theory Comput. Syst., 58(1):133–152,  2016, doi:10.1007/S00224-014-9567-3.
  * [NR02] I. Newman and Y. Rabinovich.  A lower bound on the distortion of embedding planar metrics into euclidean space.  In SCG ’02: Proceedings of the eighteenth annual symposium on Computational geometry, pages 94–96. ACM Press,  2002, doi:http://doi.acm.org/10.1145/513400.513412.
  * [NR20] I. Newman and Y. Rabinovich.  Online embedding of metrics.  In S. Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, volume 162 of LIPIcs, pages 32:1–32:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,  2020, doi:10.4230/LIPICS.SWAT.2020.32.
  * [OS81] H. Okamura and P. Seymour.  Multicommodity flows in planar graphs.  Journal of Combinatorial Theory, Series B, 31(1):75 – 81,  1981, doi:http://dx.doi.org/10.1016/S0095-8956(81)80012-3.
  * [Pel93] D. Peleg.  Distance-dependent distributed directories.  Inf. Comput., 103(2):270–298,  1993, doi:10.1006/INCO.1993.1020.
  * [Pel00] D. Peleg.  Distributed Computing: A Locality-Sensitive Approach.  SIAM, Philadelphia, PA,  2000, doi:10.1137/1.9780898719772.
  * [PU89] D. Peleg and E. Upfal.  A trade-off between space and efficiency for routing tables.  J. ACM, 36(3):510–530,  1989, doi:10.1145/65950.65953.
  * [Rao99] S. Rao.  Small distortion and volume preserving embeddings for planar and Euclidean metrics.  In Proceedings of the Fifteenth Annual Symposium on Computational Geometry, Miami Beach, Florida, USA, June 13-16, 1999, pages 300–306,  1999, doi:10.1145/304893.304983.
  * [RS03] N. Robertson and P. D. Seymour.  Graph minors. XVI. Excluding a non-planar graph.  Journal of Combinatoral Theory Series B, 89(1):43–76,  2003, doi:10.1016/S0095-8956(03)00042-X.
  * [SBI11] S. Srivathsan, C. Busch, and S. S. Iyengar.  Oblivious buy-at-bulk in planar graphs.  In N. Katoh and A. Kumar, editors, WALCOM: Algorithms and Computation - 5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011. Proceedings, volume 6552 of Lecture Notes in Computer Science, pages 33–44. Springer,  2011, doi:10.1007/978-3-642-19094-0\\_6.
  * [Tho04a] M. Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  Journal of the ACM, 51(6):993–1024,  2004, doi:10.1145/1039488.1039493.
  * [Tho04b] M. Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  J. ACM, 51(6):993–1024,  November 2004, doi:10.1145/1039488.1039493.
  * [TZ01] M. Thorup and U. Zwick.  Compact routing schemes.  In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4-6, 2001, pages 1–10,  2001, doi:10.1145/378580.378581.

##  Appendix A Proof of Lemma 5

We restate Lemma 5 for convenience. See 5

###### Proof.

Recall Huffman prefix free code [Huf52]. Huffman constructs a binary tree such
that each edge is associated with $\pm 1$, and the elements $X$ are the leafs.
Then $h(x)$ is simply the string obtain by traversing the unique path from the
root to $x$. It is clearly prefix free. The tree constructed as follows: pick
the two elements $x,y\in X$ with minimal weight. Let $z\notin X$, and define a
new set $X^{\prime}=X\setminus\left\\{x,y\right\\}\cup\left\\{z\right\\}$ with
the same weight function $\mu$ on $X\setminus\left\\{x,y\right\\}$, and let
$\mu(z)=\mu(x)+\mu(y)$. Note that $\mu(X^{\prime})=\mu(X)$. Construct a binary
tree recursively on $X^{\prime}$. Finally add back $x,y$ as the two children
of $z$, assigning $+1$ (resp. $-1$) to the edge $\\{z,x\\}$ (resp.
$\\{z,y\\}$). As a result we obtain a binary tree. Huffman [Huf52] proved that
this code minimizes the average length: $\sum_{x\in X}\mu(x)\cdot|h(x)|$. In
contrast, here we are interested in bounding the length of each code word
separately.

To prove the lemma, it is enough to argue for every $x$, that the root to $x$
unique path has length at most
$2\cdot\left\lceil\log\frac{\mu(X)}{\mu(x)}\right\rceil$. The proof is by
induction on $|X|$. The base case, where $|X|=1$ clearly holds as the path is
of length $0$. Next we assume $|X|\geq 2$. Consider an arbitrary point $x\in
X$. If $\mu(x)\geq\frac{1}{2}\mu(X)$, then $x$ will be “contracted” exactly
once, and thus again the lemma holds. Otherwise, if in the entire process $x$
is contracted at most twice, than again we are done (as
$2\cdot\left\lceil\log\frac{\mu(X)}{\mu(x)}\right\rceil\geq 2$). Thus we can
assume that $x$ was contracted at least three times.

Consider the the first time when $x$ is combined with some element $y$ into a
point $z$. At this time the set was $X_{i}$, and $x,y$ had the minimal weight.
In particular for every $q\in X_{i}\setminus\left\\{x,y\right\\}$,
$\mu(x)\leq\mu(q)$. Consider the first time the point $z$ is contracted with a
point $q$ into $z^{\prime}$. $q$ is combined from elements in
$X_{i}\setminus\left\\{x,y\right\\}$, and hence $\mu(x)\leq\mu(q)$. It follows
that $\mu(z^{\prime})=\mu(y)+\mu(x)+\mu(q)>2\cdot\mu(x)$. Note that in the
created tree, the path from $x$ to the root goes though $z^{\prime}$. By the
induction hypothesis, there will be a path from $z^{\prime}$ to the root of
length at most $\left\lceil
2\cdot\log\frac{\mu(X)}{\mu(z^{\prime})}\right\rceil$. It follows that there
will be a path from $x$ to the root of length at most

$2+\left\lceil
2\cdot\log\frac{\mu(X)}{\mu(z^{\prime})}\right\rceil=\left\lceil
2+2\cdot\log\frac{\mu(X)}{\mu(z^{\prime})}\right\rceil=\left\lceil
2\cdot\left(1+\log\frac{\mu(X)}{\mu(z^{\prime})}\right)\right\rceil=\left\lceil
2\cdot\log\frac{2\mu(X)}{\mu(z^{\prime})}\right\rceil\leq\left\lceil
2\cdot\log\frac{\mu(X)}{\mu(x)}\right\rceil\,,$

as required. ∎


# Emergence of rogue-like waves in a reaction-diffusion system: Stochastic
output from deterministic dynamics

Edgar Knobloch  Department of Physics, University of California, Berkeley,
California 94720, USA  Arik Yochelis<EMAIL_ADDRESS>Swiss Institute for
Dryland Environmental and Energy Research, Blaustein Institutes for Desert
Research, Ben-Gurion University of the Negev, Sede Boqer Campus, Midreshet
Ben-Gurion 8499000, Israel  Department of Physics, Ben-Gurion University of
the Negev, Be’er Sheva 8410501, Israel

###### Abstract

Rogue waves are an intriguing nonlinear phenomenon arising across different
scales, ranging from ocean waves through optics to Bose-Einstein condensate.
We describe the emergence of rogue wave-like dynamics in a reaction-diffusion
system that arise as a result of a subcritical Turing instability. This state
is present in the regime where all time-independent states are unstable, and
consists of intermittent excitation of spatially localized spikes, followed by
collapse to an unstable state and subsequent regrowth. We characterize the
spatiotemporal organization of spikes and show that in sufficiently large
domains the dynamics are consistent with a memoryless process.

Rogue waves are large excitations that appear intermittently and unpredictably
in many conservative systems arising in nature, including nonlinear optics and
ocean waves. We show here that in forced dissipative spatially distributed
systems, a subcritical Turing bifurcation may also lead to irregular and
memoryless rogue wave-like dynamics, i.e., we identify a mechanism whereby
deterministic time-dependent dynamics with stochastic properties arise even in
the absence of an oscillatory instability. Since the Turing instability is a
generic pattern-forming instability of reaction-diffusion models, our results
reveal a generic mechanism that sheds fresh light on time-dependent patterns
in physicochemical and biological applications.

Rogue waves (RW) are isolated events that “appear out of nowhere and disappear
without a trace”,[1] often referred to as freak, monster, or giant waves.[2]
RW are usually studied in the context of certain Hamiltonian models [3, 4, 5,
6, 7] describing extreme localized events in oceanic [8, 5] and atmospheric
flows,[9] and systems such as Bose-Einstein condensates,[10] nonlinear
optics,[3, 11, 12, 13, 14, 15] parametrically driven capillary waves,[16]
superfluid He,[17] and even in financial markets.[18] Recently, it has been
shown that RW may also arise in near-resonant driven dissipative systems,[19]
and in this study, we present a distinct and broadly applicable mechanism for
generating RW in a reaction-diffusion system highlighting the role of a
subcritical Turing bifurcation.

The Turing bifurcation,[20, 21] and more broadly a finite wavenumber
bifurcation,[22] is of fundamental importance in the study of steady-state
patterns in media driven far from equilibrium, particularly in reaction-
diffusion (RD) models.[22, 23, 24, 25] When the bifurcation is supercritical
one finds steady small amplitude spatially periodic patterns.[22] In the
subcritical case, these patterns are unstable, and further away from the
Turing bifurcation onset, these may transition into secondary states
consisting of unstable equidistant (repelling) localized spikes, organized in
a foliated snaking structure.[26, 27]

(a) (b) (c)

(d) (e) (f)

Figure 1: Summary of different parameter regimes (middle panel) together with
sample solutions (a-f) shown in space-time-amplitude plots of $A(x,t)$
obtained from direct numerical simulations (DNS) of Eqs. 1 with PBCs in
domains of large (a-c) and moderate (d-f) lengths, $L=200$ and $L=60$,
respectively. Rogue waves (RW) are present in $\rho_{\rm SNIPER}\approx
0.99005\lesssim\rho<\rho_{\rm T}\approx 1.0011$, i.e., between the lower left
fold of ${\bf P}_{*}$ [Fig. 2(a)] and the Turing bifurcation on ${\bf P}_{*}$.
The amplitude $A(x,t)$ of the spikes in (a-c) varies in the interval
$A\in[0.02,3.5]$, and is indicated (for some of the spikes only) using dark
colors to indicate higher amplitude. For (a-c) the initial condition is a
single spike state (at about $x=60$) embedded in the background corresponding
to the lower portion of the ${\bf P}_{*}$ branch. For (e,f) the initial
condition consists of small amplitude random perturbation of ${\bf P}_{*}$
(lower branch), while for (d) it is the minimum amplitude state along the
limit cycle of uniform oscillations, also close to ${\bf P}_{*}$. Panels (a,d)
are for $\rho=0.99\lesssim\rho_{\rm SNIPER}$, while (b,e) are for $\rho_{\rm
SNIPER}<\rho=0.995<\rho_{\rm T}$. Solutions (c,f) are computed at
$\rho=1.0\lesssim\rho_{\rm T}$ [in (f) we omit solutions for $t<30000$, in
which only negligible fluctuations about ${\bf P}_{*}$ exist, cf. $t<5000$ in
(e)].

(a) (b) (c)

Figure 2: (a) Bifurcation diagram showing the uniform steady state ${\bf
P}_{*}$ (thin black line) and the uniform periodic oscillations ${\bf P}_{\rm
O}$ (thick black line) created in $\rho<\rho_{\rm SNIPER}$ by the SNIPER
bifurcation of uniform steady states. The bifurcation diagram shows
${\text{L}}_{2}\equiv\sqrt{(LT)^{-1}\int_{0}^{T}\int_{0}^{L}\text{d}{t}\,\text{d}{x}[{\sum_{j}P_{j}^{2}+(\partial_{x}P_{j})^{2}}]}$
as a function of $\rho$, where $L$ is the domain length, $T$ is the temporal
period of ${\bf P}_{\rm O}$ solutions and $P_{j}=A,H,S,Y$. The dashed grey
line corresponds to the branch of unstable Turing solutions ${\bf P}_{\rm T}$
that emerge from the onset at $\rho=\rho_{\text{T}}$. The right axis shows the
scaling $T\sim|\rho-\rho_{\rm SNIPER}|^{-1/2}$ near $\rho_{\rm SNIPER}$ (red
line). Solid (dashed) lines for ${\bf P}_{*}$ and ${\bf P}_{\rm T}$ indicate
the temporal stability (instability) with respect to infinitesimal
perturbations; the ${\bf P}_{\rm O}$ branch is stable in the absence of all
diffusion. (b) Partial bifurcation diagram focusing on branches of
$N=1,2,\dots$ steady spikes in an $L=60$ domain present in the foliated
snaking region of panel (a). All color (thin) lines indicate unstable
solutions while the symbols L and S, and their combinations, refer to large
and small amplitude peaks, respectively, as in [26]. Color-coded solution
profiles at $\rho_{\rm SN}$ are shown to the right. (c) Temporal eigenvalues
$\sigma$ as a function of the arclength $s$ along the ${\bf P}_{\rm T}$ branch
[panel (b)], computed on a domain of length $L_{\rm T}\equiv 2\pi/k_{\rm
T}\approx 2.88$ as in Ref.[27], ranging from $\rho_{\text{T}}$ on the left
back to $\rho_{\text{T}}$ and below to $\rho=0$ on the right. The crossover
from real unstable eigenvalues to complex conjugate eigenvalues is labeled by
$\rho=\rho_{\omega}\approx 2.09$.

(a) (b) (c) (d) (e)

Figure 3: (a-d) Space-time plots of $A(x,t)$ obtained from DNS of (1) with
PBCs at $\rho=1$, showing periodic dynamics of spikes (a-c) or jumping
oscillons (d), depending on the domain length, after decay of transients. The
jumps $\Delta t\equiv t_{n+1}-t_{n}$ in time and $\Delta
x\equiv|x_{n+1}-x_{n}|$ in space, are indicated in (d). (e) Instability of a
synchronous 2-oscillon state at $\rho=0.995$, starting from the profile in (b)
at $t=15000$.

(a)
(b)
(c)
(d)
(e)

Figure 4: Space-time plots with PBCs at (a,b) $\rho=0.995$ and (c,d) $\rho=1$,
initialized with an $N=1$ peak state at (a,c) $\rho=\rho_{\text{T}}$ (blue
panels) and (b,d) $\rho=1.5$ (violet panels); see Ref.[26] for details. (e)
Average jump period $\tau$ of oscillons (color-coded dots, logarithmic scale)
evaluated after the decay of the initial $N=1$ steady state along the dashed
black lines in (a-d) for $\rho=0.991,0.993,0.995,0.997,0.999,1.0$ and compared
with the numerically computed inverse of the maximal growth rate $\sigma_{\rm
max}$ of the Turing instability (solid red curve; the red dotted line is a
$|\rho_{\text{T}}-\rho|^{-1/2}$ fit). The diamonds show the time to the first
excitation from small amplitude perturbation of ${\bf P}_{*}$, as in Figs.
1(e,f).

(a) (b) (c)

Figure 5: (a) Spatial profile at $t=138$ for $\rho=0.995$ along the green
dashed cut in Fig. 4(a) superposed on the $\rho=\rho_{\rm T}$ initial
condition in blue; inset shows that the profile is not monotonic. (b) Typical
temporal profiles of oscillating spikes at selected values of $\rho$ in
$\rho_{\text{SNIPER}}<\rho<\rho_{\text{T}}$. (c) Probability density function
(PDF) of successive spike locations in time ($\Delta t\equiv t_{n+1}-t_{n}$)
and in space ($\Delta x\equiv|x_{n+1}-x_{n}|$) in an interval of 50000 time
units [starting from the last profile in Fig. 1(c)]. The bin width in time
(space) is taken as the width of the spike at the half-height, leading to bins
of width 10 and 3, respectively; see Appendix A for further details.

As a consequence of these secondary bifurcations, the periodic solutions along
the Turing branch remain unstable even after the branch turns around and
enters the Turing-unstable regime.[28] The absence of stable Turing and
localized patterns implies that both Turing-stable and -unstable regimes are
necessarily associated with nontrivial time dependence. This study focuses on
the Turing-unstable regime and identifies a mechanism giving rise to
intermittent spatially localized spiking that ranges from periodic to rogue
wave events. The different regimes of interest and representative spiking
oscillations are summarized in Fig. 1.

For our study, we employ Meinhardt’s four-variable activator-inhibitor-
substrate model [29] in one spatial dimension, where the four fields $A$, $H$,
$S$ and $Y$ represent the concentrations of an activator, an inhibitor, the
substrate, and a marker for differentiation:[30]

$\displaystyle\frac{\partial A}{\partial t}$ $\displaystyle=$ $\displaystyle
c\dfrac{SA^{2}}{H}-\mu
A+\rho_{\text{A}}Y+D_{\text{A}}\frac{\partial^{2}A}{\partial x^{2}},$ (1a)
$\displaystyle\frac{\partial H}{\partial t}$ $\displaystyle=$ $\displaystyle
cSA^{2}-\nu H+\rho_{\text{H}}Y+D_{\text{H}}\frac{\partial^{2}H}{\partial
x^{2}},$ (1b) $\displaystyle\frac{\partial S}{\partial t}$ $\displaystyle=$
$\displaystyle c_{0}-\gamma S-\varepsilon
YS+D_{\text{S}}\frac{\partial^{2}S}{\partial x^{2}},$ (1c)
$\displaystyle\frac{\partial Y}{\partial t}$ $\displaystyle=$ $\displaystyle
dA-eY+\dfrac{Y^{2}}{1+fY^{2}}+D_{\text{Y}}\frac{\partial^{2}Y}{\partial
x^{2}}.$ (1d)

As in earlier work,[28, 26, 27, 31] we employ the inhibitor control level,
$\rho_{\text{H}}$, as a control parameter while keeping all other parameters
fixed and within the range of previous studies: $c=0.002$, $\mu=0.16$,
$\rho_{\text{A}}=0.005$, $\nu=0.04$, $c_{0}=0.02$, $\gamma=0.02$,
$\varepsilon=0.1$, $d=0.008$, $e=0.1$, $f=10$, $D_{\text{A}}=0.001$,
$D_{\text{H}}=0.02$, $D_{\text{S}}=0.01$, with $D_{\text{Y}}=10^{-7}$ to model
negligible $Y$ diffusion (in the spirit of the original model). For these
parameter values it is convenient to present our results in terms of
$\rho\equiv 10^{5}\rho_{H}$. Figure 2 shows the parameter regime of interest,
with ${\bf P}_{*}$ denoting the branch of spatially uniform states, together
with the location of the key bifurcation points $\rho=\rho_{\rm SNIPER}\approx
0.99005$ and $\rho=\rho_{\text{T}}\approx 1.0011$ on this branch. The SNIPER
bifurcation [32] generates large amplitude, spatially coherent, long period
oscillations in $\rho<\rho_{\rm SNIPER}$, labeled ${\bf P}_{\rm O}$, with
period $T$ that diverges as $(\rho_{\rm SNIPER}-\rho)^{-1/2}$ near $\rho_{\rm
SNIPER}$. Beyond $\rho_{\rm SNIPER}$ no uniform oscillations are present and
the system evolves into one of two types of spiking states, depending on
initial conditions and domain size. In contrast, the Turing bifurcation gives
rise to an unstable steady periodic pattern labeled ${\bf P}_{\rm T}$ [Fig.
2(c)].

We start by exploring the development of spiking as a function of the domain
size $L$ when $\rho=1$, as shown in Fig. 3. Panel (a) shows periodic spiking
of a single oscillon when $L=3$. Panel (b) shows stable synchronous spiking of
two oscillons when $L=6$, while (c) shows that three oscillons in an $L=12$
domain oscillate asynchronously, although their spatial location remains
fixed. When $L=24$ the spikes reorganize into a jumping oscillon (JO)
state,[33, 34, 35] i.e., a periodically oscillating and translating state, as
demonstrated in (d). Panel (e) shows that the synchronous 2-oscillon state is
unstable at $\rho=0.995$. The JO in Fig. 3(d) travels in the direction of
decreasing $x$, with jump distance $\Delta x\equiv|x_{n+1}-x_{n}|\sim 6$ and
time $\Delta t\equiv t_{n+1}-t_{n}\sim 550$ between jumps, and reemerges at
$x=0$ after a transit time of order $2500$, corresponding to translation speed
$c\sim 0.01$. Here $x_{n}$, $t_{n}$ denote the location and time of the
$n^{\rm th}$ spike as determined by its maximum.

Such JOs can evolve from small perturbations of the unstable ${\bf P}_{*}$
state or from finite amplitude spatially localized initial conditions as in
Figs. 4(a-d). These figures show the initial behavior for different
$\rho<\rho_{\text{T}}$ when an $L=60$ system is initialized with an unstable
$N=1$ steady state. In each case the $N=1$ state necessarily collapses but in
doing so it emits jumping oscillons that propagate outwards with a well-
defined speed that depends sensitively on $\rho$. Figure 4(e) shows the jump
period $\tau$ of the emitted oscillons until such time that the
counterpropagating JOs begin to interact and compares it with the inverse of
the maximal growth rate $\sigma_{\rm max}={\rm max}_{k}\sigma(k)$ of the
Turing instability of ${\bf P}_{*}$ (red curve); since the corresponding wave
number $k_{\rm max}$ approaches $k_{\rm T}$ linearly as
$\rho\to\rho_{\text{T}}$, the maximum growth rate is expected to follow
$\sigma_{\rm max}\sim|\rho-\rho_{\text{T}}|^{-1/2}$ as is indeed the case.
Thus $\tau$ grows rapidly with $\rho$ reflecting the decreasing instability
growth rate as $\rho$ approaches $\rho_{\text{T}}$. This is in contrast to the
usual behavior observed in excitable systems where the JO propagation speed
does not exhibit sensitive dependence on parameters. The resulting front-like
propagation of the spiking behavior resembles that arising in the pearling
instability [36] or the Eckhaus instability,[37] propagative behavior that is
also generated by a real eigenvalue.

In general, the JOs organize in an approximately standing pattern for smaller
values of $\rho$ and $L$, with larger domains necessary to eliminate the
influence of the domain size and the influence of the initial conditions. When
$L=60$ the JOs tend to form wavefronts consisting typically of six oscillons
in the domain, although the oscillons do not oscillate in synchrony. In
contrast, for $\rho$ sufficiently close to $\rho_{\rm T}$ and/or larger $L$
the resulting intermittent spiking consists of short duration, well-localized
spikes at apparently random locations and times [Fig. 1(a-c)]. The mean
interspike interval is an increasing function of $\rho$ as expected from the
unstable eigenvalue $\sigma_{\rm max}$ of ${\bf P}_{*}$ and by $\rho=1$ the
spiking occurs only rarely and the spatial location of the spikes is entirely
unpredictable. This state exhibits all the hallmarks of a rogue wave state,
except for the fact that the spikes emerge from (and collapse back) into a
linearly unstable state instead of a wave-like state, and are of approximately
uniform height. Both effects are a consequence of the forced-dissipative
nature of the system (1).

Figure 5(a) shows the spatial profiles of typical spikes in the RW regime. The
figure shows that the intermittent spikes achieve a larger amplitude than the
steady peaks present in $\rho>\rho_{\rm T}$ used to initialize the computation
and are triggered by small inhomogeneities in the initial condition (dashed
curve). The spatial profile of the spikes depends on the parameter $\rho$
since this quantity determines the spatial eigenvalues $\lambda$ of ${\bf
P}_{*}$ that are reflected in the tail of the spikes.[35] In contrast, Fig.
5(b) shows that the temporal profile is essentially independent of $\rho$.
This profile is asymmetric with a steep rise typical of excitable systems and
a slower collapse back to ${\bf P}_{*}$.

To characterize the RW regime, we computed the one-dimensional probability
density functions (PDFs) $P(\Delta x)$ and $P(\Delta t)$, see Appendix A for
details. These PDFs are generated by binning the data as described in Fig.
5(c) and computed at $\rho=1.0\lesssim\rho_{\rm T}$ with $L=200$. The latter
PDF is well fitted (regression coefficient $R^{2}=0.9929$) by an exponential
function (see Appendix A for details), indicating that RW generation is a
Poisson or memoryless random process. On the other hand, $P(\Delta x)$ is well
approximated (regression coefficient $R^{2}=0.9458$) by a Gamma ($\Gamma$)
distribution (see SM) as observed for RW over varying topography.[38] This
distribution works well for $\Delta x\gtrsim 30$ but greatly underestimates
separations near the favored separation $\Delta x\approx 10$ [Figs. 4(a,b)].
We conclude that in large domains spiking occurs at a fixed parameter-
dependent mean rate in time subject to lateral inhibition in space.

In this study, we have demonstrated that in dissipative, spatially distributed
systems a (subcritical) Turing bifurcation may lead to dynamics resembling
rogue waves, i.e., large amplitude waves that appear intermittently and
unpredictably in time and space. These states arise in the Turing-unstable
(supercritical) regime (here $\rho<\rho_{\rm T}$) whenever the Turing branch
(${\bf P}_{\rm T}$) remains unstable in this regime [Fig. 2(c) and Ref.[28]].
In sufficiently large domains these irregular but deterministic events
resemble a memoryless stochastic process.[39, 40] Since the Turing instability
is a generic pattern-forming instability of activator-inhibitor models,[22,
23, 24, 25] our results reveal a distinct and generic mechanism leading to
temporal dynamics that does not rely on the presence of an oscillatory
instability.[7] We expect this mechanism to operate in quasi-one-dimensional
systems obeying biochemical kinetics, ranging from the initiation of
developmental signaling [41, 42, 43] to intracellular waves,[44, 45] while
broadening the range of possible mechanisms governing complex spatiotemporal
oscillations in biophysical systems such as spontaneous otoacoustic emission
in the cochlea [46] and interspike intervals in integrate-and-fire neural
circuits.[47] Indeed, similar dynamics may have been observed in other
spatially extended systems,[48, 49] albeit in much smaller domains.

###### Acknowledgements.

We are grateful to A. van Kan for helpful comments. This work was supported in
parts by the National Science Foundation under grant DMS-1908891 (EK), by the
Israel Science Foundation under grant 1224/21 (AY), and by grant 2022072 from
the United States - Israel Binational Science Foundation (BSF), Jerusalem,
Israel (EK and AY).

## AUTHOR DECLARATIONS

Conflicts of Interest. The authors have no conflicts to disclose.

## DATA AVAILABILITY

The data that support the findings of this study are available from the
corresponding author upon reasonable request.

##  Appendix A Fitting of distributions

(a) (b)

Figure 6: Quantiles of $\Delta t$ (a) and $\Delta x$ (b) for the exponential
and Gamma ($\Gamma$) distributions (in $\bullet$), respectively, while the
insets show the PDFs [from Fig. 5(c)] on logarithmic scale. Dashed lines
represent perfect distributions while solid lines represent a linear fit with
the coefficient of determination $R^{2}$.

For fitting of the probability density function (PDF) we use two forms, as
shown in Fig. 6:
The exponential distribution

$\rm{P}(\Delta t;\eta)=\frac{1}{\eta}e^{-\Delta t/\eta},$ (2)

and the Gamma distribution

$\rm{P}(\Delta x;\alpha,\beta)=\frac{1}{\Gamma(\alpha)\beta^{\alpha}}\Delta
x^{\alpha-1}e^{-\Delta x/\beta},$ (3)

where $\Gamma(\alpha)\equiv\int_{0}^{\infty}z^{\alpha-1}e^{-z}\text{d}z$ and
$\eta=52.6484$, $\alpha=1.82757$, $\beta=37.3291$.

## REFERENCES

## References

  * Akhmediev  _et al._ [2009] N. Akhmediev, A. Ankiewicz, and M. Taki, Physics Letters A 373, 675 (2009).
  * Yan [2012] Z. Yan, in  _Journal of Physics: Conference Series_ , Vol. 400 (IOP Publishing, 2012) p. 012084.
  * Solli  _et al._ [2007] D. R. Solli, C. Ropers, P. Koonath, and B. Jalali, Nature 450, 1054 (2007).
  * Onorato  _et al._ [2013] M. Onorato, S. Residori, U. Bortolozzo, A. Montina, and F. Arecchi, Physics Reports 528, 47 (2013).
  * Pelinovsky and Kharif [2016] E. Pelinovsky and C. Kharif,  _Extreme Ocean Waves_ (Springer International Publishing, 2016) pp. 1–236.
  * Dudley  _et al._ [2019] J. M. Dudley, G. Genty, A. Mussot, A. Chabchoub, and F. Dias, Nature Reviews Physics 1, 675 (2019).
  * Tlidi and Taki [2022] M. Tlidi and M. Taki, Advances in Optics and Photonics 14, 87 (2022).
  * Dysthe  _et al._ [2008] K. Dysthe, H. E. Krogstad, and P. Müller, Annu. Rev. Fluid Mech. 40, 287 (2008).
  * Stenflo and Marklund [2010] L. Stenflo and M. Marklund, Journal of Plasma Physics 76, 293 (2010).
  * Bludov  _et al._ [2009] Y. V. Bludov, V. Konotop, and N. Akhmediev, Physical Review A 80, 033610 (2009).
  * Akhmediev  _et al._ [2013] N. Akhmediev, J. M. Dudley, D. R. Solli, and S. K. Turitsyn, Journal of Optics 15, 060201 (2013).
  * Dudley  _et al._ [2014] J. M. Dudley, F. Dias, M. Erkintalo, and G. Genty, Nature Photonics 8, 755 (2014).
  * Akhmediev  _et al._ [2016] N. Akhmediev, B. Kibler, F. Baronio, M. Belić, W.-P. Zhong, Y. Zhang, W. Chang, J. M. Soto-Crespo, P. Vouzas, P. Grelu, _et al._ , Journal of Optics 18, 063001 (2016).
  * Song  _et al._ [2020] Y. Song, Z. Wang, C. Wang, K. Panajotov, and H. Zhang, Advanced Photonics 2, 024001 (2020).
  * Rao  _et al._ [2022] J. Rao, B. A. Malomed, D. Mihalache, and J. He, Studies in Applied Mathematics 149, 843 (2022).
  * Shats  _et al._ [2010] M. Shats, H. Punzmann, and H. Xia, Physical Review Letters 104, 104503 (2010).
  * Ganshin  _et al._ [2008] A. N. Ganshin, V. B. Efimov, G. V. Kolmakov, L. P. Mezhov-Deglin, and P. V. E. McClintock, Physical Review Letters 101, 065303 (2008).
  * Yan [2010] Z.-Y. Yan, Communications in Theoretical Physics 54, 947 (2010).
  * Subramanian  _et al._ [2022] P. Subramanian, E. Knobloch, and P. G. Kevrekidis, Physical Review E 106, 014212 (2022).
  * Turing [1952] A. Turing, Philosophical Transactions of the Royal Society B 237, 37 (1952).
  * Dawes [2016] J. H. Dawes, Historia Math. 43, 49 (2016).
  * Cross and Hohenberg [1993] M. C. Cross and P. C. Hohenberg, Reviews of Modern Physics 65, 851 (1993).
  * Maini  _et al._ [1997] P. Maini, K. Painter, and H. P. Chau, Journal of the Chemical Society, Faraday Transactions 93, 3601 (1997).
  * Kondo [2002] S. Kondo, Genes to Cells 7, 535 (2002).
  * Krause  _et al._ [2021] A. L. Krause, E. A. Gaffney, P. K. Maini, and V. Klika, Philosophical Transactions of the Royal Society A 379, 20200280 (2021).
  * Knobloch and Yochelis [2021] E. Knobloch and A. Yochelis, IMA Journal of Applied Mathematics 86, 1066 (2021).
  * Knobloch and Yochelis [2022] E. Knobloch and A. Yochelis, Chaos 32, 123129 (2022).
  * Yochelis [2021] A. Yochelis, Chaos 31, 051102 (2021).
  * Meinhardt [1976] H. Meinhardt, Differentiation 6, 117 (1976).
  * Yao  _et al._ [2007] Y. Yao, S. Nowak, A. Yochelis, A. Garfinkel, and K. I. Boström, Journal of Biological Chemistry 282, 30131 (2007).
  * Knobloch and Yochelis [2023] E. Knobloch and A. Yochelis, Chaos 33, 053115 (2023).
  * Strogatz [2018] S. H. Strogatz,  _Nonlinear Dynamics and Chaos: with Applications to Physics, Biology, Chemistry, and Engineering_ (CRC press, 2018).
  * Yang  _et al._ [2006] L. Yang, A. M. Zhabotinsky, and I. R. Epstein, Physical Chemistry Chemical Physics 8, 4647 (2006).
  * Cherkashin  _et al._ [2008] A. A. Cherkashin, V. K. Vanag, and I. R. Epstein, Journal of Chemical Physics 128, 204508 (2008).
  * Knobloch  _et al._ [2021] E. Knobloch, H. Uecker, and A. Yochelis, Physical Review E 104, L062201 (2021).
  * Powers and Goldstein [1997] T. R. Powers and R. E. Goldstein, Physical Review Letters 78, 2555 (1997).
  * Ma and Knobloch [2012] Y.-P. Ma and E. Knobloch, Chaos 22, 033101 (2012).
  * Bolles  _et al._ [2019] C. T. Bolles, K. Speer, and M. Moore, Physical Review Fluids 4, 011801 (2019).
  * Yeung and Strogatz [1998] M. S. Yeung and S. H. Strogatz, Physical Review E 58, 4421 (1998).
  * Erban  _et al._ [2009] R. Erban, S. J. Chapman, I. G. Kevrekidis, and T. Vejchodský, SIAM Journal on Applied Mathematics 70, 984 (2009).
  * Affolter  _et al._ [2009] M. Affolter, R. Zeller, and E. Caussinus, Nature Reviews Molecular Cell Biology 10, 831 (2009).
  * Iber and Menshykau [2013] D. Iber and D. Menshykau, Open Biology 3, 130088 (2013).
  * Davies [2015] J. Davies, in  _Principles of Developmental Genetics_ (Elsevier, 2015) pp. 255–264.
  * Allard and Mogilner [2013] J. Allard and A. Mogilner, Curr. Opin. Cell Biol. 25, 107 (2013).
  * Beta  _et al._ [2023] C. Beta, L. Edelstein-Keshet, N. Gov, and A. Yochelis, eLife 12, e87181 (2023).
  * Shera [2022] C. A. Shera, Journal of the Association for Research in Otolaryngology 23, 17 (2022).
  * Levenstein and Okun [2023] D. Levenstein and M. Okun, Journal of Physiology 601, 3055 (2023).
  * Beaume  _et al._ [2018] C. Beaume, A. Bergeon, and E. Knobloch, Journal of Fluid Mechanics 840, 74 (2018).
  * Laing and Omel’chenko [2023] C. Laing and O. Omel’chenko, Biological Cybernetics 117, 259 (2023).