# Stellarator optimization for nested magnetic surfaces at finite $\beta$ and
toroidal current

A. Baillod<EMAIL_ADDRESS>J. Loizu  J. P. Graves  École
Polytechnique Fédérale de Lausanne, Swiss Plasma Center, CH-1015 Lausanne,
Switzerland  M. Landreman  Institute for Research in Electronics and Applied
Physics, University of Maryland, College Park MD 20742, USA

###### Abstract

Good magnetic surfaces, as opposed to magnetic islands and chaotic field
lines, are generally desirable for stellarators. In previous work, M.
Landreman et al. [Phys. of Plasmas 28, 092505 (2021)] showed that equilibria
computed by the Stepped-Pressure Equilibrium Code (SPEC) [S. P. Hudson et al.,
Phys. Plasmas 19, 112502 (2012)] could be optimized for good magnetic surfaces
in vacuum. In this paper, we build upon their work to show the first
finite-$\beta$, fixed- and free-boundary optimization of SPEC equilibria for
good magnetic surfaces. The objective function is constructed with the
Greene’s residue of selected rational surfaces and the optimization is driven
by the SIMSOPT framework [M. Landreman et al., J. Open Source Software 6, 3525
(2021)]. We show that the size of magnetic islands and the consequent regions
occupied by chaotic field lines can be minimized in a classical stellarator
geometry by optimizing either the injected toroidal current profile, the shape
of a perfectly conducting wall surrounding the plasma (fixed-boundary case),
or the coils (free-boundary case), in a reasonable amount of computational
time. This work shows that SPEC can be used as an equilibrium code both in a
two-step or single-step stellarator optimization loop.

††preprint: AIP/123-QED

##  I Introduction

In toroidal geometries, three dimensional (3D) magnetohydrodynamic (MHD)
equilibria are, in general, a mix of nested magnetic surfaces, magnetic
islands and magnetic field line chaos Helander (2014); Hanson and Cary (1984);
Cary and Hanson (1986). In the plasma core, the latter two topologies are
usually detrimental to confinement, i.e. the radial transport of particles and
energy is generally greater than in regions of nested magnetic surfaces. In
addition to other desirable properties, a common target of stellarator
optimization is to increase the volume occupied by magnetic surfacesHudson
_et al._ (2002).

The equilibrium approach for optimizing the volume occupied by nested flux
surfaces requires three tools; (i) a fast 3D equilibrium code that does not
assume nested flux surfaces, (ii) a numerical diagnostic that provides a
measure of integrability of the magnetic field Meiss (1992); MacKay and
Percival (1985); Greene (1978); Loizu  _et al._ (2017), and (iii) an
optimization algorithm. Two fast 3D equilibrium codes are the Variational
Moments Equilibrium Code(Hirshman and Whitson, 1983; Hirshman, van RIJ, and
Merkel, 1986) (VMEC) and the Stepped Pressure Equilibrium Code(Hudson  _et
al._ , 2012) (SPEC). VMEC is based however on the assumption of the existence
of nested flux surfaces everywhere and is thus, when used as a stand-alone
code, not suitable for the optimization of magnetic islands and chaotic field
lines. On the other hand, SPEC does not assume the existence of nested flux
surfaces everywhere in the plasma. In addition, SPEC has been recently
extended to allow free-boundary calculations (Hudson  _et al._ , 2020), and to
allow the prescription of net toroidal current profiles (Baillod  _et al._ ,
2021). Numerical work has also improved its robustness and speed (Qu  _et al._
, 2020).

Most physics codes developed by the stellarator community are based on the
assumption of nested flux surfaces and thus require a VMEC equilibrium as
input. In a recently published paper, Landreman, Medasani, and Zhu (2021)
showed that by optimizing the plasma boundary, SPEC can be used in combination
with VMEC to obtain self-consistent vacuum configurations where both codes are
in agreement, ensuring good magnetic surfaces in the region of interest. This
allows then to trust in any auxiliary codes that assume nested flux surfaces
in this configuration, and to safely optimize for other metrics.

In this paper, we extend the work by Landreman, Medasani, and Zhu (2021) by
showing that finite-$\beta$ SPEC equilibria with non-zero net toroidal
currents can also be optimized to reduce the volume occupied by magnetic
islands and field line chaos in a reasonable amount of time. Additionally, we
explore the use of parameter spaces other than the plasma boundary that could
be of interest. Indeed, we leverage new capabilities of SPEC to show that the
volume of magnetic surfaces in a stellarator can be maximized by optimizing
the injected toroidal current profile, or the coil configuration — two
experimentally relevant "knobs" Geiger  _et al._ (2015). For the optimization,
we follow Landreman, Medasani, and Zhu (2021) and use the SIMSOPT framework
Landreman  _et al._ (2021), which in particular can construct an objective
function based on Greene’s residues Greene (1978) of some selected rational
surfaces.

##  II Method

Since both fixed- and free-boundary equilibria optimization are considered in
this paper, we first describe how these are computed by SPEC.

SPEC computes equilibria where the pressure profile is stepped, i.e. a finite
number of nested surfaces support a pressure discontinuity. Between these
interfaces, there is a finite volume where the pressure is constant and the
force-free magnetic field is described by a Taylor state (Taylor, 1974, 1986).
These interfaces thus describe a set of $N_{vol}$ nested annular regions,
called _SPEC volumes_ or simply _volumes_ in what follows. Details about SPEC
can be found in Hudson  _et al._ (2012, 2020) and references therein.

Using the standard cylindrical coordinate system $(R,\phi,Z)$, a plasma
boundary surface $\Gamma_{PB}$ is parametrized by $R(\theta,\phi),\
Z(\theta,\phi)$, where $\theta$ is a poloidal angle. A fixed-boundary SPEC
equilibrium is then determined by $\Gamma_{PB}$, the number of volumes
$N_{vol}$ and the toroidal flux they enclose
$\\{\psi_{l}\\}_{l=\\{1,\ldots,N_{vol}\\}}$, the pressure in each volume
$\\{p_{l}\\}_{l=\\{1,\ldots,N_{vol}\\}}$, the net toroidal current flowing at
the volumes’ interfaces $\\{I^{s}_{l,\phi}\\}_{l=\\{1,\ldots,N_{vol}\\}}$ and
the net toroidal current flowing in each volume
$\\{I^{v}_{l,\phi}\\}_{l=\\{1,\ldots,N_{vol}\\}}$. Interface currents
represent all equilibrium pressure-driven currents, such as diamagnetic,
Pfirsch-Schlüter, and bootstrap currents, as well as shielding currents
arising when an ideal interface is positioned on a resonance (Loizu  _et al._
, 2015), while volume currents represent externally driven currents such as
Electron Cyclotron Current Drive (ECCD), Neutral Beam Current Drive (NBCD) or
Ohmic current (Baillod  _et al._ , 2021). Note that SPEC can be run with
different inputs — this will however not be covered in the present paper.

A free-boundary equilibrium is determined by a computational boundary surface
$\Gamma_{CB}$ surrounding the plasma which is enclosed by the coils, and the
Fourier harmonics $V_{mn}$ of the component of the vacuum magnetic field
normal to $\Gamma_{CB}$, i.e.

$\mathbf{B}^{c}\cdot\mathbf{n}=\sum_{n=-N_{tor}}^{N_{tor}}\sum_{m=0}^{M_{pol}}V_{mn}\sin(m\theta-
nN_{fp}\phi),$ (1)

with $\mathbf{n}=\mathbf{e}_{\theta}\times\mathbf{e}_{\phi}$ a vector normal
to $\Gamma_{CB}$, $\mathbf{B}^{c}$ the magnetic field produced by the coils,
$M_{pol}$ and $N_{tor}$ are respectively the number of poloidal and toroidal
Fourier modes used in the calculation, $N_{fp}$ is the number of field
periods, and stellarator symmetry has been assumed. The Fourier harmonics
$V_{mn}$ can be obtained from the coil geometry and current; changing these
harmonics is equivalent to changing the coil system. In addition, the
calculation of a free-boundary equilibrium requires specifying the total
toroidal current flowing in the plasma, the total current flowing in the
coils, and as in fixed-boundary the profiles
$\\{\psi_{l}\\}_{l=\\{1,\ldots,N_{vol}\\}}$,
$\\{p_{l}\\}_{l=\\{1,\ldots,N_{vol}\\}}$,
$\\{I^{s}_{l,\phi}\\}_{l=\\{1,\ldots,N_{vol}\\}}$ and
$\\{I^{v}_{l,\phi}\\}_{l=\\{1,\ldots,N_{vol}\\}}$.

We now consider the optimization of a finite-$\beta$, finite current,
classical stellarator equilibrium constructed with SPEC, which presents
regions of magnetic islands and magnetic field line chaos. A classical
stellarator geometry was chosen for simplicity, as few Fourier modes are
required to described the equilibrium. An experimental instance of a classical
stellarator was W7-A Grieger, Renner, and Wobig (1985). However, the
optimization procedure presented here does not depend on the specific choice
of geometry.

We construct a free-boundary equilibrium which will be the initial state for
the optimizations presented in this paper. We choose the computational
boundary $\Gamma_{CB}$ to be a rotating ellipse,

$\displaystyle R^{CB}(\theta,\phi)$
$\displaystyle=R^{CB}_{00}+R^{CB}_{10}\cos\theta+R^{CB}_{11}\sin(\theta-
N_{fp}\phi),$ (2) $\displaystyle Z^{CB}(\theta,\phi)$
$\displaystyle=Z^{CB}_{10}\sin\theta+Z^{CB}_{11}\sin(\theta-N_{fp}\phi),$ (3)

where $R^{CB}_{00}=10$m, $R^{CB}_{10}=-Z_{10}=1$m, and
$R^{CB}_{11}=Z_{11}=0.25$m. We impose a pressure profile linear in toroidal
flux, that we approximate with seven steps, namely $N_{vol}=8$, with the last
volume being a vacuum. We assume no externally induced currents by setting the
total toroidal current flowing in each volume to zero,
$\\{I^{v}_{\phi,l}\\}=0$, and we assume that the plasma generates a bootstrap-
like toroidal current proportional to the pressure jump at the interface
$I^{s}_{\phi,l}\propto(p_{l+1}-p_{l})$ (see Figure 3). Finally, we suppose the
existence of coils such that $\mathbf{B}\cdot\mathbf{n}=0$ on $\Gamma_{CB}$ at
a plasma average beta, $\langle\beta\rangle$, of $1.5\%$, where
$\mathbf{B}=\mathbf{B}^{c}+\mathbf{B}^{p}$ and $\mathbf{B}^{p}$ is the
magnetic field produced by the plasma currents. Note that the condition
$\mathbf{B}\cdot\mathbf{n}=0$ is only valid for the specified $\Gamma_{CB}$,
$\langle\beta\rangle$ and profiles. We will refer to this initial equilibrium
as the _free-boundary equilibrium_ ; its associated un-optimized magnetic
topology is shown via its Poincare section and rotational transform, plotted
on the top left panel of Figure 1 and on Figure 2 respectively. The
discontinuities observed in the rotational transform profile are due to SPEC
stepped-pressure equilibrium model — since the magnetic field is generally
discontinuous across the interfaces, and so therefore is the rotational
transform.

The exact same equilibrium can be generated with fixed-boundary conditions if
we assume that a perfectly conducting wall $\Gamma_{w}$, parametrized by
$R^{w}(\theta,\phi)$ and $Z^{w}(\theta,\phi)$, is positioned at the
computational boundary given by Eqs.(2)-(3). The difference is, however, that
for any value of $\langle\beta\rangle$ and choice of profiles
$\\{I^{v}_{\phi,l}\\}$, $\\{I^{s}_{\phi,l}\\}$, the condition
$\mathbf{B}\cdot\mathbf{n}=0$ would remain valid. We will refer to this
equilibrium as the _perfectly conducting wall equilibrium_. Note that the
free-boundary equilibrium has effectively no conducting wall (no wall limit).

