2021

[1]Sushil Mujumdar

[1]Nano-optics and Mesoscopic Optics Laboratory, Tata Institute of Fundamental
Research, 1, Dr. Homi Bhabha Road, Mumbai, 400005, Maharashtra, India

#  Quantum echo route towards exceptional points in Anderson localized lasers

Krishna Joshi<EMAIL_ADDRESS>*

###### Abstract

Exceptional points, that are spectral degeneracies in the parameter space of
non-Hermitian systems, have evoked a massive interest in the optical domain
owing to their striking consequences on optical behavior of commonly known
systems. Through careful engineering of gain and loss, exceptional points have
been demonstrated in a variety of photonic systems ranging from optical fibers
to chaotic cavities, exhibiting extra-ordinary phenomena and augmented
functionalities. However, in the domain of disordered systems, there are still
no realizations of exceptional points even though mode-coupling and non-
Hermitian behavior is amply demonstrated. The obvious challenge lies in the
probabilistic nature of disorder, which is a difficult candidate for
parametric control. Here, we exploit the probabilistic nature of Anderson
localizing systems by implementing thousands of disorder configurations. We
demonstrate statistical occurrences of lasing over exceptional points. Our
route towards exceptional points begins with detection of quantum echoes,
which are temporal signatures of coupling between modes. Quantum echoes
unambiguously set apart two coupled modes from a pair of two isolated modes
that are spectrally close perchance. Simultaneous temporal, spectral and
spatial investigations provide corroborative evidence of the convergence of
eigenvalues and eigenvectors in the approach to the exceptional points.
Ultimately, the vanishing of the echo and coalescence of spectral peaks and
spatial intensity distributions, accompanied by the square-Lorentzian
lineshape of lasing peaks, identify the exceptional point, at which the lasing
intensity is seen to be significantly higher.

###### keywords:

Exceptional points, Anderson localization, Non-Hermitian optical systems

##  1 Main

A recent, high-impact development in the field of photonics has been the
revelation of parity-time symmetric systems endowed with rich novel
physicsbender1999pt ; bender1998real ; el2018non ; ruter2010observation ;
regensburger2012parity ; jing2014pt ; lin2011unidirectional ; zhu2014p ;
benisty2011implementation ; ding2015coalescence . At the barycenter of the
literature on PT-symmetry in photonics lie peculiar spectral degeneracies
called the exceptional pointspeng2014parity ; peng2014loss ;
cerjan2016exceptional ; feng2013experimental ; jing2017high ;
ding2016emergence ; kang2016chiral ; zhen2015spawning . Originating from the
realm of quantum mechanics, exceptional points (EPs) signify singularities at
which the eigenvalues and eigenfunctions of non-Hermitian matrices cannot be
described analyticallyheiss2012physics ; kato1966analytic . At the EP, two or
more eigenvalues coalesce, simultaneously with the coalescence of associated
eigenfunctionsheiss1999phases ; moiseyev2011non ; el2007theory ;
pick2017general . This theoretical construct has led to immense physical
consequences in real experimental systemsmiri2019exceptional . Previously
discussed in the quantum theory of atomic and molecular
resonancesmoiseyev1998quantum , EPs are now demonstrated in carefully designed
photonic systems motivated by the upgradation of systemic functionalities,
such as, for instance, enhancement in output intensityfeng2014single ;
hodaei2014parity ; takata2021observing  and increased sensing
capabilityhodaei2017enhanced ; chen2017exceptional ; hokmabadi2019non . The
ability of precise nanofabrication and on-demand gain/loss has allowed for the
realization of several photonic platforms for the observation of
EPsozdemir2019parity ; brandstetter2014reversing . However, to our knowledge,
there are no experimental reports of observations of EPs in disordered
mesoscopic systems despite several investigations on non-Hermiticity in such
systemsvazquez2014gain ; bachelard2022coalescence ; davy2019probing ;
huang2021wave ; weidemann2020nonhermitian ; balasubrahmaniyam2020necklace ;
sahoo2022anomalous .

The procedure of demonstration of exceptional points in photonic structures
has typically followed a common theme. The gain or loss parameter in one
cavity is systematically tuned while the emission spectrum and the spatial
intensity in the sample is monitored. For example, in a coupled microring
system, the authors fabricated two physically identical microrings at a pre-
defined separation and couplinghodaei2014parity ; hodaei2015parity . Optical
excitation provided gain, and the loss in one of the cavities was continuously
tuned by filtering out the pump energy. At the exceptional point, the lasing
exclusively occurred over one microring, and the emission intensity was
considerably higher than that from an individual microring pumped at par. This
strategy has been adopted in various photonic systems takata2021observing ;
kim2016direct ; chang2014parity ; peng2014loss  that are carefully designed
using physically separate cavities with tunable gain/loss. However, such a
strategy is not feasible in an Anderson-localizing
structureanderson1958absence ; john1987strong ; segev2013anderson ;
chabanov2000statistical ; wiersma1997localization ; sapienza2010cavity ;
schwartz2007transport ; lahini2008anderson ; riboli2011anderson  for several
reasons. Anderson-localizing systems are nondeterministic, wherein the
occurrence of a resonance is probabilistic. In a situation of coupled modes,
both the cavities reside in the same physical structure and often involve
common scatterers for distributed feedback. Naturally, calibrated introduction
of gain/loss into individual localized modes is inconceivable. Hence, the
conventional strategy of observing exceptional points is implausible in
Anderson-localizing systems. In such a nondeterministic scenario, another
route towards an EP can be adopted. The formation of an EP within a localizing
system is a probabilistic event. Therefore, if a sufficiently large number of
configurations can be generated and monitored, then an exceptional point can
be expected with the right probability. Although easily said, this is a
challenging prospect because the three ingredients , namely, (i) achieving
Anderson localization, (ii) achieving coupled modes thereof, and (iii)
addition of adequate gain/loss into the system, are all formidable
experimental challenges. Nonetheless, this is the route we adopt in this work,
and demonstrate Anderson-localization based lasing over exceptional points.

We use a technique which allows us to create and monitor thousands of disorder
configurationsjoshi2020reduction ; joshi2022anomalous . The system is one-
dimensional, and hence has an increased probability of Anderson localization
and, therefore, coupled Anderson-localized modes. Optical sources are
distributed throughout the structure so that any localized modes existing at
any spatial location are readily excited. We employ a simultaneous spectral,
spatial and temporal diagnostic setup to completely characterize the emission
from the microcavity array. The introduction of temporal diagnostics is a
vital step towards identification of coupled modes. Usually, coupling is
identified on the basis of spectral splitting. However, the spectra of
Anderson localizing systems are random and multimodal in character. One cannot
unambiguously distinguish a coupled-mode splitting from a pair of individual
isolated modes with comparable spectral separation. On the other hand, the
temporal signatures of the two cases are fundamentally different and provide
conclusive evidence of splitting. Since temporal diagnostics are hitherto not
reported at EP in lasing systems, we first simulate a deterministic prototype
lasing structure and introduce the systematic temporal, spectral and spatial
behavior at, and during the approach to, an EP. The EP-approach is
characterized by quantum echoes (QE) that signify energy transfer between the
coupled resonances, equivalent to Rabi oscillations in two-level
systemsdietz2007rabi ; dembowski2004first . The echoes vanish at the EP.
Subsequently, we illustrate the experimental results in our system wherein the
spectra exhibit coupled modes via spectral splitting and the temporal
diagnostics simultaneously exhibit quantum echoes. The spatial intensity
distributions exhibit the expected supermodes of the coupled system. The
approach to an EP is evident in reduced splittings and lower oscillation
frequencies, accompanied by increased output intensity. Eventually, emission
peaks with largely enhanced intensity are shown, wherein the spatial intensity
resides exclusively in one Anderson-localizing cavity. In these cases, the
spectral profiles are seen to follow a square-Lorentzian profile, identifying
an EP.

Figure 1: Quantum echo diagnosis of an exceptional point in a simulated,
deterministic, model system: (a) Temporal evolution of emission from two
coupled microring resonators, as computed from finite-difference time-domain
computations. Top panel: Situation for spectral splitting of
$\delta\lambda=3.6~{}$nm. Blue curve shows the echo in the emission at one
wavelength, showing a period of $T$ ($=\frac{1}{\Omega}$, where $\Omega$ is
the echo frequency). The echo in the emission at the other wavelength (orange
curve) is out of phase, quantified by $\Delta T/T$. Middle panel: Dynamics for
$\delta\lambda=1~{}$nm, where $T$ is increased, while the $\Delta T/T$ is
reduced. Bottom panel: Behavior at the exceptional point (EP), i.e,
$\delta\lambda=0~{}$nm, where there is no echo or oscillation. A single
temporal profile is seen because of the eigenvalue coalescence. (b) Spectro-
spatial observations corresponding to (a). Insets show intensity distribution
in the coupled system averaged over the entire echo. The energy resides in
both the resonators at large splittings, while it exists exclusively in the
amplifying resonator at the EP. (c) Phase difference ($\Delta T/T$) in the two
echoes (blue markers, left Y axis) reduces systematically with
$\delta\lambda$, and is zero at the EP. Peak emission intensity (red markers,
right Y-axis) $I_{p}$ diverges at the EP. Inset shows $\Omega$ with
$\delta\lambda$. (d) Correspondence between the quantum echo behavior of (a)
and PT-symmetry breaking and EP-formation. Circle markers mark the situations
in (a) and (b).

