# Anomalous supercurrent and diode effect in locally perturbed topological
Josephson junctions

Samuele Fracassi  Dipartimento di Fisica, Università di Genova, Via Dodecaneso
33, 16146, Genova, Italy  Simone Traverso  Dipartimento di Fisica, Università
di Genova, Via Dodecaneso 33, 16146, Genova, Italy  Niccolo Traverso Ziani
Dipartimento di Fisica, Università di Genova, Via Dodecaneso 33, 16146,
Genova, Italy  CNR-SPIN, Via Dodecaneso 33, 16146, Genova, Italy  Matteo
Carrega  CNR-SPIN, Via Dodecaneso 33, 16146, Genova, Italy  Stefan Heun  NEST,
Istituto Nanoscienze-CNR and Scuola Normale Superiore, Piazza San Silvestro
12, 56127 Pisa, Italy  Maura Sassetti  Dipartimento di Fisica, Università di
Genova, Via Dodecaneso 33, 16146, Genova, Italy  CNR-SPIN, Via Dodecaneso 33,
16146, Genova, Italy

###### Abstract

The simultaneous breaking of time-reversal and inversion symmetry can lead to
peculiar effects in Josephson junctions, such as the anomalous Josephson
effect or supercurrent rectification, which is a dissipationless analog of the
diode effect. Due to their impact in new quantum technologies, it is important
to find robust platforms and external means to manipulate the above effects in
a controlled way. Here, we theoretically consider a quantum spin Hall-based
Josephson junction subjected to a magnetic field in the direction defined by
spin-momentum locking, and in presence of a local tip in close proximity to
the normal region. We consider different local perturbations, model normal and
magnetic tips, and study how they affect the Josephson response of the device.
In particular, we argue that magnetic tips are a useful tool that allows for
tunability of both $\phi_{0}$ response and supercurrent rectification.

††preprint: AIP/123-QED

During the last years, there has been a widespread interest in the physics of
low-dimensional semiconductors featuring strong spin-orbit coupling (SOC).
Indeed, these systems offer an ideal platform to develop new architectures
able to coherently control electron spin, with great impact in spintronics and
topological quantum computing [1, 2, 3, 4, 5, 6]. Thanks to their strong SOC,
quantum spin Hall systems, such as HgTe/CdTe heterostructures [7, 8, 9], are
widely studied platforms presenting, among all, a non-trivial topological
phase with conducting helical edge channels[10, 11, 12, 13, 14, 15, 16, 17].
Furthermore, great interest has been recently dedicated to the interplay
between strong SOC and superconducting correlations [18, 19, 6, 20, 21, 22,
23, 24], leading for instance to several theoretical and experimental studies
on topological Josephson junctions (JJs) [25, 9, 4, 26, 27, 28, 29, 30, 31,
32]. These consist of SNS devices, where the normal (N) part, in between two
superconducting (S) contacts, resides in the topological phase. These
junctions can display fascinating physics, ranging from the emergence of
Majorana bound states [6, 11] to anomalous dc and ac Josephson responses [26,
9, 15, 33, 30]. In particular, it has been predicted that, in presence of a
small magnetic field, a topological JJ can sustain a finite supercurrent at
zero phase bias, the so-called $\phi_{0}$ effect [26]. At the heart of this
phenomenon is the simultaneous breaking of time-reversal and inversion
symmetry. Notably, it is well known that these two ingredients can lead to
non-reciprocal charge transport and form the theoretical basis behind the
diode effect.

Very recently [34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44], it has been
realized that a superconducting analog of the diode is possible, on the basis
of the same arguments, leading to dissipationless supercurrent rectification.
The supercurrent diode effect (SDE), can greatly impact low temperature
(superconducting) technology. The first experimental reports on SDE relied on
magnetic or layered bulk materials [38, 45, 46, 47, 48, 49, 50, 51], but
recent measurements on JJs, based for instance on III-V semiconductors, have
been also reported [52, 53, 54, 24, 55, 56]. Still, several questions on
dissipationless nonreciprocal transport are open, including its microscopic
origin [39, 57, 58, 59, 60, 61, 62] and its tunability by external means.

In the context of quantum spin Hall systems, in Ref. [26] it has been shown by
scattering matrix formalism that a bare topological JJ, subjected to a
longitudinal (parallel to the direction defined by spin-momentum locking)
magnetic field, can give rise to the anomalous Josephson effect. Moreover,
finite supercurrent rectification is present along a single helical edge,
while the effect disappears when considering the whole sample [26].

Inspired by the success in the field of Wigner crystallization[63, 64, 65], in
this work we consider a model of a quantum spin Hall-based topological JJ in
the presence of a closely spaced local tip. We model different tips that act
as local perturbations on the normal region. First, we show that a tip
capacitively coupled to the edge states does not alter at all the
supercurrent. Then, we demonstrate that a magnetic tip [66, 67, 68] with
magnetization parallel to the spin axis defined by spin-momentum locking (here
in the $z$-axis) only shifts the current-phase relation (CPR), thus
influencing the current at zero phase bias but not the SDE. Finally, a
magnetic tip with magnetization perpendicular to the previous one (hence along
any direction in the $xy$ plane) influences both the current at zero phase
bias and the SDE.

The system is modeled as two one-dimensional channels, located at the opposite
sides of the structure. Each channel is helical, and the helicity of the two
channels is opposite. Moreover, the system is partially proximitized by a
superconductor so to define a JJ [26], subjected to a magnetic field. We also
assume that only one of the edges (say the upper one) is perturbed by the tip.
Quantitatively, the model we use is represented by the Bogoliubov-de Gennes
Hamiltonian [69, 70, 71]

$H=\frac{1}{2}\left[\left(\sum_{\lambda=\pm}H_{\lambda}\right)+H_{t}\right].$
(1)

Here, $H_{\lambda}$ is the Hamiltonian of the unperturbed edges, with
$\lambda=\pm$ for the upper/lower edge, respectively, and $H_{t}$ describes
the interaction with the tip. We have

$H_{\lambda}=\int_{-\infty}^{\infty}\operatorname{d\\!}x\,\Psi^{{\dagger}}_{\lambda}(x)\mathcal{H}_{\lambda}(x)\Psi_{\lambda}(x),$
(2)

with the Hamiltonian density (hereafter we set $\hbar=1$)

$\mathcal{H}_{\lambda}(x)=-\lambda
v_{F}i\partial_{x}\tau_{z}\sigma_{z}+\Delta(x)\tau_{x}\sigma_{0}+\mathcal{U}_{z}\tau_{0}\sigma_{z},$
(3)

with basis
$\Psi_{\lambda}(x)=\left(\psi_{\lambda,\uparrow}(x),\psi_{\lambda,\downarrow}(x),\psi^{\dagger}_{\lambda,\downarrow}(x),-\psi^{\dagger}_{\lambda,\uparrow}(x)\right)^{T}$,
where $\psi_{\lambda,\uparrow/\downarrow}(x)$ are the Fermi field operators
for electrons in the edge $\lambda$ and with spin projection
$\uparrow/\downarrow$. Here, $v_{F}$ is the Fermi velocity, $\tau_{i}$ and
$\sigma_{i}$ ($i=0,x,y,z$) are the identity and the Pauli matrices in
particle-hole and spin space respectively and
$\Delta(x)=\Delta_{0}[\theta(-x-L/2)e^{i\varphi/2}+\theta(x-L/2)e^{-i\varphi/2}]$
is the superconducting pairing, with $L$ and $\varphi$ the distance and the
phase difference between the two superconducting sections. The parameter
$\Delta_{0}$ represents the effective amplitude of the proximitized
superconducting pairing seen by the edge states. Finally,
$\mathcal{U}_{z}=g\mu_{B}B_{z}$ is the energy associated to a finite magnetic
field $B_{z}$ via the usual Zeeman coupling, where
$\mu_{B}=$5.788\text{\times}{10}^{-5}\text{\,}\mathrm{eV}\text{\,}{\mathrm{T}}^{-1}$$
is the Bohr magneton and $g$ the effective gyromagnetic factor for the helical
edges. Both orbital effects and inter-edge interactions are neglected in our
analysis.

The Hamiltonian related to the tip, which only perturbs the upper edge
($\lambda=+$), is given by

$H_{t}=\int_{x_{0}-d/2}^{x_{0}+d/2}\operatorname{d\\!}x\sum_{\zeta=1}^{3}\Psi^{\dagger}_{+}(x)\mathcal{H}_{t}^{(\zeta)}(x)\Psi_{+}(x),$
(4)

where we have imposed that the tip only influences the system for
$x_{0}-d/2<x<x_{0}+d/2$, with $d>0$ representing the width of the tip, $\
x_{0}-d/2>-L/2,\ x_{0}+d/2<L/2$, and

$\displaystyle\mathcal{H}_{t}^{(1)}(x)$
$\displaystyle=\delta\mu\tau_{z}\sigma_{0},$ (5)
$\displaystyle\mathcal{H}_{t}^{(2)}(x)$
$\displaystyle=\delta\mathcal{U}_{z}\tau_{0}\sigma_{z},$ (6)
$\displaystyle\mathcal{H}_{t}^{(3)}(x)$
$\displaystyle=\delta\mathcal{U}_{x}\tau_{z}\sigma_{x}.$ (7)

Here, $\delta\mu$ represents a local capacitive coupling, and
$\delta\mathcal{U}_{z/x}=g\mu_{B}\delta B_{z/x}$ Zeeman energies related to
local magnetic fields parallel or perpendicular to the axis defined by spin-
momentum locking, respectively. In the following, the perturbations
$\mathcal{H}_{t}^{(\zeta)}$ will be addressed separately. Notably, none of our
results will bear any explicit dependence on the tip position $x_{0}$. A
schematic of the system is presented in Fig. 1.

Figure 1: Schematic of the system under study, consisting of a Josephson
junction lying in the $xy$ plane, with a topological insulator as the normal
part. A tip of size $d$ along the channel axis ($x$-axis) perturbs the upper
helical edge states with an Hamiltonian $\mathcal{H}_{t}$. The direction
defined by the spin-momentum locking in assumed parallel to the $z$-axis.

The quantity under investigation is the supercurrent $I(\varphi)$ as a
function of the phase difference between the two superconducting regions,
which are kept at the same voltage. The supercurrent is the sum of the
supercurrents $I_{\lambda}(\varphi)$ carried by the single edges. The current
$I_{\lambda}(\varphi)$ is evaluated by means of the scattering matrix
formalism [69, 70, 71], and in particular by using the relation [72]

$I_{\lambda}(\varphi)=-4eT\frac{\partial}{\partial\varphi}\sum_{\nu\,=\,0}^{\infty}\Re\left[\frac{1}{2}\ln[D_{\lambda}(i\omega_{\nu};\varphi)]\right].$
(8)

Here $\omega_{\nu}=(2\nu+1)\pi T$ are the thermal fermionic Matsubara
frequencies and $D_{\lambda}(z;\varphi)$ is the analytic continuation of
$\operatorname{Det}[\mathbb{I}-S_{\text{bound}_{\lambda}}(E,\varphi)]$ in the
upper complex plane. $S_{\text{bound}_{\lambda}}$ is the full scattering
matrix related to the Andreev bound states. These are subject to the bound
state condition $\Psi^{\text{Out}}_{\lambda}=\Psi^{\text{In}}_{\lambda}$,
where $\Psi^{\text{In}}_{\lambda}$ describes the in states and
$\Psi^{\text{Out}}_{\lambda}$ the out states for the edge $\lambda$. 111The
$1/2$ in front of the logarithm is necessary in order not to take into account
the negative energy states that arise from particle-hole symmetry.

For the problem at hand, the scattering matrix $S_{\text{bound}_{\lambda}}$ is
given by $S_{\text{bound}_{+}}=S_{A_{+}}S_{\text{prop}_{+}}$ for the upper
(perturbed) edge. In addition, one has
$S_{\text{bound}_{-}}=S_{A_{-}}S_{\text{prop}_{-}}^{\text{free}}$ for the
lower (unperturbed) edge. In the above expressions, $S_{A_{\lambda}}$
represents the scattering matrix associated to Andreev processes [70, 71]. The
explicit form of $S_{\text{bound}_{\lambda}}$ for the different cases is given
in the Supplementary Material (SM).