We now consider different degrees of freedom depending on the type of initial
equilibrium. For the free-boundary equilibrium, the parameter space is a
selected set of the Fourier harmonics $V_{mn}$, which emulate an optimization
of the coil geometry and current, as would be done in a "single-step
stellarator optimization" Hudson  _et al._ (2002). For the perfectly
conducting wall equilibrium, we consider two different parameter spaces. The
first is the current flowing in the plasma volumes,
$\\{I^{v}_{l,\phi}\\}_{l=\\{1,\ldots,N_{vol}\\}}$, which is the externally
induced net toroidal plasma current. This parameter space is relevant for
example for scenario design, where one could desire to heal magnetic islands
and chaos for a given plasma geometry and coil system. The second parameter
space is the geometry of the wall expressed as Fourier series,

$\displaystyle R^{w}(\theta,\phi)$
$\displaystyle=\sum_{m=0}^{M_{pol}}\sum_{n=-N_{tor}}^{N_{tor}}R^{w}_{mn}\cos(m\theta-
nN_{fp}\phi)$ (4) $\displaystyle Z^{w}(\theta,\phi)$
$\displaystyle=\sum_{m=0}^{M_{pol}}\sum_{n=-N_{tor}}^{N_{tor}}Z^{w}_{mn}\sin(m\theta-
nN_{fp}\phi).$ (5)

The degrees of freedom are then a selected set of Fourier harmonics
$\\{R^{w}_{mn},Z^{w}_{mn}\\}$.

The objective functions for each optimization are based on Greene’s residues
(Greene, 1978). The Greene’s residue $R$ is a quantity that can be computed
for any periodic orbit, with $R=0$ when the island width is zero, $R<1$ for an
O-point, and $R>1$ for an X-point. The objective function is

$f_{G}=\sum_{i}R_{i}^{2},$ (6)

where $R_{i}$ is the residue for a field line on the $i^{\textit{th}}$
targeted island chain. The downside of this approach is that each resonant
field line has to be selected by hand before starting the optimization. If a
new resonance becomes excited during the optimization, it will not be included
in the objective function. From the initial equilibrium, Fig.1 (top left), we
can identify a set of resonant rational surfaces and their associated residue,
listed in Table 1. We use the SIMSOPT framework to drive the optimization,
which is based on the default _scipy.optimize_ (Virtanen  _et al._ , 2020)
python algorithm for non-linear least squares optimization.

Index | Volume $l$ | toroidal mode $n$ | poloidal mode $m$ | $\iota\\!\\!\\!\text{-}$
---|---|---|---|---
1 | 8 | 5 | 9 | $0.55$
2 | 8 | 5 | 8 | $0.63$
3 | 8 | 5 | 7 | $0.71$
4 | 5 | 5 | 6 | $0.83$
5 | 5 | 5 | 5 | $1.00$
6 | 4 | 5 | 5 | $1.00$
7 | 3 | 5 | 6 | $0.83$
8 | 3 | 5 | 5 | $1.00$
9 | 3 | 5 | 4 | $1.25$
Table 1: Identified resonant surfaces and their rotational transform
$\iota\\!\\!\\!\text{-}$ from the initial equilibrium.

##  III Results

###  III.1 Free-boundary optimization

We start by optimizing the free-boundary equilibrium. Residues 1-3 of Table 1
are used to build the objective function according to Eq.(6). These residues
correspond to the islands and subsequent chaos present in the vacuum region,
right outside the plasma edge. The parameter space is a selected set of
Fourier modes $\\{V_{mn}\\}$, $(m,n)=\\{(6,n)\\}_{n=\\{-3,\ldots,3\\}}$. More
residues could be targeted if more $\\{V_{mn}\\}$ modes were used as degrees
of freedom. This is however computationally expensive and was not done for
this proof-of-principle calculation.

The Poincare section of the optimized equilibrium is plotted on the top right
of Figure 1. As expected, $\Gamma_{CB}$ is no longer a flux surface since
$\mathbf{B}^{c}$ has been changed relative to the un-optimized equilibrium
shown on the top left panel of Figure 1. The difference between the magnetic
field generated by the coils pre- and post-optimization is of the order of 1%
of the total magnetic field, i.e. $\delta B/B\sim 1\%$. We observe that the
targeted island chains have disappeared. However, new resonances appeared
close to the computational boundary $\Gamma_{CB}$, in particular one with mode
number $(m,n)=(10,5)$. The residues associated with these resonances are not
included in the objective function, which explains why the optimizer converged
to this state. Nevertheless, this optimization demonstrates that the parameter
space $\\{V_{mn}\\}$ is suitable for stellarator optimization.

The rotational transform profile of the optimized equilibrium is plotted on
Figure 2. We observe that the rotational transform profile after optimization
is of the same order as before the optimization — it still crosses the same
rationals, but these rationals do not resonate anymore!

Figure 1: Poincare section of the initial and optimized equilibria. Top left:
Initial equilibrium (free-boundary and perfectly conducting wall cases). Red
magnetic surfaces are SPEC’s interfaces which support the pressure jumps.
Outermost red interface is $\Gamma_{CB}$. Top right: free-boundary
equilibrium, optimization of $\\{V_{mn}\\}$. In red: $\Gamma_{CB}$ is the same
as the initial $\Gamma_{CB}$. In yellow: inner interfaces of the optimized
equilibrium. Bottom left: optimization of
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$. In red: $\Gamma_{w}$ is the same
as the initial equilibrium. In blue: inner interfaces of the optimized
equilibrium. Bottom right: optimization of $\Gamma_{w}$. In orange, optimized
$\Gamma_{w}$ and inner interfaces, in red, initial $\Gamma_{w}$. The bottom
plots are fixed-boundary equilibria.

###  III.2 Perfectly conducting wall optimization

We now look at two different optimizations of the perfectly conducting wall
equilibrium. In the first one, we only target the residues in the vacuum
region, i.e. residues 1-3 of Table 1, and the parameter space is the profile
of current flowing in the plasma volumes
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$. If more residues were included in
the objective function, the optimizer could not lower the objective function
sufficiently to observe an effect on the island width. This might be because
not enough degrees of freedom were provided. Increasing the number of volumes
in SPEC is however not a solution, since it adds additional topological
constraints on the magnetic field and some island chains might remain
undetected. Note that this optimization could also be achieved in free-
boundary, but fixed-boundary calculations were considered here for simplicity.

In the second optimization, all residues listed in Table 1 were included in
the objective function and the geometry of the perfectly conducting wall
$\Gamma_{w}$ was optimized. The selected degrees of freedom are the modes
$R^{w}_{mn}$ and $Z^{w}_{mn}$ with $(m,n)=(1,1),\ (1,2),\ (2,1)$.

Figure 1 shows the result of the optimization of
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$ (bottom left) and the optimization
of $\Gamma_{w}$ (bottom right). Comparing both Poincare plots with the initial
equilibrium (top left), we observe that the targeted residues have indeed been
minimized - the islands are now much smaller, or even disappeared in some
cases.

The rotational transform profile is plotted on Figure 2 and the total enclosed
toroidal current on Figure 3. Again, the rotational transform is of the same
order as for the un-optimized case. Regarding the optimized current profile,
the total injected current is $\Delta I_{\phi}=-5.2$kA, less than $20\%$ of
the initial total enclosed toroidal current.

Figure 2: Rotational transform as a function of the normalized square-root of
the toroidal flux $\Psi$, where $\Psi_{edge}$ is the toroidal flux enclosed by
$\Gamma_{w}$. Left: Full profile, right: zoom on vacuum region. Red triangles:
initial equilibrium and profiles. Orange crosses: optimization of
$\Gamma_{w}$. Blue circles: Optimization of
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$. Green squares: optimization of
$\\{V_{mn}\\}$. Dashed, black line: position of the plasma-vacuum interface.
Figure 3: Total enclosed toroidal current as a function of the normalized
square-root of the toroidal flux. In red: initial equilibrium and in blue:
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$ optimized equilibrium. Other
optimized equilibria have the same toroidal current profile as the initial
equilibrium, and are thus not plotted.

###  III.3 Convergence and computation time

The normalized value of the objective function as a function of the number of
iterations is plotted for each optimization in Figure 4. We see that the
optimization of $\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$ saturates at a
larger value than the optimization of $\\{V_{mn}\\}$, despite optimizing the
same objective function (the same residues were selected).

The optimization was run in parallel on $2n+1$ cores of Intel Broadwell
processors at 2.6GHz, where $n$ is the number of degrees of freedom of the
optimization. Each core computed a different SPEC equilibrium when evaluating
the finite difference estimate of the objective function gradient. The
$\\{V_{mn}\\}$ optimization required $165$ equilibrium calculations, the
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$ optimization $187$ and the
$\Gamma_{w}$ optimization $309$. The total CPU time for execution was
respectively $\sim 41$ days, $\sim 10$ days and $\sim 21$ days for a total
wall-clock time of respectively $\sim 65$h, $\sim 17$h and $\sim 39$h. As
expected, fixed-boundary optimizations were faster.

Note that the presented optimizations did not take advantage of the full
parallelization of SPEC — only a single core computed each SPEC equilibrium,
while SIMSOPT allows the user to use $M$ CPUs on $N$ SPEC instances, which
would speedup the computation greatly. Nevertheless, our optimizations show
that the total time required to perform a SPEC optimization is small enough to
be considered in more advanced stellarator optimizations.

Figure 4: Logarithmic plot of the normalized objective function as a function
of the number of SPEC calculations. Values evaluated while taking finite
differences to evaluate the jacobian of the objective function are not shown.
Orange crosses: optimization of $\Gamma_{w}$. Blue circles: optimization of
$\\{I^{v}_{\phi,l}\\}_{l=\\{1,\ldots,7\\}}$. Green squares: optimization of
$\\{V_{mn}\\}$.

##  IV Conclusion

In this paper, we showed the first fixed- and free-boundary, multi-volume,
finite $\beta$ SPEC equilibrium optimizations of a classical stellarator using
the SIMSOPT framework. The objective function was constructed from the
Greene’s residues of selected rational surfaces. Different parameter spaces
were considered: either the boundary of a perfectly conducting wall
surrounding the plasma, or the enclosed toroidal current profile, or the
vacuum field produced by the coils were optimized.

In all three optimizations, it was possible to reduce the objective function
significantly, which in turn translated to a reduction of the targeted
magnetic island width. With the exception of the case of the coil
optimization, all optimized states have a larger volume occupied by nested
flux surfaces, which is beneficial for confinement. In the case of the coil
optimization, additional rationals emerged and their related residues were not
optimized, since they were not included in the objective function, but the
islands present in the initial un-optimized equilibrium, were reduced in size.

Different measures of the magnetic field integrability are currently being
considered to overcome the shortcomings of Greene’s residues. Indeed, as
observed in the coil optimization, Greene’s residue is a local measure, which
requires input from the user — any rational surfaces emerging during the
optimization remains undetected. Ideally, a global measure is thus required.
The volume occupied by chaotic field lines, measured from the fractal
dimension of their Poincare map Loizu  _et al._ (2017) could be a possible
solution.

In the work by Landreman, Medasani, and Zhu (2021), it has been shown that
SPEC could be coupled to VMEC in order to achieve an optimization in a vacuum,
where both quasi-symmetry and nested flux surfaces could be obtained. The
obvious next step is then to perform a combined SPEC-VMEC finite-$\beta$
optimization for good magnetic surfaces as well as other metrics, such as
quasi-symmetry. This will require to deviate significantly from a classical
stellarator geometry, as opposed to what has been presented in this paper.
This will be the topic of future investigations.

###### Acknowledgements.

The authors would like to acknowledge the support from the SIMSOPT development
team, and thank Z. Qu, B. Medasani and C. Zhu for useful discussions. This
work has been carried out within the framework of the EUROfusion Consortium
and has received funding from the Euratom research and training programme 2014
- 2018 and 2019 - 2020 under grant agreement No 633053. The views and opinions
expressed herein do not necessarily reflect those of the European Commission.
This work was supported by a grant from the Simons Foundation (560651, ML). BM
and CZ are supported by the U.S. Department of Energy under Contract No. DE-
AC02-09CH11466 through the Princeton Plasma Physics Laboratory.

## Data Availability Statement

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

## References