We first illustrate the quantum echo in a known EP system, namely, a coupled
microring cavity. We simulate identical resonators with a diameter of
$d=2.0~{}\mu$m, thickness $t=0.2~{}\mu$m and a separation $s=0.4~{}\mu m$. The
system was simulated using a finite-difference time-domain scheme (Lumerical)
in the time domain, followed by full-wave finite-element computation (COMSOL)
in the frequency domain. Optical gain or loss is introduced in the complex
refractive index $n_{im}$ (see Methods for details). The $n_{im}$ in the
second cavity is employed as the tunable parameter to approach an exceptional
point, and is set to -0.01 (amplification) in the first cavity. Fig1(a)
depicts the temporal behavior of the system, while (b) describes the
corresponding eigenvalue behavior, along with the intensity distribution in
the coupled resonators. The top panels of (a) and (b) depict the situation for
identical gain, $n_{im}=-0.01$, in the two cavities. The resulting strong
coupling realizes large splitting corresponding to a wavelength splitting
$\delta\lambda$ of 3.6 nm. The emission clearly shows QE oscillations (top
panel of Fig1(a)) in the temporal profile. The blue and orange curves
represent emission from the two cavities. The high QE frequency ($\Omega$)
allows for multiple oscillations during the emission cycle, with out-of-phase
oscillations from the two cavities. The corresponding split eigenvalues are
shown in the top panel of (b), along with the intensity distribution (inset)
in the cavities. The intensity is shown here instead of fields because the
former is an experimental observable. Both the supermodes corresponding to the
two eigenvalues show identical intensity, although the fields depict the
bonding and antibonding character. See Supplementary information for the field
distributions. With reducing gain, the splitting reduces proportionately. For
example, the middle panel of (a) shows the situation for $n_{im}=-0.0073$ in
cavity 2, where the $\delta\lambda=1~{}$nm. The QE oscillation frequency and
the phase difference ($\Delta T/T$) diminishes. The intensity distribution for
the two supermodes is skewed in favour of the cavity 1, as seen in (b).
Ultimately, at $n_{im}=-0.0056$ in cavity 2, the system hits an exceptional
point. The temporal emission coalesces into a single profile seen in the
bottom panel of (a). The two eigenvalues coalesce and a single spectral peak
is observed. The entire energy is accumulated in the cavity 1, which is
indicative of eigenvector coalescence seen in the field distributions. See
Supplementary Information for the fields. Fig1(c) describes the systematic
variation of the phase difference between two echoes and the output intensity
with $\delta\lambda$. A monotonic decrease in $\Delta T/T$ (blue markers, left
Y-axis) with $\delta\lambda$ is seen. The peak output intensity $I_{p}$
increases upon approaching the EP, and maximises at the EP, indicative of
enhanced functionality of the system operating at the exceptional point. The
inset shows that $\Omega$ reduces monotonically with $\delta\lambda$. The
correspondence of the quantum echo with the PT-symmetry breaking was confirmed
by calculating the complex eigenvalues of the system. These were computed by
using a finite-element eigensolver computation, wherein the exact same
structure was simulated. The gain/loss parameter $n_{im}$ was same as in the
FDTD. The real (blue curve) and imaginary (red curve) eigenvalues are shown in
subplot (d). The circle markers on the blue curve are the situations discussed
in (a) and (b). A clear correspondence between the temporal behavior and the
theoretically-expected PT-symmetry breaking and EP-formation is seen.

Figure 2: Schematic of linear arrays of spherical microcavities: (a) white
arrows show emission and scattered directions: longitudinal emission
(transmitted signal) and out-of-axis emission. The sizes of the cavities are
about 18 $\mu m$. (b) A Finite-Element-Method (FEM) simulation showing the
longitudinal mode. Figure 3: Experimental setup and characterization of the
Anderson localized lasing system: (a) Complete schematic of the setup, see
main text for details; (b) CCD image of the microresonator array; (c) zoomed
view of the rectangular region in (a): the microresonator array is pumped by a
mode-locked Nd:YAG laser (green beam, $\lambda=532~{}nm$, pulse width =
$30~{}ps$, repetition rate = $10$ Hz). The emission in the longitudinal
direction (transmitted light) is used for the temporal measurement $I_{tmp}$,
and the transverse out-of-axis scatter gives the spatial profile $I_{sp}$
simultaneously. The schematic of emission directions is shown in (d)). The
transverse scatter is imaged onto the input slit of a spectrometer S1 coupled
with ICCD using a 4f imaging setup [L2: imaging lens (10 cm focal length); F2:
Notch filter (to remove the pump beam)]. The longitudinal emission is measured
using a mirror M located at an angle of $45^{0}$ w.r.t the array as shown in
the schematic. This emission is directed towards the input slit of a second
identical spectrometer S2 coupled to a streak camera (Optronis SC-10, temporal
resolution = $\sim 3$ ps) through a focusing lens L3 and a notch filter F2.
(e, f) represent the spatial data, where (e) shows the spectrographic image of
the multiple lasing modes, and (f) shows a typical extracted spatial profile
of one mode, yielding localization length; (g) shows the simultaneous streak
image of the same modes with (h) showing a typical extracted temporal profile.
(i) Lasing spectrum obtained by integrating the streak image over time axis,
or integrating the spectrographic image over spatial axis.

The structures we employ for these experiments, schematized in Fig 2(a), are
linear arrays of microcavities that couple to form photonic bands and
bandgaps. The microcavities are spherical in shape with diameters of about
$18~{}\mu$m. The large diameters of the spheres and the linear configuration
of the array induces coupling of longitudinal Fabry-Perot modes of the
microcavities. Figure 2(b) illustrates a finite-element computation of an
eigenmode of the periodic array, clearly depicting the longitudinal mode with
quasi-planar wavefronts, akin to a multilayer system. Loss in this structure
is induced by out-of-axis scattering of the mode by the interfaces. In order
to introduce gain, we choose the material appropriately to make the
microcavities, as described in the Methods. Disorder is introduced by
deliberately modifying the axial dimensions and spatial separations of the
microcavities. In our earlier works, we have shown that the periodic arrays
sustain Bloch modesjoshi2022anomalous , while the disordered arrays realize
Anderson localized modesjoshi2020reduction ; joshi2019effect ;
kumar2017temporal . As the fabrication process of the microcavity arrays is
dynamic in nature, we can monitor a huge number of configurations, as
discussed next.

Figure 3 illustrates the creation of the microcavity array, and its
simultaneous spectro-spatio-temporal characterization. The generation
technique, as described in details in the Methods section, creates the
microcavities from a Rhodamine-in-alcohol solution. The Rhodamine molecules
act as sources distributed throughout the length of the array, whilst also
providing gain to the mode. [CCD image shown in (b)]. Optical excitation is
provided by pulses of an Nd:YAG laser fired at 1 Hz, illustrated by the green
beam. The emission transverse to the array comprises the out-of-axis scatter
that is imaged onto a identical spectrometer (S1) coupled to an imaging CCD.
The longitudinal emission of the array, which carries the temporal signature
of the emission in Anderson localized modes, is directed to an identical
spectrometer (S2) coupled to a Streak Camera SC (Optronis SC-10). Since the
microcavities are constantly created and introduced into the pump laser focus,
every excitation laser pulse sees a different disorder configuration of the
array. This feature enables us to generate the vast ensemble of configurations
required in this study. Importantly, the Streak Camera and Spectrometer CCD
are synchronized with the pump laser to register the spectral, spatial and
temporal data of every configuration simultaneously. Panels (c) and (d)
illustrate the characterization scheme. Panel (e) depicts the spectrographic
image from S1 at a particular pump pulse. It shows the multiple emission modes
from the corresponding configuration illuminated by the laser pulse. The
horizontal axis represents the spatial axis, while the vertical axis
represents the wavelength. Subplot (f) shows the extracted spatial profile of
a representative mode labeled by the white arrow in the image (e). This is an
Anderson-localized mode, whose localization length $\xi$ can be extracted from
the decay in the wings. Panel (g) shows the Streak image of the emission of
the same configuration. Since this is directed through a spectrometer, the
vertical axis corresponds to the wavelength, while the horizontal axis
corresponds the time axis. A comparison between (g) and (e) shows that the
same modes are captured in both devices, endorsing the simultaneous diagnostic
capability of the setup. Subplot (h) is the extracted temporal profile of the
same mode as in (f). Subplot (i) shows the emission spectrum obtained by
integrating over the time-axis of (g). The same can be obtained by integrating
the space-axis of (e).

We used this diagnostic system to characterize 3,000 different configurations
of disorder, providing a massive ensemble of about 15,000 Anderson-localized
lasing modes. The limit on the configuration number is set by the volume of
the liquid present in the generator, as mentioned in the Methods. Although all
modes were captured at the same pump energy, inherent pump fluctuations
motivated us to further process the ensemble to choose modes in a very narrow
range of pump energy, to within $\sim 1~{}\mu$J at the average pump energy of
$\sim 87~{}\mu J$. The filtered ensemble still had over 5,000 modes. Among all
the captured modes, pairs of coupled modes were identified through the
temporal profiles, since the coupling resulted in a quantum echo. This clearly
stood apart against the smooth profiles of individual uncoupled modes, such as
the one shown in Figure 3(h). The coupling was further corroborated by the
splitting in the spectral profile. Various degrees of splitting allowed us to
identify the approach to a second-order exceptional point, and eventually the
EP itself.

Figure 4: Experimentally measured temporal, spectral, and spatial
characteristics of Anderson localized lasing modes around and at an
exceptional point (EP): Subplots (a-d) show the measured quantum echo from
lasing emission, with (d) being the EP. Unlike Figure 3(h), the temporal
profiles in (a) exhibit a quantum echo that decisively certifies that the two
modes are coupled. Reducing echo frequency with decreasing phase difference
between the echoes at the two wavelengths is clearly observed. Subplots (e-h)
depict the corresponding eigenvalue spectra from the same configurations as
(a-d) with mentioned splittings. The echo behavior is clearly consistent with
the splitting. (i-l) represent corresponding spatial intensity distribution of
the coupled localized states. Each spatial mode exhibits two peaks, and
signatures of shape exchange. Energy is distributed in both Anderson cavities
at large splittings, but resides mostly in one cavity at $\delta\lambda=0.2$
nm. A single profile exists at the EP in (l). The intensity behavior certifies
coalescence of eigenvectors towards and at the EP. Subplots (d), (h) and (l)
represent Anderson-localization lasing over an exceptional point, further
confirmed in Figure 5.

