# Cavity magnomechanical storage and retrieval of quantum states

Bijita Sarma, Thomas Busch  Quantum Systems Unit, Okinawa Institute of Science
and Technology Graduate University, Okinawa 904-0495, Japan  Jason Twamley
Quantum Machines Unit, Okinawa Institute of Science and Technology Graduate
University, Okinawa 904-0495, Japan
and
Centre for Engineered Quantum Systems, Department of Physics and Astronomy,
Macquarie University, Sydney, New South Wales 2109, Australia

###### Abstract

We show how a quantum state in a microwave cavity mode can be transferred to
and stored in a phononic mode via an intermediate magnon mode in a
magnomechanical system. For this we consider a ferrimagnetic yttrium iron
garnet (YIG) sphere inserted in a microwave cavity, where the microwave and
magnon modes are coupled via a magnetic-dipole interaction and the magnon and
phonon modes in the YIG sphere are coupled via magnetostrictive forces. By
modulating the cavity and magnon detunings and the driving of the magnon mode
in time, a Stimulated Raman Adiabatic Passage (STIRAP)-like coherent transfer
becomes possible between the cavity mode and the phonon mode. The phononic
mode can be used to store the photonic quantum state for long periods as it
possesses lower damping than the photonic and magnon modes. Thus our proposed
scheme offers a possibility of using magnomechanical systems as quantum memory
for photonic quantum information.

[figure]style=plain,subcapbesideposition=top

  *

Keywords: Cavity Magnomechanics, Quantum Information Storage, Stimulated Raman
Adiabatic Passage

##  1 Introduction

The coupling between magnons in a ferrimagnetic material and phonons in a
mechanical resonator has attracted wide attention in recent years due to its
application in magnomechanical settings similar to cavity quantum
electrodynamics and optomechanics. A mechanical resonator can be coupled to an
optical cavity mode via radiation pressure interaction [1, 2], as well as to a
microwave cavity mode via an electrostatic interaction [3, 4]. Thus such
mechanical mirrors can be used as transducers for the coherent transfer
between optical and microwave fields [5, 6], or as optical wavelength
converters [7]. One of the relatively new candidates in the picture is the
magnon, a collective excitation of magnetization, which can be coupled to
phonons via the magnetostrictive force [8]. This type of coupling has better
tunability as the magnon frequency can be controlled via an external magnetic
field [9, 10, 11]. Magnons can in turn be strongly coupled to microwave cavity
modes as well, particularly in the insulating magnetic material yttrium iron
garnet (YIG). The Kittel mode [12], found in YIG spheres, can couple very
strongly to cavity photons or to superconducting quantum circuits [13],
producing a hybrid system that can be efficiently used in quantum information
processing [14, 15, 16, 17, 18, 19, 20, 21, 22, 23]. This kind of magnon-
cavity coupling can also give rise to bistable behavior as studied in [24].

Combining the magnetostrictive coupling between magnons and phonons and the
magnon-cavity coupling, a new kind of photon-magnon-phonon interaction can be
realized with YIG spheres interacting with microwave cavities. This opens up
new possibilities in quantum state engineering and control. Here we consider a
photon-magnon-phonon coupled system which is capable of transferring cavity
photons to mechanical motional phonons, enabling the storage of photonic
quantum states for long durations, thanks to the lower damping rate of the
phononic mode. Storage of quantum states and information in long-lasting modes
is very important for quantum communication networks. Photons are the usual
candidate for the flying qubits, whereas some other quantum system with a
longer coherence time is necessary for the storage of quantum information in
quantum repeaters and networks [25]. The storage of quantum states has, for
example, been previously studied in atomic media, where the information is
stored as spin excitations [26, 27, 28], in optomechanical systems [29, 30,
31], in coupled optical waveguides, or in acoustic excitations [32, 33, 34,
35].

The system we consider consists of a YIG-sphere placed inside a microwave
cavity where the magnon modes of the sphere couple with the deformation phonon
modes via a magnetostrictive force, and also to the electromagnetic cavity
modes via a magnetic dipole interaction. We drive the magnon mode with a
microwave field such that the time-modulation of the amplitude of the drive on
the magnon mode yields a time-dependent coupling strength between the magnon
and the mechanics. Using additionally time-modulated resonance frequencies of
the photonic and magnon modes, a STIRAP-like one-way transfer becomes possible
[36, 37], which efficiently transfers quantum states from the cavity mode to
the mechanical mode. The quanta can be stored in the mechanical resonator for
some time and can then be extracted using a retrieval pulse. In this way
quantum states can be stored for times longer than the cavity lifetime, due to
the lower damping rate of the phononic mode. We show that our storage protocol
can be applied to various kinds of quantum states.

##  2 Model

Figure 1: (a) Schematic of the cavity magnomechanical system where a YIG-
sphere is placed inside a microwave cavity so that the magnon modes of the
sphere interact with the cavity mode via a collective-spin-photon coupling,
and also with the deformation phonon modes via a magnetostrictive force. The
vertical dashed arrows indicate an applied magnetic field and the dynamical
magnetization causes a deformation of the YIG sphere (see top view in lower
panel), which leads to magnetostrictive coupling between magnons and phonons
[8]. (b) The coupling pulses and the detunings in units of $\omega_{b}/2\pi$,
and the variation in the cavity, magnon and phonon states for different
durations of the pulse sequence. This choice of pulses leads to a STIRAP-like
one-way transfer for quantum states from the cavity mode $a$ to the mechanical
mode $b$ and after some storage delay, a transfer back to the cavity mode. The
state to be transferred is initially in the cavity mode and the filled circles
indicate the mode that the quantum state is encoded in at particular times
during the protocol. The parameters considered here are:
$2\pi\Omega_{0}/\omega_{b}=0.1$, $\omega_{b}T=108.7$,
$\omega_{b}t_{c_{1}}=-612.2$, $\omega_{b}t_{c_{2}}=612.2$,
$\omega_{b}\tau_{ch}=164.9$, $\omega_{b}\tau=1101.6$, $\kappa_{\delta}=14.05$,
and $h_{\delta}=13.94$. Here $\kappa_{\delta}$ and $h_{\delta}$ are
dimensionless parameters.

We consider a system schematically shown in Fig. 1(a), where a YIG sphere is
inserted into a microwave cavity. The Hamiltonian of the system is given by
(note that we have set $\hbar=1$)

$\displaystyle H_{0}$ $\displaystyle=$
$\displaystyle\omega_{a}a^{\dagger}a+\omega_{m}m^{\dagger}m+\omega_{b}b^{\dagger}b+g_{ma}(a^{\dagger}m+m^{\dagger}a)+g_{mb}m^{\dagger}m(b+b^{\dagger})$
(1)
$\displaystyle+i(\varepsilon_{p}m^{\dagger}e^{-i\omega_{p}t}-\varepsilon_{p}^{\ast}me^{i\omega_{p}t}),$

where $a(a^{\dagger})$, $m(m^{\dagger})$ and $b(b^{\dagger})$ are the
annihilation (creation) operators of the microwave cavity mode, the magnon
mode and the mechanical mode with resonance frequencies $\omega_{a}$,
$\omega_{m}$ and $\omega_{b}$ respectively. The magnon frequency can be tuned
by the external bias magnetic field, $\mathcal{H}$, as
$\omega_{m}=\gamma\mathcal{H}$, where $\gamma/2\pi=28\ \rm GHz/T$ is the
gyromagnetic ratio. In addition, $g_{ma}$ and $g_{mb}$ are the single
excitation coupling rates of the cavity-magnon interaction and magnon-phonon
magnetostrictive interaction. The last term in (1) describes the external
driving of the magnon mode, where $\omega_{p}$ is the frequency of the drive
magnetic field and $\varepsilon_{p}$ is the Rabi frequency between the drive
magnetic field and the magnon mode, given by
$\epsilon_{p}=\frac{\sqrt{5}}{4}\gamma\sqrt{N}B_{0}$ [20]. Here $B_{0}$ is the
amplitude of the drive magnetic field, $N=\rho V$ is the total number of spins
in a sphere of volume $V$ and $\rho=4.22\times 10^{27}\,{\rm m^{-3}}$ is the
spin density of YIG.

Moving over to the frame rotating with the drive frequency $\omega_{p}$, given
by the transformation,
$R=\exp\big{[}i\omega_{p}\,(a^{\dagger}a+m^{\dagger}m)\,t\big{]}$, with
$H=RH_{0}R^{\dagger}+i\frac{\partial R}{\partial t}R^{\dagger}$, the
Hamiltonian of the system can be written as

$\displaystyle H$ $\displaystyle=$
$\displaystyle\Delta_{a}a^{\dagger}a+\Delta_{m}m^{\dagger}m+\omega_{b}b^{\dagger}b+g_{ma}(a^{\dagger}m+m^{\dagger}a)+g_{mb}m^{\dagger}m(b+b^{\dagger})$
(2) $\displaystyle+i(\varepsilon_{p}m^{\dagger}-\varepsilon_{p}^{\ast}m),$

where $\Delta_{a}=\omega_{a}-\omega_{p}$ and
$\Delta_{m}=\omega_{m}-\omega_{p}$ are detunings.

The dynamical evolution of the system operators can then be described by the
Langevin equations

$\displaystyle\dot{a}$ $\displaystyle=$
$\displaystyle(-i\Delta_{a}-\kappa_{a})a-ig_{ma}m+\sqrt{2\kappa_{a}}a_{\rm
in},$ $\displaystyle\dot{b}$ $\displaystyle=$
$\displaystyle(-i\omega_{b}-\kappa_{b})b-ig_{mb}m^{\dagger}m+\sqrt{2\kappa_{b}}b_{\rm
in},$ (3) $\displaystyle\dot{m}$ $\displaystyle=$
$\displaystyle(-i\Delta_{m}-\kappa_{m})m-ig_{ma}a-ig_{mb}m(b+b^{\dagger})+\varepsilon_{p}+\sqrt{2\kappa_{m}}m_{\rm
in}.$

Here $\kappa_{a},\kappa_{m}$ and $\kappa_{b}$ are the losses of the cavity
mode, the magnon mode and the mechanical mode respectively and $a_{\rm
in},m_{\rm in}$ and $b_{\rm in}$ are the noise operators with zero mean
values, and correlation functions given by $\left\langle x_{\rm in}(t)x_{\rm
in}^{\dagger}(t^{\prime})\right\rangle=(\bar{n}_{x}+1)\delta(t-t^{\prime})$,
and $\left\langle x_{\rm in}^{\dagger}(t)x_{\rm
in}(t^{\prime})\right\rangle=\bar{n}_{x}\delta(t-t^{\prime})$, with
$x=\\{a,b,m\\}$. The $\bar{n}_{a}$, $\bar{n}_{m}$ and $\bar{n}_{b}$ are the
mean thermal occupations of the cavity mode, magnon mode and phonon mode,
given by $\bar{n}_{x}=(e^{\hbar\omega_{x}/k_{B}T}-1)^{-1}$, where $T$ is the
bath temperature and $k_{B}$ is the Boltzmann constant. For strong driving,
each Heisenberg operator can be expressed as a sum of its steady-state mean
value and the quantum fluctuation, i.e., $a=\alpha+a_{1},b=\beta+b_{1}$ and
$m=\eta+m_{1}$, where $\alpha$, $\beta$, $\eta$ are the classical mean field
values of the modes and $a_{1}$, $b_{1}$, $m_{1}$ are the corresponding
quantum fluctuation operators.

Following the standard linearization approach [5, 6], the dynamics of the
quantum fluctuations is given by the linearized Hamiltonian of the form

$\displaystyle H_{\rm lin}$ $\displaystyle=$
$\displaystyle\Delta_{a}a^{\dagger}_{1}a_{1}+\tilde{\Delta}_{m}m^{\dagger}_{1}m_{1}+\omega_{b}b^{\dagger}_{1}b_{1}+G_{mb}(m_{1}+m^{\dagger}_{1})(b_{1}+b^{\dagger}_{1})$
(4) $\displaystyle+g_{ma}(m^{\dagger}_{1}a_{1}+m_{1}a^{\dagger}_{1}),$

where $G_{mb}=\eta g_{mb}$ is the coherent-driving-enhanced linearized
magnomechanical coupling strength, with
$\eta=\varepsilon_{p}(i\Delta_{a}+\kappa_{a})/(g_{ma}^{2}+i(\tilde{\Delta}_{m}+\kappa_{m})(i\Delta_{a}+\kappa_{a}))$.
Here $\tilde{\Delta}_{m}=\Delta_{m}+g_{mb}(\beta+\beta^{*})$ is the
magnomechanical interaction-induced effective magnon-drive detuning.
Transforming this Hamiltonian into an interaction picture with
$U=\exp\left[-i\omega_{b}(a^{\dagger}_{1}a_{1}+m^{\dagger}_{1}m_{1}+b^{\dagger}_{1}b_{1})t\right]$
yields

$\displaystyle H$ $\displaystyle=$
$\displaystyle\delta_{a}a^{\dagger}_{1}a_{1}+\delta_{m}m^{\dagger}_{1}m_{1}+G_{mb}\bigg{(}m^{\dagger}_{1}b_{1}+m_{1}b^{\dagger}_{1}+e^{-2i\omega_{b}t}m_{1}b_{1}+$
(5) $\displaystyle
e^{2i\omega_{b}t}m^{\dagger}_{1}b^{\dagger}_{1}\bigg{)}+g_{ma}(m^{\dagger}_{1}a_{1}+m_{1}a^{\dagger}_{1}).$