As discussed in Ref. [26], in the absence of the tip, one finds that
$I_{\lambda}(\varphi=0)\neq 0$, that is, the single edge shows a $\phi_{0}$
effect. Moreover, one has that
$|\mathrm{Max}_{\varphi}\left\\{I_{\lambda}(\varphi)\right\\}|\neq|\mathrm{Min}_{\varphi}\left\\{I_{\lambda}(\varphi)\right\\}|$,
_i.e._ , one has a finite SDE as well. However, one also finds that
$I_{\lambda}(\varphi)=-I_{-\lambda}(-\varphi)$, so that both the $\phi_{0}$
effect and the SDE vanish for the full system of two edges. Since the
rectification in the system without perturbation manifests in the short-
junction regime [26], in the following we consider this regime, taking
$L/\xi=0.1$, with $\xi=v_{F}/\Delta_{0}$ the superconducting coherence length.
For the present work we consider
$\Delta_{0}=$10\text{\,}\mathrm{\SIUnitSymbolMicro eV}$$ [18, 9] and
$v_{F}=$4.6\text{\times}{10}^{4}\text{\,}\mathrm{m}\text{\,}{\mathrm{s}}^{-1}$$,
yielding a coherence length of $\xi\sim$3\text{\,}\mathrm{\SIUnitSymbolMicro
m}$$ [18, 74]. Furthermore, we choose an effective gyromagnetic factor
$g=11.5$ that is a reasonable value for helical edge states [74]. These values
are compatible with those reported for InAs/GaSb [18, 74]. Hereafter we also
take the tip width $d/L=0.2$ which corresponds to a reasonable tip physical
dimension [66, 67, 68, 63]. It is worth anticipating that our results refer to
an overall magnetic field $\mathcal{U}_{z}$ applied in the $z$ direction which
is typically considered to be much smaller than the magnetic field induced by
the tip. Furthermore, we focus on the low temperature regime with
$T\ll\Delta_{0}$, _i.e._ , $T\ll$0.1\text{\,}\mathrm{K}$$.

Figure 2: (a) Comparison of the current-phase relation for the lower edge
($I_{-}$), upper edge without the tip ($I^{\text{free}}_{+}$), and upper edge
in presence of the tip ($I_{+}$), with $\mathcal{U}_{z}/\Delta_{0}=0.5$. (b)
Comparison of the current-phase relation for the full system (both edges) in
absence ($I^{{\rm free}}$) and presence ($I$) of the tip, with
$\mathcal{U}_{z}/\Delta_{0}=0.5$. The dashed gray lines emphasize the lack of
SDE in the total current. (c) Anomalous supercurrent
$I_{\phi_{0}}=I(\varphi=0)$ as a function of $\mathcal{U}_{z}/\Delta_{0}$. In
all plots, the field of the tip (when present) is set to
$\delta\mathcal{U}_{z}=$5.4\text{\times}{10}^{-4}\text{\,}\mathrm{eV}$$ which,
assuming $g=11.5$, corresponds to a magnetic field of
$0.83\text{\,}\mathrm{T}$. The temperature is $T=$10\text{\,}\mathrm{mK}$$.

A first result of the present article is that for finite $\delta\mu$, the
Josephson current remains identical to the one obtained in the absence of the
tip. This fact closely resembles the Klein tunneling [5, 6]. Interestingly,
this effect does not rely on the precise form chosen for $\delta\mu$, but it
holds true for any spatially varying profile. Our result hence implies that
the results of Ref. [26] are robust with respect to chemical potential
fluctuations. From a mathematical point of view, the phenomenon emerges from
the analytical form of $S_{\text{bound}_{+}}$, which reduces to

$S_{\text{bound}_{+}}=S_{A_{+}}S_{\text{prop}_{+}}^{\delta\mu}.$ (9)

The Andreev scattering matrix $S_{A_{+}}$ has the form

$S_{A_{+}}=\begin{pmatrix}\textbf{0}&\sigma_{A_{+}}\\\
\sigma_{A_{+}}&\textbf{0}\end{pmatrix},$ (10)

while $S_{\text{prop}_{+}}^{\delta\mu}$ factorizes as

$S_{\text{prop}_{+}}^{\delta\mu}=\begin{pmatrix}e^{i\delta\mu\,d/v_{F}}\,\mathbb{I}_{2\times
2}&\textbf{0}\\\ \textbf{0}&e^{-i\delta\mu\,d/v_{F}}\,\mathbb{I}_{2\times
2}\end{pmatrix}S_{\text{prop}_{+}}^{\text{free}},$ (11)

with $S_{\text{prop}_{+}}^{\text{free}}$ a diagonal matrix, describing the
propagation along the upper edge in the absence of the tip. Using the folding
identity for block matrices [69, 70], one can show that the contributions due
to $\delta\mu$ cancel out in the computation of $D_{+}(z;\varphi)$ of Eq. (8),
thus leaving the current unchanged with respect to the unperturbed case.

The effect related to a finite $\delta\mathcal{U}_{z}$, i.e., a magnetic tip
with magnetization parallel to the edge spin polarization, is different with
respect to the case just discussed. It turns out that the perturbation is
again a modification of the propagation matrix $S_{\text{prop}_{+}}$

$S_{\text{prop}_{+}}^{\delta\mathcal{U}_{z}}=\begin{pmatrix}e^{i\delta\mathcal{U}_{z}\,d/v_{F}}&0&0&0\\\
0&e^{-i\delta\mathcal{U}_{z}\,d/v_{F}}&0&0\\\
0&0&e^{i\delta\mathcal{U}_{z}\,d/v_{F}}&0\\\
0&0&0&e^{-i\delta\mathcal{U}_{z}\,d/v_{F}}\end{pmatrix}S_{\text{prop}_{+}}^{\text{free}},$
(12)

but in a way that maintains the presence of the perturbation in Eq. (8), where
it manifests itself as a current-phase shift. Analytically, the phase shift is
described by the following relation

$I_{+}(\varphi)\equiv
I_{+}^{\text{free}}(\varphi-2\delta\mathcal{U}_{z}d/v_{F})=-I_{-}(2\delta\mathcal{U}_{z}d/v_{F}-\varphi),$
(13)

where $I_{+}^{\text{free}}(\varphi)$ is the CPR that one would obtain for the
upper edge in absence of the tip. This fact is shown in Fig. 2(a), where the
dashed curve represents the CPR in absence of the tip and the solid blue curve
its translation due to the presence of the local $\delta\mathcal{U}_{z}$. For
the parameters chosen ($\mathcal{U}_{z}/\Delta_{0}=0.5$) the shift in the CPR
is such that the anomalous current in the upper edge almost vanishes.

From the point of view of non-reciprocal transport, a finite
$\delta\mathcal{U}_{z}$ surprisingly does not result in any rectification,
although the critical current is affected. Indeed, this is visible in Fig.
2(b): the maximum and minimum supercurrent amplitudes are equal, and thus no
rectification is expected. Finally, from Eq. (13) one can see that the
perturbation shifts the CPR of the perturbed edge, hence producing a finite
anomalous supercurrent in the full structure, as shown in Fig. 2(c). This fact
is remarkable, since it allows to manipulate the anomalous supercurrent by
means of local perturbations.

Figure 3: (a) Comparison of the current-phase relation for the lower edge
($I_{-}$), upper edge without the tip ($I^{\text{free}}_{+}$), and upper edge
in presence of the tip ($I_{+}$), with $\mathcal{U}_{z}/\Delta_{0}=0.5$. (b)
Comparison of the current-phase relations for the full system in presence of
the tip, for different values of $\mathcal{U}_{z}/\Delta_{0}$, indicated by
the subscripts in the legend. (c) Anomalous supercurrent $I_{\phi_{0}}$ as a
function of $\mathcal{U}_{z}/\Delta_{0}$. In all plots, the field of the tip
(when present) is set to
$\delta\mathcal{U}_{x}=$4.5\text{\times}{10}^{-4}\text{\,}\mathrm{eV}$$ which,
assuming $g=11.5$, corresponds to a magnetic field of
$0.69\text{\,}\mathrm{T}$. The temperature is $T=$10\text{\,}\mathrm{mK}$$.

In the case of finite $\delta\mathcal{U}_{x}$, i.e., a magnetic tip with
perpendicular magnetization with respect to the edge spin polarization, the
scenario is more complex. Indeed, such term acts as a barrier to the
supercurrent, so that the critical current in the perturbed edge decreases.
This fact implies, for the full system, both the presence of SDE and of
anomalous supercurrent. This phenomenology arises from the fact that in the
case of a transverse magnetic field, the perturbation does not commute with
the free Hamiltonian. Therefore, in the perturbed region an energy gap is
opened in the linear dispersion relations, causing the energy eigenstates in
this magnetic gap to be exponentially suppressed. For this reason, these
states contribute to the supercurrent in a minor way. Moreover, the transfer
matrix $S_{\text{prop}_{+}}^{\delta\mathcal{U}_{x}}$ presents off-diagonal
terms, that contain the spin-flip amplitudes (see the SM). The consequence of
these effects is a change of the CPR and in particular a suppression in the
magnitude (Fig. 3(a)). This leads to an imbalance between the maximum and
minimum value of the CPR in the two edges and, consequently, to a
rectification that depends on the two magnetic scales present
($\mathcal{U}_{z}$ and $\delta\mathcal{U}_{x}$). In particular, if
$\mathcal{U}_{z}$ is increased over $\Delta_{0}$, the diode effect vanishes
(cf. Fig. 3(b)). The amplitude imbalance manifests also at $\varphi=0$ and so
in the total anomalous supercurrent. This is represented in Fig. 3(c), where
the anomalous supercurrent $I_{\phi_{0}}$ is plotted as a function of
$\mathcal{U}_{z}/\Delta_{0}$: this quantity vanishes both for
$\mathcal{U}_{z}\ll\Delta_{0}$ and $\mathcal{U}_{z}\gg\Delta_{0}$, reaching
the maximum amplitude around $\mathcal{U}_{z}\sim\Delta_{0}$.

In order to quantify the rectification effect, we compute the _rectification
coefficient_ [53, 52, 47], which is defined as

$\eta[I]=\left|\frac{|\mathrm{Max}_{\varphi}\left\\{I(\varphi)\right\\}|-|\mathrm{Min}_{\varphi}\left\\{I(\varphi)\right\\}|}{|\mathrm{Max}_{\varphi}\left\\{I(\varphi)\right\\}|+|\mathrm{Min}_{\varphi}\left\\{I(\varphi)\right\\}|}\right|.$
(14)

In Fig. 4(a) we plot the rectification coefficient for the total current
($\eta[I]\equiv\eta$), and for the upper edge current
($\eta[I_{+}]\equiv\eta_{+}$), as a function of the tip strength
$\delta\mathcal{U}_{x}$. By increasing $\delta\mathcal{U}_{x}$, we find that
$\eta$ reaches a (sharp) maximum and then decreases to a plateau. Looking at
the rectification of the single upper edge, it presents a simpler (monotonous)
structure, with a vanishing $\eta_{+}$ at large $\delta\mathcal{U}_{x}$.

To understand the physical origin of the peak in the rectification
coefficient, in Fig. 4(b) we plot the CPRs for the lower edge, upper edge (in
presence of the tip) and for the full system, with $\delta\mathcal{U}_{x}$ set
to the value for which $\eta$ reaches its maximum
($\equiv\delta\mathcal{U}_{x}^{\text{peak}}$). By comparing the three curves,
one can see that the minimum of $I$ almost coincides with the minimum of
$I_{-}$, since $I_{+}$ has a node close to where the minimum of $I_{-}$
occurs. On the other hand, due to the fact that $I_{+}$ is suppressed by the
transverse magnetic field of the tip, the maximum of $I$ (which for
$\delta\mathcal{U}_{x}=0$ coincides with the maximum of $I_{+}$) moves in the
direction of the maximum of $I_{-}$ as $\delta\mathcal{U}_{x}$ is increased.
In addition, for intermediate values of $\delta\mathcal{U}_{x}$ (i.e., as long
as $I_{+}$ is not completely suppressed) the maximum value of $I$ decreases in
magnitude. For this reason there is an increasing unbalance between the
maximum and minimum value of $I$. For higher values of
$\delta\mathcal{U}_{x}^{\text{peak}}$, the suppression of $I_{+}$ causes the
maximum value of $I_{-}$ to be increasingly influential in the CPR, and
consequently the maximum of $I$ begins to increase its value until, when
$I_{+}$ is fully suppressed, it reaches the maximum of $I_{-}$. This explains
the presence of a peak in $\eta$ as well as the successive plateau. Indeed,
for $\delta\mathcal{U}_{x}\gg\delta\mathcal{U}_{x}^{\text{peak}}$ the
supercurrent in the upper edge is fully suppressed ($I_{+}\approx 0$) and
therefore $I\approx I_{-}$. Thus,
$\eta(\delta\mathcal{U}_{x}\to\infty)\approx\eta[I_{-}]=\eta_{+}(0)$, meaning
that the plateau in $\eta$ corresponds to the value of the rectification for a
single (unperturbed) edge.