Figure 4 illustrates a representative set of measurements in the Anderson-
localizing system showing the approach to an EP. The first column of panels
shows the measured quantum echo, the middle column shows the corresponding
spectral measurement, while the third column illustrates the corresponding
spatial intensity distributions. Each row of three panels show simultaneous
diagnostics from the same disorder configuration, while different rows
represent data from different configurations. The subplot (a) shows a temporal
profile in which a high frequency quantum echo is observed. The two profiles
(orange and blue) arising from two coupled modes are out of phase by $\Delta
T/T$ as indicated in the plot. Subplot(e) shows the spectral splitting in the
emission from the two coupled modes in this configuration. Quite symmetric
spectral peaks are observed. The marked $\delta\lambda=0.6$ nm was measured
using a peakfinder algorithm. Subplot (i) shows the spatial intensity of the
two modes extracted from the spectrographic data as described earlier. Strong
spatial overlap with signatures of separated peaks are seen in the profiles.
The coupled Anderson localized modes are spread over almost the system length.
Two distinct peaks in both the profiles are seen, indicative of the two
resonant cavities that underwent coupling. These profiles strongly emphasize
the fact that the two coupled cavities are not physically separated, unlike
conventional photonic coupled-cavities (Figure 1). In such a disordered
system, the gain/loss values in the two cavities are self-determined by the
random configuration that decides the relevant parameters such as quality
factors, pump distributions etc. The lower rows show gradually decreasing
quantum echo frequency, which corresponds to the reduction in splitting seen
in the middle panels. At the same time, the intensity distributions
morphologically coalesce as the splitting diminishes. Notably, subplot (k)
shows a strong peak accompanied by a shoulder, that can be interpreted as the
intensity preferentially residing in one cavity. These configurations
represent the approach to a second-order exception point. Ultimately, the
bottom row (d, h, l) represents lasing at the exceptional point, showing only
one echoless temporal profile, one spectral peak and one intensity profile.
Subplots (a) through (d) illustrate the vanishing of the echo as the EP is
hit. The conclusive inference that (d) corresponds to a second-order EP is
provided in the next figure where we present statistical analysis of the data.

Figure 5: Confirmation of the EP in a statistical ensemble: (a) Scatter points
for the QE frequency $\Omega$ show an overall reduction with decreasing
$\delta\lambda$. Pink diamonds indicate $\langle\Omega\rangle$ at a particular
$\delta\lambda$. (b) Measured $\Delta T/T$ and (c) peak emission intensity
($I_{p}$) as a function of $\delta\lambda$, measured over $\sim 100$ modes.
Each datapoint in (b) is an average over a few oscillations in the temporal
profile. Pink squares indicate $\langle\Delta T/T\rangle$ at a particular
$\delta\lambda$. The scatter clearly shows an approach to $\Delta
T/T\rightarrow 0$ as $\delta\lambda\rightarrow 0$. The yellow band around
$\delta\lambda=0$ signifies the EP region. All datapoints here are placed at
$\delta\lambda=0$ as the $\delta\lambda$ is beyond experimental spectral
resolution. Although $\Delta T/T$ does not exist here, a suggestive datapoint
is marked at $\Delta T/T=0$ in logical follow-up to the neighbouring
datapoints. (c) shows increasing peak intensity $I_{p}$ towards the EP region,
with significant jump of over $300\%$ in the $I_{p}$ in the EP region. Inset
shows $P(I_{p})$ with emphasis shading on outlier points of high intensity.
(d) Spectral line shape at the EP (filled green plot). Blue and red plots are
Lorentzian and squared-Lorentzian fits respectively. The profile possesses a
clear squared-Lorentzian character, which is the classic signature of an EP.
Inset shows the same in logarithmic Y axis.

Fig 5(a) illustrates the frequency of the quantum echo for various splittings.
The mean frequency $\langle\Omega\rangle$ at each $\delta\lambda$ is marked as
pink diamonds. The trend in $\langle\Omega\rangle$ is determined by the
distribution of the scatter points which are constrained to a lower limit
imposed by the total pulse duration ($\sim 50$ ps). (b) shows the phase
difference between the echograms of the coupled modes as a function of
$\delta\lambda$ over several configurations. The scatter in the data reflects
the probabilistic variation in the phase difference for a given splitting,
with a large scatter existing in the range $0.2$ nm$<\delta\lambda<0.4$ nm,
wherein a large number of coupled modes were observed. Such statistical
variations are expected in non-deterministic systems due to configurational
variations. The $\langle\Delta T/T\rangle$ is marked as pink squares. As
$\delta\lambda\rightarrow 0$ nm, the $\langle\Delta T/T\rangle\rightarrow 0$.
The $\langle\delta T/T\rangle$ shows a steady rise with $\delta\lambda$. The
yellow band at $\delta\lambda=0$ signifies the EP range. Clearly, $\delta T/T$
is undefined here since there is only one mode and one temporal profile.
Nonetheless, a datapoint is intentionally marked to signify the completeness
of the trend. Figure 5(c) shows the peak intensity of the modes. The intensity
rises as modes begin to coalesce spectrally, in agreement with the typical
behavior in an EP-approach. Inside the EP range (yellow band at
$\delta\lambda=0$), six modes were identified that lased at a very high
intensity. Upto 300% enhancement in lasing intensity was observed at these
points. Such high intensity is an indicator of enhanced functionality, a
preliminary identifier of a possible EP. The inset shows the intensity
distribution over the entire ensemble of modes, emphasizing the outlier nature
of the high-intensity points. Finally, subplot (d) confirms the exceptional
point character of the modes using an analytical fit for the lineshape of one
of the high-intensity peaks. It is known that LDOS is modified at the
exceptional point such that the resonant lineshape approaches to the
$n^{th}$-power of Lorentzian for an $n^{th}$-order EP. Consistent with this,
the red solid line in (d) depicts the square-Lorentzian profile
$\propto\frac{\gamma^{2}}{4\pi[(\Delta\omega^{2}+\gamma^{2})]^{2}}$ that
perfectly fits the experimental peak. In comparison, the blue line is the
conventional Lorentzian fit which visibly deviates from the observed data. The
inset shows the same on a logarithmic Y-axis, emphasizing the fit by the
square-Lorentzian. The modified LDOS at the EP leads to a maximal peak
enhancement of 4 in passive systems, and can be even more in the presence of
gain. Although our system is random and every configuration has cavities of
varying quality-factors, the average behavior of $I_{p}$ in subplot (c) does
exhibit instances of peak enhancement $>4$ compared to the coupled modes. The
Supplementary material elucidates further data regarding fits on other
exceptional point modes. Thus, these spectral lineshape diagnostics confirm
that the lasing modes shown here occurred over exceptional points in non-
Hermitian Anderson-localizing systems.

In summary, we have identified exceptional points in one-dimensional Anderson
localizing systems, and have extracted lasing over the corresponding modes.
The methodology adopted here significantly deviates from the tuning-parameter
mechanism that is conventionally utilized in photonics. Our technique
preserves the statistical variations in disorder that are sacrosanct in the
domain of mesoscopic optics. We sample thousands of disorder configurations,
and identify the quantum echo which is set up whenever coupled Anderson-
localized modes are realized within the structures. The echo provides
unambiguous signatures of coupling, and sets the coupled modes apart from
random neighbouring modes in the spectrum. Our method realizes a large
multitude of disorder configurations and simultaneously measures spatial,
spectral and temporal dynamics therein. The presence of a quantum echo in the
temporal signal allows us to track configurations with spectral splitting. We
find that reduced splitting is accompanied by enhanced output intensity which
allows us to identify individual modes that provide exceedingly large
outcoupled intensity. Spectral shape analysis of these intense modes reveal
the characteristic square-Lorentzian shapes originating from a second-order
exceptional point degeneracy, as against Lorentzian peaks otherwise. The
excess intensity in these modes is testimonial to the enhanced functionality
afforded by the exceptional points.

## Methods

### Sample preparation and system characterization

The system comprises an array of amplifying micro-droplets made of
Rhodamine-6G (with a concentration of 1.0 mM) dissolved in a mixture of
methanol and ethylene glycol with an equal proportion(50:50$\%$). Ethylene
glycol(EG) is added to obtain good stability and high index contrast
(refractive index of the droplet, $n_{d}$ = 1.38) due to its high viscosity
and refractive index value. Rh6G has a broadband gain profile in the range of
540$-$610 nm.

The array is generated using a vibrating orifice aerosol generator (VOAG). The
liquid from a chamber (1000 ml liquid capacity) was pressurized using a dry-
nitrogen cylinder and passed through VOAG. The VOAG has a circular opening
with a diameter of $10~{}\mu m$, which generates an inhomogeneous and unstable
cylindrical jet of droplets. In order to make stable and spherical-shaped
droplets, a piezoelectric gate is attached at the circular opening of the
VOAG. The gate is then perturbed by applying a periodic electronic signal.
Depending upon the amplitude and frequency of the signal, the size and spacing
of the droplets can be varied in a controlled way which allows us to generate
an ensemble of monodisperse droplets which acts as a periodic array.
Controlled deviations in the electronic signal perturb the microdroplets and
form a disordered array. For this work, we generate a disordered array of
droplets. We made a large ensemble of disordered arrays with a mean diameter
of 18.6 $\mu$m. The standard deviation in the diameters is 340.0 $nm$ which
determines the strength of disorder in the array.

### Coupled mode analysis of the binary system:

1\. Eigenvalue solver using a finite element method (FEM: COMSOL Multiphysics)
was used to calculate the complex eigenfrequencies of the coupled ring
resonator. Simulations were performed in 2D. The structural parameters of the
coupled cavities are: Diameter of the ring $D=2.0~{}\mu m$, thickness
$t=0.2~{}\mu m$ and separation $s=0.4~{}\mu m$. The cavity resonance frequency
for these parameters is $\sim$190.35 THz. The cavities’ gain or loss are
provided in terms of their complex refractive indices, $n=n_{r}+in_{im}$. The
real part of the refractive index ($n_{r}$) for both cavities is set at 3.3.
The separation between the cavities is also fixed at $s$, thus fixing the
coupling strength ($\kappa$) between the cavities. We provide a fixed amount
of gain ($n_{im}=-0.01$) in the $1^{st}$ cavity. The simulation was then
performed varying $n_{im}$ of the second cavity from -0.01 to 0. During the
tuning, exceptional points were identified to occur at $n_{im}\sim-0.0056$.

2\. Temporal analyses were done using Finite-difference time-domain method
(Lumerical FDTD). The structural and material parameters are same as mentioned
in part 1 above. In this method, we use a Lorentz gain model with a Lorentz
permittivity and resonance frequency close to the cavity frequency of the ring
resonator. The permittivity of the material for this method is given by the
relation:

$\epsilon(\omega)=\epsilon+\epsilon_{l}\omega_{0}^{2}/(\omega_{0}^{2}-2i\delta_{0}\omega-\omega^{2})$
(1)

The gain center frequency is set at $\omega_{0}$ (Lorentz Resonance) while the
width is set as $\delta_{0}$. The strength of the gain (gain amplitude) is
given by the permittivity $\epsilon_{l}$, while the sign determines whether
the material has loss or gain.