Here $\delta_{a}=\Delta_{a}-\omega_{b}$ and
$\delta_{m}=\tilde{\Delta}_{m}-\omega_{b}$ are the effective detunings. The
magnomechanical coupling, $G_{mb}$, can be varied by tuning the magnon drive
Rabi frequency, and the magnon frequency can be altered by adjusting the
strength of the external magnetic bias field [20], which can therefore be used
to tune the magnon detuning, $\delta_{m}$. The photon frequency can be
modulated by using a tunable 3D microwave cavity as realized in the Refs. [38,
39, 40, 41], which will modulate the cavity detuning, $\delta_{a}$. In the
following section we will show that, using these time-dependent modulations, a
STIRAP-like protocol can be designed to effectively transfer the microwave
cavity state to the mechanical mode and then retrieve it back to the microwave
cavity mode.

##  3 State transfer and retrieval

(a)(b)(c) Figure 2: (a) Evolution of the ‘Stokes’ eigenvalues,
$(S_{0},S_{+},S_{-})$ (dashed lines), and the instantaneous eigenvalues of the
system under the STIRAP-like pulses explained in the text (solid lines), (b)
Unitary population transfer dynamics (without any damping) of the Fock state
$|1,0,0\rangle$ showing the transfer from the microwave cavity mode to the
mechanical resonator mode and then back to the cavity mode, (c) Unitary
transfer dynamics of a coherent state with $\alpha=0.5$ in terms of the
fidelity, $F$, from the microwave cavity mode to the mechanical resonator mode
and then back to the cavity mode. The pulse parameters considered are same as
in Fig. 1.

Stimulated Raman Adiabatic Passage - or STIRAP for short - can be efficiently
used to transfer population in conventional three-level atomic systems [37,
42]. Conventional STIRAP relies on the fact that at two-photon resonance an
instantaneous eigenvector with zero eigenvalue exists, which is called a dark-
state, and which is a superposition of the initial and target states. In the
adiabatic limit the STIRAP dynamics allows to trap the population within the
‘dark state manifold’ at all times, and any population transfer to the
intermediate state, which has often a high decay rate, is avoided. The
standard STIRAP protocol then modulates the coupling strengths in time between
the two states in the dark-state manifold and the intermediate state. If this
is done using a so-called counter-intuitive pulse sequence, one can transport
population from one state in the dark-state manifold to the other state within
that manifold with perfect fidelity. However, in our system it is not suitable
to apply conventional STIRAP as the cavity-magnon coupling, $g_{ma}$, is
constant, i.e. it cannot be modulated in a time-dependent manner. We therefore
present in the following a modified STIRAP method which allows state transfer
by modulating the detunings.

(a)(b)(c)(d)(e) Figure 3: Transfer fidelities, $F(t)$, for an input coherent
state in the cavity with (a) $\alpha=0.5$, (b) $\alpha=0.75$ and (c)
$\alpha=1$. Panel (d) shows the Wigner function of the input coherent state in
the cavity mode with $\alpha=1$ and panel (e) shows the Wigner function of the
state in the cavity mode after the transfer. The phonon, magnon and cavity
mode frequencies are considered as: $\omega_{b}/2\pi=10$ MHz,
$\omega_{a}/2\pi=\omega_{m}/2\pi=10$ GHz. The pulse parameters are considered
as: $2\pi\Omega_{0}/\omega_{b}=0.1$, $T=0.01$ ms, $t_{c_{1}}=-0.061$ ms,
$t_{c_{2}}=0.061$ ms, $\tau_{ch}=0.016$ ms, $\kappa_{\delta}=14.05$,
$\tau=0.011$ ms, $h_{\delta}=13.94$. The bath temperature is considered as
$T_{\rm th}=1$ mK, and the damping rates are considered as: $\kappa_{b}=100$
Hz and $\kappa_{m}=10$ kHz.  (a)(b)(c)(d)(e) Figure 4: Transfer fidelities for
an input cat state in the cavity mode with (a) $\alpha=0.5$, (b)
$\alpha=0.75$, and (c) $\alpha=1$. Figures (d) and (e) show the input and
output Wigner functions for the cavity mode with input cat state with
$\alpha=1$. Parameters are same as in Fig. 3.

In this scheme the cavity-magnon coupling
$g_{ma}\equiv\Omega_{s}/2=\Omega_{0}/2$, which is called the ‘Stokes’ coupling
in the context of atomic STIRAP, is constant in time and the magnomechanical
coupling $G_{mb}(t)\equiv\Omega_{p}(t)/2$, which is generally known as the
‘Pump’ coupling in STIRAP, is modulated as

$\Omega_{p}(t)=\Omega_{p_{1}}(t)+\Omega_{p_{2}}(t).$ (6)

Here

$\Omega_{p_{1}}(t)=\Omega_{0}\mathrm{e}^{-\left(\frac{t-t_{c_{1}}}{T}\right)^{2}},$
(7)

and

$\Omega_{p_{2}}(t)=\Omega_{0}\mathrm{e}^{-\left(\frac{t-t_{c_{2}}}{T}\right)^{2}},$
(8)

are Gaussian-shaped pulses centered at the times $t_{c_{1}}$ and $t_{c_{2}}$,
with width $T$, and amplitude $\Omega_{0}$. Application of the pulse
$\Omega_{p_{1}}(t)$ transfers the state from the cavity to the mechanical
mode, whereas the application of the pulse $\Omega_{p_{2}}(t)$ brings the
state back to the cavity. The cavity and magnon detunings are considered as

$\displaystyle\delta_{m}(t)$
$\displaystyle=-\kappa_{\delta}h_{\delta}\frac{\Omega_{0}}{2}\left[\tanh\left(\frac{t-\tau}{\tau_{ch}}\right)+\tanh\left(\frac{t+\tau}{\tau_{ch}}\right)\right]\;,$
$\displaystyle\delta_{a}(t)$
$\displaystyle=-(\kappa_{\delta}-1)h_{\delta}\frac{\Omega_{0}}{2}\left[\tanh\left(\frac{t-\tau}{\tau_{ch}}\right)+\tanh\left(\frac{t+\tau}{\tau_{ch}}\right)\right]\;,$
(9)

so that

$\displaystyle\delta_{m}(t)-\delta_{a}(t)$ $\displaystyle=\delta_{s}(t)$
$\displaystyle=-h_{\delta}\frac{\Omega_{0}}{2}\left[\tanh\left(\frac{t-\tau}{\tau_{ch}}\right)+\tanh\left(\frac{t+\tau}{\tau_{ch}}\right)\right]\;.$
(10)

The shapes of these coupling and detuning pulses are shown in Fig. 1(b). The
choice of these pulse shapes for the magnomechanical coupling and the
detunings can be understood by looking at the instantaneous eigenvalues of the
system. In the rotating wave approximation the Hamiltonian (5) is given by

$\displaystyle H=\left[{\begin{array}[]{ccc}0&\Omega_{p}(t)/2&0\\\
\Omega_{p}^{*}(t)/2&\delta_{m}(t)&\Omega_{s}/2\\\
0&\Omega_{s}/2&\delta_{a}(t)\\\ \end{array}}\right]\;\;$ (14)

which is similar to the Hamiltonian used in STIRAP in a three-level atom with
states $|0,1,2\rangle$, where the transfer is sought from $|0\rangle$ to
$|2\rangle$ without populating $|1\rangle$. In our system this corresponds to
the transfer from $|a\rangle$ to $|b\rangle$ and vice versa in the retrieval
stage of the scheme, with no occupation of $|m\rangle$ during the storage
stage. The instantaneous eigenvalues ($\lambda_{0}$,
$\lambda_{1}$,$\lambda_{2}$) of the Hamiltonian in Eq. (11), when the time
modulated pulses are applied, are shown in Fig. 2(a) (solid lines). If we
consider the magnomechanical coupling $G_{mb}(t)$ to vanish (i.e.
$\Omega_{p}(t)=0$), the Hamiltonian is given by

$\displaystyle H_{s}=\left[{\begin{array}[]{ccc}0&0&0\\\
0&\delta_{m}(t)&\Omega_{0}/2\\\ 0&\Omega_{0}^{*}/2&\delta_{a}(t)\\\
\end{array}}\right]\;\;,$ (18)

and it acts only on the cavity-magnon subspace, i.e. it does not involve the
mechanical mode. This yields the asymptotic eigenstates
$\ket{s_{0}(t=\pm\infty)}$, and $\ket{s_{\pm}(t=\pm\infty)}$, where

$\displaystyle\ket{s_{+}(-\infty)}$
$\displaystyle\simeq\ket{\Psi_{b}}\to\ket{s_{+}(+\infty)}\simeq\ket{\Psi_{a}}\;\;,$
(19) $\displaystyle\ket{s_{-}(-\infty)}$
$\displaystyle\simeq\ket{\Psi_{a}}\to\ket{s_{-}(+\infty)}\simeq\ket{\Psi_{b}}\;\;.$
(20)

Here $\ket{\Psi_{a}}$ ($\ket{\Psi_{b}}$) are the states of the microwave
cavity (mechanical mode) and the corresponding eigenvalues are

$S_{0}=0,\quad
S_{\pm}=\frac{\delta_{a}+\delta_{m}}{2}\pm\frac{\sqrt{(\delta_{a}-\delta_{m})^{2}+\Omega_{0}^{2}}}{2}\;\;.$
(21)

The time evolution of the eigenvalues of this Stokes Hamiltonian results in
the eigenvalues $S_{\pm}(t)$ crossing the eigenvalue $S_{0}$ twice at $t\sim
t_{c_{1}}$ and $t\sim t_{c_{2}}$ as shown by the dashed lines in Fig. 2(a).
However, the application of the magnomechanical coupling $\Omega_{p}$ lifts
the degeneracy between the eigenstates $S_{-}$ and $S_{0}$ in the first
avoided crossing, and $S_{0}$ and $S_{+}$, in the second avoided crossing
(shown by the solid lines in Fig. 2(a)), which leads to state transfers at
these two points. The corresponding population transfers at these two points
for an initial Fock state in the cavity are depicted in Fig. 2(b), where we
show the time evolution of the phonon, magnon and photon mode occupancy,
$N_{b}$, $N_{m}$ and $N_{a}$ considering an initial state
$(N_{a},N_{m},N_{b})=(1,0,0)$. This behavior is obtained by solving the
Schrödinger equation without considering any coupling of the system to
external baths. One can see that the population is transferred with nearly
100% fidelity from the cavity mode $a$ to the mechanical mode $b$ and again
back to the mode $a$. The population in the magnon mode, $m$, is briefly non-
zero around $t\sim t_{c_{1}}$ and $t\sim t_{c_{2}}$, however quickly returns
to vanishing occupancy, leading to a complete transfer between the cavity and
mechanics, despite a vast difference in frequencies between them.

Next, we consider the situation where the cavity mode is initially in a
coherent state $|\Psi_{i}\rangle={\cal D}(\alpha)|0\rangle$, where ${\cal
D}(\alpha)=e^{\alpha a^{\dagger}-\alpha^{*}a}$. The performance of our quantum
memory scheme is evaluated in terms of the fidelity,
$F=\sqrt{\langle\Psi_{i}|\rho_{a}(t)|\Psi_{i}\rangle}$, which measures the
overlap of the density matrix of the instantaneous cavity state,
$\rho_{a}(t)={\rm Tr_{m,b}}[\rho(t)]$, with the initial cavity state
$|\Psi_{i}\rangle$. For an initial coherent state with $\alpha=1$ the transfer
and retrieval processes are shown in Fig. 2(c) and values of $F\sim 1$
indicate that the transferred state closely resembles the original cavity
state intended to be transferred, stored and retrieved [43]. In Fig. 2(c) the
rapid oscillations in the fidelity at the starting and ending portions of the
pulse are due to the rapid rotation of the cavity state in phase space with
large detunings. By halting the pulse at the opportune time we obtain near-
unit fidelity, which shows near-perfect transfer and retrieval.

It is to be noted that until now in our analysis, we have not taken into
account any damping existing in the system. We will therefore, in the
following, study the state transfer dynamics for various input states in a
realistic open system by coupling all modes to a thermal bath.

(a)(b)(c)(d)(e) Figure 5: The transfer fidelities for an input squeezed vacuum
state in the cavity mode with (a) $r=0.5$, (b) $r=0.75$, and (c) $r=1$.
Figures (d) and (e) show the Wigner functions for the initial and retrieved
cavity mode with input squeezed vacuum state with $r=1$. Parameters are same
as in Fig. 3.

We consider the open quantum system dynamics using the quantum master
equation,

$\displaystyle\dot{\rho}=$ $\displaystyle
i\left[\rho,H\right]+\left\\{\kappa_{a}\left(\bar{n}_{a}+1\right){\mathcal{L}}[a_{1}]+\kappa_{a}\bar{n}_{a}{\mathcal{L}}[a_{1}^{\dagger}]\right.$
(22)
$\displaystyle+\kappa_{m}\left(\bar{n}_{m}+1\right){\mathcal{L}}[m_{1}]+\kappa_{m}\bar{n}_{m}{\mathcal{L}}[m_{1}^{\dagger}]$
$\displaystyle\left.+\kappa_{b}\left(\bar{n}_{b}+1\right){\mathcal{L}}[b_{1}]+\kappa_{b}\bar{n}_{b}{\mathcal{L}}[b_{1}^{\dagger}]\right\\}\rho,$

with ${\mathcal{L}}[A]\rho\equiv A\rho
A^{\dagger}-1/2\,\\{A^{\dagger}A,\rho\\}$ representing the dissipation and
noises in the system. We consider the phonon, magnon and cavity mode
frequencies as $\omega_{b}/2\pi=10$ MHz and
$\omega_{a}/2\pi=\omega_{m}/2\pi=10$ GHz, and the bath temperature is chosen
to be $T_{\rm th}=1$ mK. Since the cavity and magnon modes oscillate at high
frequencies, coupling these to a thermal bath at mK temperatures yields almost
zero thermal occupancy, however the phonon mode is occupied. The damping rates
are considered as $\kappa_{b}=100$ Hz and $\kappa_{m}=10$ kHz. In the
following we also consider $\kappa_{a}=0$, as we are only interested in the
loss of fidelity caused by the transfer and storage processes. We start the
transfer from an initial state given by $|\alpha,0,0\rangle$, where the cavity
mode contains a coherent state, the magnon mode occupation is zero and the
mechanical mode has been precooled to the ground state [44, 45, 46].