Given the mechanism leading to the non-monotonous behaviour in the
rectification just described, one may wonder if by varying the field
$\mathcal{U}_{z}$ (and so shifting the CPRs of both the upper and lower edge
in opposite directions in phase space) it is possible to reach the peak at
lower (experimentally more accessible 222Notice that for the value
$\mathcal{U}_{z}=0.5\Delta_{0}$ chosen in Fig. 4(a-b) the magnetic field at
the peak position $\delta\mathcal{U}_{x}\sim 80\Delta_{0}$ is of the order of
$\sim$1.25\text{\,}\mathrm{T}$$.) values of $\delta\mathcal{U}_{x}$. It turns
out that this is indeed the case. In Fig. 4(c) we report plots of $\eta$ as a
function of $\delta\mathcal{U}_{x}$ for different values of $\mathcal{U}_{z}$:
one can clearly see that for values of $\mathcal{U}_{z}$ higher then
$\Delta_{0}/2$ (but still lower than $\Delta_{0}$), the peak moves to
significantly smaller values of $\delta\mathcal{U}_{x}$, while maintaining
sizeable (even larger) height.

Figure 4: (a) Comparison between the rectification coefficient associated to
the total current ($\eta(I)\equiv\eta$) and the one associated to the upper
edge current ($\eta(I_{+})\equiv\eta_{+}$) as a function of the tip field
strength $\delta\mathcal{U}_{x}$, for $\mathcal{U}_{z}/\Delta_{0}=0.5$. $\eta$
presents a sharp peak around $\delta\mathcal{U}_{x}/\Delta_{0}\sim 80$. (b)
Comparison of the current-phase relation for the lower edge ($I_{-}$), upper
edge ($I_{+}$), and full system ($I$) in presence of the tip with
$\delta\mathcal{U}_{x}/\Delta_{0}=80$, obtained for
$\mathcal{U}_{z}/\Delta_{0}=0.5$. (c) Comparison of the full system
rectification coefficient $\eta$ for different values of the magnetic field
$\mathcal{U}_{z}$. The subscript of $\eta$ in the curve labels denotes the
value of $\mathcal{U}_{z}/\Delta_{0}$.

In conclusion, we have considered the effects of local perturbations provided
by a tip on the anomalous supercurrent and on the SDE in Josephson junctions
based on a two dimensional topological insulator. We have shown that a
capacitive coupling modelled as a chemical potential step has no effect on the
transport properties, providing a generalization of the Klein paradox.
Subsequently, we have shown that a magnetic coupling in the direction of the
spin-momentum locking rigidly shifts, at the level of the single edge, the
current-phase relation. It hence enables the manipulation of the anomalous
supercurrent at the level of the full structure with two edges. However, it
does not generate any SDE, although it influences the critical current.
Finally, we have shown that a magnetic coupling perpendicular to the direction
of spin-momentum locking is able to generate both anomalous supercurrent and
SDE at the level of the full structure.

We argue that our results could be observable in InAs/GaSb quantum wells in
the helical regime. Indeed, the numerical values considered for $v_{F},\ g,\
\Delta_{0}$ are compatible with those actually measured in the proposed
material [18, 74], and magnetic fields of the tip below $1\text{\,}\mathrm{T}$
are now experimentally achievable.[66, 67, 68] Even more favorable conditions
in terms of $g$-factor and Fermi velocity are met in 2D spin-orbit coupled
quantum gases, for which single edge theory could be effectively employed. Our
work could hence provide a theoretical support to experiments aiming at the
design of manipulable anomalous supercurrents and SDE.

###### Acknowledgements.

N. T. Z. acknowledges the funding through the NextGeneration EU Curiosity-
driven project "Understanding even-odd criticality". The authors acknowledge
the funding from the project "Non-reciprocal supercurrent and topological
transitions in InSb nanoflags" No. Prot. 2022PH852L in the framework of the
Prin 2022 of MUR for the Italian National Research Program (PNRR). S. H.
acknowledges partial support by PNRR MUR Project No. PE0000023-NQSTI.

## Data Availability Statement

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