## References

  * Helander (2014) P. Helander, “Theory of plasma confinement in non-axisymmetric magnetic fields,” Reports on Progress in Physics 77, 087001 (2014).
  * Hanson and Cary (1984) J. D. Hanson and J. R. Cary, “Elimination of stochasticity in stellarators,” The Physics of Fluids 27, 767–769 (1984).
  * Cary and Hanson (1986) J. R. Cary and J. D. Hanson, “Stochasticity reduction,” Physics of Fluids 29, 2464 (1986).
  * Hudson  _et al._ (2002) S. R. Hudson, D. A. Monticello, A. H. Reiman, A. H. Boozer, D. J. Strickler, S. P. Hirshman, and M. C. Zarnstorff, “Eliminating Islands in High-Pressure Free-Boundary Stellarator Magnetohydrodynamic Equilibrium Solutions,” Physical Review Letters 89, 1–4 (2002).
  * Meiss (1992) J. D. Meiss, “Symplectic maps, variational principles, and transport,” Reviews of Modern Physics 64, 795–848 (1992).
  * MacKay and Percival (1985) R. S. MacKay and I. C. Percival, “Converse KAM: Theory and practice,” Communications in Mathematical Physics 98, 469–512 (1985).
  * Greene (1978) J. M. Greene, “A method for determining a stochastic transition,” Journal of Mathematical Physics 20, 1183–1201 (1978).
  * Loizu  _et al._ (2017) J. Loizu, S. R. Hudson, C. Nührenberg, J. Geiger, and P. Helander, “Equilibrium $\beta$-limits in classical stellarators,” Journal of Plasma Physics 83, 715830601 (2017).
  * Hirshman and Whitson (1983) S. P. Hirshman and J. C. Whitson, “Steepest-descent moment method for three-dimensional magnetohydrodynamic equilibria,” The Physics of Fluids 26, 3553 (1983).
  * Hirshman, van RIJ, and Merkel (1986) S. Hirshman, W. van RIJ, and P. Merkel, “Three-dimensional free boundary calculations using a spectral Green’s function method,” Computer Physics Communications 43, 143–155 (1986).
  * Hudson  _et al._ (2012) S. R. Hudson, R. L. Dewar, G. Dennis, M. J. Hole, M. McGann, G. Von Nessi, and S. Lazerson, “Computation of multi-region relaxed magnetohydrodynamic equilibria,” Physics of Plasmas 19, 112502 (2012).
  * Hudson  _et al._ (2020) S. R. Hudson, J. Loizu, C. Zhu, Z. S. Qu, C. Nührenberg, S. Lazerson, C. B. Smiet, and M. J. Hole, “Free-boundary MRxMHD equilibrium calculations using the Stepped-Pressure Equilibrium Code,” Plasma Physics and Controlled Fusion 62, 084002 (2020).
  * Baillod  _et al._ (2021) A. Baillod, J. Loizu, Z. Qu, A. Kumar, and J. Graves, “Computation of multi-region, relaxed magnetohydrodynamic equilibria with prescribed toroidal current profile,” Journal of Plasma Physics 87, 905870403 (2021).
  * Qu  _et al._ (2020) Z. Qu, D. Pfefferlé, S. R. Hudson, A. Baillod, A. Kumar, R. L. Dewar, and M. J. Hole, “Coordinate parametrization and spectral method optimisation for Beltrami field solver in stellarator geometry,” Plasma Physics and Controlled Fusion 62, 124004 (2020).
  * Landreman, Medasani, and Zhu (2021) M. Landreman, B. Medasani, and C. Zhu, “Stellarator optimization for good magnetic surfaces at the same time as quasisymmetry,” Physics of Plasmas 28, 092505 (2021).
  * Geiger  _et al._ (2015) J. Geiger, C. D. Beidler, Y. Feng, H. Maaßberg, N. B. Marushchenko, and Y. Turkin, “Physics in the magnetic configuration space of W7-X,” Plasma Physics and Controlled Fusion 57, 014004 (2015).
  * Landreman  _et al._ (2021) M. Landreman, B. Medasani, F. Wechsung, A. Giuliani, R. Jorge, and C. Zhu, “SIMSOPT: A flexible framework for stellarator optimization,” Journal of Open Source Software 6, 3525 (2021).
  * Taylor (1974) J. B. Taylor, “Relaxation of toroidal plasma and generation of reverse magnetic fields,” Physical Review Letters 33, 1139–1141 (1974).
  * Taylor (1986) J. B. Taylor, “Relaxation and magnetic reconnection in plasmas,” Reviews of Modern Physics 58, 741–763 (1986).
  * Loizu  _et al._ (2015) J. Loizu, S. Hudson, A. Bhattacharjee, and P. Helander, “Magnetic islands and singular currents at rational surfaces in three-dimensional magnetohydrodynamic equilibria,” Physics of Plasmas 22, 022501 (2015).
  * Grieger, Renner, and Wobig (1985) G. Grieger, H. Renner, and H. Wobig, “Wendelstein stellarators,” Nuclear Fusion 25, 1231–1242 (1985).
  * Virtanen  _et al._ (2020) P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, I. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, A. Vijaykumar, A. P. Bardelli, A. Rothberg, A. Hilboll, A. Kloeckner, A. Scopatz, A. Lee, A. Rokem, C. N. Woods, C. Fulton, C. Masson, C. Häggström, C. Fitzgerald, D. A. Nicholson, D. R. Hagen, D. V. Pasechnik, E. Olivetti, E. Martin, E. Wieser, F. Silva, F. Lenders, F. Wilhelm, G. Young, G. A. Price, G. L. Ingold, G. E. Allen, G. R. Lee, H. Audren, I. Probst, J. P. Dietrich, J. Silterra, J. T. Webber, J. Slavič, J. Nothman, J. Buchner, J. Kulick, J. L. Schönberger, J. V. de Miranda Cardoso, J. Reimer, J. Harrington, J. L. C. Rodríguez, J. Nunez-Iglesias, J. Kuczynski, K. Tritz, M. Thoma, M. Newville, M. Kümmerer, M. Bolingbroke, M. Tartre, M. Pak, N. J. Smith, N. Nowaczyk, N. Shebanov, O. Pavlyk, P. A. Brodtkorb, P. Lee, R. T. McGibbon, R. Feldbauer, S. Lewis, S. Tygier, S. Sievert, S. Vigna, S. Peterson, S. More, T. Pudlik, T. Oshima, T. J. Pingel, T. P. Robitaille, T. Spura, T. R. Jones, T. Cera, T. Leslie, T. Zito, T. Krauss, U. Upadhyay, Y. O. Halchenko, and Y. Vázquez-Baeza, “SciPy 1.0: fundamental algorithms for scientific computing in Python,” Nature Methods 17, 261–272 (2020).


# Sublinear hitting sets for some geometric graphs

Xinbu Cheng Laboratory of Mathematics and Complex Systems, Ministry of
Education, School of Mathematical Sciences, Beijing Normal University,
Beijing, China. Emails<EMAIL_ADDRESS>Zixiang Xu Extremal
Combinatorics and Probability Group (ECOPRO), Institute for Basic Science
(IBS), Daejeon, South Korea. Emails<EMAIL_ADDRESS>Supported by
IBS-R029-C4.

###### Abstract

For an $n$-vertex graph $G$, let $h(G)$ denote the smallest size of a subset
of $V(G)$ such that it intersects every maximum independent set of $G$. A
conjecture posed by Bollobás, Erdős and Tuza in early 90s remains widely open,
asserting that for any $n$-vertex graph $G$, if the independence number
$\alpha(G)=\Omega(n)$, then $h(G)=o(n)$. In this paper, we establish the
validity of this conjecture for various classes of graphs, including disk
graphs, even-hole-free graphs, circle graphs, and those hereditary graphs
having sublinear balanced separators. We also determine the exact values of
smallest possible hitting sets in comparability graphs, incomparability graphs
and the graphs with VC-dimension one.

##  1 Introduction

###  1.1 Overview

For a graph $G=(V,E)$, an _independent set_ is a set of vertices in $G$, no
two of which are adjacent. A _maximum independent set_ is an independent set
of the largest possible size for the graph $G$, and this size is called the
_independence number_ of $G$ and is usually denoted by $\alpha(G)$. We say
$T\subseteq V(G)$ is a _hitting set_ of the graph $G$ if $T\cap
I\neq\emptyset$ holds for every maximum independent set $I\subseteq V(G)$. Let
$h(G)$ be the smallest size of a hitting set $T\subseteq V(G)$. Assume that
$n$ is sufficiently large whenever this is needed. Bollobás, Erdős and Tuza
(see, [13, 20]) raised the following conjecture.

######  Conjecture 1 ([13, 20]).

Let $G$ be an $n$-vertex graph with $\alpha(G)=\Omega(n)$, then $h(G)=o(n)$.

For this conjecture, there was a clever observation of Hajnal [36], (also see
Lemma 1 in [49]) which states that for all maximum independent sets in $G$,
say $A_{1},A_{2},\ldots,A_{s}$, the following inequality always holds:

$|A_{1}\cap A_{2}\cap\cdots\cap A_{s}|+|A_{1}\cup A_{2}\cup\cdots\cup
A_{s}|\geq 2\alpha(G).$

As a simple consequence, one can see that if $\alpha(G)>\frac{|G|}{2}$, then
$|A_{1}\cap A_{2}\cap\cdots\cap A_{s}|>0$, which implies that $h(G)=1$.
However, 1 even remains open in the case of $c=\frac{1}{2}-\varepsilon$ for
any small $\varepsilon>0$. A recent major progress of 1 due to Alon [3] showed
that for every $n$-vertex regular graph $G$ with
$\alpha(G)>(\frac{1}{4}+\varepsilon)n$ for arbitrarily small $\varepsilon>0$,
we have $h(G)\leq O(\sqrt{n\log{n}})$. Alon’s proof elegantly combined the
container method [5, 6, 50] and the above observation of Hajnal. On the other
hand, Alon [3] provided an explicit construction of graph $G$ with
$\alpha(G)=\Theta(n)$ and $h(G)=\Theta(\sqrt{n})$, which means that the $o(n)$
term in 1 cannot be replaced by $o(\sqrt{n})$. Moreover, Alon provided another
type of construction of graph $G$ with $n=2^{m}$ vertices such that
$\alpha(G)=\sum_{i=0}^{\frac{m}{2}-t}\binom{n}{i}$ and $h(G)=\Theta(m^{2})$.
This construction is mainly based on some ideas from discrepancy theory and
Kleitman’s isodiametric inequality [41], which also disproves a conjecture of
Dong and Wu [17]. In particular, Alon [2] suggested to study whether
3-colorable graphs satisfy 1, and showed that for every integer $q\geq 1$,
there exists an $8$-colorable graph $G_{q}$ with $h(G)>q$, see [35, Theorem
1.3].

Notice that the condition “maximum independent sets” cannot be replaced by
“maximal independent sets”. To see this, let $G$ be a book graph that consists
of a clique $K_{(1-c)n}$, and the other $cn$ vertices are only adjacent to all
vertices in the clique $K_{(1-c)n}$. Then we need exactly $(1-c)n+1$ vertices
to hit all maximal independent sets.

One way to better understand 1 is to test whether it holds for specific
classes of graphs. In recent work of Hajebi, Li and Spirkl [35], the authors
put this idea into practice. More precisely, they proved that for any induced
$P_{5}$-free graph $G$, $h(G)\leq f(\omega(G))$, where $P_{5}$ is a path with
$5$ vertices, $f:\mathbb{N}\rightarrow\mathbb{N}$ is a function and
$\omega(G)$ is the largest size of a clique in $G$. A family of graphs
$\mathcal{G}$ is termed _hereditary_ if, for any graph $G\in\mathcal{G}$ and
any induced subgraph $G^{\prime}$ of $G$, we have $G^{\prime}\in\mathcal{G}$.
We say that a hereditary class $\mathcal{G}$ of graphs has the Erdős-Hajnal
property if there exists some $\varepsilon>0$ such that every graph
$G\in\mathcal{G}$ satisfies either $\alpha(G)>|V(G)|^{\varepsilon}$ or
$\omega(G)>|V(G)|^{\varepsilon}$. The famous Erdős-Hajnal conjecture [21]
states that every hereditary class of graphs has Erdős-Hajnal property.
Hajebi, Li and Spirkl [35] recently provided a new approach to this
conjecture. More precisely, they showed that for a hereditary class
$\mathcal{G}$ of graphs, if every graph $G\in\mathcal{G}$ satisfies
$h(G)\leq\textup{Poly}(\omega(G))$, then $\mathcal{G}$ satisfies Erdős-Hajnal
property.