In Fig. 3(a-c) we show the instantaneous fidelities for the transfer and
retrieval processes for the coherent state from the cavity to the mechanical
mode and back to the cavity mode for various values of $\alpha$. For all
examples the retrieval fidelity is nearly $100\%$. To further quantify the
effectiveness of the photon-phonon-photon transfer, we calculate the Wigner
function for the initial cavity state and for the cavity state after the
transfer. One can see from Figs. 3(d) and (e) that both these Wigner functions
are virtually identical with only a small shift after storage and retrieval
towards the vacuum state.

Next, we consider two slightly more complicated states. In Fig. 4, we show the
storage and retrival fidelity of an initial cat state given by
$|\Psi_{i}\rangle={\cal N}\,(|\alpha\rangle+|-\alpha\rangle)$, where ${\cal
N}$ is a normalization parameter. Panels (a)-(c) show the results for the
transfer fideltiy for $\alpha=0.5,0.75,1$ and panels (d) and (e) show the
Wigner functions for the cavity state before and after the transfer for the
state with $\alpha=1$. We also consider in Fig. 5 the squeezed vacuum state as
the initial state in the cavity given by
$|\Psi_{i}\rangle=e^{(ra^{\dagger^{2}}-r^{*}a^{2})/2}|0\rangle$, where $r$ is
the squeezing parameter. The storage fidelities for three different squeezing
strengths $r=0.5,0.75,1$ are shown in Figs. 5(a)-(c) and panels (d) and (e)
depict the Wigner functions for the cavity state before and after the transfer
with $r=1$. One can see in both cases that, even though the retrieval fidelity
is rather high, it does no longer reach the value of $F=1$. For the cat state
it decreases with increasing values of $\alpha$, which suggests that the
overall fluctuations of the two terms, $|\alpha\rangle$ and $|-\alpha\rangle$
become more prominent and are the reason for the loss of fidelity. Similarly
for squeezed states the decoherence distorts the squeezed feature in phase
space, resulting in the lower fidelity. As $r$ increases the distortion is
more pronounced, which is visible in the shape of the Wigner function of the
retrieved photon in Fig. 5(e). However, for all the input states described
here, the storage fidelity is still very high which shows that the transfer is
highly efficient.

(a)(b)(c) Figure 6: (a) Transfer fidelity with delay time $\Delta t=14\times
t_{c_{2}}$ for an input coherent state in the cavity mode with $\alpha=1$. The
phonon, magnon and cavity mode frequencies are considered as:
$\omega_{b}/2\pi=10$ MHz, $\omega_{a}/2\pi=\omega_{m}/2\pi=10$ GHz. The pulse
parameters are considered as: $2\pi\Omega_{0}/\omega_{b}=0.1$, $T=0.01$ ms,
$t_{c_{1}}=-0.061$ ms, $t_{c_{2}}=0.061$ ms, $\tau_{ch}=0.016$ ms,
$\kappa_{\delta}=14.05$, $\tau=0.011$ ms, $h_{\delta}=13.94$. The bath
temperature $T_{\rm th}=1$ mK, and the damping rates are taken as:
$\kappa_{b}=100$ Hz and $\kappa_{m}=10$ kHz. The solid orange line shows the
vacuum occupation which is reached by the cavity mode after the state transfer
to the mechanical mode as the storage time is chosen to be very long. (b) The
corresponding variation of the mode occupations with respect to the added
delay time, $\Delta t=14\times t_{c_{2}}$. (c) Variation of the retrieved
maximum fidelity, $F_{r}$ (red dots) with respect to the storage time $t_{s}$,
obtained with $\Delta t=(2\times t_{c_{2}},6\times t_{c_{2}},14\times
t_{c_{2}},30\times t_{c_{2}},66\times t_{c_{2}},100\times t_{c_{2}},135\times
t_{c_{2}},165\times t_{c_{2}},200\times t_{c_{2}},250\times t_{c_{2}})$. The
blue line shows an exponential decay fit of the form $F_{r}=Ae^{-t_{s}/t_{\rm
half}}+A_{0}$, where $t_{\rm half}$ is the half lifetime.

The above analysis shows that the mechanical mode can be used as a storage
mode for the photonic state. However, as the fidelity inevitably decays for
longer storage times, it is interesting to study how this decay happens. For
this we introduce a time-delay of the retrieval pulse by $\Delta t$, so that

$\Omega_{p_{2}}(t)=\Omega_{0}\mathrm{e}^{-\left(\frac{t-(t_{c_{2}}+\Delta
t)}{T}\right)^{2}}.$ (23)

and similar for the cavity and magnon detunings

$\displaystyle\delta_{m}(t)$
$\displaystyle=-\kappa_{\delta}h_{\delta}\frac{\Omega_{0}}{2}\left[\tanh\left(\frac{t-(\tau+\Delta
t)}{\tau_{ch}}\right)+\tanh\left(\frac{t+\tau}{\tau_{ch}}\right)\right]\;,$
$\displaystyle\delta_{a}(t)$
$\displaystyle=-(\kappa_{\delta}-1)h_{\delta}\frac{\Omega_{0}}{2}\left[\tanh\left(\frac{t-(\tau+\Delta
t)}{\tau_{ch}}\right)+\tanh\left(\frac{t+\tau}{\tau_{ch}}\right)\right]\;.$
(24)

For a cavity mode that is initially occupied by a coherent state with
$\alpha=1$ we show the dynamics of the fidelity for delay time $\Delta
t=14\times t_{c_{2}}$ in Fig. 6(a). Before the transfer the fidelity is equal
to one, but after the first set of pulses is applied, the cavity empties and
the fidelity drops to the value for the vacuum,
$F\sim|\langle\Psi_{i}|0\rangle|^{2}$ (indicated by the orange-colored line).
This means that the quantum state initially present in the cavity mode has
been almost fully transferred to the mechanical mode, from which it will be
retrieved when the second set of pulses is applied. At this point the cavity
state fidelity increases again and in Fig. 6(b) the corresponding mode
occupations are shown. One can see that the cavity mode occupation goes down
to zero after the initial transfer, while the mechanical mode occupation
rises. The latter also slowly increases during the storage period due to its
coupling to the thermal environment at $T=1\,{\rm mK}$, the steady-state
mechanical occupation tending towards $\bar{n}_{b}\sim 1.6$. During
application of the transfer pulses the magnon mode occupation rises briefly,
but also quickly returns to zero. In Fig. 6(c), we show the cavity fidelity
after retrieval, $F_{r}$ (red dots) as a function of the storage time,
$t_{s}$, with the blue line corresponding to an exponential fitting of these
results. The storage time can be calculated as the time difference between the
application of the transfer and retrieval pulses, which can be given
approximately as $t_{s}=(t_{c_{2}}+\Delta t-t_{c_{1}})$. The half-life of the
fitted exponential decay rate is given by 6 ms, where the primary loss arises
from the mechanical mode damping, which itself has a lifetime of 10 ms. The
additional small losses can therefore be attributed to magnon mode decay that
occurs during the transfer.

Figure 7: The number of retrieved cavity photons, ${{N_{a}}^{\rm final}}$, as
a function of the magnon damping rate $\kappa_{m}/\omega_{b}$ at a bath
temperature of $T_{\rm th}=10\ \rm mK$. The parameters considered here are:
$2\pi\Omega_{0}/\omega_{b}=0.5$, $\omega_{b}T=108.7/m$,
$\omega_{b}t_{c_{1}}=-612.2/m$, $\omega_{b}t_{c_{2}}=612.2/m$,
$\omega_{b}\tau_{ch}=164.9/m$, $\omega_{b}\tau=1101.6/m$, $\Delta t=0$, where
$m=5$. Also $2\pi\kappa_{b}/\omega_{b}=10^{-5}$, $\kappa_{\delta}=14.05$, and
$h_{\delta}=13.94$. Here $\kappa_{\delta}$ and $h_{\delta}$ are dimensionless
parameters.

For all the analysis above, we have assumed rather low values for the bath
temperature and the magnon damping rate, which are currently not
experimentally accessible. Let us therefore in the following explore the
effects of higher bath temperature and higher magnon damping. Since the
numerical treatment becomes very resource intensive for higher bath
occupations [47, 48], we first solve for the average values of the second-
order moments of the system analytically as described in the following.
Applying the master equation given in Eq. (22), a linear set of differential
equations for the second-order moments can be obtained as

${\partial}_{t}\left\langle{\hat{o}}_{i}{\hat{o}}_{j}\right\rangle=Tr\left(\dot{\rho}{\hat{o}}_{i}{\hat{o}}_{j}\right)=\sum_{m,n}{{\mu}_{m,n}\left\langle{\hat{o}}_{m}{\hat{o}}_{n}\right\rangle},$
(25)

where the ${\hat{o}}_{i}$, ${\hat{o}}_{j}$, ${\hat{o}}_{m}$, ${\hat{o}}_{n}$
are one of the operators: ${a}^{\dagger}_{1}$, $m^{\dagger}_{1}$,
${b}^{\dagger}_{1}$, $a_{1}$, $m_{1}$ and $b_{1}$; and ${\mu}_{m,n}$ are the
corresponding coefficients. We use this approach to time evolve the mean
occupations in the photon ($\langle a^{\dagger}_{1}a_{1}\rangle$), phonon
($\langle b^{\dagger}_{1}b_{1}\rangle$) and magnon ($\langle
m^{\dagger}_{1}m_{1}\rangle$) modes, considering that initially only the
cavity mode is occupied with $\langle N_{a}\rangle(=\langle
a^{\dagger}_{1}a_{1}\rangle)(t=0)=1$, and all the other second-order moments
are zero, with state $|N_{a},N_{m},N_{b}\rangle(t=0)=|1,0,0\rangle$.
Considering $T_{\rm th}=10\ \rm mK$, we show in Fig. 7 the retrieved photon
number in the cavity at the end of the scheme as a function of a decreasing
magnon damping rate. Here the storage time is chosen to be
$\omega_{b}t_{s}=1224.4$ which for $\omega_{b}/2\pi=10\ \rm MHz$ corresponds
to $t_{s}=0.19\ \rm ms$. One can see that, as expected, lower magnon damping
rates result in improved photon retrieval.

##  4 Conclusions

In conclusion, we have presented a scheme to transfer quantum states from a
microwave cavity mode to a mechanical mode in a photon-magnon-phonon hybrid
system where a YIG sphere is placed in a microwave cavity with the magnon mode
coupled both to the photonic and phononic modes. We have shown that using
time-modulated shapes for the detunings for the magnon and cavity modes and
also the magnetostrictive coupling, transfer with high fidelity between non-
directly coupled modes can be obtained for a number of different states
including coherent states, cat states and squeezed vacuum states. Given the
flexibilities in controlling the magnomechanical coupling, it is interesting
to consider this work as a first step for implementing mechanical bosonic
quantum error correction codes on the stored phononic quantum information to
further increase the mechanical storage times [49].

## Acknowledgements

This work was supported by the Okinawa Institute of Science and Technology
Graduate University. We are grateful for the help and support provided by the
Scientific Computing and Data Analysis section of Research Support Division at
OIST. We acknowledge support from the ARC Centre of Excellence for Engineered
Quantum Systems grant CE170100009.

## References