## References

  * Nowack  _et al._ [2007] K. C. Nowack, F. H. L. Koppens, Y. V. Nazarov, and L. M. K. Vandersypen, Science 318, 1430 (2007).
  * Bercioux and Lucignano [2015] D. Bercioux and P. Lucignano, Reports on Progress in Physics 78, 106001 (2015).
  * Manchon  _et al._ [2015] A. Manchon, H. C. Koo, J. Nitta, S. M. Frolov, and R. A. Duine, Nature Materials 14, 871 (2015).
  * Moehle  _et al._ [2021] C. M. Moehle, C. T. Ke, Q. Wang, C. Thomas, D. Xiao, S. Karwal, M. Lodari, V. van de Kerkhof, R. Termaat, G. C. Gardner, G. Scappucci, M. J. Manfra, and S. Goswami, Nano Letters 21, 9990 (2021).
  * Haldane [2017] F. D. M. Haldane, Rev. Mod. Phys. 89, 040502 (2017).
  * Prada  _et al._ [2020] E. Prada, P. San-Jose, M. W. A. de Moor, A. Geresdi, E. J. H. Lee, J. Klinovaja, D. Loss, J. Nygård, R. Aguado, and L. P. Kouwenhoven, Nature Reviews Physics 2, 575 (2020).
  * Bernevig, Hughes, and Zhang [2006] B. A. Bernevig, T. L. Hughes, and S.-C. Zhang, Science 314, 1757 (2006).
  * König  _et al._ [2007] M. König, S. Wiedmann, C. Brüne, A. Roth, H. Buhmann, L. W. Molenkamp, X.-L. Qi, and S.-C. Zhang, Science 318, 766 (2007).
  * Deacon  _et al._ [2017] R. S. Deacon, J. Wiedenmann, E. Bocquillon, F. Domínguez, T. M. Klapwijk, P. Leubner, C. Brüne, E. M. Hankiewicz, S. Tarucha, K. Ishibashi, H. Buhmann, and L. W. Molenkamp, Phys. Rev. X 7, 021011 (2017).
  * Wu, Bernevig, and Zhang [2006] C. Wu, B. A. Bernevig, and S.-C. Zhang, Phys. Rev. Lett. 96, 106401 (2006).
  * Qi, Hughes, and Zhang [2008] X.-L. Qi, T. L. Hughes, and S.-C. Zhang, Nature Physics 4, 273 (2008).
  * Dolcetto, Sassetti, and Schmidt [2016] G. Dolcetto, M. Sassetti, and T. L. Schmidt, La Rivista del Nuovo Cimento 39, 113 (2016).
  * Ronetti  _et al._ [2016] F. Ronetti, L. Vannucci, G. Dolcetto, M. Carrega, and M. Sassetti, Phys. Rev. B 93, 165414 (2016).
  * Traverso Ziani  _et al._ [2017] N. Traverso Ziani, C. Fleckenstein, G. Dolcetto, and B. Trauzettel, Phys. Rev. B 95, 205418 (2017).
  * Vigliotti  _et al._ [2022] L. Vigliotti, A. Calzona, B. Trauzettel, M. Sassetti, and N. T. Ziani, New Journal of Physics 24, 053017 (2022).
  * Jia  _et al._ [2022] J. Jia, E. Marcellina, A. Das, M. S. Lodge, B. Wang, D.-Q. Ho, R. Biswas, T. A. Pham, W. Tao, C.-Y. Huang, H. Lin, A. Bansil, S. Mukherjee, and B. Weber, Nature Communications 13, 6046 (2022).
  * Traverso, Sassetti, and Traverso Ziani [2024] S. Traverso, M. Sassetti, and N. Traverso Ziani, npj Quantum Materials 9, 9 (2024).
  * Pribiag  _et al._ [2015] V. S. Pribiag, A. J. A. Beukman, F. Qu, M. C. Cassidy, C. Charpentier, W. Wegscheider, and L. P. Kouwenhoven, Nature Nanotechnology 10, 593 (2015).
  * Qu  _et al._ [2016] F. Qu, J. van Veen, F. K. de Vries, A. J. A. Beukman, M. Wimmer, W. Yi, A. A. Kiselev, B.-M. Nguyen, M. Sokolich, M. J. Manfra, F. Nichele, C. M. Marcus, and L. P. Kouwenhoven, Nano Letters 16, 7509 (2016).
  * Rasmussen  _et al._ [2016] A. Rasmussen, J. Danon, H. Suominen, F. Nichele, M. Kjaergaard, and K. Flensberg, Phys. Rev. B 93, 155406 (2016).
  * Salimian  _et al._ [2021] S. Salimian, M. Carrega, I. Verma, V. Zannier, M. P. Nowak, F. Beltram, L. Sorba, and S. Heun, Applied Physics Letters 119, 214004 (2021).
  * Iorio  _et al._ [2023] A. Iorio, A. Crippa, B. Turini, S. Salimian, M. Carrega, L. Chirolli, V. Zannier, L. Sorba, E. Strambini, F. Giazotto, and S. Heun, Phys. Rev. Res. 5, 033015 (2023).
  * Kaperek  _et al._ [2022] K. Kaperek, S. Heun, M. Carrega, P. Wójcik, and M. P. Nowak, Phys. Rev. B 106, 035432 (2022).
  * Baumgartner  _et al._ [2022] C. Baumgartner, L. Fuchs, A. Costa, S. Reinhardt, S. Gronin, G. C. Gardner, T. Lindemann, M. J. Manfra, P. E. Faria Junior, D. Kochan, J. Fabian, N. Paradiso, and C. Strunk, Nature Nanotechnology 17, 39 (2022).
  * Fu and Kane [2009] L. Fu and C. L. Kane, Phys. Rev. B 79, 161408 (2009).
  * Dolcini, Houzet, and Meyer [2015] F. Dolcini, M. Houzet, and J. S. Meyer, Phys. Rev. B 92, 035428 (2015).
  * Calzona and Trauzettel [2022] A. Calzona and B. Trauzettel, Phys. Rev. Res. 4, 013182 (2022).
  * Blasi  _et al._ [2020] G. Blasi, F. Taddei, L. Arrachea, M. Carrega, and A. Braggio, Phys. Rev. Lett. 124, 227701 (2020).
  * Blasi  _et al._ [2021] G. Blasi, F. Taddei, L. Arrachea, M. Carrega, and A. Braggio, Phys. Rev. B 103, 235434 (2021).
  * Zhang  _et al._ [2022a] X. Zhang, Z. Lyu, G. Yang, B. Li, Y.-L. Hou, T. Le, X. Wang, A. Wang, X. Sun, E. Zhuo, G. Liu, J. Shen, F. Qu, and L. Lu, Chinese Physics Letters 39, 017401 (2022a).
  * Vigliotti  _et al._ [2023a] L. Vigliotti, A. Calzona, N. Traverso Ziani, F. S. Bergeret, M. Sassetti, and B. Trauzettel, Nanomaterials 13, 569 (2023a).
  * Vigliotti  _et al._ [2023b] L. Vigliotti, F. Cavaliere, G. Passetti, M. Sassetti, and N. Traverso Ziani, Nanomaterials 13, 1497 (2023b).
  * Strambini  _et al._ [2020] E. Strambini, A. Iorio, O. Durante, R. Citro, C. Sanz-Fernández, C. Guarcello, I. V. Tokatly, A. Braggio, M. Rocci, N. Ligato, V. Zannier, L. Sorba, F. S. Bergeret, and F. Giazotto, Nature Nanotechnology 15, 656 (2020).
  * Hu, Wu, and Dai [2007] J. Hu, C. Wu, and X. Dai, Phys. Rev. Lett. 99, 067004 (2007).
  * Wakatsuki  _et al._ [2017] R. Wakatsuki, Y. Saito, S. Hoshino, Y. M. Itahashi, T. Ideue, M. Ezawa, Y. Iwasa, and N. Nagaosa, Science Advances 3, e1602390 (2017).
  * Hoshino  _et al._ [2018] S. Hoshino, R. Wakatsuki, K. Hamamoto, and N. Nagaosa, Phys. Rev. B 98, 054510 (2018).
  * Yasuda  _et al._ [2019] K. Yasuda, H. Yasuda, T. Liang, R. Yoshimi, A. Tsukazaki, K. S. Takahashi, N. Nagaosa, M. Kawasaki, and Y. Tokura, Nature Communications 10, 2734 (2019).
  * Ando  _et al._ [2020] F. Ando, Y. Miyasaka, T. Li, J. Ishizuka, T. Arakawa, Y. Shiota, T. Moriyama, Y. Yanase, and T. Ono, Nature 584, 373 (2020).
  * Misaki and Nagaosa [2021] K. Misaki and N. Nagaosa, Phys. Rev. B 103, 245302 (2021).
  * Daido, Ikeda, and Yanase [2022] A. Daido, Y. Ikeda, and Y. Yanase, Phys. Rev. Lett. 128, 037001 (2022).
  * Lu  _et al._ [2023] B. Lu, S. Ikegaya, P. Burset, Y. Tanaka, and N. Nagaosa, Phys. Rev. Lett. 131, 096001 (2023).
  * Reinhardt  _et al._ [2023] S. Reinhardt, T. Ascherl, A. Costa, J. Berger, S. Gronin, G. C. Gardner, T. Lindemann, M. J. Manfra, J. Fabian, D. Kochan, C. Strunk, and N. Paradiso, (2023), arXiv:2308.01061 [cond-mat.supr-con] .
  * Souto  _et al._ [2023] R. S. Souto, M. Leijnse, C. Schrade, M. Valentini, G. Katsaros, and J. Danon, (2023), arXiv:2312.09204 [cond-mat.supr-con] .
  * Cayao, Nagaosa, and Tanaka [2024] J. Cayao, N. Nagaosa, and Y. Tanaka, Phys. Rev. B 109, L081405 (2024).
  * Yuan and Fu [2022] N. F. Q. Yuan and L. Fu, Proceedings of the National Academy of Sciences 119, e2119548119 (2022).
  * Bauriedl  _et al._ [2022] L. Bauriedl, C. Bäuml, L. Fuchs, C. Baumgartner, N. Paulik, J. M. Bauer, K.-Q. Lin, J. M. Lupton, T. Taniguchi, K. Watanabe, C. Strunk, and N. Paradiso, Nature Communications 13, 4266 (2022).
  * Strambini  _et al._ [2022] E. Strambini, M. Spies, N. Ligato, S. Ilić, M. Rouco, C. González-Orellana, M. Ilyn, C. Rogero, F. S. Bergeret, J. S. Moodera, P. Virtanen, T. T. Heikkilä, and F. Giazotto, Nature Communications 13, 2431 (2022).
  * Yun  _et al._ [2023] J. Yun, S. Son, J. Shin, G. Park, K. Zhang, Y. J. Shin, J.-G. Park, and D. Kim, Phys. Rev. Res. 5, L022064 (2023).
  * Wu  _et al._ [2022] H. Wu, Y. Wang, Y. Xu, P. K. Sivakumar, C. Pasco, U. Filippozzi, S. S. P. Parkin, Y.-J. Zeng, T. McQueen, and M. N. Ali, Nature 604, 653 (2022).
  * Sundaresh  _et al._ [2023] A. Sundaresh, J. I. Väyrynen, Y. Lyanda-Geller, and L. P. Rokhinson, Nature Communications 14, 1628 (2023).
  * Hou  _et al._ [2023] Y. Hou, F. Nichele, H. Chi, A. Lodesani, Y. Wu, M. F. Ritter, D. Z. Haxell, M. Davydova, S. Ilić, O. Glezakou-Elbert, A. Varambally, F. S. Bergeret, A. Kamra, L. Fu, P. A. Lee, and J. S. Moodera, Phys. Rev. Lett. 131, 027001 (2023).
  * Turini  _et al._ [2022] B. Turini, S. Salimian, M. Carrega, A. Iorio, E. Strambini, F. Giazotto, V. Zannier, L. Sorba, and S. Heun, Nano Letters 22, 8502 (2022).
  * Davydova, Prembabu, and Fu [2022] M. Davydova, S. Prembabu, and L. Fu, Science Advances 8, eabo0309 (2022).
  * Souto, Leijnse, and Schrade [2022] R. S. Souto, M. Leijnse, and C. Schrade, Phys. Rev. Lett. 129, 267702 (2022).
  * Wang  _et al._ [2024] J. Wang, Y. Jiang, J. J. Wang, and J.-F. Liu, Phys. Rev. B 109, 075412 (2024).
  * Pillet  _et al._ [2023] J.-D. Pillet, S. Annabi, A. Peugeot, H. Riechert, E. Arrighi, J. Griesmar, and L. Bretheau, Phys. Rev. Res. 5, 033199 (2023).
  * He, Tanaka, and Nagaosa [2022] J. J. He, Y. Tanaka, and N. Nagaosa, New Journal of Physics 24, 053014 (2022).
  * Ilić and Bergeret [2022] S. Ilić and F. S. Bergeret, Phys. Rev. Lett. 128, 177001 (2022).
  * Zhang  _et al._ [2022b] Y. Zhang, Y. Gu, P. Li, J. Hu, and K. Jiang, Phys. Rev. X 12, 041013 (2022b).
  * Costa, Fabian, and Kochan [2023] A. Costa, J. Fabian, and D. Kochan, Phys. Rev. B 108, 054522 (2023).
  * Steiner  _et al._ [2023] J. F. Steiner, L. Melischek, M. Trahms, K. J. Franke, and F. von Oppen, Phys. Rev. Lett. 130, 177002 (2023).
  * Coraiola  _et al._ [2024] M. Coraiola, A. E. Svetogorov, D. Z. Haxell, D. Sabonis, M. Hinderling, S. C. ten Kate, E. Cheah, F. Krizek, R. Schott, W. Wegscheider, J. C. Cuevas, W. Belzig, and F. Nichele, ACS Nano 18, 9221 (2024), pMID: 38488287, https://doi.org/10.1021/acsnano.4c01642 .
  * Qian, Halperin, and Heller [2010] J. Qian, B. I. Halperin, and E. J. Heller, Phys. Rev. B 81, 125323 (2010).
  * Ziani, Cavaliere, and Sassetti [2013] N. T. Ziani, F. Cavaliere, and M. Sassetti, Europhysics Letters 102, 47006 (2013).
  * Shapir  _et al._ [2019] I. Shapir, A. Hamo, S. Pecker, C. P. Moca, O. Legeza, G. Zarand, and S. Ilani, Science 364, 870 (2019).
  * Michlmayr  _et al._ [2006] T. Michlmayr, N. Saratz, A. Vaterlaus, D. Pescia, and U. Ramsperger, Journal of Applied Physics 99, 08N502 (2006).
  * Phark and Sander [2017] S.-h. Phark and D. Sander, Nano Convergence 4, 8 (2017).
  * Haze  _et al._ [2019] M. Haze, H.-H. Yang, K. Asakawa, N. Watanabe, R. Yamamoto, Y. Yoshida, and Y. Hasegawa, Review of Scientific Instruments 90, 013704 (2019).
  * Beenakker [1991] C. W. J. Beenakker, Phys. Rev. Lett. 67, 3836 (1991).
  * Beenakker and van Houten [1992] C. W. J. Beenakker and H. van Houten, in  _Nanostructures and Mesoscopic Systems_, edited by W. P. Kirk and M. A. Reed (Academic Press, 1992) pp. 481–497.
  * Beenakker [1992] C. W. J. Beenakker, in  _Transport Phenomena in Mesoscopic Systems_ , edited by H. Fukuyama and T. Ando (Springer Berlin Heidelberg, Berlin, Heidelberg, 1992) pp. 235–253.
  * Dolcini and Giazotto [2007] F. Dolcini and F. Giazotto, Phys. Rev. B 75, 140511 (2007).
  * Note [1] The $1/2$ in front of the logarithm is necessary in order not to take into account the negative energy states that arise from particle-hole symmetry.
  * Mu, Sullivan, and Du [2016] X. Mu, G. Sullivan, and R.-R. Du, Applied Physics Letters 108, 012101 (2016).
  * Note [2] Notice that for the value $\mathcal{U}_{z}=0.5\Delta_{0}$ chosen in Fig. 4(a-b) the magnetic field at the peak position $\delta\mathcal{U}_{x}\sim 80\Delta_{0}$ is of the order of $\sim$1.25\text{\,}\mathrm{T}$$.


# Better magneto-optical filters with cascaded vapor cells in the Faraday-
Faraday and Faraday-Voigt geometries.

Fraser D. Logue  Department of Physics, Durham University, Durham, DH1 3LE,
United Kingdom  Corresponding author<EMAIL_ADDRESS>Jack D.
Briscoe  Department of Physics, Durham University, Durham, DH1 3LE, United
Kingdom  Danielle Pizzey  Department of Physics, Durham University, Durham,
DH1 3LE, United Kingdom  Steven A. Wrathmall  Department of Physics, Durham
University, Durham, DH1 3LE, United Kingdom  Ifan G. Hughes  Department of
Physics, Durham University, Durham, DH1 3LE, United Kingdom

###### Abstract

Single-cell magneto-optical Faraday filters find great utility and are
realized with either ‘wing’ or ‘line center’ spectral profiles. We show that
cascading a second cell with independent axial (Faraday) or transverse (Voigt)
magnetic field leads to improved performance in terms of figure of merit (FOM)
and spectral profile. The first cell optically rotates the plane of
polarization of light creating the high transmission window; the second cell
selectively absorbs the light eliminating unwanted transmission. Using
naturally-abundant Rb vapor cells, we realize a Faraday-Faraday wing filter
and the first recorded Faraday-Voigt line center filter which show excellent
agreement with theory. The two filters have FOM values of 0.86 and 1.63 GHz-1
respectively, the latter of which is the largest FOM atomic line filter
recorded.

††journal: ol

Magneto-optical effects can be used to probe all kinds of matter [1, 2, 3]
from non-invasive magnetometry of livestock [4] to black hole accretion flows
[5] and vacuum birefringence [6]. Atomic line filtering is an advantageous
magneto-optical bandpass technique owing to its high transmission,
polarization sensitivity and tunability [7]. Applications vary widely
including weak signal detection [8], quantum information processing [9, 10],
self-stabilizing laser systems [11, 12, 13], atmospheric [14] and ocean
temperature measurements [15]. Single cell Faraday filters, where a magnetic
field is exerted parallel to the k-vector of the light, are discussed widely
in the literature [16, 17, 18, 19] in particular in rubidium vapor [20, 21,
22]. Spectroscopy in the Voigt geometry, with a magnetic field perpendicular
to the k-vector of the light, is less explored [23, 24] though several single
cell Voigt filters have been built [25, 26, 27]. Dependent on the application,
a filter can be ‘line center’ where filter transmission occurs at the center
of the atomic resonance or a ‘wing’ type where transmission is detuned from
center [28].

Figure 1: A schematic of the experimental setup. Light from an external cavity
diode (ECD) laser on the Rb-D2 line passes through an optical isolator (OI)
and is divided into two paths: reference and experiment optics. The laser
power is attenuated with a neutral density (ND) filter. The first cell in both
experiments is placed between crossed Glan-Taylor polarizers (GTP) with an
axial magnetic field generated by a solenoid. The solenoid also heats the
atoms to reach the required number density. The second cell is placed in
either a transverse (line center) or axial (wing) magnetic field. The second
cell rests in a separate copper heater. In the wing filter experiment there is
a quarter waveplate before the second cell, whereas in the line center
experiment, the second cell is placed before the second GTP. We detect output
signals with photodetectors (P.D). PBS - Polarizing Beamsplitter, 50:50 BS -
50:50 Beamsplitter