The gain level ($n_{l}=\sqrt{\epsilon_{l}}$) in the $1^{st}$ cavity is kept
fixed at -0.01. It was confirmed that this value of gain did not lead to any
divergence due to an exponential growth of the field. The gain level in the
second cavity is gradually reduced from this value and replaced with loss.
Both cavities are uniformly excited using a set of identical dipole sources at
the cavity resonance frequency. The time signal of the field and intensity are
measured by placing field time monitors inside the cavities. Spectra are
calculated using the standard Fourier transform method. A full apodization
method is used to measure the frequency-resolved temporal evolution of the
cavity modes. This technique applies a window function to the fields $E(t)$
before its Fourier transform. By using this method, it is possible to
calculate $E(\omega)$ from a portion of the time signal.

Data availability All data relating to the paper are available from the
corresponding author upon reasonable request.

Code availability All the relevant computing codes used in this study are
available from the corresponding author upon reasonable request.

Supplementary information A Supplementary Information document has been
attached with the manuscript.

Author contributions S. M. conceived the project. S. M. and K. J. designed the
experimental setup. K. J. performed the experiment, numerical simulations and
analyzed the data. K. J. and S. M. wrote the manuscript. S. M. supervised the
whole project.

Competing interests The authors declare no competing interests.

Acknowledgments SM would like to acknowledge the Swarnajayanti Fellowship from
the Department of Science and Technology, Government of India. We acknowledge
funding from the Department of Atomic Energy, Government of India (12-R $\&$
D-TFR-5.02-0200).

## References

  * (1)
  * (2) Bender, C.M., Boettcher, S., Meisinger, P.N.: PT-symmetric quantum mechanics. Journal of Mathematical Physics 40(5), 2201–2229 (1999)
  * (3) Bender, C.M., Boettcher, S.: Real spectra in non-Hermitian Hamiltonians having p t symmetry. Physical Review Letters 80(24), 5243 (1998)
  * (4) El-Ganainy, R., Makris, K.G., Khajavikhan, M., Musslimani, Z.H., Rotter, S., Christodoulides, D.N.: Non-Hermitian physics and PT symmetry. Nature Physics 14(1), 11–19 (2018)
  * (5) Rüter, C.E., Makris, K.G., El-Ganainy, R., Christodoulides, D.N., Segev, M., Kip, D.: Observation of parity–time symmetry in optics. Nature Physics 6(3), 192–195 (2010)
  * (6) Regensburger, A., Bersch, C., Miri, M.-A., Onishchukov, G., Christodoulides, D.N., Peschel, U.: Parity–time synthetic photonic lattices. Nature 488(7410), 167–171 (2012)
  * (7) Jing, H., Özdemir, S., Lü, X.-Y., Zhang, J., Yang, L., Nori, F.: PT-symmetric phonon laser. Physical Review Letters 113(5), 053604 (2014)
  * (8) Lin, Z., Ramezani, H., Eichelkraut, T., Kottos, T., Cao, H., Christodoulides, D.N.: Unidirectional invisibility induced by PT-symmetric periodic structures. Physical Review Letters 106(21), 213901 (2011)
  * (9) Zhu, X., Ramezani, H., Shi, C., Zhu, J., Zhang, X.: PT-symmetric acoustics. Physical Review X 4(3), 031042 (2014)
  * (10) Benisty, H., Degiron, A., Lupu, A., De Lustrac, A., Chénais, S., Forget, S., Besbes, M., Barbillon, G., Bruyant, A., Blaize, S., et al.: Implementation of PT symmetric devices using plasmonics: principle and applications. Optics Express 19(19), 18004–18019 (2011)
  * (11) Ding, K., Zhang, Z., Chan, C.T.: Coalescence of exceptional points and phase diagrams for one-dimensional PT-symmetric photonic crystals. Physical Review B 92(23), 235310 (2015)
  * (12) Peng, B., Özdemir, Ş.K., Lei, F., Monifi, F., Gianfreda, M., Long, G.L., Fan, S., Nori, F., Bender, C.M., Yang, L.: Parity–time-symmetric whispering-gallery microcavities. Nature Physics 10(5), 394–398 (2014)
  * (13) Peng, B., Özdemir, Ş., Rotter, S., Yilmaz, H., Liertzer, M., Monifi, F., Bender, C., Nori, F., Yang, L.: Loss-induced suppression and revival of lasing. Science 346(6207), 328–332 (2014)
  * (14) Cerjan, A., Raman, A., Fan, S.: Exceptional contours and band structure design in parity-time symmetric photonic crystals. Physical Review Letters 116(20), 203902 (2016)
  * (15) Feng, L., Xu, Y.-L., Fegadolli, W.S., Lu, M.-H., Oliveira, J.E., Almeida, V.R., Chen, Y.-F., Scherer, A.: Experimental demonstration of a unidirectional reflectionless parity-time metamaterial at optical frequencies. Nature materials 12(2), 108–113 (2013)
  * (16) Jing, H., Özdemir, Ş., Lü, H., Nori, F.: High-order exceptional points in optomechanics. Scientific Reports 7(1), 1–10 (2017)
  * (17) Ding, K., Ma, G., Xiao, M., Zhang, Z., Chan, C.T.: Emergence, coalescence, and topological properties of multiple exceptional points and their experimental realization. Physical Review X 6(2), 021007 (2016)
  * (18) Kang, M., Chen, J., Chong, Y.: Chiral exceptional points in metasurfaces. Physical Review A 94(3), 033834 (2016)
  * (19) Zhen, B., Hsu, C.W., Igarashi, Y., Lu, L., Kaminer, I., Pick, A., Chua, S.-L., Joannopoulos, J.D., Soljačić, M.: Spawning rings of exceptional points out of dirac cones. Nature 525(7569), 354–358 (2015)
  * (20) Heiss, W.: The physics of exceptional points. Journal of Physics A: Mathematical and Theoretical 45(44), 444016 (2012)
  * (21) Kato, T.: Analytic perturbation theory, pp. 364–426. Springer (1966)
  * (22) Heiss, W.: Phases of wave functions and level repulsion. The European Physical Journal D-Atomic, Molecular, Optical and Plasma Physics 7(1), 1–4 (1999)
  * (23) Moiseyev, N.: Non-Hermitian quantum mechanics. Cambridge University Press (2011)
  * (24) El-Ganainy, R., Makris, K., Christodoulides, D., Musslimani, Z.H.: Theory of coupled optical PT-symmetric structures. Optics Letters 32(17), 2632–2634 (2007)
  * (25) Pick, A., Zhen, B., Miller, O.D., Hsu, C.W., Hernandez, F., Rodriguez, A.W., Soljačić, M., Johnson, S.G.: General theory of spontaneous emission near exceptional points. Optics Express 25(11), 12325–12348 (2017)
  * (26) Miri, M.-A., Alù, A.: Exceptional points in optics and photonics. Science 363(6422), 7709 (2019)
  * (27) Moiseyev, N.: Quantum theory of resonances: calculating energies, widths and cross-sections by complex scaling. Physics Reports 302(5-6), 212–293 (1998)
  * (28) Feng, L., Wong, Z.J., Ma, R.-M., Wang, Y., Zhang, X.: Single-mode laser by parity-time symmetry breaking. Science 346(6212), 972–975 (2014)
  * (29) Hodaei, H., Miri, M.-A., Heinrich, M., Christodoulides, D.N., Khajavikhan, M.: Parity-time–symmetric microring lasers. Science 346(6212), 975–978 (2014)
  * (30) Takata, K., Nozaki, K., Kuramochi, E., Matsuo, S., Takeda, K., Fujii, T., Kita, S., Shinya, A., Notomi, M.: Observing exceptional point degeneracy of radiation with electrically pumped photonic crystal coupled-nanocavity lasers. Optica 8(2), 184–192 (2021)
  * (31) Hodaei, H., Hassan, A.U., Wittek, S., Garcia-Gracia, H., El-Ganainy, R., Christodoulides, D.N., Khajavikhan, M.: Enhanced sensitivity at higher-order exceptional points. Nature 548(7666), 187–191 (2017)
  * (32) Chen, W., Kaya Özdemir, Ş., Zhao, G., Wiersig, J., Yang, L.: Exceptional points enhance sensing in an optical microcavity. Nature 548(7666), 192–196 (2017)
  * (33) Hokmabadi, M.P., Schumer, A., Christodoulides, D.N., Khajavikhan, M.: Non-Hermitian ring laser gyroscopes with enhanced sagnac sensitivity. Nature 576(7785), 70–74 (2019)
  * (34) Özdemir, Ş.K., Rotter, S., Nori, F., Yang, L.: Parity–time symmetry and exceptional points in photonics. Nature Materials 18(8), 783–798 (2019)
  * (35) Brandstetter, M., Liertzer, M., Deutsch, C., Klang, P., Schöberl, J., Türeci, H.E., Strasser, G., Unterrainer, K., Rotter, S.: Reversing the pump dependence of a laser at an exceptional point. Nature Communications 5(1), 1–7 (2014)
  * (36) Vázquez-Candanedo, O., Hernández-Herrejón, J., Izrailev, F., Christodoulides, D.: Gain-or loss-induced localization in one-dimensional PT-symmetric tight-binding models. Physical Review A 89(1), 013832 (2014)
  * (37) Bachelard, N., Schumer, A., Kumar, B., Garay, C., Arlandis, J., Touzani, R., Sebbah, P.: Coalescence of Anderson-localized modes at an exceptional point in 2d random media. Optics Express 30(11), 18098–18107 (2022)
  * (38) Davy, M., Genack, A.Z.: Probing nonorthogonality of eigenfunctions and its impact on transport through open systems. Physical Review Research 1(3), 033026 (2019)
  * (39) Huang, Y., Kang, Y., Genack, A.Z.: Wave excitation and dynamics in non-Hermitian disordered systems. Physical Review Research 4, 013102 (2022)
  * (40) Weidemann, S., Kremer, M., Longhi, S., Szameit, A.: Non-Hermitian Anderson Transport (2020)
  * (41) Balasubrahmaniyam, M., Mondal, S., Mujumdar, S.: Necklace-state-mediated anomalous enhancement of transport in Anderson-localized non-Hermitian hybrid systems. Physical Review Letters 124(12), 123901 (2020)
  * (42) Sahoo, H., Vijay, R., Mujumdar, S.: Anomalous transport regime in a non-Hermitian Anderson-localized hybrid system. Physical Review Research 4(4), 043081 (2022)
  * (43) Hodaei, H., Miri, M.A., Hassan, A.U., Hayenga, W., Heinrich, M., Christodoulides, D., Khajavikhan, M.: Parity-time-symmetric coupled microring lasers operating around an exceptional point. Optics Letters 40(21), 4955–4958 (2015)
  * (44) Kim, K.-H., Hwang, M.-S., Kim, H.-R., Choi, J.-H., No, Y.-S., Park, H.-G.: Direct observation of exceptional points in coupled photonic-crystal lasers with asymmetric optical gains. Nature Communications 7(1), 1–9 (2016)
  * (45) Chang, L., Jiang, X., Hua, S., Yang, C., Wen, J., Jiang, L., Li, G., Wang, G., Xiao, M.: Parity–time symmetry and variable optical isolation in active–passive-coupled microresonators. Nature Photonics 8(7), 524–529 (2014)
  * (46) Anderson, P.W.: Absence of diffusion in certain random lattices. Physical Review 109(5), 1492 (1958)
  * (47) John, S.: Strong localization of photons in certain disordered dielectric superlattices. Physical Review Letters 58(23), 2486 (1987)
  * (48) Segev, M., Silberberg, Y., Christodoulides, D.N.: Anderson localization of light. Nature Photonics 7(3), 197–204 (2013)
  * (49) Chabanov, A., Stoytchev, M., Genack, A.: Statistical signatures of photon localization. Nature 404(6780), 850–853 (2000)
  * (50) Wiersma, D.S., Bartolini, P., Lagendijk, A., Righini, R.: Localization of light in a disordered medium. Nature 390(6661), 671–673 (1997)
  * (51) Sapienza, L., Thyrrestrup, H., Stobbe, S., Garcia, P.D., Smolka, S., Lodahl, P.: Cavity quantum electrodynamics with Anderson-localized modes. Science 327(5971), 1352–1355 (2010)
  * (52) Schwartz, T., Bartal, G., Fishman, S., Segev, M.: Transport and Anderson localization in disordered two-dimensional photonic lattices. Nature 446(7131), 52–55 (2007)
  * (53) Lahini, Y., Avidan, A., Pozzi, F., Sorel, M., Morandotti, R., Christodoulides, D.N., Silberberg, Y.: Anderson localization and nonlinearity in one-dimensional disordered photonic lattices. Physical Review Letters 100(1), 013906 (2008)
  * (54) Riboli, F., Barthelemy, P., Vignolini, S., Intonti, F., De Rossi, A., Combrie, S., Wiersma, D.: Anderson localization of near-visible light in two dimensions. Optics Letters 36(2), 127–129 (2011)
  * (55) Joshi, K., Mondal, S., Kumar, R., Mujumdar, S.: Reduction in generalized conductance with increasing gain in amplifying Anderson-localized systems. Optics Letters 45(8), 2239–2242 (2020)
  * (56) Joshi, K., Kumar, R., Mujumdar, S.: Anomalous localization and transport behavior of amplifying periodic-on-average random systems at critical disorder. Physical Review A 105(3), 033505 (2022)
  * (57) Dietz, B., Friedrich, T., Metz, J., Miski-Oglu, M., Richter, A., Schäfer, F., Stafford, C.: Rabi oscillations at exceptional points in microwave billiards. Physical Review E 75(2), 027201 (2007)
  * (58) Dembowski, C., Dietz, B., Friedrich, T., Gräf, H.-D., Heine, A., Mejía-Monasterio, C., Miski-Oglu, M., Richter, A., Seligman, T.: First experimental evidence for quantum echoes in scattering systems. Physical Review Letters 93(13), 134102 (2004)
  * (59) Joshi, K., Kumar, R., Balasubrahmaniyam, M., Mujumdar, S.: Effect of critical disorder on lifetime distributions of Anderson-localized lasing modes. Physical Review A 100(2), 023803 (2019)
  * (60) Kumar, R., Balasubrahmaniyam, M., Alee, K.S., Mujumdar, S.: Temporal complexity in emission from Anderson localized lasers. Physical Review A 96(6), 063816 (2017)
  * (61) Makris, K.G., El-Ganainy, R., Christodoulides, D., Musslimani, Z.H.: Beam dynamics in PT symmetric optical lattices. Physical Review Letters 100(10), 103904 (2008)
  * (62) Gao, T., Estrecho, E., Bliokh, K., Liew, T., Fraser, M., Brodbeck, S., Kamp, M., Schneider, C., Höfling, S., Yamamoto, Y., et al.: Observation of non-Hermitian degeneracies in a chaotic exciton-polariton billiard. Nature 526(7574), 554–558 (2015)
  * (63) Zhang, J., Peng, B., Özdemir, Ş.K., Pichler, K., Krimer, D.O., Zhao, G., Nori, F., Liu, Y.-x., Rotter, S., Yang, L.: A phonon laser operating at an exceptional point. Nature Photonics 12(8), 479–484 (2018)
  * (64) Tiwari, A.K., Mujumdar, S.: Random lasing over gap states from a quasi-one-dimensional amplifying periodic-on-average random superlattice. Physical Review Letters 111(23), 233903 (2013)
  * (65) Wiersig, J.: Review of exceptional point-based sensors. Photonics Research 8(9), 1457–1467 (2020)
  * (66) Pick, A., Lin, Z., Jin, W., Rodriguez, A.W.: Enhanced nonlinear frequency conversion and purcell enhancement at exceptional points. Physical Review B 96(22), 224303 (2017)