However, this approach does not always work. Note that the family of graphs
with VC-dimension at most $d\in\mathbb{N}$ is hereditary.

######  Theorem 1.1.

There exists some graph $G$ with VC-dimension at most $3$ and $\omega(G)=3$
such that $h(G)\geq\frac{\sqrt{|G|}}{2}$.

Theorem 1.1 follows from Alon’s construction in [3, Theorem 1.3], we will
discuss this in Section 5.4.1.

###  1.2 Our contributions

In this paper, we will demonstrate the validity of 1 for several important
classes of graphs, some of which stem from geometry, while others exhibit
highly favorable combinatorial properties.

A _hole_ in a graph is an induced subgraph which is a cycle of length at least
four. A hole is called even if it has an even number of vertices. An _even-
hole-free graph_ is a graph with no even holes. One of the most important sub-
classes of the even-hole-free graphs is the family of chordal graphs. A
_chordal graph_ is a simple graph in which every cycle of length four and
greater has a cycle chord.

The absence of even-hole-free graphs attracts broad attention in the field of
graph theory. The renowned strong perfect graph theorem, established by
Chudnovsky, Robertson, Seymour, and Thomas [11], states that a graph achieves
perfection precisely when it forbids both odd holes and odd anti-holes
(defined as the complements of holes). Graphs without any odd holes and odd
anti-holes are termed Berge graphs. It has been observed that the structure of
even-hole-free graphs bears striking similarities to that of Berge graphs, for
instance, the prohibition of induced $4$-holes necessitates the exclusion of
any anti-hole with a length of at least $6$. For a positive integer $\gamma$,
we define a vertex $v\in V(G)$ to be _$\gamma$ -simplicial_ if its
neighborhood $N_{G}(v)$ forms a disjoint union of at most $\gamma$ cliques.
Chudnovsky and Seymour [12] recently provided a valid proof and showed that
every even-hole-free graph contains a $2$-simplicial vertex, thereby settling
a conjecture posed by Reed [38]. It then follows that $h(G)\leq 2\omega(G)+1$
by 2.1. We also refer interested readers to a survey for even-hole-free graphs
[56]. Here we confirm that 1 holds for any even-hole-free graph.

######  Theorem 1.2.

Let $G$ be an even-hole-free graph with $\alpha(G)=cn$ for some $c>0$, then we
have $h(G)\leq\frac{5n}{\log{n}}$.

To prove Theorem 1.2, we develop a framework to show that graphs with certain
locally sparse properties satisfy 1, see Theorem 3.1. Under this framework, we
can also prove 1 holds for the _disk graph_ , which is the intersection graph
of disks in two-dimensional space.

######  Theorem 1.3.

Let $G$ be an $n$-vertex disk graph with $\alpha(G)=cn$ for some $c>0$, then
we have $h(G)\leq\frac{25n}{\log{n}}$.

Our subsequent result concerning disk graphs follows in a similar vein as the
recent work of Chudnovsky and Seymour [12], which is also related to the
problem of Hajebi, Li and Spirkl [35].

######  Theorem 1.4.

Every disk graph $G$ contains an $11$-simplicial vertex. Consequently, every
disk graph $G$ satisfies $h(G)\leq 11\omega(G)+1$.

The constant $11$ above might be improved and we make no attempt to optimize
it here. There are some special sub-families of the disk graphs, for instance,
a _unit disk graph_ is a disk graph with an intersection graph consisting of
disks of unit size, one can easily show $h(G)=O(1)$ when $\alpha(G)=cn$ since
unit disk graph $G$ is induced $K_{1,6}$-free. A _coin graph_ is a disk graph
with the additional condition that no two disks have more than one point in
common. Note that the circle packing theorem, first proven by Paul Koebe [42]
in 1936, states that a graph is planar only if it is a coin graph. Therefore
any $n$-vertex coin graph has at most $3n-6$ edges, which implies we can only
use $6$ vertices to hit all maximum independent sets in any coin graph by 2.1.

Moreover, the results in Theorem 1.3 can be generalized to the intersection
graph of higher dimensional balls by simple modification of our proof. One of
the useful auxiliary results is that, in any $d$-dimensional space, the number
of unit balls that can touch a unit ball is bounded by $f(d)$ for some
function $f$ [48]. For instance, $f(2)=6$ implies that the unit disk graph is
induced $K_{1,6}$-free.

Next, our attention shifts to the _circle graph_ $G$, where $V(G)$ comprises a
finite set of chords on a circle, with two vertices being adjacent if and only
if their corresponding chords intersect. Circle graphs and their
representations play a pivotal role in numerous unexpected fields. Exemplary
instances include knot theory [7] and quantum computing [54]. Also, circle
graphs have garnered considerable interest both in graph theory [8, 31, 32]
and computer science [9, 39, 40]. In particular, a very recent breakthrough of
Davies and McCarty [15] showed that the chromatic number of circle graphs is
quadratic in its clique number, which significantly improves the previous
results in [43, 44]. Shortly after this, the upper bound was further improved
by Davies [14], who showed the sharp upper bound $\chi(G)\leq
O(\omega(G)\log{\omega(G)})$ when $G$ is a circle graph. Further exploration
of circle graphs can be found in an informative textbook [34]. We can show
that 1 also holds for circle graphs.

######  Theorem 1.5.

Let $G$ be a circle graph with $\alpha(G)=cn$ for some $c>0$, then
$h(G)\leq\frac{2(1-c)n\log\log{n}}{c\log{n}}+1$.

Given a partially ordered set $(P,\prec)$, its _comparability graph_ is a
graph with vertex set corresponding to elements of $P$ with two vertices
sharing an edge if and only if the corresponding elements are comparable in
$P$. On the other hand, an _incomparability graph_ is a graph that connects
pairs of elements of a poset that are not comparable to each other in a
partial order, i.e. it is the complement of a comparability graph. The graph
on posets is one of the important topics in the field of extremal
combinatorics, see [22, 29]. For both the comparability graphs and the
incomparability graphs, we can prove the sharp results on $h(G)$.

######  Proposition 1.6.

Let $G$ be an $n$-vertex comparability graph, then
$h(G)\leq\frac{n}{\alpha(G)}$. In particular, if $\alpha(G)=cn$ for some
$c>0$, then $h(G)\leq\lfloor\frac{1}{c}\rfloor$.

######  Proposition 1.7.

Let $G$ be an $n$-vertex incomparability graph, then
$h(G)\leq\frac{n}{\alpha(G)}$. In particular, if $\alpha(G)=cn$ for some
$c>0$, then $h(G)\leq\lfloor\frac{1}{c}\rfloor$.

Assume that $\alpha(G)\mid n$, there are two types of constructions attaining
the upper bounds on the above theorems. The first one the complete
$\frac{n}{\alpha(G)}$-partite graph, the second one is the disjoint union of
$\alpha(G)$ many cliques of size $\frac{n}{\alpha(G)}$. We will provide a
short proof of 1.6 via simply applying Dilworth’s theorem, and we also give an
alternative proof in [10], which might be useful in other graphs.

Let $\mathcal{F}\subseteq 2^{[n]}$ be a set system, the _Vapnik-Chervonenkis
dimension_ (for short, _VC-dimension_) of $\mathcal{F}$ is the largest integer
$d$ for which there exists a subset $S\subseteq[n]$ with $|S|=d$ such that for
every subset $B\subseteq S$, one can find a member $A\in\mathcal{F}$ with
$A\cap S=B$. We say that the graph $G$ has VC-dimension $d$ if the set system
$\mathcal{F}:=\\{N_{G}(v):v\in V(G)\\}$ induced by the neighborhood of
vertices in $G$ has VC-dimension $d$. The VC-dimension is one of the most
useful combinatorial parameters that measure its complexity. The notion was
introduced by Vapnik and Chervonenkis [55] in 1971, as a tool in mathematical
statistics.

We can derive the sharp upper bound on $h(G)$ for graphs with VC-dimension
one.

######  Theorem 1.8.

Let $G$ be an $n$-vertex graph with VC-dimension $1$, then
$h(G)\leq\max\\{\frac{n}{\alpha(G)},3\\}$. In particular, if $\alpha(G)=cn$
for positive constant $c\neq\frac{2}{5}$, then
$h(G)\leq\lfloor\frac{1}{c}\rfloor$; if $\alpha(G)=\frac{2n}{5}$, then
$h(G)\leq 3$.

The upper bounds on Theorem 1.8 are sharp for different region of $c$. The
exact results reflect a rare phenomenon, where the performance of $h(G)$ is
highly sensitive to the selection of $c$. Indeed, when $c\neq\frac{2}{5}$, if
$\lfloor\frac{1}{c}\rfloor$ is an integer, one can take the complete balanced
$\frac{1}{c}$-partite graph, otherwise, one can take complete
$\lceil\frac{1}{c}\rceil$-partite graph with parts
$A_{1},A_{2},\ldots,A_{\lceil\frac{1}{c}\rceil}$ such that
$|A_{1}|=(1-c\cdot\lfloor\frac{1}{c}\rfloor)n$ and $|A_{i}|=cn$ for any $i\geq
2$. It is easy to check that the complete multipartite graph has VC-dimension
one. Particularly when $c=\frac{2}{5}$, we can see $G=C_{5}[\frac{n}{5}]$
satisfies $h(G)=3$ and the VC-dimension of $G$ is one. Note that when
$\frac{1}{3}<c\leq\frac{1}{2}$, only when $\frac{2}{5}$, $h(G)$ might be $3$,
while in other cases $h(G)$ must be strictly less than $3$.

For convenience, we construct a partially ordered diagram illustrated in Fig.
1.1 to depict the principal findings of this paper and elucidate the
interconnections among various graph classes, as well as some open problems.

Circle $k$-gon graph: $O(\frac{n\log{\log{n}}}{\log{n}})$Interval filament
graph: 4Even-hole-free graph: $O(\frac{n}{\log{n}})$String graph: 3Chordal
graph: $O(\frac{n}{\log{n}})$Circle graph:
$O(\frac{n\log{\log{n}}}{\log{n}})$Trapezoid graph:
$\frac{n}{\alpha(G)}$Incomparability graph: $\frac{n}{\alpha(G)}$Circular-arc
graph: $O(\frac{n}{\alpha(G)})$Interval graph:
$\frac{n}{\alpha(G)}$Comparability graph: $\frac{n}{\alpha(G)}$Disk graph:
$O(\frac{n}{\log{n}})$Graph with bounded VC-dimension: 2Unit disk graph:
$O(\frac{n}{\alpha(G)})$Graph with VC-dimension one: $\frac{n}{\alpha(G)}$
Figure 1.1: Upper bounds on $h(G)$ for various families of graphs $G$ with
$\alpha(G)=\Omega(n)$. $A\rightarrow B$: $B$ is a sub-family of $A$

Structure of this paper. In Section 2, we introduce some basics on this topic
and We provide the proofs of 1.6, 1.7 and Theorem 1.8. In Section 3, we will
show more general results for graphs with certain locally sparse properties in
Theorem 3.1. We also discuss the combinatorial properties of disk graphs and
even-hole-free graphs and provide the proofs of Theorem 1.2 and Theorem 1.3 in
detail. We will prove Theorem 1.5 in Section 4. We conclude this paper and
propose several conjectures related to the main topic of this paper in Section
5.

Notations. For a vertex $u\in V(G)$, we will use $N_{G}(u)$ (or $N(u)$ if the
subscript is clear) to denote the set of the neighborhood of $u$. Let
$\delta(G):=\min_{v\in V(G)}|N_{G}(v)|$ be the minimum degree of $G$. Let
$N_{G}(A)=\bigcup_{a\in A}N_{G}(a)$. For two sets $A$ and $B$, let $A\setminus
B:=\\{x\in A,x\notin B\\}$ and let $A\triangle B:=(A\setminus
B)\cup(B\setminus A)$ be the symmetric difference between $A$ and $B$. For a
graph $H$, we write $H[t]$ the _$t$ -blowup_ of $H$ by replacing every vertex
of $H$ by an independent set of size $t$ and every edge of $H$ by a copy of
$K_{t,t}$ and we write $H[\cdot]$ when mentioning a blow-up of $H$ without
specifying its size (and the sizes of these independent sets could be
different). We use $\mathcal{I}_{\textup{max}}(G)$ to denote the collection of
all maximum independent sets in $G$. We say a graph $G$ is _acyclic_ if $G$
does not contain any cycle.