Cascaded wing Faraday-Faraday setups are employed extensively in solar filter
setups [29, 30, 31] which typically exploit magnetic fields on the order of 1
kG. While magnetic fields homogeneous over the length scale of vapor cells at
this magnitude have been realized [32, 33], high performance Faraday-Faraday
filters in low fields have not yet been presented. Voigt-Voigt and Voigt-
Faraday filters have been presented in [34] but to our knowledge a Faraday-
Voigt configuration has not been discussed in the literature previously.

Figure 2: A Rb-D2 Faraday-Faraday wing filter output (purple) for four
magnetic fields across the second cell a) Zero field, b) $373$ G, c) $747$ G,
d) $2000$ G. Fixed parameters are $T_{1}\leavevmode\nobreak\
=\leavevmode\nobreak\ 86^{\circ}\rm{C},\hskip 1.42271pt\textit{B}_{1}=49\hskip
1.42271pt\rm{G},\hskip 1.42271pt\textit{T}_{2}=110^{\circ}\rm{C}$ with cell
lengths 75 mm and 5 mm. In red, the transmission through the second cell given
left hand circular light input. In blue, the filter output if the second cell
is removed. In olive, the evolution of the figure of merit (FOM) with second
cell magnetic field. The heat map shows the transmission through the second
cell given left hand circular light with evolving second cell magnetic field.
We experimentally realize the filter with the parameters shown in (c) (see
Fig. 4).

In this Letter, we demonstrate improved wing and line center filter
performance on the Rb-D2 line by adding a second cell which absorbs light from
the first cell in unwanted transmission regions. We theoretically compute
parameters using a modified version of ElecSus [35, 36] and experimentally
realize a Faraday-Faraday wing filter and a Faraday-Voigt line center filter
which show excellent agreement with theory. The former is an improvement on
previous Rb wing filters and the latter is the largest figure of merit atomic
line filter realized to date.

Figure 3: A Rb-D2 Faraday-Voigt line center filter output (purple) for four
magnetic fields across the second cell e) Zero field, f) $1254$ G, g) $2528$
G, h) $3000$ G. Fixed parameters are $T_{1}=100^{\circ}\rm{C},\hskip
1.42271pt\textit{B}_{1}=162\hskip 1.42271pt\rm{G},\hskip
1.42271pt\textit{T}_{2}=121^{\circ}\rm{C}$ with cell lengths 5 mm and 5 mm. In
red, the transmission through the second cell given vertical light input. In
blue, the filter output if the second cell is removed. In olive, the evolution
of FOM with second cell magnetic field. The heat map shows the transmission
through the second cell given vertical light input with evolving second cell
magnetic field. We experimentally realize the filter with the parameters shown
in (g) (see Fig. 4). This cascaded-cell filter has both an improved FOM and
better spectral profile than single-cell filters.

We use a figure of merit (FOM) to evaluate filter performance first introduced
in [37]. $\rm{FOM}=$ $\mathcal{T}({\nu}_{\rm{s}})/\rm{ENBW}$ where
$\mathcal{T}({\nu}_{\rm{s}})$ is the transmission of the signal frequency,
$\nu_{\rm{s}}$. The equivalent noise bandwidth is defined as
$\rm{ENBW}=\int$$\mathcal{T}({\nu})$$\rm{d}$${\nu}$/$\mathcal{T}({\nu}_{\rm{s}})$
where ${\nu}$ is the optical frequency. Our figure of merit seeks to maximize
the transmission at the signal frequency while minimizing the equivalent noise
bandwidth. Optimizations with natural abundance Rb in ElecSus show that
Faraday-Voigt is the highest figure of merit configuration whereas a Faraday-
Faraday configuration yields the best wing lineshapes.
The schematic of our setup is shown in Fig 1. Light scanning over the Rb-D2
line is directed into two experiments in a linear horizontal polarization at a
laser power on the order of 100 nW with a $1/\rm{e}^{2}$ width of 100
${\upmu}$m. This ensures we remain in the weak probe regime which our model,
ElecSus, assumes [38]. In both experiments, the first vapor cell is placed
after the first Glan-Taylor polarizer with a B-field parallel to the k-vector
of the light (Faraday). In the wing filter setup, a second crossed polarizer
and a quarter waveplate follows which transforms the linear output light into
left hand circular light. This light is input into the second cell, also in
the Faraday geometry, before being detected. In the line center experiment,
the light output from the first cell is directed into the second cell before
the second polarizer with a magnetic field directed perpendicular to the
light’s k-vector (Voigt). Part of the light is directed towards a room
temperature zero field Rb reference and a Fabry-Pérot etalon which allows us
to calibrate the frequency axis.
The first cell’s role is to optically rotate the linearly polarized light
while the dominant role of the second cell is to absorb unwanted transmission
regions. The angle between the magnetic field and the light k-vector
determines the selection rules of the atom-light interaction and the
frequencies where light of a particular polarization will be most absorbed
[39, 40]. In addition, parameters such as temperature and cell length increase
the number of atoms the light interacts with thus increasing the strength of
transitions induced. In the Faraday geometry, $\sigma^{+}$/$\sigma^{-}$
transitions are induced by left/right hand circular light respectively [41].
By applying larger magnetic fields, the $\sigma^{+}$/$\sigma^{-}$ transition
frequencies experience a positive/negative Zeeman shift away from detuning
center. At sufficient temperatures, the Doppler widths of the transitions
create ‘well-like’ lineshapes that absorb over a wider frequency range. In the
wing filter horizontal linearly polarized light is input and the vertical
component of the rotated light is transmitted by the second polarizer. After
traversing a quarter waveplate this light induces $\sigma^{+}$ transitions in
the second vapor cell resulting in significant absorption in the positive
detuning region. This allows us to select for the wing in the negative
detuning region. Fig. 2 and Fig. 4 show how the wing filter output varies with
magnetic field and temperature across the second cell respectively.
In the Voigt geometry, both $\sigma^{+}$ and $\sigma^{-}$ transitions are
induced by vertical linearly polarized light. In the line center experiment,
the first cell rotates the light from a horizontal to a vertical state. The
magnetic field is chosen such that the $\sigma^{+}$ and $\sigma^{-}$
absorption wells are shifted leaving a small transmission region around
detuning center. This results in high transmission at detuning center and high
absorption everywhere else. Fig. 3 and Fig. 4 show how the line center filter
output varies with magnetic field and temperature across the second cell
respectively.
We use ElecSus [35, 36] to choose suitable parameters and experimentally
verify these predictions for natural abundance rubidium vapor cells. For the
wing filter/line center experiment we choose a 75 mm/5 mm first cell placed
inside a solenoid. For both experiments the magnetic field across the 5 mm
second cell is generated by two NeFeB top hat permanent magnets [28] placed in
either the Faraday or Voigt geometry. The transverse and axial field over the
optical path length is homogeneous to 1%. We fit the data to our model which
show excellent agreement [42] with RMS fit errors of 0.6%/0.09% for the wing
and line center filters respectively. The mean parameters obtained and fits
are shown in Fig. 4. The wing filter FOM of 0.86 GHz-1 is larger than any
previously realized Rb wing type filter and the line center filter FOM of 1.63
GHz-1 is the largest published to date for an atomic line filter.
In conclusion, we have shown that dual cell cascaded Rb filters show
improvement over the single cell case both in terms of increased FOM and in
creating lineshapes that better meet the basic criteria for their
applications. We have shown theoretically that this relies on the first and
second cells being dominant optical rotators and absorbers respectively. This
theory is general and holds for other alkali metals given large enough second
cell magnetic fields and temperatures to create the well-like lineshapes.
Adding another cell to a setup is an inexpensive and non-intensive step
provided the application is not too sensitive to the additional light loss. We
plan to give a detailed treatise on the atom-light interactions involved [43]
in a future publication.

Filter Type | $\boldsymbol{T_{1}\hskip 2.84544pt(^{\circ}\rm{C})}$ | $\boldsymbol{B_{1}\hskip 2.84544pt(\rm{G})}$ | $\boldsymbol{T_{2}\hskip 2.84544pt(^{\circ}\rm{C})}$ | $\boldsymbol{B_{2}\hskip 2.84544pt(\rm{G}})$ |  ENBW $\boldsymbol{(\rm{GHz})}$ |  FWHM $\boldsymbol{(\rm{MHz})}$ |  FOM $\boldsymbol{(\rm{GHz^{-1}})}$
---|---|---|---|---|---|---|---
Wing | $85.6\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.3$ | $48.9\pm 0.5$ | $110.1\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.3$ | $747\pm 7$ | $0.92\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.01$ | $599\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 1$ | $0.86\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.01$
Line Center | $100.29\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.07$ | $162.2\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.3$ | $120.79\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.08$ | $2527.6\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.3$ | $0.42\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.01$ | $389\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 1$ | $1.63\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.01$

Figure 4: (Left) Main plot shows data (gold) and theory (purple) plotted for a
natural abundance Rb-D2 Faraday-Faraday wing filter with 75 mm and 5 mm cells.
(Right) Main plot shows data (gold) and theory (purple) plotted for a natural
abundance Rb-D2 Faraday-Voigt line center filter with two 5 mm cells. Both
sets of data show excellent agreement with theory with RMS fit errors of 0.6%
and 0.09% respectively. The insets show theory plots of ENBW, FWHM and maximum
transmission against second cell temperature. On the left plot, the maximum
transmission of both the selected (S) peak and the suppressed (A) peak are
plotted. All other parameters are fixed. The red dotted line indicates the
experimental value of $T_{2}$. A zero-field Rb absorption spectrum at
$15^{\circ}\rm{C}$ is shown in grey. Detuning axis is weighted with respect to
the Rb-D2 lines. The table shows the mean parameter values obtained from fits
of five spectra. The ENBW, FWHM and FOM values stated also account for the
systematic errors involved in linearization. These cascaded-cell filters have
both an improved FOM and better spectral profile than single-cell filters.

Funding ESPRC Grant EP/R002061/1

Acknowledgments We would like to thank Stephen Lishman and the mechanical
workshop for fabricating the 5mm heater used. We appreciate the helpful
feedback provided by Clare Higgins while drafting this paper and Thomas Cutler
and Matthew Jamieson for their advice.

Disclosures The authors declare no conflicts of interest.

Data availability Data underlying the results presented in this paper are
available in Ref. [44].