# Sparse maps

Elia Portnoy

###### Abstract

We prove a generalization of the Kolmogorov-Barzdin theorem for maps from
simplicial complexes into Euclidean space. This improves a bound from Gromov
and Guth [GG]. Along the way we introduce the notion of sparse maps and
discuss maps from simplicial complexes with controlled 1-width.

## Introduction

We consider the following quantitative embedding problem. Suppose $Y$ is some
large complicated simplicial complex with a small number simplicies adjacent
to each vertex. What is the smallest number $R$, so that $Y$ admits a map into
a Euclidian $n$-ball of radius $R$ for which the pre-image of each unit ball
intersects a small number of simplices from $Y$? To make $R$ small we might
have to stretch and fold $Y$ in some complicated way. In [KB], Kolmogorov and
Barzdin proved the first such result about maps from graphs into
$\mathbb{R}^{3}$. They showed that for any graph $Y$ with $V$ vertices and
degree at most $D$, there is a embedding of $Y$ into a ball of radius
$C(D)V^{1/2}$ in $\mathbb{R}^{3}$, so that the pre-image of each unit ball
intersects at most $C(D)$ edges. Here $C(D)$ is some constant that only
depends on $D$. They also found that this bound on the radius is sharp up to a
constant for expander graphs. In [GG], Gromov and Guth generalized this result
to maps from simplicial complexes as follows. Suppose $Y$ is a $d$-dimensional
simplicial complex with $V$ vertices, so that each vertex lies in at most $D$
simplices. Theorem 2.1 from [GG] says that for $n\geq 2d+1$, $Y$ can be mapped
into a ball of radius $C(d,n,D)V^{\frac{1}{n-d}}log(V)^{2d+2}$ in
$\mathbb{R}^{n}$, so that the pre-image of each unit ball intersects at most
$C(d,n,D)$ simplices.111In fact, the theorem from [GG] gave a slightly
stronger condition on the map. Namely, that the map is an embedding and the
distance between the images of any two simplices, which do not share a vertex,
is at least 1. They refer to such maps as combinatorially thick embeddings.
Here, $C(d,n,D)$ stands for a constant that only depends on $d,n$ and $D$. One
of the consequences of our main theorem is to remove the $polylog(V)$ factor
from Gromov and Guth’s bound on the radius.

Our main theorem concerns maps which are $m$-sparse, which is a strengthening
of the condition that pre-images of every unit ball intersect a small constant
number of simplices. In the next section we will give a full definition of
$m$-sparse maps. Roughly, a map from a $d$-dimensional simplicial complex $Y$
to $\mathbb{R}^{n}$ is $m$-sparse if the pre-image of each coordinate
$m$-dimensional plane in $\mathbb{R}^{n}$ intersects a small constant number
of simplices in $Y$. We also impose an additional condition on the map, that
the image of the $k$-skeleton of $Y$ must lie in the $k$-skeleton of the unit
lattice in $\mathbb{R}^{n}$ for each $0\leq k\leq d$. For example, a
$1$-sparse map from a $0$-dimensional $Y$ (a set of vertices) into
$\mathbb{R}^{2}$ is a way to place the vertices of $Y$ in
$\mathbb{Z}^{2}\subset\mathbb{R}^{2}$ so that each vertical and horizontal
line intersects only a constant number of points from $Y$. So if $Y$ is a set
of $V$ vertices, then there is a 1-sparse map into $[0,V]^{2}$, where we place
the vertices along the diagonal of the square. A 1-sparse map from a graph $Y$
into $\mathbb{R}^{n}$ maps each each edge of $Y$ to a path in the unit grid so
that the pre-image of each straight line in the grid intersects at most a
constant number of edges in $Y$. In fact, Kolmogorov and Barzdin showed that
if a graph $Y$ had $V$ vertices and constant degree, then there is a 1-sparse
map of $Y$ into a ball of radius roughly $V^{1/2}$ in $\mathbb{R}^{3}$. Here
is our main theorem.

######  Theorem 1.

For any three dimensions $0\leq d\leq m\leq n$ and number $D>0$ the following
holds. Suppose $Y$ is a $d$-dimensional simplicial complex with $V$ vertices,
so that each vertex lies in at most $D$ simplices. Then there is a $m$-sparse
map,

$F:Y\to[0,C(d,m,n,D)V^{\frac{1}{n-m}}]^{n}\subset\mathbb{R}^{n}$

where $C(d,m,n,D)$ is a constant that only depends on $d,m,n$ and $D$.