The notations $o(\cdot)$, $O(\cdot)$, $\Theta(\cdot)$ and $\Omega(\cdot)$ have
their usual asymptotic meanings. We use $\log$ throughout to denote the base
$2$ logarithm. For the sake of clarity of presentation, we omit floors and
ceilings and treat large numbers as integers whenever this does not affect the
argument.

##  2 Warm-ups

###  2.1 Basics

Regarding the main problem in this paper, there are some simple results as
follows.

######  Proposition 2.1.

  1. (1)

If $G$ has connected components $G_{1},G_{2},\ldots,G_{m}$, then
$h(G)\leq\min\limits_{i}h(G_{i})$.

  2. (2)

For any vertex $v\in V(G)$, $\\{v\\}\cup N_{G}(v)$ is a hitting set of $G$. In
particular, $h(G)\leq\delta(G)+1$.

  3. (3)

If $G$ is a bipartite graph, then $h(G)\leq 2$.

###### Proof of 2.1.

For (1), note that every $I\in\mathcal{I}_{\textup{max}}(G)$ is a disjoint
union of $I_{i}\in\mathcal{I}_{\textup{max}}(G_{i})$ for $i\in[m]$, therefore,
to hit all maximum independent sets in $G$, it suffices to hit all maximum
independent sets in a connected component. For (2), if there is some
$I\in\mathcal{I}_{\textup{max}}(G)$ such that $I\cap N_{G}(v)=\emptyset$, then
$v\in I$. For (3), let $G=A\cup B$, if $|A|\neq|B|$, then
$\alpha(G)>\frac{|G|}{2}$, which yields $h(G)=1$ by Hajnal’s observation.
Assume $|A|=|B|$, if there is a subset $S\subseteq A$ such that $|S|>|N(S)|$,
then $\alpha(G)\geq|S\cup B\setminus N(S)|>\frac{|G|}{2}$, which implies
$h(G)=1$. Otherwise, by Hall’s theorem [37], there is a perfect matching
between $A$ and $B$. Take one edge $ab$ from this matching and put two
endpoints $a$ and $b$ into the hitting set. It is easy to check that there is
no independent set of size $\frac{|G|}{2}$ in the induced subgraph on subset
$V(G)\setminus\\{a,b\\}$. ∎

###  2.2 Comparability graphs and incomparability graphs

An _antichain_ in a poset $P$ is a set of elements such that no two of which
are comparable to each other, and a _chain_ is a set of elements such that
every two of which are comparable. A _chain decomposition_ is a partition of
the elements of the order into disjoint chains. Dilworth’s theorem [16] states
that, in any finite poset, the largest antichain has the same size as the
smallest chain decomposition.

######  Theorem 2.2 (Dilworth [16]).

Let $P$ be a finite poset, then

$\min\\{m:\leavevmode\nobreak\ \exists\leavevmode\nobreak\ \textup{chains\
}C_{1},C_{2},\ldots,C_{m}\leavevmode\nobreak\
\textup{s.t.}\leavevmode\nobreak\
P=\bigcup_{i=1}^{m}C_{i}\\}=\max\\{|A|:A\leavevmode\nobreak\ \textup{is\ an\
antichain}\\}$

###### Proof of 1.6.

Let $P$ be a poset and $G$ be a comparability graph on $P$. Note that
$\alpha(G)$ is the maximum size of antichain in $P$. By Theorem 2.2, there is
a chain decomposition of $P$ of size $\alpha(G)$, namely $P=C_{1}\cup
C_{2}\cup\cdots\cup C_{\alpha(G)}$. We claim that for each $i\in[\alpha(G)]$,
$C_{i}$ is a hitting set for $\mathcal{I}_{\textup{max}}(G)$. Indeed, by
Theorem 2.2 again, we see that the size of largest antichain in $P\setminus
C_{i}$ is at most $\alpha(G)-1$.

Therefore by pigeonhole principle, there is a chain $C_{i}$ with size at most
$\frac{n}{\alpha(G)}$ such that $C_{i}$ hits all maximum independent sets in
$G$. ∎

###### Proof of 1.7.

Let $P$ be a poset and $G$ be the incomparability graph on $P$ with
$\alpha(G)=\alpha$. For every maximum independent set $I$ in $G$, label its
vertices as $b_{1}\prec\cdots\prec b_{\alpha}$, and color each vertex $b_{i}$
with color $i$.

######  Claim 2.3.

Every vertex in $G$ receives at most one color.

###### Proof of claim.

Suppose that there is a vertex $v$ receiving two colors. Thus, there are two
chains of length $\alpha$ containing $v$, say
$\mathcal{X}=x_{1}\prec\cdots\prec x_{\alpha}$ and
$\mathcal{Y}=y_{1}\prec\cdots\prec y_{\alpha}$, such that $v=x_{i}=y_{j}$ with
$i<j$. Then $y_{1}\prec y_{2}\prec\cdots\prec y_{j-1}\prec v\prec
x_{i+1}\prec\cdots\prec x_{\alpha}$ is a chain of length $\alpha+1$, a
contradiction. ∎

Therefore, we colored all vertices that belong to a maximum independent set
with $\alpha$ colors. For any color $i\in[\alpha]$, the set of all vertices
with color $i$ hits all maximum independent sets of $G$. Hence, by the
pigeonhole principle, we have $h(G)\leq\frac{n}{\alpha}$. ∎

###  2.3 Graphs with VC-dimension $1$: Proof of Theorem 1.8

Let $G$ be a graph with VC-dimension $1$ and $\alpha(G)=\alpha$.

######  Lemma 2.4.

Let $G$ be a graph with VC-dimension one, then $G$ is induced $P_{5}$-free.

###### Proof of Lemma 2.4.

Suppose there is an induced copy of $P_{5}:=x_{1}x_{2}x_{3}x_{4}x_{5}$, then
$\\{x_{2},x_{4}\\}$ is shattered, a contradiction. ∎

Moreover, we can also obtain the following simple structural property.

######  Lemma 2.5.

Let $G$ be a graph with VC-dimension one. If there is a triangle in $G$ with
vertices $a_{1},a_{2},a_{3}$, then every vertex in
$V(G)\setminus\\{a_{1},a_{2},a_{3}\\}$ is adjacent to at least two vertices in
$\\{a_{1},a_{2},a_{3}\\}$.

###### Proof of Lemma 2.5.

If a vertex $v\in V(G)\setminus\\{a_{1},a_{2},a_{3}\\}$ is not adjacent to any
vertex in $\\{a_{1},a_{2},a_{3}\\}$, then the set $\\{a_{1},a_{2}\\}$ is
shattered. Moreover, if $v$ is adjacent to exactly one of
$\\{a_{1},a_{2},a_{3}\\}$, by symmetry, assume $va_{1}\in E(G)$, then
$\\{a_{2},a_{3}\\}$ is shattered. ∎

We will also take advantage of the structural property of triangle-free graphs
without induced $P_{5}$, which was proven by Sumner [52] in 1981.

######  Theorem 2.6 ([52]).

Let $G$ be an induced $P_{5}$-free and triangle-free graph, then each
connected component of $G$ is either a bipartite graph, or a copy of
$C_{5}[\cdot]$.

Suppose that $G$ is triangle-free, then by Theorem 2.6, if $G$ is bipartite,
then 2.1 yields that $h(G)\leq 2$, otherwise $G=C_{5}[\cdot]$ with parts
$F_{1},F_{2},F_{3},F_{4},F_{5}$, and one can see $\alpha(G)\geq\frac{2n}{5}$.
We further notice that if $c\neq\frac{2}{5}$, then $h(G)\leq 2$. To see this,
if $c\neq\frac{2}{5}$, then there exists some pair $(i,j)$ with
$|i-j|\not\equiv 1\pmod{5}$ such that $|F_{i}\cup F_{j}|<\frac{2n}{5}$.
Without loss of generality, assume $|F_{1}\cup F_{3}|<\frac{2n}{5}$, then we
can pick arbitrary one vertex $u\in F_{4}$ and $v\in F_{5}$ respectively.
Obviously for every $I\in\mathcal{I}_{\textup{max}}(G)$,
$I\cap\\{u,v\\}\neq\emptyset$, which yields $h(G)\leq 2$. when
$c=\frac{2}{5}$, if $|F_{i}|=\frac{n}{5}$ for each $i\in[5]$, then $h(G)=3$,
otherwise, we can see $h(G)\leq 2$ via the identical argument as above.

Next we can assume that there is a triangle with vertex set
$\\{a_{1},a_{2},a_{3}\\}$. Take an arbitrary
$I:=\\{v_{1},v_{2},\ldots,v_{\alpha}\\}\in\mathcal{I}_{\textup{max}}(G)$.
Suppose that $I\cap\\{a_{1},a_{2},a_{3}\\}=\emptyset$, then by Lemma 2.5,
$v_{1}$ must be adjacent to at least two vertices in
$\\{a_{1},a_{2},a_{3}\\}$. Without loss of generality, we can assume that
$v_{1}a_{1}\in E(G)$ and $v_{1}a_{2}\in E(G)$. As $v_{1},a_{1},a_{2}$ together
form a copy of triangle, then for every vertex $v_{j}\in
I\setminus\\{v_{1}\\}$, $v_{j}$ must be adjacent to both of $a_{1}$ and
$a_{2}$ by Lemma 2.5, which indicates that all of vertices in $I$ are adjacent
to both of $a_{1}$ and $a_{2}$. Moreover, as $a_{3}\notin I$, then $a_{3}$
must be adjacent to some vertex in $I$, say $a_{3}v_{k}\in E(G)$, which
implies that $a_{1},a_{3},v_{k}$ form a copy of triangle. Again by Lemma 2.5,
any vertex $v_{\ell}\in I\setminus\\{v_{k}\\}$ should be adjacent to $a_{3}$.
Now let $v\in V(G)\setminus(I\cup\\{a_{1},a_{2},a_{3}\\})$. First, $v$ must be
adjacent to at least two vertices in $\\{a_{1},a_{2},a_{3}\\}$, and we assume
$a_{1}v,a_{2}v\in E(G)$ without loss of generality. As $v\notin I$, there must
be some vertex $v_{q}$ such that $v_{q}v\in E(G)$, which implies that
$a_{1}v_{q}v$ forms a copy of triangle, then by Lemma 2.5, every vertex in $I$
should be adjacent to the vertex $v$.

One can also apply the same argument to show that if
$|I\cap\\{a_{1},a_{2},a_{3}\\}|=1$, every vertex $v\in V(G)\setminus I$ is
adjacent to all vertices in $I$. We omit the repeated details here.

Therefore, if $G$ contains a copy of triangle as a subgraph, then all of the
maximum independent sets of $G$ must be disjoint, which implies that
$h(G)\leq\frac{n}{\alpha}$ in this case. This finishes the proof.

##  3 A general framework for locally sparse graphs

In this section, we provide a general framework to find a relatively small
hitting set. This framework performs well for those graphs with linear
independence number and certain locally sparse property. As examples, here we
show that the even-hole-free graphs and disk graphs satisfy the property.

###  3.1 A general framework

######  Theorem 3.1.

Let $c>0$, $s\in\mathbb{N}$ and $G$ be an $n$-vertex graph with
$\alpha(G)=cn$. If for any $I_{1},I_{2}\in\mathcal{I}_{\textup{max}}(G)$,
$e(G[I_{1}\triangle I_{2}])\leq s\cdot|I_{1}\triangle I_{2}|$, then
$h(G)\leq\frac{5sn}{\log{n}}$.

###### Proof of Theorem 3.1.

Let $\delta=\frac{a}{\log{n}}$ where $a=5s$ is a constant and let $b=0.98a$.
Select a maximal sequence $I_{1},\ldots,I_{t}\in\mathcal{I}_{\textup{max}}(G)$
such that for each $k\in[t]$,
$|I_{k}\setminus\big{(}\bigcup_{i=1}^{k-1}I_{i}\big{)}|>\frac{\delta n}{bk}$.
Let $W=\bigcup_{i=1}^{t}I_{i}$ and $G^{\prime}=G[W]$. Then

$n\geq|W|\geq cn+\sum\limits_{i=2}^{t}\frac{\delta
n}{bi}=cn+(\log{t}-O(1))\frac{\delta n}{b},$