## References

  * [1] A. Das, B. C. Das, D. Bhattacharyya, and S. De, Journal of Physics B: Atomic, Molecular and Optical Physics 53, 025502 (2019).
  * [2] A. Sargsyan, A. Amiryan, A. Tonoyan, E. Klinger, and D. Sarkisyan, Physics Letters A 390, 127114 (2021).
  * [3] D. L. Carr, N. L. Spong, I. G. Hughes, and C. S. Adams, European Journal of Physics 41, 025301 (2020).
  * [4] J. U. Sutter, O. Lewis, C. Robinson _et al._ , Computers and Electronics in Agriculture 177, 105651 (2020).
  * [5] A. Ricarte, B. S. Prather, G. N. Wong, R. Narayan, C. Gammie, and M. D. Johnson, Monthly Notices of the Royal Astronomical Society 498, 5468 (2020).
  * [6] A. Ejlli, F. Della Valle, U. Gastaldi, G. Messineo, R. Pengo, G. Ruoso, and G. Zavattini, Physics Reports 871, 1 (2020).
  * [7] C. R. Higgins, D. Pizzey, R. S. Mathew, and I. G. Hughes, OSA Continuum 3, 961 (2020).
  * [8] D. Pan, T. Shi, B. Luo, J. Chen, and H. Guo, Scientific Reports 8, 1 (2018).
  * [9] H. Sun, X. Jia, S. Fan, H. Zhang, and H. Guo, Physics Letters A 382, 1556 (2018).
  * [10] G. Wang, Y.-S. Wang, E. K. Huang, W. Hung, K.-L. Chao, P.-Y. Wu, Y.-H. Chen, and I. A. Yu, Scientific Reports 8, 1 (2018).
  * [11] H. Tang, H. Zhao, R. Wang, L. Li, Z. Yang, H. Wang, W. Yang, K. Han, and X. Xu, Optics Express 29, 38728 (2021).
  * [12] B. Luo, R. Ma, Q. Ji, L. Yin, J. Chen, and H. Guo, Optics Letters 46, 5372 (2021).
  * [13] B. Luo, L. Yin, J. Xiong, J. Chen, and H. Guo, Optics Letters 43, 2458 (2018).
  * [14] H. Chen, M. A. White, D. A. Krueger, and C. Y. She, Optics Letters 21, 1093 (1996).
  * [15] A. Rudolf and T. Walther, Optics Letters 37, 4477 (2012).
  * [16] J. Menders, K. Benson, S. H. Bloom, C. S. Liu, and E. Korevaar, Optics Letters 16, 846 (1991).
  * [17] M. A. Zentile, D. J. Whiting, J. Keaveney, C. S. Adams, and I. G. Hughes, Optics Letters 40, 2000 (2015).
  * [18] I. Gerhardt, Optics Letters 43, 5295 (2018).
  * [19] E. T. Dressler, A. E. Laux, and R. I. Billmers, JOSA B 13, 1849 (1996).
  * [20] Z. He, Y. Zhang, S. Liu, and P. Yuan, Chinese Optics Letters 5, 252 (2007).
  * [21] Y. Peng, W. Zhang, L. Zhang, and J. Tang, Optics Communications 282, 236 (2009).
  * [22] J. A. Zielińska, F. A. Beduini, N. Godbout, and M. W. Mitchell, Optics Letters 37, 524 (2012).
  * [23] J. Keaveney, F. S. Ponciano-Ojeda, S. M. Rieche, M. J. Raine, D. P. Hampshire, and I. G. Hughes, Journal of Physics B: Atomic, Molecular and Optical Physics 52, 055003 (2019).
  * [24] F. S. Ponciano-Ojeda, F. D. Logue, and I. G. Hughes, Journal of Physics B: Atomic, Molecular and Optical Physics 54, 015401 (2020).
  * [25] M. W. Kudenov, B. Pantalone, and R. Yang, Applied Optics 59, 5282 (2020).
  * [26] J. Menders, P. Searcy, K. Roff, and E. Korevaar, Optics Letters 17, 1388 (1992).
  * [27] L. Yin, B. Luo, J. Xiong, and H. Guo, Optics Express 24, 6088 (2016).
  * [28] J. Keaveney, S. A. Wrathmall, C. S. Adams, and I. G. Hughes, Optics Letters 43, 4272 (2018).
  * [29] R. Erdélyi, M. B. Korsós, X. Huang _et al._ , Journal of Space Weather and Space Climate 12, 2 (2022).
  * [30] R. Speziali, A. Di Paola, M. Centrone, M. Oliviero, D. Bonaccini Calia, L. Dal Sasso, M. Faccini, V. Mauriello, and L. Terranegra, Journal of Space Weather and Space Climate 11, 22 (2021).
  * [31] A. Cacciani, D. Ricci, P. Rosati, E. Rhodes, E. Smith, S. Tomczyk, and R. Ulrich, Il Nuovo Cimento C 13, 125 (1990).
  * [32] D. Pizzey, Review of Scientific Instruments 92, 123002 (2021).
  * [33] G. Trénec, W. Volondat, O. Cugat, and J. Vigué, Applied Optics 50, 4788 (2011).
  * [34] A. Cacciani and M. Fofi, Solar Physics 59, 179 (1978).
  * [35] M. A. Zentile, J. Keaveney, L. Weller, D. J. Whiting, C. S. Adams, and I. G. Hughes, Computer Physics Communications 189, 162 (2015).
  * [36] J. Keaveney, C. S. Adams, and I. G. Hughes, Computer Physics Communications 224, 311 (2018).
  * [37] W. Kiefer, R. Löw, J. Wrachtrup, and I. Gerhardt, Scientific Reports 4, 1 (2014).
  * [38] B. E. Sherlock and I. G. Hughes, American Journal of Physics 77, 111 (2009).
  * [39] M. D. Rotondaro, B. V. Zhdanov, and R. J. Knize, Journal of the Optical Society of America B Optical Physics 32, 2507 (2015).
  * [40] E. D. Palik and J. K. Furdyna, Reports on Progress in Physics 33, 1193 (1970).
  * [41] C. S. Adams and I. G. Hughes, _Optics f2f: from Fourier to Fresnel_ (Oxford University Press, 2018).
  * [42] I. G. Hughes and T. P. A. Hase, _Measurements and their Uncertainties: A Practical Guide to Modern Error Analysis_ (OUP, Oxford, 2010).
  * [43] J. D. Briscoe, F. D. Logue, D. Pizzey, S. A. Wrathmall, and I. G. Hughes.
  * [44] F. D. Logue, “Dataset,” http://doi.org/10.15128/r12227mp71g.


# Quasipolynomiality of the Smallest Missing Induced Subgraph

David Eppstein, Andrea Lincoln, and Virginia Vassilevska Williams Computer
Science Department, University of California, Irvine<EMAIL_ADDRESS>Research supported in part by NSF grant CCF-2212129.Boston University.
Research performed while the author was at MIT and the University of
California, Berkeley.EECS and CSAIL, Massachusetts Institute of Technology,
<EMAIL_ADDRESS>Research supported in part by NSF Grant CCF-2129139.

###### Abstract

We study the problem of finding the smallest graph that does not occur as an
induced subgraph of a given graph. This missing induced subgraph has at most
logarithmic size and can be found by a brute-force search, in an $n$-vertex
graph, in time $n^{O(\log n)}$. We show that under the Exponential Time
Hypothesis this quasipolynomial time bound is optimal. We also consider
variations of the problem in which either the missing subgraph or the given
graph comes from a restricted graph family; for instance, we prove that the
smallest missing planar induced subgraph of a given planar graph can be found
in polynomial time.

##  1 Introduction

In recent years, the older conventional wisdom that all natural computational
problems have time either polynomial (or better) or exponential (or worse) has
frayed, with the discovery of several natural problems whose best known time
complexity is _quasipolynomial_ , of the form $n^{f(n)}$ for a
polylogarithmically bounded function $f$. Of course, it is possible to obtain
quasipolynomial time bounds from parameterized time bounds, by an appropriate
choice of parameter, but instead we seek problems in which quasipolynomiality
arises naturally from an unparameterized problem. Such problems for which the
best known time is quasipolynomial include:

  * •

Finding minimum dominating sets in tournaments [35]

  * •

Computing the Vapnik–Chervonenkis dimension of a family of sets [31, 41, 37].
Approximating VC dimension up to any constant factor [34].

  * •

Constructing $\epsilon$-approximate Nash equilibria, for constant
$\varepsilon$ [32].

  * •

Graph isomorphism and graph canonization [6].

  * •

Maximum independent set in unit ball graphs in the hyperbolic plane [27].

More strongly, in some of these cases, the form of the quasipolynomial time
bound has been precisely determined (up to constant factors in the exponent)
under the _Exponential Time Hypothesis_ (ETH) of Impagliazzo and Paturi [26],
the assumption that $3$-SAT cannot be solved in time $2^{o(n)}$. For instance,
for both $\epsilon$-approximate Nash equilibria and hyperbolic unit ball
independent sets, the upper bound is $n^{O(\log n)}$, while ETH implies the
impossibility of improving this bound to $n^{o(\log n)}$ [9, 27].

In this work, we find another natural example of a problem that has both a
quasipolynomial upper bound and a matching lower bound derived from the
Exponential Time Hypothesis. Our problem is the _Smallest Missing Induced
Subgraph_ : given an undirected graph $G$ as input, find another undirected
graph $H$, with as few vertices as possible, such that $H$ is not isomorphic
to an induced subgraph of $G$. As we show, this problem can be solved in time
$n^{O(\log n)}$ in $n$-vertex graphs $G$ (Theorem 1), and improving this to
time $n^{o(\log n)}$ would contradict ETH (Theorem 2).

We also consider variations of the problem in which either the missing
subgraph or the given graph comes from a restricted graph family. For
instance, the smallest missing planar induced subgraph, in a given graph $G$,
measures the quality of $G$ as a _universal graph_ for planar graphs and as
the basis for adjacency-labeling schemes for planar graphs [17]. We prove that
the smallest missing planar induced subgraph of a given planar graph can be
found in polynomial time (Theorem 3).

##  2 Upper bounds

The Smallest Missing Induced Subgraph can be found by exactly counting the
number of induced subgraphs of each type, of increasing size, until finding a
size for which one of the counts is zero. Related problems of counting all
types of subgraphs, exactly or approximately, have long been studied [18, 28,
40], and have recently gained popularity in bioinformatics, where small
induced subgraphs are called “graphlets” [38, 25, 1]. A naïve counting
algorithm can solve this problem simply by enumerating all ordered $k$-tuples
of vertices, determining the type of subgraph each $k$-tuple induces, and
incrementing a counter for that type of subgraph.

In more detail:

  * •

We begin with $k=2$, the smallest possible size of a missing induced subgraph
in a graph with two or more vertices.

  * •

A $k$-vertex subgraph can be represented by a binary value with
$\tbinom{k}{2}$ bits, representing (the lower half of) its adjacency matrix.
We use these binary values as indices into an array of counters, initially all
zero. We consider the vertices of the subgraphs to be labeled, so that
permutations of the vertices are considered as different subgraphs.

  * •

We loop through all ordered $k$-tuples of vertices of the given graph. For
each $k$-tuple, we can construct the binary value representing its adjacency
matrix in average $O(k)$ time per $k$-tuple, by updating it from the previous
$k$-tuple in the enumeration. After this step, we increment the counter
indexed by that binary value. Note that by going through every $k$-tuple in
the graph we are incrementing at least once for every possible re-labeling of
each subgraph on $k$ nodes. In other words, we can not ‘miss’ a valid labeling
as we are going through all $n^{k}$ possible combinations of nodes.

  * •

We loop through all cells of the array of counters, searching for one that is
zero. If found, we decode it and output it as a missing subgraph; otherwise,
we increment $k$ and repeat the previous steps.

The time for each $k$ is $O(kn^{k}+2^{k(k-1)/2})$. As this increases
superexponentially with $k$, it is dominated by the last step, the one in
which we find a missing induced subgraph.

######  Lemma 1.

This algorithm succeeds for some $k\leq 2\log_{2}n+2$.

###### Proof.

If it ever reaches $k>2\log_{2}n+1$, the number of array cell counters will be

$2^{\binom{k}{2}}=2^{k(k-1)/2}>2^{k\log_{2}n}=n^{k}.$

There are more counters than increment steps, and some counter will remain
unincremented. Therefore, the algorithm must necessarily terminate whenever
$k$ becomes this large. Since $k$ is increased by one in each iteration, the
value at which it exceeds this threshold is at most $2\log_{2}n+2$. ∎

######  Corollary 2.

In any $n$-vertex graph, the smallest missing induced subgraph has at most
$2\log_{2}n+2$ vertices.

Constructions of Alon [2] and Alstrup, Kaplan, Thorup, and Zwick [4] produce
graphs in which the smallest missing induced subgraph has $2\log_{2}n-O(1)$
vertices, showing that this bound is nearly tight. By plugging this value of
$k$ into the time bound for the algorithm as a function of $n$ and $k$, and
simplifying the resulting expression, we obtain:

######  Theorem 1.

The algorithm above takes time $O(n^{2\log_{2}n+3})$ to find the smallest
missing induced subgraph of any $n$-vertex graph.

The bottleneck in this time bound is initializing and searching the table of
counters. When $k=2\log_{2}n+2$, the size of this table is sufficiently larger
than $n^{k}$ to make this step slower than the search through all $k$-tuples
of vertices. The time can be reduced to $O(n^{2\log_{2}n+2}\log n)$, at the
expense of randomization, by replacing the table of counters by a hash table;
we omit the details.