## References

  * [1] Kippenberg T, Rokhsari H, Carmon T, Scherer A and Vahala K 2005 Phys. Rev. Lett. 95 033901
  * [2] Arcizet O, Cohadon P F, Briant T, Pinard M and Heidmann A 2006 Nature 444 71–74
  * [3] Teufel J D, Li D, Allman M, Cicak K, Sirois A, Whittaker J and Simmonds R 2011 Nature 471 204–208
  * [4] Andrews R W, Peterson R W, Purdy T P, Cicak K, Simmonds R W, Regal C A and Lehnert K W 2014 Nature Phys. 10 321–326
  * [5] Wang Y D and Clerk A A 2012 Phys. Rev. Lett. 108 153603
  * [6] Tian L 2012 Phys. Rev. Lett. 108 153604
  * [7] Hill J T, Safavi-Naeini A H, Chan J and Painter O 2012 Nature Comm. 3 1–7
  * [8] Zhang X, Zou C L, Jiang L and Tang H X 2016 Sci. Adv. 2 e1501286
  * [9] Serga A, Chumak A and Hillebrands B 2010 J. Phys. D: Appl. Phys. 43 264002
  * [10] Lenk B, Ulrichs H, Garbs F and Münzenberg M 2011 Phys. Rep. 507 107–136
  * [11] Chumak A V, Vasyuchka V I, Serga A A and Hillebrands B 2015 Nature Phys. 11 453–461
  * [12] Kittel C 1948 Phys. Rev. 73 155–161
  * [13] Tabuchi Y, Ishino S, Noguchi A, Ishikawa T, Yamazaki R, Usami K and Nakamura Y 2015 Science 349 405–408
  * [14] Huebl H, Zollitsch C W, Lotze J, Hocke F, Greifenstein M, Marx A, Gross R and Goennenwein S T 2013 Phys. Rev. Lett. 111 127003
  * [15] Tabuchi Y, Ishino S, Ishikawa T, Yamazaki R, Usami K and Nakamura Y 2014 Phys. Rev. Lett. 113 083603
  * [16] Zhang X, Zou C L, Jiang L and Tang H X 2014 Phys. Rev. Lett. 113 156401
  * [17] Goryachev M, Farr W G, Creedon D L, Fan Y, Kostylev M and Tobar M E 2014 Phys. Rev. Appl. 2 054002
  * [18] Bai L, Harder M, Chen Y P, Fan X, Xiao J Q and Hu C M 2015 Phys. Rev. Lett. 114 227201
  * [19] Zhang D, Wang X M, Li T F, Luo X Q, Wu W, Nori F and You J 2015 npj Quantum Inf. 1 1
  * [20] Li J, Zhu S Y and Agarwal G 2018 Phys. Rev. Lett. 121 203601
  * [21] Li J, Zhu S Y and Agarwal G 2019 Phys. Rev. A 99 021801
  * [22] Li J and Gröblacher S 2021 Quant. Sci. Tech. 6 024005
  * [23] Qi S F and Jing J 2020 arXiv:2011.05642
  * [24] Wang Y P, Zhang G Q, Zhang D, Li T F, Hu C M and You J Q 2018 Phys. Rev. Lett. 120 057202
  * [25] Briegel H J, Dür W, Cirac J I and Zoller P 1998 Phys. Rev. Lett. 81 5932
  * [26] Liu C, Dutton Z, Behroozi C H and Hau L V 2001 Nature 409 490–493
  * [27] Phillips D F, Fleischhauer A, Mair A, Walsworth R L and Lukin M D 2001 Phys. Rev. Lett. 86 783
  * [28] Hammerer K, Sørensen A S and Polzik E S 2010 Rev. Mod. Phys. 82 1041
  * [29] Fiore V, Yang Y, Kuzyk M C, Barbour R, Tian L and Wang H 2011 Phys. Rev. Lett. 107 133601
  * [30] Fiore V, Dong C, Kuzyk M C and Wang H 2013 Phys. Rev. A 87 023812
  * [31] Kumar P and Bhattacharya M 2019 Phys. Rev. A 99 023811
  * [32] Yanik M F and Fan S 2004 Phys. Rev. Lett. 92 083901
  * [33] Xu Q, Dong P and Lipson M 2007 Nature Phys. 3 406–410
  * [34] Baba T 2008 Nature Photon. 2 465–473
  * [35] Zhu Z, Gauthier D J and Boyd R W 2007 Science 318 1748–1750
  * [36] Bergmann K, Nägerl H C, Panda C, Gabrielse G, Miloglyadov E, Quack M, Seyfang G, Wichmann G, Ospelkaus S, Kuhn A et al. 2019 J. Phys. B: At. Mol. Opt. Phys. 52 202001
  * [37] Bergmann K, Vitanov N V and Shore B W 2015 J. Chem. Phys. 142 170901
  * [38] Carvalho N C, Fan Y, Le Floch J M and Tobar M E 2014 Rev. Sci. Instrum. 85 104705
  * [39] C Carvalho N, Fan Y and Tobar M 2016 Rev. Sci. Instrum. 87 094702
  * [40] Clark T, Vadakkumbatt V, Souris F, Ramp H and Davis J 2018 Rev. Sci. Instrum. 89 114704
  * [41] Ramp H, Clark T, Hauer B, Doolin C, Balram K C, Srinivasan K and Davis J 2020 Appl. Phys. Lett. 116 174005
  * [42] Vitanov N V, Rangelov A A, Shore B W and Bergmann K 2017 Rev. Mod. Phys. 89 015006
  * [43] Nielsen M A and Chuang I L 2011 Quantum Computation and Quantum Information (Taylor & Francis)
  * [44] Teufel J D, Donner T, Li D, Harlow J W, Allman M, Cicak K, Sirois A J, Whittaker J D, Lehnert K W and Simmonds R W 2011 Nature 475 359–363
  * [45] Schliesser A, Del’Haye P, Nooshi N, Vahala K and Kippenberg T J 2006 Phys. Rev. Lett. 97 243905
  * [46] Sarma B, Busch T and Twamley J 2020 New J. Phys. 22 103043
  * [47] Johansson J R, Nation P D and Nori F 2012 Comput. Phys. Commun. 183 1760–1772
  * [48] Johansson J, Nation P and Nori F 2013 Comput. Phys. Commun. 184 1234–1240
  * [49] Terhal B, Conrad J and Vuillot C 2020 Quant. Sci. Tech. 5 043001


# Universality for graphs with bounded density

Noga Alon Department of Mathematics, Princeton University, USA. Email:
<EMAIL_ADDRESS>This author was supported by the NSF under grant
DMS-2154082. Natalie Dodson Middlebury College, USA. Email:
<EMAIL_ADDRESS>This author was supported by the NSF under grant
DMS-2150434. Carmen Jackson Northwestern University, USA. Email:
<EMAIL_ADDRESS>This author was supported by the NSF
under grant DMS-2150434. Rose McCarty Department of Mathematics, Princeton
University, USA. Current affiliation: School of Mathematics and School of
Computer Science, Georgia Institute of Technology, USA. Email:
<EMAIL_ADDRESS>This author was supported by the NSF under grants
DMS-2150434 and DMS-2202961. Rajko Nenadov School of Computer Science,
University of Auckland, New Zealand. Email<EMAIL_ADDRESS>Lani
Southern Willamette University, USA. Email<EMAIL_ADDRESS>This
author was supported by the NSF under grant DMS-2150434.

###### Abstract

A graph $G$ is _universal_ for a (finite) family $\mathcal{H}$ of graphs if
every $H\in\mathcal{H}$ is a subgraph of $G$. For a given family
$\mathcal{H}$, the goal is to determine the smallest number of edges an
$\mathcal{H}$-universal graph can have. With the aim of unifying a number of
recent results, we consider a family of graphs with bounded density. In
particular, we construct a graph with

$O_{d}\left(n^{2-1/(\lceil d\rceil+1)}\right)$

edges which contains every $n$-vertex graph with density at most
$d\in\mathbb{Q}$ ($d\geq 1$), which is close to a lower bound
$\Omega(n^{2-1/d-o(1)})$ obtained by counting lifts of a carefully chosen
(small) graph. When restricting the maximum degree of such graphs to be
constant, we obtain a near-optimal universality. If we further assume
$d\in\mathbb{N}$, we get an asymptotically optimal construction.

##  1 Introduction

A graph $G$ is _universal_ for a (finite) family $\mathcal{H}$ of graphs if
every $H\in\mathcal{H}$ is a (not necessarily induced) subgraph of $G$. The
complete graph with $n$ vertices is universal for the family of all graphs
with $n$ vertices, and this is clearly the smallest universal graph for this
family. However, if we restrict our attention to a family of graphs with some
additional properties, more efficient (in terms of the number of edges)
universal graphs might exist. This is a natural combinatorial question, with
applications in VLSI circuit design [15], data storage [23], and simulation of
parallel computer architecture [14].

The problem of estimating the minimum possible number of edges in a universal
graph for various families has received a considerable amount of attention.
The previous work deals with families of graphs with properties which
naturally bound their density, such as graphs with bounded maximum degree [5,
7, 6, 8, 9], forests [20, 21, 22, 28] and, more generally, graphs with bounded
degeneracy [2, 33], as well as families of graphs with additional structural
properties such as planar graphs [12, 26] and graphs with small separators
[17, 18, 19], to name a few. Our focus is on the former case. Aiming to unify
these results, we initiate the study of universality for a family of graphs
with bounded density and no other assumptions. The density of a graph $H$ is
defined as

$m(H)=\max_{H^{\prime}\subseteq H}\frac{e(H^{\prime})}{v(H^{\prime})}$

where $e(H^{\prime})$ is the numbers of edges of $H^{\prime}$ and
$v(H^{\prime})$ is the number of its vertices. In plain words, a graph $G$ has
density $d\in\mathbb{Q}$ if not only the number of edges of $G$ is at most
$v(G)d$, but this also holds for every subgraph of $G$. For $d\in\mathbb{Q}$
and $n\in\mathbb{N}$, we denote with $\mathcal{H}_{d}(n)$ the family of all
graphs with $n$ vertices and density at most $d$.

As already hinted, the family of graphs with bounded density generalizes many
interesting families. For example, graphs with maximum degree $d$ have density
at most $d/2$. Forests have density arbitrarily close to $1$, and
$d$-degenerate graphs and, more generally, graphs of arboricity $d$, have
density arbitrarily close to $d$ (a graph is $d$-degenerate if every subgraph
has minimum degree at most $d$). Note that every graph of density at most $d$
is also $\lfloor 2d\rfloor$-degenerate, thus bounded density implies bounded
degeneracy. However, as we are aiming for an optimal dependence on the
parameters, this implication does not suffice. A number of (almost-)optimal
results have been obtained in some of these cases [2, 7, 21], and we
conjecture that for all such families the bound on the size of a smallest
universal graph is largely governed by the density. Therefore, generalizing
all of these results, we believe the following is true.

######  Conjecture 1.1.

For every $d\in\mathbb{Q}$, $d>1$, and $n\in\mathbb{N}$, there exists a graph
with $G$ with

$e(G)\leq Cn^{2-1/d}$

edges which is $\mathcal{H}_{d}(n)$-universal, where $C=C(d)$.

If true, the bound in Conjecture 1.1 is the best possible up to a constant
$C$. Indeed, a simple counting argument shows that if $e(G)=o(n^{2-1/d})$ then
the number of graphs with density at most $d$ which can possibly appear in $G$
is less than the total number of such graphs. Moreover, we obtain such a lower
bound even when restricting $\mathcal{H}_{d}(n)$ to graphs with bounded
maximum degree. This is summarised in the following proposition.

######  Proposition 1.2.

For every $d\in\mathbb{Q}$ ($d\geq 1$) there exists $D\in\mathbb{N}$ and
$\alpha>0$ such that the following holds for every sufficiently large $n$. If
$G$ is an $\mathcal{H}_{d}^{D}(n)$-universal graph then

$e(G)\geq\alpha n^{2-1/d},$

where $\mathcal{H}_{d}^{D}(n)$ is the family of all graphs
$H\in\mathcal{H}_{d}(n)$ with maximum degree at most $D$.

A careful reader will notice that we require $d>1$ in Conjecture 1.1. Indeed,
if a graph $H$ has density at most $1$ then each connected component of $H$
contains at most one cycle, thus $H$ is almost a forest. For the family of all
forests it is known that $\Theta(n\log n)$ edges are both necessary and
sufficient [20, 21]. This seems to be an artifact of the fact that having only
$\Theta(n)$ edges is simply too restrictive with how we can arrange them,
which we believe is not the case when we have $O(n^{1+\varepsilon})$ edges for
any constant $\varepsilon>0$. While this justification is vague, one can draw
analogy with the theory of random graphs, where the multiplicative $\log(n)$
factor becomes unnecessary when moving from Hamilton cycles to, say, powers of
Hamilton cycles [30] (signifying the difference between unicyclic graphs and
those of density $d>1$).

A reader familiar with random graph theory [16] will notice that a random
graph with $n$ vertices and $\omega(n^{2-1/d})$ edges is likely to contain a
given graph $H$ with $m(H)\leq d$, provided $v(H)$ is significantly smaller
than $n$. However, it is known that if $v(H)$ is large then, in some cases
such as when $H$ is a collection of many triangles, a significantly denser
random graph is needed in order for $H$ to appear. It is interesting that from
the point of view of constructing universal graphs, this phenomena does not
happen.

A recent result of Allen, Böttcher, and Liebenau [2] establishes the bound in
Conjecture 1.1 (up to a $\log^{2/d}(n)$ factor) in the special case where we
restrict attention to the graphs in $\mathcal{H}_{d}(n)$ which are also
$d$-degenerate (for $d$ an integer). Moreover, using the fact that a graph of
density $d$ is $\lfloor 2d\rfloor$-degenerate, their result also implies an
upper bound of order

$O_{d}\left(n^{2-1/\lfloor 2d\rfloor}\log^{1/(2d)+o(1)}(n)\right).$

for $\mathcal{H}_{d}(n)$-universality. Our first main result, Theorem 1.3,
significantly improves this starting from $d\geq 1.5$.

######  Theorem 1.3.

For every $n\in\mathbb{N}$ and $d\in\mathbb{Q}$, $d>1$, there exists a graph
$G$ with

$e(G)\leq Cn^{2-1/(\lceil d\rceil+1)}$

edges which is $\mathcal{H}_{d}(n)$-universal, where $C=C(d)$.

As a further support towards Conjecture 1.1, we consider the family
$\mathcal{H}_{d}^{D}(n)$ of graph $H\in\mathcal{H}_{d}(n)$ with maximum degree
$D$. In this case, we get a nearly-optimal bound.

######  Theorem 1.4.

For every $D,n\in\mathbb{N}$ and $d\in\mathbb{Q}$, $d>1$, there exists a graph
$G$ with

$e(G)\leq n^{2-1/d}\cdot 2^{C\sqrt{\log n}}$

edges which is $\mathcal{H}_{q}^{D}(n)$-universal, where $C=C(D,d)$.

Finally, in the case where $d$ is an integer, we obtain an optimal bound.

######  Theorem 1.5.

For every $D,n\in\mathbb{N}$ and $d\in\mathbb{N}$, there exists a graph $G$
with

$e(G)\leq Cn^{2-1/d}$

edges which is $\mathcal{H}_{d}^{D}(n)$-universal, where $C=C(D,d)$.

Let us briefly compare these results with the previous ones. Alon and Capalbo
[7] constructed a graph with $O_{D}(n^{2-2/D})$ edges which is universal for
the family of all $n$-vertex graphs with maximum degree at most $D$. Theorem
1.5 implies this result, and further generalizes it, in the case $D$ is even.
In the case $D$ is odd, Theorem 1.4 provides a bound which is by a factor of
$2^{O(\sqrt{\log n})}$ weaker than the one from [7]. However, in comparison
with the proof from [7] which relies on the fact that bounded degree graphs
can be decomposed into path-like pieces, we use a much more general
decomposition (Lemma 3.1) which applies to all graphs with bounded density.
Moreover, Theorem 1.5 improves a result of the fifth author [33] on
universality of $d$-degenerate graphs with bounded degree, to an optimal one.
That being said, improving Theorem 1.4 is a natural first step towards
Conjecture 1.1.