and so $t\leq e^{b/\delta+O(1)}<\frac{n^{0.99}}{2s}$. Then, by the assumption,
we have

$e_{G}(I_{1},\bigcup_{i=2}^{t}I_{i})\leq\sum_{i=2}^{t}e(G[I_{1}\triangle
I_{i}])\leq 2s(t-1)cn<cn^{1.99}.$ (1)

Now suppose that $G^{\prime}=G$. By Eq. 1 and the pigeonhole principle, there
exists a vertex $v\in I_{1}$ with $d_{G}(v)<n^{0.99}$ and we are done by 2.1.

It remains to consider the case that $G^{\prime}\neq G$. Again by Eq. 1, we
can pick a subset $C\subseteq I_{1}$ with $|C|=\frac{\delta n}{4s(t-1)}$ such
that $e_{G}(C,\bigcup_{i=2}^{t}I_{i})\leq 2s(t-1)|C|\leq\frac{\delta n}{2}$.
Note that

$|C|+|N_{G^{\prime}}(C)|\leq|C|+e_{G}(C,\bigcup_{i=2}^{t}I_{i})\leq\delta
n=\frac{5sn}{\log n}.$

It suffices to show that $C\cup N_{G^{\prime}}(C)$ hits all maximum
independent sets in $G$. Fix an arbitrary $I\in\mathcal{I}_{\textup{max}}(G)$.
The maximality of $t$ infers that $|I\setminus W|\leq\frac{\delta n}{b(t+1)}$.
Suppose to the contrary that $I\cap(C\cup N_{G^{\prime}}(C))=\emptyset$. Then,
$(I\cap W)\cup C$ is an independent set of size $|C|+|I|-|I\setminus
W|\geq\frac{\delta n}{4s(t-1)}+(cn-\frac{\delta n}{b(t+1)})>cn$ as
$b=0.99a>4s$, contradicting to $\alpha(G)=cn$. ∎

###  3.2 Even-hole-free graphs: Proof of Theorem 1.2

A well-known result states that the number of edges in an acyclic graph is
less than the number of vertices. Based on Theorem 3.1, to prove Theorem 1.2,
it suffices to show the following lemma.

######  Lemma 3.2.

Let $G$ be an even-hole-free graph. Then, for any
$I_{1},I_{2}\in\mathcal{I}_{\textup{max}}(G)$, $G[I_{1}\triangle I_{2}]$ is
acyclic.

###### Proof of Lemma 3.2.

Consider a minimal cycle $C$ in $G^{\prime}=G[I_{1}\triangle I_{2}]$ if
exists. By minimality, $C$ is an induced cycle in $G$. As $G^{\prime}$ is
bipartite, $C$ is an induced even cycle, a contradiction. Thus no such cycle
exists and $G^{\prime}$ is acyclic as desired. ∎

###  3.3 Disk graphs: Proof of Theorem 1.3

Similarly as above, based on Theorem 3.1, to prove Theorem 1.3, it suffices to
show the following lemma.

######  Lemma 3.3.

Let $G$ be an $n$-vertex disk graph with $\alpha(G)=cn$ for some $c>0$. For
any $I_{1},I_{2}\in\mathcal{I}_{\textup{max}}(G)$, $e(G[I_{1}\triangle
I_{2}])\leq 5|I_{1}\triangle I_{2}|$.

###### Proof of Lemma 3.3.

Firstly, we prove the following claim using the geometric intuition that a
disk cannot intersect simultaneously with too many non-intersecting larger
disks. For a vertex $v$, we denote $\rho(v)$ the radius of the disk
corresponding to $v$.

######  Claim 3.4.

Let $v\in V(G)$ be a vertex with radius $\rho(v)$, then there is no
independent set $I$ of size $6$ in the induced subgraph $G[N_{G}(v)]$ such
that every vertex $u$ in $I$ satisfies $\rho(u)\geq\rho(v)$.

###### Proof of claim.

Suppose there are seven disks $A,B_{1},B_{2},\ldots,B_{6}$ with centers
$\bm{x},\bm{y}_{1},\bm{y}_{2},\ldots,\bm{y}_{6}$ and radii
$r_{A},r_{1},r_{2},\ldots,r_{6}$ such that for all $i\in[6]$, $r_{A}\leq
r_{i}$, $A$ intersects $B_{i}$ and $B_{i}$ are pairwise disjoint. Then, for
any $j\neq i$, $|\bm{x}-\bm{y}_{i}|\leq r_{A}+r_{i}\leq
r_{j}+r_{i}<|\bm{y}_{i}-\bm{y}_{j}|$ and $|\bm{x}-\bm{y}_{j}|\leq
r_{A}+r_{j}\leq r_{i}+r_{j}<|\bm{y}_{i}-\bm{y}_{j}|$. Therefore, the angle
$\angle\bm{y}_{i}\bm{x}\bm{y}_{j}$ is greater than $\frac{\pi}{3}$ for any
pair of $1\leq i<j\leq 6$. This yields
$2\pi<\angle\bm{y}_{1}\bm{x}\bm{y}_{2}+\cdots+\angle\bm{y}_{5}\bm{x}\bm{y}_{6}+\angle\bm{y}_{6}\bm{x}\bm{y}_{1}=2\pi$,
a contradiction. ∎

For a subset $S\subseteq V(G)$, let $d_{S}^{\geq}(u)$ be the number of
neighbors $w\in N_{S}(u)$ such that $\rho(w)\geq\rho(u)$. For any
$I_{1},I_{2}\in\mathcal{I}_{\textup{max}}(G)$, By 3.4 we have

$e(G[I_{1}\triangle I_{2}])\leq\sum\limits_{u\in
I_{1}}d^{\geq}_{I_{2}\setminus I_{1}}(u)+\sum\limits_{v\in
I_{2}}d^{\geq}_{I_{1}\setminus I_{2}}(v)\leq 5|I_{1}\triangle I_{2}|.$

∎

###  3.4 Proof of Theorem 1.4

We prove that disk graphs have an $11$-simplicial vertex, i.e. the set of its
neighbors is the union of $11$ cliques.

For a disk graph $G$ and $v\in V(G)$, denote by $D_{G}(v)$ the disk
corresponding to $v$ and $\rho_{G}(v)$ the radius of $D_{G}(v)$. Let $v_{0}\in
V(G)$ be a vertex with minimum radius $\rho_{G}(v_{0})$ among all vertices in
$G$. By rescaling, we may assume $\rho(v_{0})=1$. We shall prove that $v_{0}$
is the desired $11$-simplicial vertex.

For each neighbor $v\in N_{G}(v)$, define a new disk $D^{\prime}(v)$ with
radius 1 internally tangent to $D_{G}(v)$ such that the common point
$A=D^{\prime}(v)\cap D_{G}(v)$ lies on the line going through centers of
$D_{G}(v_{0})$ and $D_{G}(v)$ (see Fig. 3.2). As each new disk $D^{\prime}(v)$
is contained in the original $D_{G}(v)$, for any $v,w\in N_{G}(v_{0})$, if
$D^{\prime}(v)\cap D^{\prime}(w)\neq\varnothing$, then $vw\in E(G)$. As
depicted in Fig. 3.2, the family of all new disks
${\mathcal{D}}=\\{D^{\prime}(v):v\in N_{G}(v_{0})\\}$, all of which intersect
$D_{G}(v_{0})$, can be pierced by at most 11 points, implying that $v_{0}$ is
an 11-simplicial vertex in $G$.

$D_{0}$$D^{\prime}$$A$$D$ Figure 3.1: Create the disk $D^{\prime}$ according
to the disks $D_{0}$ and $D$

Figure 3.2: Any unit disk $D$ which intersects $D_{0}$ must contain one of the
eleven points

##  4 Circle graphs: Proof of Theorem 1.5

Consider a circle $O$, where the vertex set of graph $G$ consists of $n$
distinct chords in $O$. By perturbation, we may assume that none of these $n$
chords are diameters of $O$. For each $v\in V(G)$, let $C_{v}$ denote its
corresponding chord and $A_{v}$ the minor arc associated to $C_{v}$.

For two non-crossing chords $C_{a},C_{b}$, we say that $C_{a}$ _covers_
$C_{b}$ if $A_{a}\supseteq A_{b}$. Furthermore, we say that $C_{a}$ _directly
covers_ $C_{b}$ if there does not exist any other chord $C_{c}$ with
$A_{a}\supseteq A_{c}\supseteq A_{b}$ (see Fig. 4.2). For
$X\in\mathcal{I}_{\textup{max}}(G)$ and $x\in X$, let $K_{X}(x)$ be the set of
vertices in $X$ which are covered by $x$ and let $k_{X}(x):=|K_{X}(x)|$.
Obviously, $0\leq k_{X}(x)\leq cn-1$. Note also that for any $a,b\in X$, if
$C_{a}$ covers $C_{b}$, then $k_{X}(a)>k_{X}(b)$. Now, for each
$I\in\mathcal{I}_{\textup{max}}(G)$ and $v\in I$, assign it the color
$k_{I}(v)$.

ABCD Figure 4.1: $A$ covers $B,C,D$, but $A$ does not directly cover $C,D$

Figure 4.2: Any chord can cross at most two distinct chords in $Z_{I}$

######  Claim 4.1.

Each vertex in $V(G)$ receives at most one color.

###### Proof of claim.

Suppose that some vertex $u$ receives two distinct colors, say for
$X,Y\in\mathcal{I}_{\textup{max}}(G)$, $k_{X}(u)=i<j=k_{Y}(u)$. Note that
chords in $X\setminus K_{X}(u)$ are disjoint from those in $K_{Y}(u)$ as they
lie in different sides of $C_{u}$. Therefore, $(X\setminus K_{X}(u))\cup
K_{Y}(u)$ is also an independent set of size $cn-i+j>cn$, a contradiction. ∎

Next, for $I\in\mathcal{I}_{\textup{max}}(G)$, consider a vertex $v\in I$ with
minimum $k_{I}(v)$. The minimality of $v$ implies that it does not cover any
other vertex in $I$ and so $k_{I}(v)=0$. Thus, we have the following claim.

######  Claim 4.2.

For each $I\in\mathcal{I}_{\textup{max}}(G)$, the set $Z_{I}=\\{v\in
I:k_{I}(v)=0\\}\neq\emptyset$.

Note that for any $I\in\mathcal{I}_{\textup{max}}(G)$ and any three pairwise
non-crossing chords in $Z_{I}$, any other chord can cross at most two of them
(see Fig. 4.2). Thus, the number of edges between $Z_{I}$ and $V(G)\setminus
I$ is at most $2(1-c)n$ and there exists a vertex $v\in Z_{I}$ with
$d_{G}(v)\leq\frac{2(1-c)n}{|Z_{I}|}$. Then by 2.1,
$h(G)\leq\frac{2(1-c)n}{|Z_{I}|}+1$. Consequently, if there is $I$ with
$|Z_{I}|>\frac{\log{n}}{\log\log{n}}$, then we are done. We may then assume
that $|Z_{I}|\leq M:=\frac{\log{n}}{\log\log{n}}$ for all
$I\in\mathcal{I}_{\textup{max}}(G)$.

Let $R\subseteq V(G)$ denote the set of vertices that do not belong to any
maximum independent set. By 4.1, every vertex in $V(G)\setminus R$ is assigned
a unique color in $\\{0,1,\ldots,cn-1\\}$. Partition $V(G)\setminus R$ by
colors $V(G)\setminus R=V_{0}\cup V_{1}\cup V_{2}\cup\cdots\cup V_{cn-1}$,
where any vertex $v\in V_{i}$ satisfies $k_{I}(v)=i$ for any
$I\in\mathcal{I}_{\textup{max}}(G)$. By 4.2, $V_{0}$ is a hitting set for
$\mathcal{I}_{\textup{max}}(G)$. However, it is hard to bound the size $V_{0}$
directly. We will instead use multiple layers of $V_{i}$ instead.

Fix an $I\in\mathcal{I}_{\textup{max}}(G)$ with $|Z_{I}|\leq M$.

######  Claim 4.3.

For any $v\in I$, $v$ directly covers at most $M$ other vertices in $I$.

###### Proof of claim.