The copies of any single $k$-vertex subgraph type can be counted in the
substantially smaller time bound $O(n^{0.174k+o(k)})$ [15] but multiplying
this bound by the number of distinct subgraph types would lead to a slower
algorithm than the one above. Although there has been research on applying
fast matrix multiplication to the induced subgraph counting problem for
specific small values of $k$ [28, 29], using sparsity parameters of the host
graph to reduce the time for subgraph counting [23, 21], or using the
structural features of specific types of subgraphs to speed up algorithms for
counting only those subgraphs [43], we do not know of significant general
speedups to the naïve counting algorithm above based on these ideas. Indeed,
to make any significant improvement based on counting methods we would need
not only algorithmic ideas, but a better bound than Corollary 2 on the
smallest $k$ for which success is guaranteed or a counting algorithm which
takes less than $O(1)$ time per possible subgraph of size $k$. This is
because, for the value of $k$ given by Corollary 2, our time bound is not
significantly larger than what would be required merely to output all subgraph
counts.

##  3 Lower bounds

Our lower bound on the smallest missing induced subgraph follows from the
hardness of finding cliques of logarithmic size, a special case of known
results on the parameterized complexity of the clique problem [11, 12, 33]. We
spell out the proof to clarify its applicability to the range of parameter
values that we need. We follow the proof outline from Lokshtanov et al [33].

######  Lemma 3.

Under the Exponential Time Hypothesis, for any constant $c>0$, it is
impossible to find a maximum clique, in an $n$-vertex graph for which that
clique is guaranteed to have size at most $c\log n$, in time $n^{o(\log n)}$.

###### Proof.

We reduce 3-coloring of $N$-vertex graphs to clique-finding on exponentially-
larger graphs, as follows. Choose a parameter $\delta>0$, and partition the
given $N$-vertex graph $G$ into $t=\lfloor\delta\sqrt{N}\rfloor$ subsets of at
most $\lceil N/t\rceil$ vertices. Form a graph $H$ representing the possible
3-colorings of each subset, and add an edge in $H$ between pairs of compatible
subset 3-colorings. (Two subset 3-colorings are compatible if they represent
proper colorings of the induced subgraphs of different subsets, and they do
not combine to form any monochromatic edge.) Then cliques of size $t$ in $H$
correspond to proper 3-colorings of $G$. The number $n$ of vertices in $H$ is
$O(t3^{N/t})$, so $t=\Theta(\log n)$, with a constant of proportionality that
can be made arbitrarily small by choosing a sufficiently small value of
$\delta$, meeting the guarantee of the lemma. If we could find a $t$-clique in
time $n^{o(\log n)}$, this would give us a 3-coloring algorithm with time
$(t3^{N/t})^{o(t)}=3^{o(N)}$, contradicting the exponential-time hypothesis. ∎

To reduce from clique-finding to missing subgraphs, we use a construction for
a family of graphs in which the unique smallest missing subgraph is a clique:

Figure 1: The labeled graph $X_{4}$ of Lemma 4. Every graph with four or fewer
vertices exists as an induced subgraph of $X_{4}$, except for a clique of size
four. More strongly, whenever $H$ is a four-vertex graph $H$ labeled by the
four numbers 1, 2, 3, 4 that does not have an edge labeled 1–2, $H$ appears as
a labeled induced subgraph of $X_{4}$.

######  Lemma 4.

For each positive integer $i>1$, there exists a graph $X_{i}$ that does not
contain a clique of size $i$, but contains all other $i$-vertex induced
subgraphs, and has a total of $2^{i}-2$ vertices.

###### Proof.

More strongly, we form a family of labeled graphs $X_{i}$ with the following
properties:

  * •

$X_{i}$ has its vertices labeled by the numbers from $1$ to $i$. It has one
vertex labeled 1 and one vertex labled 2, and $2^{j-1}$ vertices labeled $j$
for $j>2$.

  * •

The vertices having the same label form an independent set, so each clique
must have vertices of distinct labels.

  * •

There is no edge labeled 1–2, so it is not possible for both of these labels
to appear in a clique. Therefore, the $i$-vertex clique is a missing induced
subgraph.

  * •

If $H$ is any $i$-vertex graph $H$ labeled by distinct integers from $1$ to
$i$, such that $H$ does not have an edge labeled 1–2, then $H$ appears with
the same labels as an induced subgraph of $X_{i}$.

Every $i$-vertex graph that is not a clique can be labeled by distinct
integers from $1$ to $i$ so that its vertices labeled 1 and 2 are non-
adjacent; therefore, for a graph $X_{i}$ with the properties listed above,
every $i$-vertex graph that is not a clique appears as an induced subgraph,
and the $i$-vertex clique is the unique smallest missing induced subgraph.

We construct the graphs $X_{i}$ inductively, as illustrated in Fig. 1. As a
base case, for $i=2$, let $X_{2}$ consist of two isolated vertices, one with
labeled $1$ and the other labeled $2$. For ease of notation call the set of
all vertices labeled $i$ $T_{i}$. To form $X_{i}$ from $X_{i-1}$ add $2^{i-1}$
vertices, labeled $i$, one for each subset of $\\{1,2,\dots,i-1\\}$. For a
vertex $v$ labeled $i$ corresponding to the subset $S\in\\{1,2,\dots,i-1\\}$,
add edges between $v$ and $u$ for all $u\in T_{\ell}$ for all $\ell\in S$.
That is, connect $v$ to all verticies $u$ that have a label in $S$.

The resulting graph clearly has the first three properties listed above. To
show that it has the last property, let $H$ be any $i$-vertex graph $H$
labeled by distinct integers from $1$ to $i$, such that $H$ does not have an
edge labeled 1–2. Let $H^{-}$ be obtained from $H$ by removing the vertex
labeled $i$, and let $S$ be the set of labels of neighbors of the removed
vertex. Then by induction, $H^{-}$ appears as an induced subgraph of
$X_{i-1}$, with the same labels. To form $H$ as an induced subgraph of
$X_{i}$, add one more vertex to this copy of $H^{-}$, the vertex with label
$i$ that corresponds to set $S$. ∎

Noga Alon (personal communication) has observed that a randomized construction
from his work on induced-universal graphs [2] can be modified to produce
smaller graphs with the same properties as in Lemma 4, with
$2^{(i-1)/2}\bigl{(}1+o(1)\bigr{)}$ vertices. This size bound is within a
lower-order additive term of optimal. However, for our purposes it is more
important to have a deterministic construction than to optimize the exponent.

######  Theorem 2.

Under the exponential-time hypothesis, it is impossible to find the smallest
missing induced subgraph of every $n$-vertex graph in time $n^{o(\log n)}$.

###### Proof.

Let $X_{i}$ denote the family of graphs constructed by Lemma 4. We can use an
algorithm for the smallest missing induced subgraph to find a maximum clique
of size up to $\log_{2}n$, in a graph $G$ for which the maximum clique has
that size, by successively finding the smallest missing induced subgraph in
the disjoint union of graphs $G\cup X_{i}$ for $i=2,3,\dots$ until finding an
$i$ for which this missing subgraph is an $i$-vertex clique. The maximum
clique in $G$ has size one less than this stopping value of $i$. The addition
of $X_{i}$ to $G$ at most doubles the number of vertices, which does not
change the form of a time bound of form $n^{o(\log n)}$, and the loop through
successive values of $i$ also does not change this form. Therefore, an
algorithm for the smallest missing induced subgraph with time $n^{o(\log n)}$
would contradict Lemma 3. ∎

##  4 Restricted missing subgraphs

A natural extension of the smallest missing induced subgraph would be to
search for the smallest missing induced subgraph from a given graph family
$\mathcal{F}$, either in a larger graph from the same family or more
generally. When $\mathcal{F}$ is totally ordered by the induced subgraph
relation, this is equivalent to finding the largest induced subgraph in
$\mathcal{F}$ in a given graph $G$; for instance, the classical problems of
finding the largest clique, largest independent set, and longest induced path
in a graph can all be expressed as a missing induced subgraph problem in this
way.

For general graph families $\mathcal{F}$, the size of smallest missing induced
subgraph in $\mathcal{F}$, in a graph $G$, is one plus the largest $k$ for
which $G$ is _$k$ -induced-universal_, meaning that it contains all $k$-vertex
graphs in $\mathcal{F}$ as induced subgraphs. A universal graph in this sense
is not required to belong to $\mathcal{F}$ itself. Universality is equivalent
to the existence of an _adjacency labeling scheme_ , an assignment of binary
labels to the vertices of graphs in $\mathcal{F}$ such that the adjacency of
two vertices can be determined from their labels. If a $k$-universal graph
exists, and has $n_{k}$ vertices, the identities of its vertices can be used
as labels in an adjacency labeling scheme with $\lceil\log_{2}n\rceil$ bits
per label. Conversely, if an adjacency labeling scheme with $b$ bits per label
is possible, then one can construct a $k$-universal graph with $2^{b}$
vertices, one for each possible label, with adjacency determined according to
the labeling scheme. The computational problem of finding the smallest missing
induced subgraph from $\mathcal{F}$ in $G$, then, is the same as determining
the $k$ for which $G$ is $k$-universal. If the smallest missing subgraph from
$\mathcal{F}$ in $G$ is of size $k+1$ then all subgraphs of size $k$ appear
$G$ making $G$ $k$-universal (for the family $\mathcal{F}$). Thus, known upper
bounds on the size of universal graphs translate into lower bounds on the
possible size of the smallest missing subgraph. For instance, trees have
universal graphs of linear size, from which it follows that the smallest
missing tree, in a given graph, may also have linear size [14]. Translating
other known results on universal graphs into this form, it follows that the
smallest missing induced subgraph of maximum degree $\Delta$ can have size
$\Theta(n^{2/\Delta})$ [3] and that the smallest missing planar induced
subgraph can have size $n^{1-o(1)}$ [17].

Additional problems of this type arise when both the induced subgraph and $G$
are restricted to belong to the same family $\mathcal{F}$. For instance, for
the smallest missing induced bipartite subgraph of a given bipartite graph, a
counting argument similar to the one we used for general graphs shows that
this subgraph has size $O(\log n)$, from which it follows that we can find
this subgraph by a brute-force search in quasipolynomial time. However, our
ability to prove the optimality of this time bound is limited in two ways: we
do not have a construction for a bipartite graph in which the unique smallest
missing induced bipartite subgraph is a biclique, analogous to our
construction for cliques, and we do not know ETH-tight bounds on the
complexity of finding bicliques in bipartite graphs [30].

Another interesting case is the problem of finding the smallest missing
induced planar subgraph, in a given planar graph. Like the unconstrained
smallest missing induced subgraph, the smallest planar missing induced
subgraph in a planar graph has logarithmic size. However, in this case the
search for the subgraph can take advantage of planarity, speeding up the
overall algorithm to polynomial time. In the remainder of this section we
detail this result.

######  Lemma 5.

The smallest missing induced planar subgraph, in a given $n$-vertex planar
graph, has $O(\log n)$ vertices.

###### Proof.

The high level idea is to compare the exponential number of 4-connected planar
triangulations (that is, maximal planar graphs) of size $k$, on the one hand,
and an $O(n)$ bound on the number of 4-connected triangulations that can exist
as induced subgraphs of a given $n$-vertex graph, on the other hand. When all
$k$-vertex 4-connected planar triangulations are present in a graph, their
exponential number must be $O(n)$, from which it follows that $k$ must be
$O(\log n)$. Although the smallest missing induced subgraph might not be
4-connected or maximal planar, it has at most $k$ vertices.

In more detail, the number of 4-connected planar triangulations on $k$
unlabeled vertices can be upper-bounded by $c^{k}$ for some constant $c$ [42,
39]. However, a given planar graph $G$, with $n$ vertices, can only have
$O(n)$ induced subgraphs that are 4-connected and maximal planar. This is
because each such subgraph is one of the linearly many graphs formed when $G$
is partitioned along its separating triangles, which necessarily form a nested
family of separations [22]. This partition cannot subdivide any 4-connected
triangulation, because if it could be subdivided in this way it would not be
4-connected. Conversely, if $G$ contains a 4-connected triangulation as an
induced subgraph, each face of the triangulation must either be a face of $G$
or a separating triangle, so this triangulation will be separated from all the
other vertices of $G$ by the partition of $G$ on its separating triangles.
Putting the two bounds on the number of $k$-vertex triangulations and on the
number of induced 4-connected triangulations together, if $G$ is an $n$-vertex
graph for which all $k$-vertex planar graphs are present as induced subgraphs,
it must be the case that $c^{k}=O(n)$. Taking logarithms of both sides shows
that $k=O(\log n)$. For the induced subgraphs of any larger size, at least one
is missing. ∎