If $d=m$ we recover the theorem of Gromov and Guth without the polylog factor.
Namely, that a $d$-dimensional simplicial complex $Y$ can be mapped into a
ball of radius $C(d,n,D)V^{\frac{1}{n-d}}$ in $\mathbb{R}^{n}$, so that the
pre-image of each unit ball intersects at most $C(d,n,D)$ simplices. Let’s
explain how the estimate on the radius here is sharp because of the existence
of high-dimensional expanders. Define the $k$-width of a simplicial complex
$Y$ as follows

$W_{k}(Y)=\min_{f:Y\to\mathbb{R}^{k}}\max_{p\in\mathbb{R}^{k}}|f^{-1}(p)|$

where the min is over all continuous map to $\mathbb{R}^{k}$, and
$|f^{-1}(p)|$ stands for the number of simplices in that intersect the fiber
at $p\in\mathbb{R}^{k}$. For example, if $Y$ is an expander graph with $V$
vertices then $W_{1}(Y)$ is $V$, up to a constant. For $d\geq 2$, we that a
family of $d$-dimensional simplicial complexes $\\{Y_{i}\\}_{i=1}^{\infty}$ is
a (topological) high dimensional expander if the following conditions are
satisfied.

  1. 1.

The number of vertices in $Y_{i}$ is $V_{i}$ and $\\{V_{i}\\}_{i=1}^{\infty}$
is unbounded.

  2. 2.

The number of simplices adjacent to any vertex in any $Y_{i}$ is uniformly
bounded, independent of $i$.

  3. 3.

For each $i\geq 1$, $W_{d}(Y_{i})\geq cV_{i}$ for some constant $c>0$
independent of $i$.

In [GE], Gromov asked whether high dimensional expanders exist. In [EK], Evra
and Kaufman remarkably gave an example of a family of high dimensional
expanders in every dimension. If for each $i\geq 1$, we had a $d$-sparse map
$F:Y_{i}\to[0,R_{i}]^{n}\subset\mathbb{R}^{n}$, then $W_{d}(Y_{i})$ would be
bounded from above by roughly $R_{i}^{n-d}$. This is because each fiber of the
linear projection from $[0,R_{i}]^{n}$ to $[0,R_{i}]^{d}$ intersects the unit
lattice in roughly $R_{i}^{n-d}$ cells. This would give us the bound
$R_{i}^{n-d}\geq cV_{i}$, which tells us that Theorem 1 is sharp, up to a
constant, for high-dimensional expanders when $d=m$.

We now say a bit about the proof of Theorem 1. Our proof is modeled after
Kolmogorov’s and Barzdin’s original proof, but involves an inductive argument.
The inductive argument will explain why the theorem holds for parameters
$(d,m,n)$, given that it holds for parameters $(d-1,m-1,n-1)$. Here is the
main idea for the graph case $d=1$. Suppose we have we already have found a
$(m-1)$-sparse $f$ map of the vertices of $Y$ into the hyperplane
$[0,CV^{\frac{1}{n-m}}]^{n-1}\times\\{0\\}\subset\mathbb{R}^{n}$, and we want
to extend $f$ to a $m$-sparse map of the edges of $Y$ into
$[0,CV^{\frac{1}{n-m}}]^{n}\subset\mathbb{R}^{n}$. We will choose an integer
label $L(e)$ between $1$ and $CV^{\frac{1}{n-m}}$ for each edge $e\in Y$. $F$
will map an edge $e$ to a piece-wise linear path in $\mathbb{R}^{n}$. If
$v_{1}$ and $v_{2}$ are the two vertices adjacent to $e$, then the path $F(e)$
will contain the two initial segments going from $f(v_{i})$ to
$f(v_{i})+L(e)u_{n}$, where $u_{n}$ is the $n^{th}$ unit coordinate vector in
$\mathbb{R}^{n}$ and $i\in\\{1,2\\}$. To complete $F(e)$ we just need to
connect the endpoints of these two segments with a path in the hyperplane
$[0,CV^{\frac{1}{n-m}}]^{n-1}\times\\{L(e)\\}$. After we add in these initial
segments for each edge of $Y$, we reduce our original problem to finding a
$m$-sparse set of paths within in each hyperplane
$[0,CV^{\frac{1}{n-m}}]^{n-1}\times\\{j\\}$, for each
$j\in[1,CV^{\frac{1}{n-m}}]$. If we label our edges carefully, then the set of
vertices that we need to connect in each hyperplane form an $m$-sparse set.
This implies that at most $CV^{\frac{n-m-1}{n-m}}$ edges share the same label.
So finding the $m$-sparse set of paths within in each hyperplane is an easier
problem than the one we started with.

Our next theorem says that if a simplicial complex has a small 1-width, then
we can improve our quantitative embedding.

######  Theorem 2.

Suppose $Y$ is a $d$-dimensional simplicial complex with $V$ vertices, so that
each vertex lies in at most $D$ simplices. Then for $n\geq d+1$, there is a
map

$F:Y\to[0,C(d,n,D)V^{\frac{1}{n}}W_{1}(Y)^{\frac{d}{n(n-d)}}]^{n}\subset\mathbb{R}^{n}$

so that the pre-image of each unit ball intersects at most $C(d,n,D)$
simplices, where $C(d,n,D)$ is a constant that only depends on $d,n$ and $D$.

The idea of the proof is to use the map which realizes the 1-width to chop up
$Y$ into pieces of size roughly $W_{1}(Y)$ and to map these pieces into balls
in $\mathbb{R}^{n}$ using Theorem 1. Then we arrange these balls in a row in
$\mathbb{R}^{n}$, map in the simplices that have vertices in different pieces,
and then finally bend this row of balls into a larger ball in
$\mathbb{R}^{n}$. Note that if $W_{1}(Y)$ is roughly like $V$ then the bound
in Theorem 2 matches the one in Theorem 1 for $d=m$.

Here is an application of this theorem. Let $B_{\mathbb{H}}$ be 2-dimensional
ball of volume $V$ in hyperbolic space. The area of a ball in hyperbolic space
is exponential in its radius, so $W_{1}(B_{\mathbb{H}})$ is at most
$polylog(V)$. Theorem 2 says that there is a map from $B_{\mathbb{H}}$ to a
ball of volume $Vpolylog(V)$ in $\mathbb{R}^{3}$, so that the pre-image of
each unit ball in $\mathbb{R}^{3}$ can be covered by a small constant number
of unit balls in the hyperbolic space. On one hand, such a map should expand
many directions in $B_{\mathbb{H}}$ by a factor of at least
$V^{1/3}polylog^{-1}(V)$, on the other hand, the image of most unit balls in
$B_{\mathbb{H}}$ should be covered by about $polylog(V)$ balls in
$\mathbb{R}^{3}$. So this map must be very distorted. It would be interesting
to consider what happens when we try to construct a map from a large ball in a
higher dimensional hyperbolic space into Euclidean space, so that the pre-
image of every unit ball has at most constant volume.

This paper is organized as follows. Section 1 contains the definition of
sparse maps and a proof of Theorem 1. In section 2 we prove Theorem 2.

## Acknowledgments

I would like to thank Ting-Chun Lin for discussing embeddings of simplicial
complexes with me. Ting-Chun Lin also mentioned some other methods that could
lead to an improvement on the bound in [GG]. Larry Guth and I had several
discussions about these topics that were helpful.

## The main theorem for sparse maps

We begin this section by giving the definition of a $m$-sparse map. Let
$\Lambda^{n}$ be the unit lattice in $\mathbb{R}^{n}$ equipped with the
natural skeletal decomposition. The $0$-skeleton of $\Lambda^{n}$ is
$\mathbb{Z}^{n}$, the $1$-skeleton is all the edges between neighboring points
of $\mathbb{Z}^{n}$ in the $n$ coordinate directions, and so on. The
$k$-skeleton of $\Lambda^{n}$ will be denoted $\Lambda^{n}(k)$. A $k$-plane in
$\Lambda^{n}(k)$ is a set of points for which some $(n-k)$-coordinates are
fixed integers. For example,
$\\{(x_{1},3,x_{2},x_{3},2):(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}\\}$ is a
3-plane in $\Lambda^{5}(3)$.

######  Definition 1.

Fix three dimensions $0\leq d\leq m\leq n$, an integer $D>0$, and a constant
$C(d,m,n,D)>0$. Let $Y$ be a $d$-dimensional simplicial complex, so that each
vertex is contained in at most $D$ simplices. Denote the $k$-skeleton of $Y$
by $Y(k)$. A map $F:Y\to\mathbb{R}^{n}$ is $m$-sparse if the following
conditions hold.222In this paper we are interested in properties related to
$m$-sparse maps that hold when the size of the simplicial complex goes to
inifinity, but $d,m,n$ and $D$ stay bounded. So when we say that there is a
sparse map from a simplicial complex $Y$ to $\mathbb{R}^{n}$ that satisfies a
certain property, we implicitly mean that the constant $C(d,m,n,D)$ here
depends on this property, but not on the size of $Y$.

  1. 1.

For each dimension $0\leq k\leq d$, we have $F(Y(k))\subset\Lambda^{n}(k)$.

  2. 2.

The image of each $d$-simplex of $Y$ intersects at most $C(d,m,n,D)$
$m$-planes in $\Lambda^{n}(m)$ in a set of dimension $d$.

  3. 3.

For each $m$-plane $H$ in $\Lambda^{n}(m)$, there are at most $C(d,m,n,D)$
$d$-simplices of $Y$ whose image intersects $H$ in a set of dimension $d$.

The larger $m$ is, the more restrictions are placed on a map to be $m$-sparse.
Here is our main theorem about $m$-sparse maps.

######  Theorem (1).

For any three dimensions $0\leq d\leq m\leq n$ and integer $D>0$ the following
holds. Suppose $Y$ is a $d$-dimensional simplicial complex with $V$ vertices,
so that each vertex lies in at most $D$ simplices. Then there is a $m$-sparse
map,

$F:Y\to[0,C(d,m,n,D)V^{\frac{1}{n-m}}]^{n}\subset\mathbb{R}^{n}$

where $C(d,m,n,D)$ is a constant that only depends on $d,m,n$ and $D$.

We’ll prove Theorem 1 using an inductive argument that involves $d,m$ and $n$.
The base case will be $d=0$ and is given by the following lemma.

######  Lemma 1.

Let $Y$ be a $0$-dimensional simplicial complex, which is a set of $V$
vertices. Then for any $0\leq m\leq n$, there is a $m$-sparse map
$F:Y\to[0,C(m,n)V^{\frac{1}{n-m}}]^{n}\subset\mathbb{R}^{n}$, where $C(m,n)$
is a constant that only depends on $m$ and $n$.