######  Conjecture 1.6.

For every $D,n\in\mathbb{N}$ and $d\in\mathbb{Q}$, $d\geq 1$, there exists a
graph $G$ with

$e(G)\leq Cn^{2-1/d}$

edges which is $\mathcal{H}_{d}^{D}(n)$-universal, where $C=C(D,d)$.

Unlike in the case of graphs with arbitrarily large degree, an additional
multiplicative $\log(n)$ factor is not needed even in the case of forests
[28]. Thus we can relax the condition to $d\geq 1$.

Finally, let us briefly note that our constructions of universal graphs are
based on a _product construction_ first used by Alon and Capalbo [6, 7],
refining an earlier approach by Alon, Capalbo, Kohayakawa, Rödl, Ruciński, and
Szemerédi [9]. The proofs here also apply some of the ideas of Beck and Fiala
[13] from Discrepancy Theory, results of Feldman, Friedman and Pippenger [27]
(see also [24]) from the theory of nonblocking networks, and random walks on
expanders, together with the Matroid Decomposition Theorem of Edmonds [25].

The paper is organised as follows. In the next section we prove that the bound
in Conjecture 1.1, if true, is optimal even if we only restrict attention to
$\mathcal{H}_{d}^{D}(n)\subseteq\mathcal{H}_{d}(n)$, where the bound $D$ on
the maximum degree depends on $d$. Section 3 collects some results used in two
or all three proofs. We then proceed with proofs of our main theorems.
Comments on differences between proofs are given when appropriate. Throughout
the paper we assume, whenever this is needed, that the parameter $n$ is
sufficiently large as a function of any other parameter. To simplify the
presentation we omit all floor and ceiling signs whenever they are not
crucial.

##  2 Lower bound

Consider a (fixed) graph $F$ such that $m(F)=e(F)/v(F)$. Such graphs are
called _balanced_. Let $n\in\mathbb{N}$ be sufficiently large and divisible by
$v(F)$. We obtain a large family of $n$-vertex graphs $H$ with $m(H)=m(F)$ as
follows. Set $V(H)=V_{1}\cup\ldots\cup V_{v(F)}$, where $V_{i}$’s are disjoint
sets of size $n/v(F)$, and for each $ij\in E(G)$ put a perfect matching
between $V_{i}$ and $V_{j}$. The resulting graph $H$ is called a _lift_ of
$F$. It is not difficult to check that regardless of which perfect matching we
choose, we have $m(H)=m(F)$. The number of such (labelled) graphs $H$ is

$\left(\left(\frac{n}{v(F)}\right)!\right)^{e(F)}>\left(\frac{n}{3v(F)}\right)^{ne(F)/v(F)}.$
(1)

We use this bound to prove Proposition 1.2.

###### Proof of Proposition 1.2.

The result of Rúcinski and Vince [34] implies that for every $d\in\mathbb{Q}$,
$d\geq 1$, there exists a balanced graph $F$ with $m(F)=d$. As a lift $H$ of
$F$ has maximum degree $D=v(F)$, we have $H\in\mathcal{H}_{d}^{D}(n)$.

Suppose that a graph $G$ contains every lift of $F$ of order $n$, and let
$M=e(G)$. As every lift contains exactly $ne(F)/v(F)$ edges, by (1) we
necessarily have

$\binom{M}{ne(F)/v(F)}n!>\left(\frac{n}{3v(F)}\right)^{ne(F)/v(F)},$ (2)

as otherwise there is a lift of $F$ which does not appear in $G$. Note that
the $n!$ term on the left hand side takes into account that every choice of
$ne(F)/v(F)$ edges accounts for at most $n!$ different labeled subgraphs. We
can further upper bound the left hand side of (2) as follows:

$\binom{M}{ne(F)/v(F)}n!<\left(\frac{3M}{n}\right)^{ne(F)/v(F)}n^{n}=\left(\frac{3M}{n^{1-v(F)/e(F)}}\right)^{ne(F)/v(F)}.$

Comparing this with the right hand side of (2), we conclude

$M>\frac{1}{9v(F)}n^{2-v(F)/e(F)}=\frac{1}{9v(F)}n^{2-1/m(F)}.$

∎

##  3 Preliminaries

In the following lemma we identify a graph with its edge set. We say that a
graph is _unicyclic_ if it contains at most one cycle. The proofs of all our
three main theorems are based on the decomposition given by the following
lemma. Its proof applies some basic results from Matroid Theory, see, e.g,
[35] for the relevant notions.

######  Lemma 3.1.

Let $H$ be a simple graph satisfying $m(H)\geq 1$ and $H^{(b)}$ a multigraph
obtained from $H$ by duplicating each edge $b\in\mathbb{N}$ times. Then there
exists a partition $H^{(b)}=H_{1}\cup\ldots\cup H_{k}$, where $k=\lceil b\cdot
m(H)\rceil$, such that, for every $i\in[k]$, each component of $H_{i}$ is a
simple unicyclic graph.

###### Proof.

It suffices to prove the statement in the case $H$ is connected.

Let $\mathcal{B}$ be the family of all spanning subgraphs $B\subseteq H^{(b)}$
which are simple, connected, and unicyclic. We will shortly prove that
$\mathcal{M}=(E(H^{(b)}),\mathcal{B})$ is a matroid, with $\mathcal{B}$ being
the family of bases of $\mathcal{M}$. Assume for now that this is true.
Consider some $H^{\prime}\subseteq H^{(b)}$, and let $H^{\prime\prime}$ be the
graph obtained from $H^{\prime}$ by removing duplicate edges. Then the rank
$r(H^{\prime})$ of $H^{\prime}$ in $\mathcal{M}$ is $v(H^{\prime\prime})$ if
$H^{\prime\prime}$ contains a cycle, and $v(H^{\prime\prime})-1$ otherwise
(and note that $v(H^{\prime})=v(H^{\prime\prime})$). In the former case we
have

$|H^{\prime}|/r(H^{\prime})=e(H^{\prime})/r(H^{\prime})\leq b\cdot
e(H^{\prime\prime})/v(H^{\prime\prime})\leq b\cdot m(H).$

In the latter case we necessarily have
$e(H^{\prime\prime})<v(H^{\prime\prime})$, thus

$e(H^{\prime})/r(H^{\prime})\leq
b\cdot(v(H^{\prime\prime})-1)/(v(H^{\prime\prime})-1)=b\leq b\cdot m(H).$

By a result of Edmonds [25], one can cover $H$ with $\lceil b\cdot m(H)\rceil$
disjoint independent sets from $\mathcal{M}$, which proves the lemma.

Let us verify that $\mathcal{M}$ is indeed a matroid. Consider some distinct
bases $X,Y\in\mathcal{B}$, and let $e\in X\setminus Y$. We aim to find
$e^{\prime}\in Y\setminus X$ such that
$(X\setminus\\{e\\})\cup\\{e^{\prime}\\}\in\mathcal{B}$. If $e$ lies on the
cycle of $X$, then $X\setminus\\{e\\}$ is a tree thus adding any edge
$e^{\prime}\in Y\setminus X$ produces a spanning unicyclic graph. Otherwise,
$X\setminus\\{e\\}$ breaks $X$ into two components, a tree $X_{1}$ and a
unicyclic $X_{2}$. As $e\notin Y$, there has to exist $e^{\prime}\in
Y\setminus X$ with one endpoint in $V(X_{1})$ and the other in $V(X_{2})$.
Therefore, $(X\setminus\\{e\\})\cup\\{e^{\prime}\\}$ is again a spanning
unicyclic subgraph. ∎

In the proofs of Theorem 1.3 and Theorem 1.5, we make use of the following
simple known lemma (see, e.g., [3, Lemma 2.2]).

######  Lemma 3.2 ([3]).

For every forest $F$ with $n$ vertices and every $r\in\mathbb{N}$, there
exists a subset $R\subseteq V(F)$ of size $|R|\leq r$ such that each connected
component in $F\setminus R$ is of size at most $n/r$.

In the proofs of Theorems 1.3 and 1.4, we use the notion of a graph _blowup_ ,
thus we define it here for the reference.

######  Definition 3.3.

Given a graph $G$ and $b\in\mathbb{N}$, we define a _$b$ -blowup_ of $G$ to be
a graph $\Gamma$ on the vertex set $V(\Gamma)=\bigcup_{u\in V(G)}V_{u}$, where
each $V_{u}$ is of size $b$ and all the sets are disjoint, and there is an
edge between $a\in V_{u}$ and $b\in V_{w}$ iff $uv\in E(G)$ or $u=v$. In
particular, $\Gamma$ has $v(G)b$ vertices and $v(G)\binom{b}{2}+e(G)b^{2}$
edges.

In the proofs of Theorem 1.4 and Theorem 1.5 we make use of the so-called
_$(n,t,\lambda)$ -graphs_. These are $t$-regular graphs with $n$ vertices and
the second largest absolute eigenvalue at most $\lambda$. For small $\lambda$
such graphs are known to be good expanders. We use the following result of the
first author [4] which provides an explicit construction of such graphs for an
almost optimal value of $\lambda$ (note that a construction of Lubotzky,
Phillips, and Sarnak [31] can be used as well, even though it does not provide
a construction for every $t$).

######  Theorem 3.4.

For every $t\in\mathbb{N}$ and $n\geq n_{0}(t)$ such that $nt$ is even, there
exist an explicit construction of an $(n,t,\lambda)$-graph with $\lambda\leq
3\sqrt{t}$.

It is worth noting that the proof in [4] and the known results about the
Linnik problem imply that $n_{0}(t)\leq t^{O(1)}$. In particular, this is
relevant for the proof of Theorem 1.4.

##  4 Graphs with bounded density

We need the following lemma from Discrepancy Theory. The proof applies the
Beck-Fiala method [13]. We only use it with $q=1/2$, however, as this does not
make the proof any easier, we state it in greater generality.

######  Lemma 4.1.

The following holds for any positive integers $t$, $d$ and real $q\in[0,1]$
Let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{t}$ be a sequence of
vectors in $\mathbb{R}^{d}$, each having $\ell_{1}$-norm at most $1$. Then
there is a subset $I\subseteq\\{1,2,\ldots,t\\}$ so that

$\left\lVert\sum_{i\in
I}\mathbf{v}_{i}-q\sum_{i=1}^{t}\mathbf{v}_{i}\right\rVert_{\infty}<1.$

###### Proof.

Associate each vector $\mathbf{v}_{i}=(v_{i1},v_{i2},\ldots,v_{id})$ with a
real variable $x_{i}\in[0,1]$. Starting with $x_{i}=q$ for all $i$, we
describe an algorithm for rounding each $x_{i}$ to either $0$ or $1$ without
changing the sum $\sum x_{i}v_{i}$ by much. During this algorithm, call a
variable $x_{i}$ floating if $x_{i}$ lies in the open interval $(0,1)$,
otherwise (that is, if $x_{i}\in\\{0,1\\}$) call it fixed. Once a variable
becomes fixed it will stay fixed until the end. In each phase, the algorithm
proceeds as follows. If all variables are fixed, terminate. Otherwise, let
$F\subseteq\\{1,2,\ldots,t\\}$ denote the set of all indices of floating
variables and consider the following linear system of equations in these
variables.

For every coordinate $j\in\\{1,2,\ldots,d\\}$ for which

$\sum_{i\in F}|v_{ij}|>1,$ (3)

include the equation

$\sum_{i=1}^{t}x_{i}v_{ij}=q\sum_{i=1}^{t}v_{ij}.$ (4)

Note that only the floating variables $\\{x_{i}\colon i\in F\\}$ are
considered as variables at this point; the fixed variables are already fixed
and are treated as constants. During the algorithm, we maintain the property
that for every coordinate $j$ for which (3) holds, the equality (4) holds as
well. This is certainly true at the beginning, when $x_{i}=q$ for all $i$.

By the assumption about the $\ell_{1}$-norm of the vectors $v_{i}$, we have

$\sum_{i\in F}\sum_{j=1}^{d}|v_{ij}|\leq|F|$

and therefore the number of indices $j$ for which (3) holds is strictly
smaller than $|F|$. Thus there are more variables than equations and hence
there is a line of solutions. One can move along this line starting with the
existing point on it (that corresponds to the current value of the floating
variables $x_{i}$) until the first point in which at least one of the floating
variables $x_{i}$ becomes $0$ or $1$. Fix this variable (as well as any other
floating variables that become $0$ or $1$, if any), and continue with the next
phase. Note that the desired property is maintained since no new coordinate
$j$ can satisfy (3) as $F$ gets smaller.

Since each phase fixes at least one floating variable, the algorithm must
terminate when all the variables $x_{i}$ are fixed. Now, for a coordinate $j$,
consider the first phase when condition (3) is not satisfied. The equality (4)
holds at this phase since it is the first time (3) is not satisfied. Moreover,
for the rest of the algorithm, the value of the sum
$\sum_{i=1}^{t}x_{i}v_{ij}$ can only change by strictly less than $\sum_{i\in
F}|v_{ij}|\leq 1$, since only the floating variables change after that. This
shows that upon termination, for every index $j\in\\{1,2,\ldots,d\\}$,

$\left|\sum_{i=1}^{t}x_{i}v_{ij}-q\sum_{i=1}^{t}v_{ij}\right|<1.$

Therefore the set $I=\\{i:x_{i}=1\\}$ of all indices in which the final value
of $x_{i}$ is $1$ satisfies the conclusion of the lemma. ∎