Let $U\subseteq I$ be the set of vertices in $I$ that are directly covered by
$v$. Then no vertex in $U$ covers another. This, together with the fact that
$U\subseteq I$ is independent, infers that the minor arcs $A_{u}$, $u\in U$,
are pairwise disjoint. Then, considering a vertex $u^{\prime}$ with minimal
color with $A_{u^{\prime}}\subseteq A_{u}$ for each $u\in U$, we see that
$|Z_{I}|\geq|U|$ finishing the proof. ∎

######  Claim 4.4.

$I\cap\bigcup_{i=1}^{M}V_{i}\neq\varnothing$ and $|I\cap V_{i}|\leq M$ for all
$i\in[cn-1]$. In particular, $h(G)\leq|\bigcup_{i=1}^{M}V_{i}|$.

###### Proof of claim.

Consider a vertex $u\in I\setminus Z_{I}$ with minimum color. By the
minimality, $u$ can cover only vertices in $Z_{I}$ and so
$k_{I}(u)\leq|Z_{I}|$.

Fix $i\in[cn-1]$, then the minor arcs $A_{u}$, $u\in I\cap V_{i}$, are
pairwise disjoint. Again, considering a vertex $u^{\prime}$ with minimal color
with $A_{u^{\prime}}\subseteq A_{u}$ for each $u\in I\cap V_{i}$, we see that
$|Z_{I}|\geq|I\cap V_{i}|$. ∎

Let $t$ be the largest positive integer such that
$(2M)^{t+1}\leq\lfloor\frac{cn}{M+1}\rfloor$. Then by 4.4, we see that $I$
contains vertices with color at least $(2M)^{t+1}+1$, that is,
$I\setminus(\bigcup_{i=1}^{(2M)^{t+1}}V_{i})\neq\varnothing$.

######  Claim 4.5.

For each $0\leq j\leq t$,
$I\cap\bigcup_{k=(2M)^{j}+1}^{(2M)^{j+1}}V_{k}\neq\varnothing$. In particular,
$h(G)\leq|\bigcup_{k=(2M)^{j}+1}^{(2M)^{j+1}}V_{k}|$.

###### Proof of claim.

We prove it by induction on $0\leq j\leq t$. The base case $j=0$ follows from
4.4. For the inductive step, suppose the claim holds for all $0\leq
j^{\prime}<j\leq t$. Consider a vertex $w$ in
$I\setminus(\bigcup_{i=1}^{(2M)^{j+1}}V_{i})$ with minimum color. Then, as $w$
can directly cover at most $M$ vertices in $I$ by 4.3, there must exist a
vertex $u$ covering at least $\frac{(2M)^{j+1}+1-M}{M}\geq(2M)^{j}+1$
vertices. On the other hand $u$ covers at most $(2M)^{j+1}$ vertices by the
minimality of $w$. This finishes the proof. ∎

As each $\bigcup_{k=(2M)^{j}+1}^{(2M)^{j+1}}V_{k}$, $j=0,1,\ldots,t$, is a
hitting set for $\mathcal{I}_{\textup{max}}(G)$, by averaging, there is a
hitting set of size at most $\lfloor\frac{n}{t+1}\rfloor$. By the choice of
$t$, $(2M)^{t+2}\geq\frac{cn}{M+1}$ and so
$t\geq\frac{\log\frac{cn}{M+1}}{\log(2M)}-2\geq\frac{\log n}{4\log\log n}$.
Thus, $h(G)\leq\frac{4n\log\log{n}}{\log{n}}$. The proof is finished.

##  5 Concluding remarks

In conclusion, our study delves into the longstanding open problem proposed by
Bollobás, Erdős and Tuza, which posits that for any $n$-vertex graph with
$\alpha(G)=\Omega(n)$, it suffices to employ $o(n)$ vertices to hit all
maximum independent sets. Our investigation draws inspiration from the
remarkable result, along with its elegant proof, by Alon [3], demonstrating
validity of 1 for regular graphs with large independence number, as well as
the work of Hajebi, Li, and Spirkl [35], establishing the existence of small
hitting sets for induced $P_{5}$-free graphs.

Our primary contribution lies not only in confirming the validity of 1 across
several significant graph classes but also in synthesizing concepts from
diverse fields to either construct or demonstrate the existence of small
hitting sets. We envision our ideas serving as a springboard for further
exploration aimed at tackling this conjecture.

It is intriguing to note that the conjecture remains open even when
$\alpha(G)=(\frac{1}{2}-\varepsilon)|G|$ for any small $\varepsilon>0$. We
believe that addressing this weaker conjecture presents its own set of
challenges worthy of pursuit.

###  5.1 Constant-sized hitting sets in various sporadic graphs

In addition to the graph classes we have discussed in Section 2, in many other
classes of geometric graphs, we can also prove the existence of hitting sets
of constant size. We select some representative ones to introduce the sketches
briefly. For a configuration $S$ in high dimensional space $\mathbb{R}^{d}$,
let $\mu(S)$ be the Lebesgue measure of $S$, and $|\bm{x}-\bm{y}|$ represent
the Euclidean distance between points $\bm{x},\bm{y}\in\mathbb{R}^{d}$, we
define the diameter of $S$ as
$\textup{Diam}(S):=\sup\\{|\bm{a}-\bm{b}|:\bm{a},\bm{b}\in S\\}$. Observe that
in an intersection graph of configurations with positive measures and bounded
diameter $D$, there is no large induced star, because the ball of radius $2D$
can only contain bounded number of pairwise disjoint configurations.
Therefore, the following result follows.

######  Proposition 5.1.

Let $\varepsilon>0$ be a real number and $d\geq 1$ be a positive integer. Let
$\mathcal{S}:=\\{S_{1},S_{2},\ldots,S_{n}\\}\subseteq\mathbb{R}^{d}$ be a
collection of $n$ sets such that for each $i\in[n]$, $\mu(S_{i})>\varepsilon$
and $\textup{Diam}(S_{i})\leq D$ for some constant $D>0$. Let $G$ be the
intersection graph of the sets in $\mathcal{S}$, then
$h(G)=O_{\varepsilon,D,d}(\frac{n}{\alpha(G)})$. In particular, if
$\alpha(G)=cn$ for some $c>0$, then $h(G)=O_{\varepsilon,D,d,c}(1)$.

In low dimensional space, the _interval graph_ is formed from a set of
intervals on the real line, with a vertex for each interval and an edge
between vertices whose intervals intersect. It was known that any interval
graph is an incomparability graph, therefore, by 1.7, we can see
$h(G)\leq\frac{n}{\alpha(G)}$ when $G$ is an $n$-vertex interval graph.

An interesting generalization of interval graph is _circular-arc graph_ ,
which is the intersection graph of a set of arcs on the circle. It has one
vertex for each arc in the set, and an edge between every pair of vertices
corresponding to arcs that intersect. Observe that, for any given maximum
independent set $I$, if a vertex $v\in V(G)\setminus I$ such that
$|N_{G}(v)\cap I|\geq 4$, then $v$ cannot belong to any maximum independent
set in $G$. Based on this, the following result follows.

######  Proposition 5.2.

Let $G$ be a circular-arc graph, then we have
$h(G)\leq\frac{3n}{\alpha(G)}-2$, and in particular if $\alpha(G)=cn$ for some
$c>0$, we have $h(G)\leq\frac{3}{c}-2$.

###  5.2 Extension of circle graphs

We can also extend the technique in the proof of Theorem 1.5 to a more general
class of graphs. More precisely, a _circle $k$-gon_ is the region that lies
between $k$ or fewer non-crossing chords of a circle, no chord connecting the
arcs between two other chords. The sides of a circle $k$-gon are either chords
or arcs of the circle. A graph is a _circle k-gon graph_ if it is the
intersection graph of circle $k$-gons in a common circle. One can see that any
circle graph is indeed a circle $1$-gon graph. Using the almost identical
argument, we can show the following more general result.

######  Theorem 5.3.

Let $k\geq 1$ be a positive integer and let $G$ be a circle $k$-gon graph with
$\alpha(G)=\Omega(n)$, then we have $h(G)\leq
O(\frac{n\log\log{n}}{\log{n}})$.

###  5.3 The bridge between the balanced separators and the hitting sets

For an $n$-vertex graph $G$, a subset $S\subseteq V(G)$ is a _balanced
separator_ if every component of $G\setminus X$ has at most $\frac{2n}{3}$
vertices. Equivalently, $S\subseteq V(G)$ is a balanced separator if there is
a partition $V:=S\cup V_{1}\cup V_{2}$ with
$|V_{1}|,|V_{2}|\leq\frac{2|V(G)|}{3}$ such that no vertex in $V_{1}$ is
adjacent to any vertex in $V_{2}$.

Here, we establish a straightforward connection between the balanced separator
and the hitting set. Let $\mathcal{G}_{\varepsilon}$ be a hereditary family of
graphs such that for every graph $G\in\mathcal{G}$, there exists a balanced
separator of size at most $\varepsilon|V(G)|$. Note that for any $n$-vertex
graph, we can repeatedly take balanced separators and consider the subgraphs
induced by smaller components by 2.1. Note that the union of those separators
forms a hitting set, which is of size at most
$\sum\limits_{i}\frac{\varepsilon n}{2^{i-1}}\leq 2\varepsilon n$.

######  Proposition 5.4.

Let $G\in\mathcal{G}_{\varepsilon}$ be an $n$-vertex graph, then $h(G)\leq
2\varepsilon n$.

Therefore, for those hereditary graphs having sublinear balanced separators,
they also have sublinear hitting sets. For instance, a classical result of
Lipton and Tarjan [45] shows that every $n$-vertex planar graph contains a
balanced separator of size $O(\sqrt{n})$. This result on planar graphs has
also been generalized to graphs embedded in a surface of bounded genus [33],
graphs with a forbidden minor [4], and intersection graphs of some geometric
objects [23, 46].

In addition to the aforementioned classical results, a recent study by Dvořák,
McCarty, and Norin [18] provided a sufficient condition for an intersection
graph of compact convex sets in $\mathbb{R}^{d}$ to possess a balanced
separator of sublinear size. Furthermore, Dvořák and Wood [19] have elucidated
the connection between balanced separators and other parameters such as tree-
width, path-width, and tree-depth. For additional hereditary families of
graphs with sublinear balanced separators, we recommend interested readers to
refer to [18] and the references therein.

###  5.4 Some open problems

####  5.4.1 Graphs with bounded VC-dimension

Theorem 1.8 indicates that any graph with VC-dimension one has a very small
hitting set. While for any larger positive integer $d\geq 2$, it remains an
interesting open problem.

######  Conjecture 2.

Let $d\geq 2$ be a positive integer, and let $G$ be an $n$-vertex graph with
VC-dimension at most $d$. If $\alpha(G)=\Omega(n)$, then $h(G)=o(n)$.

We anticipate that insights from several papers [1, 25, 26, 27, 47, 51] may
prove instrumental in our exploration. Motivated by the recent work of Nguyen,
Scott and Seymour [47], who proved that graphs with bounded VC-dimension have
Erdős-Hajnal property, one might expect that
$h(G)\leq\textup{Poly}(\omega(G))$ holds for the graphs with bounded VC-
dimension. However, this is not true. Alon’s construction in [3, Theorem 1.3]
showed that there is a graph $G$ with bounded VC-dimension and small clique
number, but $h(G)$ cannot be upper bounded by any function of $\omega(G)$.

###### Proof of Theorem 1.1.

Let $k$ be a positive integer and $K:=\\{1,2,\ldots,2k\\}$. The set of
vertices of $G$ is the set of all ordered pairs $(i,j)$ with distinct $i,j\in
K$. Note that the number of vertices is $n=2k(2k-1)$. A pair of vertices
$(a,b)$ and $(c,d)$ are adjacent if $b=c$ or $a=d$. Alon [3] has already
proved that $h(G)\geq\frac{\sqrt{n}}{2}$. It then remains to show
$\omega(G)=3$ and VC-dimension is at most $3$. First, it is easy to check that
any triangle in $G$ must be of the form $(a,b),(b,c),(c,a)$, where $a,b,c\in
K$ are distinct, moreover, it is obvious that these three vertices have no
common neighbor. For the VC-dimension of $G$, suppose
$S=\\{(a_{i},b_{i}):i\in[4]\\}$ is a shattered set. Let $(x,y)$ be the vertex
such that $N_{G}((x,y))\supseteq N_{G}(S)$. Then for each $1\leq i\leq 4$,
either $a_{i}=y$ or $b_{i}=x$. If for each $1\leq i\leq 4$, $a_{i}=y$ (or
$b_{i}=x$ respectively), then there is no vertex $(z,w)$ such that
$|N_{G}((z,w))\cap S|=3$. Therefore, without loss of generality, we can assume
there exist three vertices in $S$ of the form $(a_{1},x),(a_{2},x),(y,b_{3})$
(or $(b_{1},y),(b_{2},y),(a_{3},x)$), then it is easy to check that these
three vertices have no common neighbor other than $(x,y)$. This finishes the
proof. ∎