###### Proof.

We can show that such a map $F$ exists by using a greedy algorithm. Order the
vertices of $Y$ from $1$ to $V$. For some $1\leq k<V$, suppose we have found a
way of mapping the first $(k-1)$ vertices of $Y$ into
$\mathbb{Z}^{n}\cap[0,C(m,n)V^{\frac{1}{n-m}}]^{n}$ so that each $m$-plane in
$\Lambda^{n}(m)$ contains at most one vertex of $Y$. Then the number of
$m$-planes of $\Lambda^{n}(m)$ that contain some vertex of $Y$ is at most
${n\choose m}(k-1)$. Also each $m$-plane contains at most
$C(m,n)^{m}V^{\frac{m}{n-m}}$ vertices. So if we choose $C(m,n)$ large enough
so that

${n\choose m}C(m,n)^{m}<C(m,n)^{n}$

then there must be some vertex
$p\in\mathbb{Z}^{n}\cap[0,C(m,n)V^{\frac{1}{n-m}}]^{n}$ that does not lie in
an $m$-plane which contains one of the first $(k-1)$ vertices of $Y$. Then we
let $F$ map the $k^{th}$ vertex of $Y$ to $p$. Continuing in this way we can
construct the desired $m$-sparse map $F$. ∎

Next we’ll prove an extension theorem that serves as the inductive step in the
proof of Theorem 1.

######  Theorem 3.

Suppose $Y$ is a $d$-dimensional simplicial complex with at most $V$ vertices,
so that each vertex lies in at most $D$ simplices and $d\geq 1$. Also suppose
that for some $d\leq m\leq n$ and constant $C(d-1,m-1,n,D)$, we have a
$(m-1)$-sparse map from the $(d-1)$-skeleton of $Y$,

$f:Y(d-1)\to[0,C(d-1,m-1,n,D)V^{\frac{1}{n-m}}]^{n-1}\times\\{0\\}\subset\mathbb{R}^{n}$

Then there is $d$-sparse map $F$ which extends $f$ as follows,

$F:Y\to[0,C(d,m,n,D)V^{\frac{1}{n-m}}]^{n}\subset\mathbb{R}^{n}$

where $C(d,m,n,D)$ is a constant that only depends on $d,m,n,D$ and the
constant $C(d-1,m-1,n,D)$.

###### Proof.

We will prove this theorem by induction on $n$ with $d$ and $m$ fixed. Let
$R=C(d,m,n,D)V^{\frac{1}{n-m}}$, where $C(d,m,n,D)$ will be determined in the
course of the proof. For each $d$-simplex of $\sigma\in Y$, we would like to
find a suitable filling of $f(\partial\sigma)$ inside $[0,R]^{n}$, so that the
filling is the image of a map from a $d$-dimensional ball. We will then define
$F(\sigma)$ to be this filling.

Let us first deal with the case when $m=n$, which will be the base case for
our induction. In this case, since $f$ is $(n-1)$-sparse and its image is
contained in a $(n-1)$-plane, we have that $V\leq C(d-1,m-1,n,D)$. The main
thing we worry about here is that the fillings lie in $\Lambda^{n}(d)$. For
each $d$-simplex $\sigma\in Y$, we fill $f(\partial\sigma)$ by projecting it
to subspaces of smaller and smaller dimension and then cone it off. Here are
the details. For an affine subspace $H\subset\mathbb{R}^{n}$, let $\pi_{H}$
denote the linear projection to $H$ in $\mathbb{R}^{n}$. So for example,
$\pi_{\\{x_{1}=0,x_{2}=0\\}}$ will denote the projection to the 2-dimensional
subspace spanned by the first two coordinates. If $Y^{\prime}$ is a chain in
$\mathbb{R}^{n}$, let $P_{H}(Y^{\prime})$ denote the chain whose boundary is
$Y^{\prime}-\pi_{H}(Y^{\prime})$ which consists of all segments perpendicular
to $H$, that go between $Y^{\prime}$ and $\pi_{H}(Y^{\prime})$. Also let
$Cone(Y^{\prime})$ denote the chain which is a cone from $Y^{\prime}$ to some
vertex $p\in Y^{\prime}$. Our filling for $f(\partial\sigma)$ is defined as
follows

$P_{\\{x_{1}=0\\}}(f(\partial\sigma))+\sum_{i=2}^{n-d+1}P_{\\{x_{1}=0,x_{2}=0,\ldots
x_{i}=0\\}}(\pi_{\\{x_{1}=0,x_{2}=0,\ldots
x_{i-1}=0\\}}f(\partial\sigma))+Cone(\pi_{\\{x_{1}=0,x_{2}=0,\ldots
x_{n-d+1}=0\\}}f(\partial\sigma))$

Notice that this filling can be defined to be the image of a $d$-ball into
$\mathbb{R}^{n}$ and so we get a well defined extension of $f$ to a map
$F:Y\to[0,R]^{n}\cap\Lambda^{n}(d)$. If $f(\partial\sigma)$ intersected some
number $I$ of the $(m-1)$-planes of $\Lambda^{n}(m-1)$ in dimension $(d-1)$,
then our filling of $f(\partial\sigma)$ intersects at most $nI$ of the
$m$-planes of $\Lambda^{n}(m)$ in dimension $d$. Also each $m$-plane in
$\Lambda^{n}(m)$ intersects at most

$VD\leq C(d-1,m-1,n,D)D$

$d$-simplices in the image of $F$. So our extension $F$ is $m$-sparse. This
completes the $m=n$ case.

From now on we assume that $1\leq m<n$ and suppose the inductive hypothesis
tells us that this theorem holds for $m$-sparse maps into $\mathbb{R}^{n-1}$.
In this case, we construct the fillings of $f(\partial\sigma)$ by spreading
them out across parallel hyperplanes perpendicular to the $n^{th}$ coordinate
direction. We will pick a label $L(\sigma)$ for each $d$-simplex $\sigma\in
Y$, and most filling of $f(\partial\sigma)$ will lie in
$[0,R]^{n-1}\times\\{L(\sigma)\\}$. The following lemma tells us how to select
these labels.

######  Lemma 2.

If $C(d,m,n,D)$ is large enough, then we can find a labeling,

$L:\\{\text{$d$-simplices of $Y$}\\}\to[1,R]$

so that for each $j\in[1,R]$ the following holds. Let
$Y_{j}=\bigcup\limits_{L(\sigma)=j}\partial\sigma$ be a subcomplex of
$Y(d-1)$. Then $f$ is $m$-sparse when restricted to $Y_{j}$ and the number of
vertices in $Y_{j}$ is at most $C(m,n,D)V^{\frac{n-m-1}{n-m}}$.

###### Proof.

The proof is again an application of the greedy algorithm. We order the
$d$-simplices of $Y$ and choose the labels in order. Suppose we have already
chosen a label for the first $(k-1)$ simplices. We need to show that we can
choose a suitable label for the $k^{th}$ simplex, $\sigma_{k}$. Call a label
$j$ bad, if for some $k^{\prime}\leq k$ there is some $d$-simplex
$\sigma_{k^{\prime}}$ with label $L(\sigma_{k^{\prime}})=j$ and an $m$-plane
of $\Lambda^{n}(m)$ which intersects both $f(\partial\sigma_{k^{\prime}})$ and
$f(\partial\sigma_{k})$ in a set of dimension $(d-1)$.

By our sparsity assumption on $f$, each $m$-plane intersects at most
$C(d-1,m-1,n,D)mR$ simplices from $Y(d-1)$ in a set of dimension $(d-1)$. Also
by the definition of an $(m-1)$-sparse map, the number of $(m-1)$ planes that
$f(\partial\sigma_{k^{\prime}})$ intersects is dimension $(d-1)$ is at most
$(d+1)C(d-1,m-1,n,D)$. Thus, we can bound the number of bad labels from above
by

$(d+1)mC(d-1,m-1,n,D)^{2}R$

As long as $(d+1)mC(d-1,m-1,n,D)^{2}<C(d,m,n,D)$, we can choose some label
$j^{\prime}\in[1,R]$ which is not bad. Now set $L(\sigma_{k})=j^{\prime}$. By
the definition of bad labels, if $1\leq k^{\prime}<k$ and
$L(\sigma_{k})=L(\sigma_{k^{\prime}})$, then no $m$-plane can intersect both
$f(\sigma_{k})$ and $f(\sigma_{k^{\prime}})$ in a set of dimension $(d-1)$.
This completes the construction of $L$. The estimate on the number of vertices
of $Y_{j}$ follows from the definition of a $m$-sparse map and the fact that
$f(Y_{j})$ lies in $[0,R]^{n-1}\times\\{0\\}$. ∎

Lets us explain how to find a filling for all the $d$-simplices with a fixed
label $j\in[1,R]$. Recall that for an affine subset $H\subset\mathbb{R}^{n}$,
we let $\pi_{H}$ be the linear projection to $H$ in $\mathbb{R}^{n}$. For a
$d$-simplex $\sigma\in Y$ with $L(\sigma)=j$, we will fill $f(\partial\sigma)$
in two steps. For first part of the filling we find a chain with boundaries
$f(\partial\sigma)$ and $\pi_{\\{x_{n}=j,x_{n-1}=0\\}}f(\partial\sigma)$. For
the second part of the filling we will use the inductive hypothesis to fill
$\pi_{\\{x_{n}=j,x_{n-1}=0\\}}f(\partial\sigma)$ inside the hyperplane
$[0,R]^{n-1}\times\\{j\\}$. Here are the details. Consider the map

$f_{j}:\bigsqcup_{L(\sigma)=j}\partial\sigma\to[0,R]^{n-2}\times
0\times\\{j\\}$