By repeated application of the previous lemma, we get the following.

######  Corollary 4.2.

The following holds for any three positive integers $t,d,m=2^{k}$. Let
$\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{t}$ be a sequence of vectors
in $\mathbb{R}^{d}$, each having $\ell_{1}$-norm at most $1$. Then there is a
partition of the vectors into $m$ pairwise disjoint sets $\\{v_{i}\colon i\in
I_{p}\\}$, $1\leq p\leq m$, where $[t]=I_{1}\cup\ldots\cup I_{m}$, the sets
$I_{j}$ are pairwise disjoint, and for every $p\in[m]$ we have

$\left\lVert\sum_{i\in
I_{p}}\mathbf{v}_{i}-\frac{1}{m}\sum_{i=1}^{t}\mathbf{v}_{i}\right\rVert_{\infty}\leq\sum_{i=0}^{k-1}2^{-i}<2.$

###### Proof.

We prove the statement by induction on $k$. For $k=1$ it is equivalent to
Lemma 4.1 with $q=1/2$. Suppose that it hold for $m=2^{k-1}$, for $k\geq 2$.
We show that then it also holds for $m=2^{k}$.

Apply Lemma 4.1 with $q=1/2$ to split the vectors into two collections,
$[t]=C_{1}\cup C_{2}$, such that for $i\in\\{1,2\\}$ we have

$\left\lVert\sum_{i\in
C_{i}}\mathbf{v}_{i}-\frac{1}{2}\sum_{i=1}^{t}\mathbf{v}_{i}\right\rVert_{\infty}<1.$
(5)

By the induction hypothesis, there is a partition $C_{1}=I_{1}\cup\ldots\cup
I_{m/2}$ such that for each $p\in[m/2]$ we have

$\left\lVert\sum_{i\in I_{p}}\mathbf{v}_{i}-\frac{2}{m}\sum_{i\in
C_{1}}\mathbf{v}_{i}\right\rVert_{\infty}\leq\sum_{i=0}^{k-2}2^{-i}.$ (6)

By the triangle inequality, from (5) and (6) we conclude

$\left\lVert\sum_{i\in
I_{p}}\mathbf{v}_{i}-\frac{1}{m}\sum_{i=1}^{t}\mathbf{v}_{i}\right\rVert_{\infty}=\left\lVert\left(\sum_{i\in
I_{p}}\mathbf{v}_{i}-\frac{2}{m}\sum_{i\in
C_{1}}\mathbf{v}_{i}\right)+\frac{2}{m}\left(\sum_{i\in
C_{1}}\mathbf{v}_{i}-\frac{1}{2}\sum_{i=1}^{t}\mathbf{v}_{i}\right)\right\rVert_{\infty}\leq\sum_{i=0}^{k-2}2^{-i}+2/m.$

The same argument applies to $C_{2}$, which gives a desired partition
$[t]=I_{1}\cup\ldots\cup I_{m}$. ∎

###### Proof of Theorem 1.3.

Note that it suffices to prove the theorem for $d\in\mathbb{N}$.

Let $m$ be the smallest power of $2$ that is at least $n^{1/(d+1)}$, and
suppose $m\geq 4$. First, form a graph $\Gamma$ on the vertex set $[m]^{d}$
where two vertices $\mathbf{u}=(u_{1},u_{2},\ldots,u_{d})$ and
$\mathbf{v}=(v_{1},v_{2},\ldots,v_{d})$ are connected if $u_{i}=v_{i}$ for
some $i\in[d]$. The graph $\Gamma^{+}$ is the $(3m+3)$-blowup of $\Gamma$ (see
Definition 3.3) together with another set $V^{+}$ of $2dn/m$ vertices and all
edges incident with at least one of them. Note that $\Gamma^{+}$ has
$O(dn^{1-1/(d+1)})$ edges. We proceed to show that it is
$\mathcal{H}_{d}(n)$-universal.

Consider some $H\in\mathcal{H}_{d}(n)$. Let $H=H_{1}\cup\ldots\cup H_{d}$ be a
decomposition given by Lemma 3.1 (with $b=1$), and recall that each component,
of each $H_{i}$, is unicyclic. First form $R^{\prime}\subset V(H)$ as follows:
For every $i\in[d]$ and every component of $H_{i}$ of size at least $m$, take
one vertex from a cycle in that component (if such exist). This adds up to at
most $dn/m$ vertices. Next, by applying Lemma 3.2 with $F=H_{i}\setminus
R^{\prime}$ (which is now a forest) and $r=n/m$ for each $i\in[d]$, we obtain
a set $R\subseteq V(H)$ of size $|R|\leq dn/m$ such that each connected
component of $H_{i}\setminus(R\cup R^{\prime})$ is of size at most $m$. All
the vertices of $R\cup R^{\prime}$ will be mapped into $V^{+}$, thus we can
set $H=H\setminus(R\cup R^{\prime})$ and $H_{i}=H_{i}\setminus(R\cup
R^{\prime})$.

Let $\mathcal{C}_{i}$ denote the family of connected components in $H_{i}$ (we
identify a connected component by its vertex set). For each $h\in V(H)$, let
$c_{i}(h)$ denote the component $K\in\mathcal{C}_{i}$ that contains $h$. We
show, by induction on $i$, that there exist functions
$\phi_{i}\colon\mathcal{C}_{i}\mapsto[m]$ such that for each $i\in[d]$ and
every $\mathbf{v}=(v_{1},v_{2},\ldots,v_{i})\in[m]^{i}$ we have

$|S_{\mathbf{v}}|\leq\frac{n}{m^{i}}+2m+3$ (7)

where

$S_{\mathbf{v}}=\\{h\in
V(H):\phi_{1}(c_{1}(h))=v_{1},\phi_{2}(c_{2}(h))=v_{2},\ldots,\phi_{i}(c_{i}(h))=v_{i}\\}.$

Once we have this for $i=d$, by injectively mapping each $S_{\mathbf{v}}$ into
the blowup of $\mathbf{v}$, for $\mathbf{v}\in[m]^{d}$, we obtain an embedding
of $H$ in $\Gamma^{+}$.

Inequality (7) trivially holds for $i=0$. Suppose that (7) holds for some
$i-1$, for $i\in[d]$. We show we can find $\phi_{i}$ so that it holds for $i$.
For each connected component $K\in\mathcal{C}_{i}$ define a vector
$\mathbf{v}_{K}$ of length $m^{i-1}$ indexed by the vectors
$\mathbf{u}=(u_{1},u_{2},\ldots,u_{i-1})\in[m]^{i-1}$ as follows: The
coordinate of $\mathbf{v}_{K}$ indexed by $\mathbf{u}$ is the number of
vertices $h\in K$ such that

$\phi_{1}(c_{1}(h))=u_{1},\;\phi_{2}(c_{2}(h))=u_{2},\ldots,\;\phi_{i-1}(c_{i-1}(h))=u_{i-1}.$

Note that the $\ell_{1}$-norm of each $\mathbf{v}_{K}$ is the number of
vertices of $K$, which is at most $m$. In addition, the sum of all the vectors
$\mathbf{v}_{K}$ in each coordinate $\mathbf{u}$ is exactly
$|S_{\mathbf{u}}|$, which, by the induction hypothesis, is at most
$n/m^{i-1}+2m+3$.

By Corollary 4.2 these vectors can be partitioned into $m$ pairwise disjoint
collections so that the sum of the vectors in each collection, and with
respect to each coordinate, is at most

$\frac{n/m^{i-1}+2m+3}{m}+2m\leq n/m^{i}+2m+3.$

The value of $\phi_{i}(K)$ is now set to be the index of the collection
containing $K$, implying the required inequality for $i$ and completing the
proof. ∎

##  5 Graphs with bounded density and degree

The basic idea behind the proofs of Theorem 1.4 and Theorem 1.5 is similar to
that in the proof of Theorem 1.3. In Theorem 1.3 we obtain $n^{-1/(d+1)}$
instead of desired $n^{-1/d}$ because, in each of the $d$ steps, we assign the
same coordinate to all the vertices of a connected component in $H_{i}$.
Intuitively, if same vertices of $H$ belong to the same connected component
across each $H_{i}$, this is not sufficient to disambiguate them and we are
forced to take a small blowup at the end.

When $H$ has bounded maximum degree, we avoid this by using the following
idea, at least in the case $d\in\mathbb{N}$: Our basic graph $\Gamma$ is again
defined on the vertex set $[m]^{d}$ (now with $m\approx n^{1/d}$), however
this time we connect $\mathbf{v},\mathbf{u}\in[m]^{d}$ by an edge if some
$v_{i}$ and $u_{i}$ are connected by an edge in a bounded-degree expander $G$
on the vertex set $[m]$, which we fix upfront. Instead of mapping all the
vertices of one component of $H_{i}$ into a single coordinate, we disperse
them across $[m]$ by using edges of the expander $G$. In Theorem 1.5 we can
make this approach disambiguate all the vertices of $H$, thus avoiding the use
of a final blowup all together. In Theorem 1.4 the number of vertices which
are pairwise ambiguous ends up being of order $2^{O(\sqrt{\log n})}$, thus we
take a very small blowup at the end – significantly smaller than in the proof
of Theorem 1.3 – to deal with this.

The proof of Theorem 1.4, presented next, borrows ideas of using random walks
in expanders from [6]. One significant difficulty in the proof of Theorem 1.4
is that we are not able to split $H_{i}$ into small connected components and
we have to deal with the whole $H_{i}$ at once, which further emphasizes
dispersion via expanders. The proof of Theorem 1.5 generalizes the approach
from [7] from embedding paths in expanders, in a specific way, to embedding
bounded-degree trees. This is done using some of the ideas in [27] and [24].

###  5.1 Density bounded by a rational

We use the following well known property of random walks on expanders, see,
e.g., [29].

######  Lemma 5.1.

Let $G$ be an $(n,t,\lambda)$-graph, and consider a random walk starting in a
given vertex $v\in V(G)$. The probability that after exactly $\ell$ steps we
finish in a vertex $w\in V(G)$ is at most

$1/n+(\lambda/t)^{\ell}.$

#### Randomized tree homomorphism.

Given a tree $T$ with the designated root $r$ and a graph $G$, we use the
following randomized procedure for constructing a homomorphism $\phi\colon
T\hookrightarrow G$:

  1. (i)

Consider any ordering $h_{1},\ldots,h_{n}$ of $V(T)$ such that $h_{1}=r$ and,
for each $i\geq 2$, $h_{i}$ has exactly one neighbour within
$\\{h_{1},\ldots,h_{i-1}\\}$.

  2. (ii)

Take $s_{1}\in V(G)$ to be some upfront chosen vertex in $V(G)$.

  3. (iii)

For $i=\\{2,\ldots,n\\}$, sequentially, take $s_{i}$ to be a neighbour of
$s_{j}$ in $G$ chosen uniformly at random, where $j<i$ is a unique index such
that $h_{j}h_{i}\in T$.

The homomorphism is then given by $\phi(h_{i}):=s_{i}$. Note that the ordering
of the vertices $h_{2},\ldots,h_{n}$ plays no role in the distribution of
$\phi$, as long as each vertex other than $h_{1}$ has exactly one predecessor.

######  Lemma 5.2.

Let $G$ be an $(m,t,3\sqrt{t})$-graph where $t=2^{\sqrt{\log n}}$ and $n\geq
m$. Suppose $T$ is a tree with the root $r$, and $U\subseteq
V(T)\setminus\\{r\\}$ a subset such that every two $t,t^{\prime}\in
U\cup\\{r\\}$ are at distance at least $16\sqrt{\log n}$ in $T$. Let $\phi$ be
a random homomorphism $\phi\colon T\hookrightarrow G$ obtained by the
described procedure. Then, for any $v\in V(G)$, the size of the set

$U_{v}=\\{u\in U\colon\phi(u)=v\\}$

is stochastically dominated by a binomial random variable
$B(|U|,1/m+1/n^{3})$.

###### Proof.

Let $u_{1},\ldots,u_{k}$ be an ordering of the vertices in $U$ such that if
$u_{j}$ is closer to $r$ than $u_{i}$, then $j<i$. Let $P_{1}$ be the path
from $r$ to $u_{1}$ and set $x_{1}=r$. For each $2\leq i\leq k$, define the
path $P_{i}$ as follows:

  * •

Let $x_{i}\in V(T)$ be the first vertex on a path from $u_{i}$ to $r$ which
belongs to $\bigcup_{j<i}V(P_{j})$;

  * •

Set $P_{i}$ to be the path from $x_{i}$ to $u_{i}$.

Importantly, for every $i\in[k]$ we have $|P_{i}|\geq 8\sqrt{\log n}$. Let us
quickly prove this. As $x_{i}\in\bigcup_{j<i}V(P_{j})$ we have $x_{i}\in
V(P_{j})$, for some $j<i$. That implies $u_{j}$ is not further from $r$ than
$u_{i}$, thus the path from $x_{i}$ to $u_{j}$ is not larger than $|P_{i}|$.
Therefore $u_{i}$ and $u_{j}$ are at distance at most $2|P_{i}|$, which gives
the desired lower bound.

We now describe an equivalent way of generating $\phi$:

  1. (i)

Set $\phi(r)$ to be the upfront chosen vertex $s_{1}$ in $V(G)$.

  2. (ii)

For each $i\in[k]$, sequentially, extend the partial mapping $\phi$ to
$V(P_{i})\setminus\\{x_{i}\\}$ by taking a random walk of length $|P_{i}|$
which starts in $\phi(x_{i})$.

  3. (iii)

Let $f_{1},\ldots,f_{k^{\prime}}$ be an ordering of the vertices in

$V_{P}=V(T)\setminus\bigcup_{i\in[k]}V(P_{i})$