####  5.4.2 String graphs

In a fundamental sense, curves represent the most versatile geometric objects
on the plane, defined as the images of continuous functions
$\phi:[0,1]\rightarrow\mathbb{R}^{2}$. A string graph emerges as the
intersection graph of such curves. Notice that the majority of graph families
examined within this paper align with the concept of string graphs.
Consequently, the following conjecture assumes significant relevance.

######  Conjecture 3.

Let $G$ be an $n$-vertex string graph.

  1. (1)

If $\alpha(G)=\Omega(n)$, then $h(G)=o(n)$.

  2. (2)

There exists some constant $s>0$ such that $h(G)\leq\omega(G)^{s}$.

The significant finding by Fox and Pach [24] might be helpful, which asserts
that any dense string graph must contain a dense incomparability graph as a
spanning subgraph. 3(2) is also motivated by a recent breakthrough by Tomon
[53], who demonstrated that string graphs have the Erdős-Hajnal property (also
see a more flexible result [28]). Building on the relationship discovered in
[35], a proof of 3(2) would offer a novel proof of Tomon’s theorem and
possibly lead to potential quantitative improvements.

We are also interested in the family of interval filament graphs introduced by
Gavril [30]. A graph is an _interval filament graph_ if it is the intersection
graph of continuous non-negative functions defined on closed intervals with
zero-values on their endpoints. One of the motivations is that the family of
interval filament graphs is a common generalization of the incomparability
graphs, the circle graphs and the chordal graphs.

######  Conjecture 4.

Let $G$ be an $n$-vertex interval filament graph with $\alpha(G)=\Omega(n)$,
then $h(G)=o(n)$.

####  5.4.3 Optimal construction

We believe that 1 is true, but currently we are unable to prove it.
Conversely, we conjecture that the $o(n)$ term in the conjecture is optimal,
suggesting that the following conjecture may be valid.

######  Conjecture 5.

For any positive constant $\varepsilon>0$, there exists an $n$-vertex graph
$G$ with $\alpha(G)=cn$ for some constant $c>0$ and $h(G)\geq
n^{1-\varepsilon}$.

## Acknowledgement

Zixiang Xu would like to express sincere gratitude to Prof. Hong Liu for his
extensive suggestions on the writing of this draft, and for providing the
proof of 1.6. The authors also thank Prof. Noga Alon for helpful comments.

## References

  * [1] J. Ai, H. Liu, Z. Xu, and Q. Zhou.  Piercing independent sets in graphs without large induced matching.  arXiv preprint, arXiv: 2403.19737, 2024.
  * [2] N. Alon.  Hitting all maximum independent sets, appeared in open problems of oberwolfach,.  https://www.ucw.cz/~kral/ow22-openproblems.pdf, 2022.
  * [3] N. Alon.  Hitting all maximum independent sets.  arXiv preprint, arXiv: 2103.05998, 2021.
  * [4] N. Alon, P. Seymour, and R. Thomas.  A separator theorem for nonplanar graphs.  J. Amer. Math. Soc., 3(4):801–808, 1990.
  * [5] N. Alon and J. H. Spencer.  The probabilistic method.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.
  * [6] J. Balogh, R. Morris, and W. Samotij.  Independent sets in hypergraphs.  J. Amer. Math. Soc., 28(3):669–709, 2015.
  * [7] J. S. Birman and X.-S. Lin.  Knot polynomials and Vassiliev’s invariants.  Invent. Math., 111(2):225–270, 1993.
  * [8] A. Bouchet.  Circle graph obstructions.  J. Combin. Theory Ser. B, 60(1):107–144, 1994.
  * [9] G. Brückner, I. Rutter, and P. Stumpf.  Extending partial representations of circle graphs in near-linear time.  In 47th International Symposium on Mathematical Foundations of Computer Science, volume 241 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 25, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022.
  * [10] X. Cheng and Z. Xu.  Small hitting sets in comparability graphs avoiding Dilworth theorem.  www.ibs.re.kr/ecopro/zixiangxu/wp-content/uploads/sites/7/2024/04/NDL.pdf, 2024.
  * [11] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas.  The strong perfect graph theorem.  Ann. of Math. (2), 164(1):51–229, 2006.
  * [12] M. Chudnovsky and P. Seymour.  Even-hole-free graphs still have bisimplicial vertices.  J. Combin. Theory Ser. B, 161:331–381, 2023.
  * [13] F. Chung and R. Graham.  Erdős on graphs. His legacy of unsolved problems.  Wellesley, MA: A K Peters, 1999.
  * [14] J. Davies.  Improved bounds for colouring circle graphs.  Proc. Amer. Math. Soc., 150(12):5121–5135, 2022.
  * [15] J. Davies and R. McCarty.  Circle graphs are quadratically $\chi$-bounded.  Bull. Lond. Math. Soc., 53(3):673–679, 2021.
  * [16] R. P. Dilworth.  A decomposition theorem for partially ordered sets.  Ann. of Math. (2), 51:161–166, 1950.
  * [17] Z. Dong and Z. Wu.  On the stability of the graph independence number.  SIAM J. Discrete Math., 36(1):229–240, 2022.
  * [18] Z. Dvořák, R. McCarty, and S. Norin.  Sublinear separators in intersection graphs of convex shapes.  SIAM J. Discrete Math., 35(2):1149–1164, 2021.
  * [19] Z. Dvořák and D. R. Wood.  Product structure of graph classes with strongly sublinear separators.  arXiv preprint, arXiv: 2208.10074, 2022.
  * [20] P. Erdős.  Problems and results on set systems and hypergraphs.  In Extremal problems for finite sets (Visegrád, 1991), volume 3 of Bolyai Soc. Math. Stud., pages 217–227. János Bolyai Math. Soc., Budapest, 1994.
  * [21] P. Erdős and A. Hajnal.  Ramsey-type theorems.  volume 25, pages 37–52. 1989.  Combinatorics and complexity (Chicago, IL, 1987).
  * [22] J. Fox.  A bipartite analogue of Dilworth’s theorem.  Order, 23(2-3):197–209, 2006.
  * [23] J. Fox and J. Pach.  Separator theorems and Turán-type results for planar intersection graphs.  Adv. Math., 219(3):1070–1080, 2008.
  * [24] J. Fox and J. Pach.  String graphs and incomparability graphs.  Adv. Math., 230(3):1381–1401, 2012.
  * [25] J. Fox, J. Pach, and A. Suk.  Erdős-Hajnal conjecture for graphs with bounded VC-dimension.  Discrete Comput. Geom., 61(4):809–829, 2019.
  * [26] J. Fox, J. Pach, and A. Suk.  Bounded VC-dimension implies the Schur-Erdős conjecture.  Combinatorica, 41(6):803–813, 2021.
  * [27] J. Fox, J. Pach, and A. Suk.  Sunflowers in set systems of bounded dimension.  Combinatorica, 43(1):187–202, 2023.
  * [28] J. Fox, J. Pach, and A. Suk.  Quasiplanar graphs, string graphs, and the Erdős-Gallai problem.  In Graph drawing and network visualization, volume 13764 of Lecture Notes in Comput. Sci., pages 219–231. Springer, Cham, [2023] ©2023.
  * [29] J. Fox and H. T. Pham.  A multipartite analogue of Dilworth’s theorem.  arXiv preprint, arXiv: 2401.00827, 2024.
  * [30] F. Gavril.  Maximum weight independent sets and cliques in intersection graphs of filaments.  Inform. Process. Lett., 73(5-6):181–188, 2000.
  * [31] J. Geelen and E. Lee.  Naji’s characterization of circle graphs.  J. Graph Theory, 93(1):21–33, 2020.
  * [32] J. Geelen and S. Oum.  Circle graph obstructions under pivoting.  J. Graph Theory, 61(1):1–11, 2009.
  * [33] J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan.  A separator theorem for graphs of bounded genus.  J. Algorithms, 5(3):391–407, 1984.
  * [34] M. C. Golumbic.  Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics.  Elsevier Science B.V., Amsterdam, second edition, 2004.  With a foreword by Claude Berge.
  * [35] S. Hajebi, Y. Li, and S. Spirkl.  Hitting all maximum stable sets in $P_{5}$-free graphs.  J. Combin. Theory Ser. B, 165:142–163, 2024.
  * [36] A. Hajnal.  A theorem on k-saturated graphs.  Can. J. Math., 17:720–724, 1965.
  * [37] P. Hall.  On Representatives of Subsets.  J. London Math. Soc., 10(1):26–30, 1935.
  * [38] R. Hayward and B. A. Reed.  Forbidding holes and antiholes.  In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 113–137. Wiley, Chichester, 2001.
  * [39] W. L. Hsu.  Maximum weight clique algorithms for circular-arc graphs and circle graphs.  SIAM J. Comput., 14(1):224–231, 1985.
  * [40] V. Kalisz, P. Klavík, and P. Zeman.  Circle graph isomorphism in almost linear time.  In Theory and applications of models of computation, volume 13571 of Lecture Notes in Comput. Sci., pages 176–188. Springer, Cham, [2022] ©2022.
  * [41] D. J. Kleitman.  On a combinatorial conjecture of Erdős.  J. Combinatorial Theory, 1:209–214, 1966.
  * [42] P. Koebe.  Kontaktprobleme der konformen Abbildung.  Ber. Verh. Sächs. Akad. Leipzig 88, 141-164 (1936)., 1936.
  * [43] A. Kostochka and J. Kratochvíl.  Covering and coloring polygon-circle graphs.  Discrete Math., 163(1-3):299–305, 1997.
  * [44] A. V. Kostochka.  Upper bounds on the chromatic number of graphs.  Trudy Inst. Mat. (Novosibirsk), 10:204–226, 265, 1988.
  * [45] R. J. Lipton and R. E. Tarjan.  A separator theorem for planar graphs.  SIAM J. Appl. Math., 36(2):177–189, 1979.
  * [46] G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis.  Separators for sphere-packings and nearest neighbor graphs.  J. ACM, 44(1):1–29, 1997.
  * [47] T. Nguyen, A. Scott, and P. Seymour.  Induced subgraph density. VI. Bounded VC-dimension.  arXiv preprint, arXiv: 2312.15572, 2023.
  * [48] A. M. Odlyzko and N. J. A. Sloane.  New bounds on the number of unit spheres that can touch a unit sphere in $n$ dimensions.  J. Combin. Theory Ser. A, 26(2):210–214, 1979.
  * [49] L. Rabern.  On hitting all maximum cliques with an independent set.  J. Graph Theory, 66(1):32–37, 2011.
  * [50] D. Saxton and A. Thomason.  Hypergraph containers.  Invent. Math., 201(3):925–992, 2015.
  * [51] A. Suk.  On short edges in complete topological graphs.  arXiv preprint, arXiv: 2307.08165, 2023.
  * [52] D. P. Sumner.  Subtrees of a graph and the chromatic number.  In The theory and applications of graphs (Kalamazoo, Mich., 1980), pages 557–576. Wiley, New York, 1981.
  * [53] I. Tomon.  String graphs have the Erdős–Hajnal property.  J. Eur. Math. Soc. (JEMS), 26(1):275–287, 2024.
  * [54] M. Van den Nest, J. Dehaene, and B. De Moor.  Invariants of the local Clifford group.  Phys. Rev. A (3), 71(2):022310, 9, 2005.
  * [55] V. N. Vapnik and A. Y. Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In Measures of complexity, pages 11–30. Springer, Cham, 2015.  Reprint of Theor. Probability Appl. 16 (1971), 264–280.
  * [56] K. Vušković.  Even-hole-free graphs: a survey.  Appl. Anal. Discrete Math., 4(2):219–240, 2010.