where the disjoint union runs over all $d$-simplices with label $j$ and
$f_{j}(\partial\sigma)=\pi_{\\{x_{n}=j,x_{n-1}=0\\}}f(\partial\sigma)$. The
map $f_{j}$ is defined by restricting the map $f$ to the boundaries of the
$d$-simplices in $Y_{j}$, translating the image to the hyperplane
$\\{x_{n}=j\\}$, and then projecting the image to the hyperplane
$\\{x_{n-1}=0\\}$. Our labels were chosen specifically so that the map $f_{j}$
is $(m-1)$-sparse. This follows from the fact that $f$ is $m$-sparse on
$Y_{j}$, and that the composition of an $m$-sparse map with a projection to a
hyperplane is $(m-1)$-sparse. Furthermore, the number of vertices in the
domain of $f_{j}$ is at most $C(D)$ times the number of vertices in $Y_{j}$,
which is bounded by $C(m,n,D)V^{\frac{n-m-1}{n-m}}$. Now we can apply the
inductive hypothesis to the map $f_{j}$ by treating it as a map from a
$(d-1)$-dimensional simplicial complex into a $(n-1)$-dimensional Euclidean
space $\mathbb{R}^{n-1}\times\\{j\\}$. If our constant $C(d,m,n,D)$ is large
enough, depending on $C(d,m,n-1,D)$, then we get an extension of $f_{j}$ to a
map,

$F_{j}:\bigsqcup_{L(\sigma)=j}\sigma\to[0,R]^{n-1}\times\\{j\\}$

which is $m$-sparse. Now for any $d$-simplex $\sigma$, the filling of
$f(\partial\sigma)$ is defined as follows

$P_{\\{x_{n}=L(\sigma)\\}}(f(\partial\sigma))+P_{\\{x_{n}=L(\sigma),x_{n-1}\\}}(\pi_{\\{x_{n}=L(\sigma)\\}}f(\partial\sigma))+F_{L(\sigma)}(\sigma)$

Notice that each filling consists of at most $3n$ projections and a cone. So
these fillings can be defined to be the image of a map from a $d$-ball into
$\mathbb{R}^{n}$ and so we get a well defined extension of $f$ to a map
$F:Y\to[0,R]^{n}\cap\Lambda^{n}(d)$. Also if $f(\partial\sigma)$ intersected
some number $I$ of the $(m-1)$-planes of $\Lambda^{n}(m-1)$ in dimension
$(d-1)$, then our filling of $f(\partial\sigma)$ intersects at most
$C(d,m,n,D)I$ of the $m$-planes of $\Lambda^{n}(m)$ in dimension $d$. So $F$
is indeed a $m$-sparse map. ∎

###### Proof of Theorem 1.

By Lemma 1, the theorem is true for any $0\leq m\leq n$ and $d=0$. By Theorem
3, if the theorem is true for some fixed $d=d_{0},m=m_{0}$ and $n=n_{0}$ with
$0\leq d_{0}\leq m_{0}\leq n_{0}$ then is it also true for
$d=d_{0}+1,m=m_{0}+1$ and $n=n_{0}+1$. Thus, the theorem holds for any $0\leq
d\leq m\leq n$. ∎

## Maps from simplicial complexes with controlled 1-width

In this section we prove Theorem 2.

######  Theorem (2).

Suppose $Y$ is a $d$-dimensional simplicial complex with $V$ vertices, so that
each vertex lies in at most $D$ simplices. Then for $n\geq d+1$, there is a
map

$F:Y\to[0,C(n,D)V^{\frac{1}{n}}W_{1}(Y)^{\frac{d}{n(n-d)}}]^{n}\subset\mathbb{R}^{n}$

so that the pre-image of each unit ball intersects at most $C(d,n,D)$
simplices.

###### Proof.

Let $f:Y\to[0,1]$ be a map that realizes the 1-width $W=W_{1}(Y)$. That is,
each fiber of $f$ intersects at most $W$ simplices of $Y$. We can modify $f$
so that it is linear on each simplex of $Y$ and is injective on the vertices
of $Y$. Furthermore, this modification can be done so that the size of the
fibers changes by at most a factor of $C(D)$. Choose $N\leq VW^{-1}$ points in
$\mathbb{R}$, $0=p_{0}<p_{1}\ldots p_{N_{1}}<p_{N}=1$, so that $f^{-1}(p_{i})$
does not contain any vertices of $Y$ and $f^{-1}([p_{i},p_{i+1}])$ contains
between $C(D)^{-1}W$ and $C(D)W$ vertices of $Y$, for each $0\leq i<N$. Since
$f$ is linear on the simplices, each fiber $f^{-1}(p_{i})$ can intersect a
$d$-simplex of $Y$ in a $(d-1)$-dimensional polytope with at most $C(d)$
sides. And by the definition of $W$, the pre-image of each $p_{i}$ consists of
at most $C(D)W$ such polytopes. We can subdivide $Y$ to get a simplicial
complex that contains each $f^{-1}(p_{i})$ in its $(d-1)$-skeleton, but still
has at most $C(d)V$ vertices and, furthermore, each vertex is contained in at
most $C(d,D)$ simplices. Let $Y^{\prime}$ be this subdivision of $Y$. It now
suffices to find a map from $Y^{\prime}$ to $\mathbb{R}^{n}$ that satisfies
the conditions of the theorem. We begin by finding a map $F^{\prime}$ from
$Y^{\prime}$ to a $n$-dimensional rectangular prism $R$ with one side of
length roughly $NW^{\frac{1}{n-d}}$ and $(n-1)$ sides of length roughly
$W^{\frac{1}{n-d}}$. To define $F^{\prime}$ we divide $R$ into $N$ cubes of
side-length roughly $W^{\frac{1}{n-d}}$. We will define $F^{\prime}$ to map
$f^{-1}((p_{i},p_{i+1}])$ near the $i^{th}$ cube by repeatedly using Theorem 3
on each cube separately. Then we will compose $F^{\prime}$ with a map that
bends $R$ into a $n$-dimensional ball to get our final map $F$.

Here are the details. For each $0\leq i<N$, define the cube

$Q_{i}=[iC(d,n,D)W^{\frac{1}{n-d}},(i+1)C(d,n,D)W^{\frac{1}{n-d}}]\times[0,C(d,n,D)W^{\frac{1}{n-d}}]^{n-1}\subset\mathbb{R}^{n}$

where $C(d,n,D)$ is some constant depending only on $d,n$ and $D$ that we will
choose in the course of the proof. Also define each cube’s intersection with
the subspace spanned by the first $k$ coordinates by
$Q^{k}_{i}=Q_{i}\cap(\mathbb{R}^{k}\times\\{0\\}^{n-k})$. The number of
vertices in $Y^{\prime}\cap f^{-1}([p_{i},p_{i+1}])$ is at most $C(d,D)W$. So
if $C(d,n,D)$ is large enough, then for each $i$ we can define $F^{\prime}$ to
injectively map the vertices in $Y^{\prime}\cap f^{-1}((p_{i},p_{i+1}])$ into
$Q_{i}^{n-d}\cap\mathbb{Z}^{n}$. In other words, $F^{\prime}$ is a $0$-sparse
map when restricted to the vertices of $Y^{\prime}$. Next, we will repeatedly
use Theorem 3 from the previous section to extend $F^{\prime}$ to all of
$Y^{\prime}$ so that it maps $f^{-1}([p_{i},p_{i}+1])$ into $Q_{i-1}\cup
Q_{i}$ and so that it is $d$-sparse on each such set. Here we define $Q_{-1}$
to be the empty set.

Define subcomplexes $Z_{i}^{k+1}=(Y^{\prime}(k)\cap
f^{-1}(p_{i}))\cup(Y^{\prime}(k+1)\cap f^{-1}(p_{i},p_{i+1}])\subset
Y^{\prime}$, which each have at most $C(d,n,D)W$ vertices. Suppose that for
some $0\leq i<N$ and some $0\leq k<d$, we have already defined $F^{\prime}$ on
each $Y^{\prime}\cap f^{-1}([p_{j},p_{j+1}])$, with $0\leq j<i$ so that it is
$d$-sparse on each such set and maps it into $Q_{j-1}\cup Q_{j}$. Suppose we
have also defined $F^{\prime}$ on the $k$-dimensional complex
$Z^{k+1}_{i}(k)$, so that it is $k$-sparse on this set and maps it into
$Q^{n-d+k}_{i-1}\cup Q^{n-d+k}_{i}$. If $C(d,n,D)$ is large enough, then
Theorem 3 tells us that we can extend $F^{\prime}$ to $Z^{k+1}_{i}$, so that
it is $(k+1)$-sparse on this set and maps it into $Q^{n-d+k+1}_{i-1}\cup
Q^{n-d+k+1}_{i}$. Proceeding in this way we get the desired map $F^{\prime}$
which is $d$-sparse on each $f^{-1}([p_{i},p_{i+1}])$ and maps this set into
$Q_{i-1}\cup Q_{i}$, for $0\leq i<N$. Let $R=\bigcup_{i=0}^{N-1}Q_{i}$. Then
$F^{\prime}$ maps $Y^{\prime}$ into $R$, and the $F^{\prime}$ pre-image of any
unit ball intersects at most $C(d,n,D)$ simplices from $Y^{\prime}$. The
rectangular prism $R$ has volume $C(d,n,D)^{n}NW^{\frac{n}{n-d}}\leq
C(d,n,D)^{n}VW^{\frac{d}{n-d}}$. Since one side of the prism is roughly $N$
times longer than all the others, and $N$ is much larger than 1, there is an
injective map that snakes $R$ into a ball of roughly the same volume as $R$,
and which is $C(n)$-bilipschitz on every unit ball. Let this map be

$S:R\to[0,C(d,n,D)V^{\frac{1}{n}}W^{\frac{d}{n(n-d)}}]^{n}\subset\mathbb{R}^{n}$

Note that the $S$ pre-image of any unit ball in $\mathbb{R}^{n}$ lies in a
ball of radius $C(n)$ in $R$. We define our final map to be $F=S\circ
F^{\prime}$. Since $Y^{\prime}$ is a subdivision of $Y$, the $F$ pre-image of
any unit ball intersects at most $C(d,n,D)$ simplices from $Y$. ∎

## References

  * [EK] Evra, S. and Kaufman, T. (2016, June). Bounded degree cosystolic expanders of every dimension. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (pp. 36-48).
  * [GE] Gromov, M. (2010). Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geometric and Functional Analysis, 20(2), 416-526.
  * [GG] Gromov M. and Guth L. Generalizations of the Kolmogorov-Barzdin embedding estimates. Duke Mathematical Journal. 2012 Oct;161(13):2549-603.
  * [KB] Kolmogorov A. N. and Barzdin, Y. M. (1993). On the realization of networks in three-dimensional space. Selected Works of AN Kolmogorov: Volume III: Information Theory and the Theory of Algorithms, 194-202.