such that each $f_{i}$ has exactly one neighbour $f_{i}^{\prime}\in
V_{P}\cup\\{f_{1},\ldots,f_{i-1}\\}$. Sequentially, for $i\in[k^{\prime}]$,
extend $\phi$ to $f_{i}$ by taking a random neighbour of
$\phi(f_{i}^{\prime})$.

By Lemma 5.1 we have

$\Pr[\phi(u_{i})=v\mid\phi(u_{1}),\ldots,\phi(u_{i-1})]\leq
1/m+(4/\sqrt{t})^{|P_{i}|}<1/m+1/n^{3},$

thus the conclusion of the lemma follows. ∎

Finally, we make use of the following lemma which allows us to treat unicyclic
graphs as trees.

######  Lemma 5.3.

Let $H$ be a connected unicyclic graph. Then there exists a tree $T$ on the
same vertex set such that $\Delta(T)\leq\Delta(H)$ and $H\subseteq T^{2}$.

###### Proof.

Let $v_{1},\ldots,v_{k}\in V(H)$ be the vertices along the cycle in $H$. Form
a tree $T$ by removing the edges on the cycle in $H$, and adding the edges on
the path $v_{1}v_{k}v_{2}v_{k-1}v_{3}v_{k-2}\ldots v_{k^{\prime}}$, where
$k^{\prime}=\lceil(k+1)/2\rceil$. ∎

We are ready to prove Theorem 1.4.

###### Proof of Theorem 1.4.

Suppose $d=a/b$, for some $a,b\in\mathbb{N}$ with $a\geq b$. Let $m=n^{1/a}$
and $t=2^{\sqrt{\log n}}$, and let $G$ be an $(m,t,3\sqrt{t})$-graph on the
vertex set $[m]^{a}$ (see Theorem 3.4). We form the graph $\Gamma$ as follows:
$V(\Gamma)=[m]^{a}$, and two vertices $\mathbf{v}=(v_{1},\ldots,v_{a})$ and
$\mathbf{w}=(w_{1},\ldots,w_{a})$ are connected by an edge iff there exist at
least $b$ distinct indices $i_{1},\ldots,i_{b}\in[a]$ such that $v_{j}w_{j}\in
G^{2}$, for each $j\in\\{i_{1},\ldots,i_{b}\\}$. Finally, take $\Gamma^{+}$ to
be a $(2^{C\sqrt{\log n}})$-blowup of $\Gamma$, for $C$ being a sufficiently
large constant. The graph $\Gamma^{+}$ has

$O\left(n^{2-b/a}\cdot 2^{2C\sqrt{\log n}}\right)$

edges. It remains to show that $\Gamma^{+}$ is
$\mathcal{H}_{d}^{D}(n)$-universal.

Consider some $H\in\mathcal{H}_{d}^{D}(n)$. Applying Lemma 3.1 with $b$, we
obtain subgraphs $H_{1},\ldots,H_{a}\subseteq H$ such that each connected
component, of each $H_{i}$, is unicyclic, and each edge $e\in H$ belongs to
exactly $b$ of these subgraphs. By Lemma 5.3, for each component $H_{i}$ there
exists a forest $T_{i}$ such that $H_{i}\subseteq T_{i}^{2}$ and
$\Delta(T_{i})\leq D$. Therefore, any homomorphism of $T_{i}$ into $G$ is also
a homomorphism of $H_{i}$ into $G^{2}$. By adding edges across leaves of some
components in $T_{i}$, we can assume that $T_{i}$ is a spanning tree on the
vertex set $V(H)$. Let $r\in V(H)$ be an arbitrary vertex which will serve as
the root of every tree $T_{i}$.

Form an auxiliary graph $A$ by taking an edge between $h,h^{\prime}\in V(H)$
iff they are at distance at most $16\sqrt{\log n}$ in some $T_{i}$. Then

$\Delta(A)\leq aD^{16\sqrt{\log n}}.$

Take $U_{0}\subseteq V(H)$ to be the set of all vertices in $V(H)$ which are
neighbours of $r$ in $A$, together with $r$ itself. Using Hajnal-Szemerédi
theorem, partition $V(H)\setminus U_{0}$ into independent sets
$U_{1},\ldots,U_{\Delta(A)+1}$ in $A$.

Our goal is to find homomorphisms $\phi_{i}\colon T_{i}\hookrightarrow G$ such
that, for each $i\in[a]$, $\mathbf{v}=(v_{1},\ldots,v_{i})\in[m]^{i}$ and
$j\in\\{1,\ldots,\Delta(A)+1\\}$, we have

$|S_{\mathbf{v}}^{j}|\leq\max\\{2n^{(a-i)/a},4\log n\\},$ (8)

where

$S_{\mathbf{v}}^{j}=\\{h\in
U_{j}\colon\phi_{1}(h)=v_{1},\ldots,\phi_{i}(h)=v_{i}\\}.$

This implies that, for every $\mathbf{v}=(v_{1},\ldots,v_{a})\in[m]^{a}$, the
set

$S_{\mathbf{v}}=\\{h\in
V(H)\colon\phi_{1}(h)=v_{1},\ldots,\phi_{a}(h)=v_{a}\\}$

is of size

$|S_{\mathbf{v}}|\leq|U_{0}|+(\Delta(A)+1)\cdot 4\log n<2^{C\sqrt{\log n}},$

thus by injectivelly mapping $S_{\mathbf{v}}$ into the blowup of $\mathbf{v}$,
we obtain a copy of $H$ in $\Gamma^{+}$.

Suppose that we have found $\phi_{1},\ldots,\phi_{i-1}$ such that (8) holds.
Let $\phi_{i}\colon T_{i}\hookrightarrow G$ be a random homomorphism generated
as described at the beginning of this section. By Lemma 5.2 and standard
estimates of the binomial distribution, this holds for one particular choice
of $\mathbf{v}=(v_{1},\ldots,v_{i})$ and $j\in\\{1,\ldots,\Delta(A)+1\\}$ with
probability at least $1-1/n^{2}$. Therefore, by the union-bound, it holds for
all choices with positive probability, thus a desired homomorphism exists. ∎

###  5.2 Density bounded by an integer

The following lemma replaces the use of randomness in the proof of Theorem 1.4
and is the core of the proof of Theorem 1.5.

######  Lemma 5.4.

For every $D\in\mathbb{N}$ there exist $t\in\mathbb{N}$ and $\varepsilon>0$
such that the following holds. Let $G$ be an $(n,t,3\sqrt{t})$-graph, and let
$T$ be a tree with $v(T)\leq n/(3t)$ vertices and maximum degree
$\Delta(T)\leq D$. Then for any family of subsets $\\{S_{v}\subseteq
V(G)\\}_{v\in V(T)}$ with $|S_{v}|\geq(1-\varepsilon)n$ for each $v\in V(T)$,
there exists an embedding $\phi\colon T\rightarrow G$ such that $\phi(v)\in
S_{v}$ for every $v\in V(T)$.

The main machinery underlying the proof of Lemma 5.4 is a result from the
theory of _nonblocking networks_ , due to Feldman, Friedman, and Pippenger
[27, Proposition 1]. An efficient algorithmic version of this result was
obtained by Aggarwal et al. [1].

######  Definition 5.5.

Given $t,s\in\mathbb{N}$, we say that a bipartite graph $B=(V_{1}\cup
V_{2},E)$ is _$(t,s)$ -nonblocking_ if there exists a family $\mathcal{S}$ of
subsets of $E$, called the _safe_ states, such that the following holds:

  1. (P1)

$\emptyset\in\mathcal{S}$,

  2. (P2)

if $E^{\prime\prime}\subseteq E^{\prime}$ and $E^{\prime}\in\mathcal{S}$ then
$E^{\prime\prime}\in\mathcal{S}$, and

  3. (P3)

given $E^{\prime}\in\mathcal{S}$ of size $|E^{\prime}|<s$ and a vertex $v\in
V_{1}$ with $\deg_{E^{\prime}}(v)<t$ (that is, $v$ is incident to less than
$t$ edges in $E^{\prime}$), there exists an edge $e=(v,w)\in E\setminus
E^{\prime}$ such that $E^{\prime}\cup\\{e\\}\in\mathcal{S}$ and $w$ is not
incident to any edge in $E^{\prime}$.

######  Lemma 5.6 ([27]).

Let $B=(V_{1}\cup V_{2},E)$ be a bipartite graph and $a,t\in\mathbb{N}$. If

$|N_{B}(X)|\geq 2t|X|$

for every $X\subseteq V_{1}$ of size $1\leq|X|\leq 2a$, then $B$ is
$(t,ta)$-nonblocking.

We are now ready to prove Lemma 5.4.

###### Proof of Lemma 5.4.

Let $h_{1},\ldots,h_{r}$ be an ordering of the vertices of $T$ such that for
each $2\leq i\leq r=v(T)$, $h_{i}$ has exactly one neighbour within
$\\{h_{1},\ldots,h_{i-1}\\}$. For $i\in\\{r,\ldots,1\\}$, iteratively, define
the set $A_{i}\subseteq S_{h_{i}}$ as follows: If $h_{i}$ does not have a
neighbour within $\\{h_{i+1},\ldots,h_{r}\\}$, set $A_{i}=S_{h_{i}}$;
otherwise, let $R_{i}=\\{j>i\colon h_{i}h_{j}\in T\\}$ and set

$A_{i}=\\{v\in S_{h_{i}}\colon|N_{G}(v,A_{j})|\geq(1-\beta)t\text{ for every
}j\in R_{i}\\},$

where $\beta>0$ is a sufficiently small constant we will specify shortly. We
show that each $A_{i}$ is of size $|A_{i}|\geq(1-2\varepsilon)n$. This clearly
holds for $i=r$. Suppose that it holds for $A_{i+1},\ldots,A_{r}$, for some
$1\leq i\leq r-1$. We show that it then holds for $A_{i}$ as well. We can
assume $R_{i}\neq\emptyset$, as otherwise we are immediately done. Suppose,
towards a contradiction, that $|A_{i}|<(1-2\varepsilon)n$. As $|R_{i}|\leq D$,
there exists $j\in R_{i}$ such that the set

$X=\\{v\in S_{h_{i}}\colon|N_{G}(v,A_{j})|<(1-\beta)t\\}$

is of size $|X|\geq\varepsilon n/D$. By the definition of $X$ and [11, Theorem
9.2.4], we have

$|X|(\beta-2\varepsilon)^{2}t^{2}\leq\sum_{v\in
X}\left(|N_{G}(v,A_{j})|-(1-2\varepsilon)t\right)^{2}\leq 9t\cdot 2\varepsilon
n.$

For $t>18D/(\beta-2\varepsilon)^{2}$ this gives $|X|<\varepsilon n/D$, thus a
contradiction.

Before we move to the embedding of $T$, we need another bit of preparation.
Let $B$ be the bipartite graph on the vertex set $V(G)\times\\{1,2\\}$ where
$(v,i)$ and $(w,j)$ are connected by an edge iff $vw\in G$ and $i\neq j$. By,
e.g. [10, Lemma 2.4], for sufficiently small $\beta>0$ we have

$|N_{B}(X\times\\{1\\})|\geq 4\beta t|X|$

for each $X\subseteq V(G)$ of size $|X|\leq 2n/t$. Therefore, by Lemma 5.6,
$B$ is $(2\beta t,n/t)$-nonblocking.

We find distinct vertices $s_{1},\ldots,s_{r}\in V(G)$ such that mapping
$h_{i}$ to $h_{i}$ gives a copy of $T$ in $G$. Throughout the procedure we
maintain a _safe_ subset $E\subseteq B$ (see Definition 5.5), which is
initially empty. First choose arbitrary $s_{1}\in A_{1}$. Then, for each
$2\leq i\leq r$, sequentially, do the following:

  1. (i)

Let $j<i$ be the unique index such that $h_{j}h_{i}\in T$.

  2. (ii)

Obtain $E\subset E^{\prime}\in\mathcal{S}$ by repeatedly applying 3 with
$v=(s_{j},1)$, such that at the end we have
$\deg_{E^{\prime}}((s_{j},1))=2\beta t$.

  3. (iii)

Choose an edge $((s_{j},1),(w,2))\in E^{\prime}\setminus E$ such that $w\in
A_{i}\setminus\\{s_{1}\\}$. Set $s_{i}:=w$ and $E=E\cup\\{(s_{i},2)\\}$.

Note that $E$ remains a safe subset throughout the procedure. It is also
evident from the description of the procedure that $\deg_{E}(v)\leq\Delta(T)$
for every $v\in V(G)\times\\{1\\}$, and $|E|<v(T)$. As $v(T)+2\beta h<n/(2h)$,
step ii is well-defined. It remains to show that a desired edge in iii always
exists. Consider some step $i$. As $s_{j}\in A_{j}$ and
$\deg_{E^{\prime}}(s_{j})=2\beta t$, by the definition of $A_{j}$ we have

$|N_{E^{\prime}}(s_{j},A_{i})|\geq\beta t,$

thus $\deg_{E}(s_{j})\leq D<\beta t-1$ (by choosing $t$ to be sufficiently
large) implies the desired edge indeed exists. Note that we need to explicitly
exclude $s_{1}$ in iii as $(s_{1},2)$ is not an endpoint of any edge in $E$. ∎

Note that in the previous proof, one could as well use [24, Theorem 2.8]. For
our purposes, we find Lemma 5.6 to provide cleaner framework.

###### Proof of Theorem 1.5.