Although we do not need it, we note that conversely there exist planar graphs
whose smallest missing induced subgraph has size $\Omega(\log n)$. This
follows from the fact that the number of $k$-vertex unlabeled planar graphs of
all types is only singly exponential in $k$ [24]. An $n$-vertex planar graph
whose smallest missing planar induced subgraph is logarithmic can be
constructed by choosing the largest $k$ such that the disjoint union of all
$k$-vertex planar graphs has at most $n$ vertices, and then padding this
disjoint union to exactly $n$ vertices by adding isolated vertices.

######  Theorem 3.

The smallest missing induced planar subgraph, in a given $n$-vertex planar
graph $G$, can be found in time polynomial in $n$.

###### Proof.

For each positive integer $k$, in numerical order, we list all $k$-vertex
planar graphs and test for each one whether it is an induced subgraph of $G$.
The $k$-vertex unlabeled planar graphs can be listed in total time exponential
in $k$ using standard planar graph enumeration methods [10, 8]. An algorithm
of Eppstein [20], subsequently improved by Dorn [16] and Bonsma [7], allows
testing whether a graph $H$ of size $k$ is a subgraph or induced subgraph of a
graph $G$ of size $n$, in time $2^{O(k)}n$. Because we only apply these
algorithms for $k=O(\log n)$, the total time bound is polynomial in $n$. ∎

The constant factor in the logarithmic bound on the size of the smallest
missing induced planar subgraph that can be obtained from our proof of Lemma 5
is unlikely to be tight, and the base of the exponential function in the
$2^{O(k)}n$ time bound for planar subgraph isomorphism is large (approximately
$76^{k}$ in Bonsma’s version). For this reason we have not analyzed the time
bound of Theorem 3 more carefully to determine its exact exponent.

##  5 Conclusions and Related Problems

We have shown that, to find the smallest missing induced subgraph of a given
$n$-vertex graph, it is possible to use an algorithm with running time
$n^{O(\log n)}$, and that under standard assumptions no better time bound is
possible. We have also investigated similar problems where the induced
subgraph or the given graph must belong to a more restricted family of graphs.

More generally, the problem of asking for the smallest missing subobject of an
object can be extended to many other inclusion orderings of other types of
objects. For substrings or subsequences, it is not difficult to solve in
polynomial time. A more interesting example of the same type of problem arises
for permutations and permutation patterns, smaller permutations with the same
ordering as a subsequence of a larger permutation. A permutation that contains
all patterns of length up to some value $k$ is known as a _superpattern_ , and
so the problem of finding the smallest missing permutation is equivalent to
asking for what $k$ a given pattern is a superpattern. A counting argument
shows that a $k$-superpattern must have length $\Omega(k^{2})$, and
superpatterns of this length are known [5, 36, 13, 19]. Turning this around,
any permutation of length $n$ must have a missing pattern of length
$O(\sqrt{n})$, from which it follows that this missing pattern can be found in
time $n^{O(\sqrt{n})}$. Is a time bound of this form tight?

## References

  * [1] Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick Duffield.  Efficient graphlet counting for large networks.  In 2015 IEEE International Conference on Data Mining, November 2015\.  doi:10.1109/icdm.2015.141.
  * [2] Noga Alon.  Asymptotically optimal induced universal graphs.  Geom. Funct. Anal., 27(1):1–32, 2017.  doi:10.1007/s00039-017-0396-9.
  * [3] Noga Alon and Rajko Nenadov.  Optimal induced universal graphs for bounded-degree graphs.  Math. Proc. Cambridge Philos. Soc., 166(1):61–74, 2019.  doi:10.1017/S0305004117000706.
  * [4] Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick.  Adjacency labeling schemes and induced-universal graphs.  SIAM J. Discrete Math., 33(1):116–137, 2019.  doi:10.1137/16M1105967.
  * [5] Richard Arratia.  On the Stanley–Wilf conjecture for the number of permutations avoiding a given pattern.  Electron. J. Combin., 6:N1, 1999.  doi:10.37236/1477.
  * [6] László Babai.  Canonical form for graphs in quasipolynomial time: preliminary report.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23–26, 2019, pages 1237–1246, 2019.  doi:10.1145/3313276.3316356.
  * [7] Paul S. Bonsma.  Surface split decompositions and subgraph isomorphism in graphs on surfaces.  In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th – March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 531–542. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.  doi:10.4230/LIPIcs.STACS.2012.531.
  * [8] Prosenjit Bose and Ferran Hurtado.  Flips in planar graphs.  Comput. Geom., 42(1):60–80, 2009.  doi:10.1016/j.comgeo.2008.04.001.
  * [9] Mark Braverman, Young Kun-Ko, and Omri Weinstein.  Approximating the best Nash equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis.  In Piotr Indyk, editor, Proceedings of the 26th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015, pages 970–982, 2015.  doi:10.1137/1.9781611973730.66.
  * [10] Gunnar Brinkmann and Brendan D. McKay.  Fast generation of planar graphs.  MATCH Commun. Math. Comput. Chem., 58(2):323–357, 2007.
  * [11] Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, and Ge Xia.  Tight lower bounds for certain parameterized NP-hard problems.  Inform. and Comput., 201(2):216–231, 2005.  doi:10.1016/j.ic.2005.05.001.
  * [12] Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia.  Strong computational lower bounds via parameterized complexity.  J. Comput. System Sci., 72(8):1346–1367, 2006.  doi:10.1016/j.jcss.2006.04.007.
  * [13] Zachary Chroman, Matthew Kwan, and Mihir Singhal.  Lower bounds for superpatterns and universal sequences.  J. Combinatorial Theory Ser. A, 182:105467, 2021.  doi:10.1016/j.jcta.2021.105467.
  * [14] Fan R. K. Chung.  Universal graphs and induced-universal graphs.  J. Graph Theory, 14(4):443–454, 1990.  doi:10.1002/jgt.3190140408.
  * [15] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19–23, 2017, pages 210–223, 2017\.  doi:10.1145/3055399.3055502.
  * [16] Frederic Dorn.  Planar subgraph isomorphism revisited.  In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4–6, 2010, Nancy, France, volume 5 of LIPIcs, pages 263–274. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.  doi:10.4230/LIPIcs.STACS.2010.2460.
  * [17] Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin.  Adjacency labelling for planar graphs (and beyond).  J. ACM, 68(6):A42:1–A42:33, 2021.  doi:10.1145/3477542.
  * [18] Richard A. Duke, Hanno Lefmann, and Vojtěch Rödl.  A fast approximation algorithm for computing the frequencies of subgraphs in a given graph.  SIAM J. Comput., 24(3):598–620, 1995.  doi:10.1137/S0097539793247634.
  * [19] Michael Engen and Vincent Vatter.  Containing all permutations.  Amer. Math. Monthly, 128(1):4–24, 2021.  doi:10.1080/00029890.2021.1835384.
  * [20] David Eppstein.  Subgraph isomorphism in planar graphs and related problems.  J. Graph Algorithms & Applications, 3(3):1–27, 1999.  doi:10.7155/jgaa.00014.
  * [21] David Eppstein, Michael T. Goodrich, Darren Strash, and Lowell Trott.  Extended dynamic subgraph statistics using $h$-index parameterized data structures.  Theoret. Comput. Sci., 447:44–52, 2012.  doi:10.1016/j.tcs.2011.11.034.
  * [22] David Eppstein and Bruce Reed.  Finding maximal sets of laminar 3-separators in planar graphs in linear time.  In Timothy M. Chan, editor, Proceedings of the 30th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019, pages 589–605. Society for Industrial and Applied Mathematics, 2019.  doi:10.1137/1.9781611975482.37.
  * [23] David Eppstein and Emma S. Spiro.  The $h$-index of a graph and its application to dynamic subgraph statistics.  J. Graph Algorithms & Applications, 16(2):543–567, 2012.  doi:10.7155/jgaa.00273.
  * [24] Omer Giménez and Marc Noy.  Asymptotic enumeration and limit laws of planar graphs.  J. Amer. Math. Soc., 22(2):309–329, 2009.  doi:10.1090/S0894-0347-08-00624-3.
  * [25] Tomaž Hočevar and Janez Demšar.  A combinatorial approach to graphlet counting.  Bioinformatics, 30(4):559–565, February 2014.  doi:10.1093/bioinformatics/btt717.
  * [26] Russell Impagliazzo and Ramamohan Paturi.  Complexity of $k$-SAT.  In Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pages 237–240, 1999.  doi:10.1109/CCC.1999.766282.
  * [27] Sándor Kisfaludi-Bak.  Hyperbolic intersection graphs and (quasi)-polynomial time.  In Shuchi Chawla, editor, Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020, pages 1621–1638, 2020.  doi:10.1137/1.9781611975994.100.
  * [28] Ton Kloks, Dieter Kratsch, and Haiko Müller.  Finding and counting small induced subgraphs efficiently.  Inform. Process. Lett., 74(3-4):115–121, 2000.  doi:10.1016/S0020-0190(00)00047-8.
  * [29] Mirosław Kowaluk, Andrzej Lingas, and Eva-Marta Lundell.  Counting and detecting small subgraphs via equations.  SIAM J. Discrete Math., 27(2):892–909, 2013.  doi:10.1137/110859798.
  * [30] Bingkai Lin.  The parameterized complexity of the $k$-biclique problem.  J. ACM, 65(5):A34:1–A34:21, 2018.  doi:10.1145/3212622.
  * [31] Nathan Linial, Yishay Mansour, and Ronald L. Rivest.  Results on learnability and the Vapnik-Chervonenkis dimension.  Inform. and Comput., 90(1):33–49, 1991.  doi:10.1016/0890-5401(91)90058-A.
  * [32] Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta.  Playing large games using simple strategies.  In Daniel A. Menascé and Noam Nisan, editors, Proceedings of the 4th ACM Conference on Electronic Commerce (EC-2003), San Diego, California, USA, June 9–12, 2003, pages 36–41, 2003.  doi:10.1145/779928.779933.
  * [33] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Lower bounds based on the exponential time hypothesis.  Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 105:41–71, 2011\.
  * [34] Pasin Manurangsi.  Improved inapproximability of VC dimension and littlestone’s dimension via (unbalanced) biclique.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 85:1–85:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.ITCS.2023.85.
  * [35] Nimrod Megiddo and Uzi Vishkin.  On finding a minimum dominating set in a tournament.  Theoret. Comput. Sci., 61(2-3):307–316, 1988.  doi:10.1016/0304-3975(88)90131-4.
  * [36] Alison Miller.  Asymptotic bounds for permutations containing many different patterns.  J. Combinatorial Theory Ser. A, 116(1):92–108, 2009.  doi:10.1016/j.jcta.2008.04.007.
  * [37] Christos H. Papadimitriou and Mihalis Yannakakis.  On limited nondeterminism and the complexity of the V-C dimension.  J. Comput. System Sci., 53(2):161–170, 1996.  doi:10.1006/jcss.1996.0058.
  * [38] Nataša Pržulj.  Biological network comparison using graphlet degree distribution.  Bioinformatics, 23(2):e177–e183, January 2007.  doi:10.1093/bioinformatics/btl301.
  * [39] P. N. Rathie.  A census of simple planar triangulations.  J. Combinatorial Theory Ser. B, 16:134–138, 1974.  doi:10.1016/0095-8956(74)90055-0.
  * [40] Pedro Ribeiro, Pedro Paredes, Miguel E. P. Silva, David Aparicio, and Fernando Silva.  A survey on subgraph counting.  ACM Computing Surveys, 54(2):1–36, March 2022.  doi:10.1145/3433652.
  * [41] Ayumi Shinohara.  Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions.  Theoret. Comput. Sci., 137(1):129–144, 1995.  doi:10.1016/0304-3975(94)00164-E.
  * [42] W. T. Tutte.  A census of planar triangulations.  Canadian J. Math., 14:21–38, 1962.  doi:10.4153/CJM-1962-002-9.
  * [43] Virginia Vassilevska Williams and Ryan Williams.  Finding, minimizing, and counting weighted subgraphs.  SIAM J. Comput., 42(3):831–854, 2013.  doi:10.1137/09076619X.