Let $t\in\mathbb{N}$ and $\varepsilon>0$ be as given by Lemma 5.4.
Furthermore, let $m=Cn^{1/d}$, for sufficiently large $C$, and let $G$ be an
$(m,t,3\sqrt{t})$-graph on the vertex set $[m]$ (see Theorem 3.4). We first
construct $\Gamma$ as follows: $V(\Gamma_{n})=[m]^{d}$ and two vertices
$\mathbf{v}=(v_{1},\ldots,v_{k})$ and $\mathbf{w}=(w_{1},\ldots,w_{k})$ are
connected by an edge iff there exists $i\in[d]$ such that $v_{i}w_{i}\in G$.
Note that $\Gamma$ has $O(n)$ vertices and $O(n^{2-1/d})$ edges. Finally, we
construct $\Gamma^{+}$ by adding a new set $V^{+}$ of $2dn/m$ vertices and
adding all the edges incident to at least one vertex in $V^{+}$. The number of
edges of $\Gamma^{+}$ remains $O(n^{2-1/d})$. We show that $\Gamma^{+}$ is
$\mathcal{H}_{d}^{D}(n)$-universal.

Consider some $H\in\mathcal{H}_{d}^{D}(n)$, and let $H=H_{1}\cup\ldots\cup
H_{d}$ be a decomposition of $H$ given by Lemma 3.1 (with $b=1$). We clean-up
$H_{i}$’s as in the proof of Theorem 1.3. First form $R^{\prime}\subset V(H)$
as follows: For every $i\in[d]$ and every component of $H_{i}$ of size at
least $m$, take one vertex from a cycle in that component (if such exist).
This adds up to at most $dn/m$ vertices. Next, by applying Lemma 3.2 with
$F=H_{i}\setminus R^{\prime}$ (which is now a forest) and $r=n/m$ for each
$i\in[d]$, we obtain a set $R\subseteq V(H)$ of size $|R|\leq dn/m$ such that
each connected component of $H_{i}\setminus(R\cup R^{\prime})$ is of size at
most $m$. All the vertices of $R\cup R^{\prime}$ will be mapped into $V^{+}$,
thus we can set $H=H\setminus(R\cup R^{\prime})$ and
$H_{i}=H_{i}\setminus(R\cup R^{\prime})$.

We iteratively find homomorphisms $\phi_{i}\colon H_{i}\hookrightarrow G$ such
that, for each $\mathbf{v}=(v_{1},\ldots,v_{i})\in[m]^{i}$, we have

$|S_{\mathbf{v}}|\leq n^{(d-i)/d},$ (9)

where

$S_{\mathbf{v}}=\left\\{h\in
V(H)\colon\phi_{1}(h)=v_{1},\ldots,\phi_{i}(h)=v_{i}\right\\}.$

Once we have this, a homomorphism $\phi\colon H\hookrightarrow\Gamma$ given by
$\phi(h)=(\phi_{1}(h),\ldots,\phi_{k}(h))$ is an injection, thus $H$ is indeed
a subgraph of $\Gamma$.

Suppose we have found homomorphisms $\phi_{1},\ldots,\phi_{i-1}$, for some
$i\in[d]$, such that (9) holds. To find a desired homomorphism $\phi_{i}\colon
H_{i}\hookrightarrow G$, we do the following. Take trees in $H_{i}$ one at a
time, in an arbitrary order, and extend $\phi_{i}$ to the current tree $T$ by
taking an embedding of $T$ into $G$ with each $w\in T$ mapped to
$S_{w}=V(G)\setminus R_{w}$, where

$R_{w}=\\{v\in V(G)\colon\exists S_{\mathbf{v}}=(v_{1},\ldots,v_{i-1},v)\text{
such that }|S_{\mathbf{v}}|=n^{(d-i)/d}\text{ and }w\in
S_{\mathbf{v}}^{-}\\},$

where $S_{\mathbf{v}}$ is defined with respect to the current partial
homomorphism $\phi_{i}$ and $S_{\mathbf{v}}^{-}=(v_{1},\ldots,v_{i-1})$. By
taking $C$ to be sufficiently large we have $|R_{w}|<\varepsilon m$, thus we
can apply Lemma 5.4 to find a desired embedding. ∎

Finally, we are in position to say something about the difference between the
proofs of Theorem 1.4 and Theorem 1.5. In Theorem 1.5 we are able to ‘cut’
forests in such a way that each tree is of size $o(v(G))$, where $G$ is an
expander. This greatly helps us with planning how to embed the vertices such
that the homomorphisms are as dispersed as possible: Embed one tree, revise
forbidden subsets for images of some vertices, embed the next tree, revise,
and so on. The fact that for each next tree we can freely choose where the
root is embedded makes it possible to implement this strategy. In contrast, in
the proof of Theorem 1.4 we cannot ‘cut’ forests in this way: We would need to
remove $O(n^{1-1/a})$ vertices, resulting in $O(n^{2-1/a})$ edges in
$\Gamma^{+}$ which is way too much. Instead we need to find a homomorphism of
the whole $H_{i}$ at once, and consequently we cannot do the planning one tree
at a time. We resort to randomness, and drift away from the optimal bound in
order to beat certain union bound. It would be interesting to improve this and
resolve Conjecture 1.6.

##  6 Concluding remarks and open problems

  * •

It is possible to decrease the number of vertices in the constructions in all
three main theorems to $(1+\varepsilon)n$, increasing the number of edges by a
factor of $c(\varepsilon)$. This can be done following the construction in
Theorem 5 of [9] which is based on an appropriate concentrator (unbalanced
expander).

  * •

The proofs of all theorems provide efficient (deterministic or randomized)
algorithms for embedding a given input graph $H$ of the corresponding family
in the appropriate universal graph.

  * •

The proof of Theorem 1.3 can be easily extended to provide economical
universal graphs for any family of graphs on $n$ vertices in which the edges
of each graph in the family can be partitioned into a given number $d$ of
subgraphs from a family with strongly sublinear separators. Indeed it need
only be possible to break each of these subgraphs into small connected
components by removing a relatively small number of vertices. The number of
edges will depend on the size of the separators.

  * •

There are several natural classes of sparse graphs that are subsets of the
family of graphs with appropriate bounded density. Notable examples are graphs
with a bounded acyclic chromatic number, graphs with a bounded arboricity,
degenerate graphs and graphs with a bounded maximum degree. Here are some
brief details.

The acyclic chromatic number of a graph $H$ is the minimum integer $k$ so that
there is a proper vertex coloring of $H$ by $k$ colors and the vertices of
each cycle of $H$ receive at least $3$ distinct colors. Equivalently this
means that there is a proper vertex coloring of $H$ by $k$ colors so that the
induced subgraph on the union of any two color classes is ayclic, that is, a
forest. A graph $H$ is $k$-degenerate if every subgraph of it contains a
vertex of degree at most $k$. A graph has arboricity $k$ if its edge-set can
be partitioned into $k$ forests.

It is not difficult to check that if the acylic chromatic number of a graph
$H$ is $k$, then every nonempty subset $U$ of its vertices spans at most
$(k-1)(|U|-1)$ edges. Therefore, by Edmonds’ Matroid Decomposition Theorem
[25] (which for the graphic matroid that is the one relevant here has been
proved earlier by Nash-Williams [32]), the arboricity of $H$ is at most $k-1$.
If the aroboricity is at most $k-1$ then the density $m(H)$ is also clearly at
most $k-1$. Another simple observation is that if $H$ is $d$-degenerate, then
its arboricity (and hence also its density) is at most $d$. Finally it is
obvious that if the maximum degree of $H$ is $t$ then its density is at most
$t/2$. It follows that the main theorems in this paper also provide economical
constructions of universal graphs for the families of $n$-vertex graphs in
each of these classes.

  * •

The main open problem remaining is the assertion of Conjecture 1.1 for all
rationals $d>1$. The results proved here as well as the special cases
established in [2, 7, 21] indicate that it is likely to hold in full
generality.

## Acknowledgements

This project began at the 2023 REU “Combinatorics and Coding Theory in the
Tropics” which was run by Anant Godbole and Fernando Piñero. The authors are
grateful to them for their impact, as well as to other participants of the
REU, especially Mackenzie Bookamer, Sarah Capute, and Liza Ter-Saakov. We also
thank Kalina Petrova for pointing out a helpful reference.

## References

  * [1] A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber, and M. Sudan.  Efficient routing in optical networks.  J. ACM, 43(6):973–1001, 1996.
  * [2] P. Allen, J. Böttcher, and A. Liebenau.  Universality for graphs of bounded degeneracy.  arXiv preprint arXiv:2309.05468, 2023.
  * [3] N. Alon.  Covering a hypergraph of subgraphs.  Discrete Math., 257(2-3):249–254, 2002.
  * [4] N. Alon.  Explicit expanders of every degree and size.  Combinatorica, 41(4):447–463, 2021.
  * [5] N. Alon and V. Asodi.  Sparse universal graphs.  J. Comput. Appl. Math., 142(1):1–11, 2002.
  * [6] N. Alon and M. Capalbo.  Sparse universal graphs for bounded-degree graphs.  Random Struct. Algorithms, 31(2):123–133, 2007.
  * [7] N. Alon and M. Capalbo.  Optimal universal graphs with deterministic embedding.  In Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20–22, 2008, pages 373–378. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2008.
  * [8] N. Alon, M. Capalbo, Y. Kohayakawa, V. Rodl, A. Rucinski, and E. Szemerédi.  Universality and tolerance.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 14–21. IEEE, 2000.
  * [9] N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi.  Near-optimum universal graphs for graphs with bounded degrees.  In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 170–180. Springer, 2001.
  * [10] N. Alon, E. Mossel, and R. Pemantle.  Distributed corruption detection in networks.  Theory Comput., 16:23, 2020.  Id/No 1.
  * [11] N. Alon and J. H. Spencer.  The probabilistic method.  Wiley-Intersci. Ser. Discrete Math. Optim. Hoboken, NJ: John Wiley & Sons, 4th edition edition, 2016.
  * [12] L. Babai, F. R. K. Chung, P. Erdős, R. L. Graham, and J. H. Spencer.  On graphs which contain all sparse graphs.  Ann. Discrete Math. 12, 21-26 (1982)., 1982.
  * [13] J. Beck and T. Fiala.  “Integer-making” theorems.  Discrete Appl. Math., 3:1–8, 1981.
  * [14] S. Bhatt, F. Chung, T. Leighton, and A. Rosenberg.  Optimal simulations of tree machines.  In 27th Annual Symposium on Foundations of Computer Science, pages 274–282. IEEE, 1986.
  * [15] S. Bhatt and T. Leighton.  A framework for solving VLSI graph layout problems.  J. Comput. Syst. Sci., 28:300–343, 1984.
  * [16] B. Bollobás.  Threshold functions for small subgraphs.  Math. Proc. Camb. Philos. Soc., 90:197–206, 1981.
  * [17] M. Capalbo.  Small universal graphs for bounded-degree planar graphs.  Combinatorica, 22(3):345–359, 2002.
  * [18] M. R. Capalbo and S. R. Kosaraju.  Small universal graphs.  In Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999, pages 741–749. New York, NY: ACM, Association for Computing Machinery, 1999.
  * [19] F. R. K. Chung.  Separator theorems and their applications.  Paths, flows, and VLSI-layout, Proc. Meet., Bonn/Ger. 1988, Algorithms Comb. 9, 17-34., 1990.
  * [20] F. R. K. Chung and R. L. Graham.  On graphs which contain all small trees.  J. Comb. Theory, Ser. B, 24:14–23, 1978.
  * [21] F. R. K. Chung and R. L. Graham.  On universal graphs for spanning trees.  J. Lond. Math. Soc., II. Ser., 27:203–211, 1983.
  * [22] F. R. K. Chung, R. L. Graham, and N. Pippenger.  On graphs which contain all small trees. II.  Combinatorics, Keszthely 1976, Colloq. Math. Soc. Janos Bolyai 18, 213-223 (1978)., 1978.
  * [23] F. R. K. Chung, A. L. Rosenberg, and L. Snyder.  Perfect storage representations for families of data structures.  SIAM J. Algebraic Discrete Methods, 4:548–565, 1983.
  * [24] N. Draganić, M. Krivelevich, and R. Nenadov.  Rolling backwards can move you forward: on embedding problems in sparse expanders.  Trans. Am. Math. Soc., 375(7):5195–5216, 2022.
  * [25] J. Edmonds.  Minimum partition of a matroid into independent subsets.  J. Res. Natl. Bur. Stand., Sect. B, 69:67–72, 1965.
  * [26] L. Esperet, G. Joret, and P. Morin.  Sparse universal graphs for planarity.  J. Lond. Math. Soc., II. Ser., 108(4):1333–1357, 2023.
  * [27] P. Feldman, J. Friedman, and N. Pippenger.  Wide-sense nonblocking networks.  SIAM J. Discrete Math., 1(2):158–173, 1988.
  * [28] J. Friedman and N. Pippenger.  Expanding graphs contain all small trees.  Combinatorica, 7:71–76, 1987.
  * [29] S. Hoory, N. Linial, and A. Wigderson.  Expander graphs and their applications.  Bull. Amer. Math. Soc., 43(04):439–562.
  * [30] J. Kahn, B. Narayanan, and J. Park.  The threshold for the square of a Hamilton cycle.  Proc. Am. Math. Soc., 149(8):3201–3208, 2021.
  * [31] A. Lubotzky, R. Phillips, and P. Sarnak.  Ramanujan graphs.  Combinatorica, 8(3):261–277, 1988.
  * [32] C. St. J. A. Nash-Williams.  Decomposition of finite graphs into forests.  J. London Math. Soc., 39 (1964), 12.
  * [33] R. Nenadov.  Ramsey and universality properties of random graphs.  PhD thesis, ETH Zurich, 2016.
  * [34] A. Ruciński and A. Vince.  Strongly balanced graphs and random graphs.  J. Graph Theory, 10(2):251–264, 1986.
  * [35] D. J. A. Welsh.  Matroid Theory.  L. M. S. Monographs, No. 8. Academic Press, London - New York, 1976, xi+433 pp.