text:
\section{Introduction}

An important quantity to characterize the composition of cosmic rays
is the spread in the range of masses in the primary beam. In
theoretical source models regarding protons as the dominant particle
type, the composition is expected to be (almost) pure, while in other
scenarios also allowing heavier nuclei to be accelerated, a mixed
composition is predicted.  For instance, in the `dip'
model~\cite{berezinsky_dip_prl2005,berezinsky_dip_ankle_2006}, two
observed features of the energy spectrum could be naturally understood
as a signature of proton interactions during propagation (ankle at
$\lg(E/\mathrm{eV}) \simeq 18.7$ from pair-production and flux
suppression at $\lg(E/\mathrm{eV}) \simeq 19.6$ from photopion
production). Therefore, the dip model predicts an almost pure
cosmic-ray composition with small spread in primary masses.

In a recent publication, the distributions of depths of shower maximum
\ensuremath{X_\mathrm{max}}\ (the atmospheric depth where the number of particles in the
air shower reaches a maximum value) observed at the Pierre Auger
Observatory were interpreted in terms of primary
masses~\cite{longXmax_fits2014} based on current hadronic interaction
models.  The results suggest a mixed mass composition, but there are
differences between the interaction models, and a clear rejection of
the dip model is hindered due to the uncertainties in modeling
hadronic interactions\footnote{For indirect tests of the dip model
  using cosmogenic neutrinos, see e.g.~\cite{dip_neutrinos2015} and
  references therein.}.  Specifically, around the ankle, a very light
composition consisting of proton and helium nuclei only is favoured
using QGSJetII-04~\cite{qgsjetii04} and Sibyll~2.1~\cite{sibyll21},
while for EPOS-LHC{}~\cite{eposlhc}, intermediate nuclei (of mass
number $A \simeq 14$) contribute. The spread of masses in the primary
beam near the ankle, estimated from the moments of the
\ensuremath{X_\mathrm{max}}\ distributions measured at the Pierre Auger
Observatory~\cite{PAO_Xmax_JCAP2013,longXmax2014}, depends as well on
the details of the hadronic interactions and the results include the
possibility of a pure mass composition.  Observations of \ensuremath{X_\mathrm{max}}\ by
the Telescope Array in the northern hemisphere were found compatible
within uncertainties to both a pure proton
composition~\cite{TA_MD2014} and to the data from the Auger
Observatory~\cite{WGmass_UHECR2014}.

In this report, by exploiting the correlation between two observables
registered simultaneously with different detector systems, we present
results on the spread of primary masses in the energy range
\logenr{18.5}{19.0}, i.e. around the ankle feature. These results are
robust with respect to experimental systematic uncertainties and to
the uncertainties in the description of hadronic interactions.

\section{Method and observables}

We follow~\cite{Risse_corrAP2012}
where it was proposed to exploit the correlation between \ensuremath{X_\mathrm{max}}\ and
the number of muons $N_\mu$ in air showers
to determine whether the mass composition is pure or mixed.  The
measurement must be performed by two independent detector systems to
avoid correlated detector systematics.  For pure cosmic-ray mass
compositions, correlation coefficients close to or larger than zero
are found in simulations.  In contrast, mixed mass compositions show a
negative correlation, which can be understood as a general
characteristic of air showers well reproduced within a semi-empirical
model~\cite{matthews_heitler}: heavier primaries have on average a
smaller \ensuremath{X_\mathrm{max}}\ ($\Delta\ensuremath{X_\mathrm{max}}\sim-\Delta\ln A$) and larger $N_\mu$
($N_\mu\sim A^{1-\beta}$, $\beta\simeq0.9$~\cite{alvarez2002}), such
that for mixtures of different primary masses, a negative correlation
appears.
This way, the correlation coefficient can be used to determine
the spread $\sigma(\ln A)$ of primary masses, given by
$\sigma(\ln A)=\sqrt{\langle\ln^2 A\rangle-\langle\ln A\rangle^2}$
where $\langle\ln A\rangle=\sum_i f_i\ln A_i$ and
$\langle\ln^2 A\rangle=\sum_i f_i\ln^2 A_i$
with $f_i$ being the relative fraction of mass $A_i$.
In particular, a more negative correlation indicates a larger
spread of primary masses.

At the Pierre Auger Observatory, the fluorescence telescopes allow a
direct measurement of \ensuremath{X_\mathrm{max}}\ and energy, and the surface array of
water Cherenkov detectors provide a significant sensitivity to muons:
for zenith angles between 20 and 60 degrees, muons contribute about
40\% to 90\%~\cite{auger_icrc2013_kegl} of \ensuremath{S(1000)}, the total signal at
a core distance of 1000 m.  Due to this unique feature the proposed
method can be adapted via replacement of $N_\mu$ by \ensuremath{S(1000)}, which is a
fundamental observable of the surface array.

Since \ensuremath{S(1000)}\ and \ensuremath{X_\mathrm{max}}\ of an air shower depend on its energy
and, in case of \ensuremath{S(1000)}, also on its zenith angle, \ensuremath{S(1000)}\ and
\ensuremath{X_\mathrm{max}}\ are scaled to a reference energy and zenith angle. This way we
avoid a decorrelation between the observables from combining different
energies and zenith angles in the data set. \ensuremath{S(1000)}\ is scaled to
38$^\circ$ and 10~EeV using the parameterisations
from~\cite{schulz_spec_icrc13}. \ensuremath{X_\mathrm{max}}\ is scaled to 10~EeV using an
elongation rate $d\langle\ensuremath{X_\mathrm{max}}\rangle/d\lg(E/{\rm
  eV})=58$~g\,cm${}^{-2}$/decade, an average value with little variation between
different primaries and interaction models~\cite{longXmax2014}. Here,
these scaled quantities will be denoted as \ensuremath{X_\mathrm{max}^{*}}\ and \ensuremath{S^*_{38}}.  Thus,
\ensuremath{X_\mathrm{max}^{*}}\ and \ensuremath{S^*_{38}}\ are the values of \ensuremath{X_\mathrm{max}}\ and \ensuremath{S(1000)}\ one would
have observed, had the shower arrived at 38$^\circ$ and 10~EeV. It
should be noted that the specific choice of the reference values is
irrelevant, since a transformation to another reference value shifts
the data set as a whole, leaving the correlation coefficient
invariant.

As a measure of the correlation between \ensuremath{X_\mathrm{max}^{*}}\ and \ensuremath{S^*_{38}}\ the
ranking coefficient \ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}\ introduced by Gideon and
Hollister~\cite{Gideon_JASA87} is taken. Conclusions are unchanged
when using other definitions of correlation coefficients, including
the coefficients of Pearson or Spearman, or other
ones~\cite{Niven_corr2012}. As for any ranking coefficient, the
\ensuremath{r_\mathrm{G}}\ value is invariant against any modifications leaving the ranks
of events unchanged (in particular to systematic shifts in the
observables). The main distinction from other ranking coefficients is
that the values of ranks are not used directly to calculate
\ensuremath{r_\mathrm{G}}. Rather the general statistical dependence between \ensuremath{X_\mathrm{max}^{*}}\ and
\ensuremath{S^*_{38}}\ is estimated by counting the difference in numbers of events
with ranks deviating from the expectations for perfect correlation and
anti-correlation. Thus, the contribution of each event is equal to 0
or 1, making \ensuremath{r_\mathrm{G}}\ less sensitive to a removal of individual events,
as it will be discussed also below.

The dependence of the statistical uncertainty $\Delta \ensuremath{r_\mathrm{G}}$ on the
number of events $n$ in a set and on the \ensuremath{r_\mathrm{G}}\ value itself was
determined by drawing random subsamples from large sets of simulated
events with different compositions. The statistical uncertainty can be
approximated by $\Delta \ensuremath{r_\mathrm{G}} \simeq 0.9/\sqrt{n}$. For the event set
used here $\Delta \ensuremath{r_\mathrm{G}}({\rm data})=0.024$.

\section{Data and simulations}

The analysis is based on the same hybrid events as
in~\cite{longXmax2014} recorded by both the fluorescence and the
surface detectors during the time period from 01.12.2004 until
31.12.2012. The data selection procedure, described in detail
in~\cite{longXmax2014}, guarantees that only high-quality events are
included in the analysis and that the mass composition of the selected
sample is unbiased. The reliable reconstruction of \ensuremath{S(1000)}\ requires an
additional application of the fiducial trigger cut (the station with
the highest signal should have at least 5 active neighbour
stations). This requirement does not introduce a mass composition
bias since in the energy and zenith ranges considered the surface
detector is fully efficient to hadronic
primaries~\cite{auger_SDtrigger2010,ltp_auger2011}.  Selecting
energies of \logenr{18.5}{19.0} and zenith angles $<$65$^\circ$, the
final data set contains 1376 events.  The resolution and systematic
uncertainties are about 8\% and 14\% in primary
energy~\cite{auger_icrc2013_verzi}, $<20$~${\rm g~cm^{-2}}$ and
10~${\rm g~cm^{-2}}$ in \ensuremath{X_\mathrm{max}}~\cite{longXmax2014}, and $<12$\% and
5\%~\cite{aveSD_icrc2007} in \ensuremath{S(1000)}, respectively.

The simulations were performed with CORSIKA~\cite{corsika}, using
EPOS-LHC{}, QGSJetII-04 or Sibyll~2.1 as the high-energy hadronic
interaction model, and FLUKA~\cite{fluka2008} as the low-energy model.
All events passed the full detector simulation and
reconstruction~\cite{offline07} with the same cuts as applied to data.
For each of the interaction models the shower library contains at
least 10000 showers for proton primaries and $5000-10000$ showers each
for helium, oxygen and iron nuclei.

\section{Results}

The observed values of \ensuremath{X_\mathrm{max}^{*}}\ {\it vs.}  \ensuremath{S^*_{38}}\, are displayed in
Fig.~\ref{fig:scatter}.  As an illustration, proton and iron
simulations for EPOS-LHC{} are shown as well, but one should keep in
mind that in this analysis we do not aim at a direct comparison of
data and simulations in terms of absolute values. In contrast to the
correlation analysis such a comparison needs to account for
systematics in both observables and suffers from larger uncertainties
from modeling of hadronic interactions.

\begin{figure}[hbt]
\includegraphics[width=0.5\textwidth]{XmaxS1000ScatterData.pdf}
\includegraphics[width=0.5\textwidth]{XmaxS1000ScatterMC.pdf}\\[0.2cm]
\caption{Left: measured \ensuremath{X_\mathrm{max}^{*}}\ {\it vs.} \ensuremath{S^*_{38}}\ for
  \logenr{18.5}{19.0}.  Right: the same distribution for 1000 proton and
  1000 iron showers simulated with EPOS-LHC{}.}
\label{fig:scatter}
\end{figure}

\begin{table}[hbt]
\caption{Observed \ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}\ with statistical uncertainty, and
  simulated \ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}\ for various compositions using different
  interaction models (statistical uncertainties are $\approx$0.01).}
\label{tab:rsmilla065g}
\begin{center}
\renewcommand{\tabcolsep}{9pt}
\begin{tabular}{cccc}
  \hline
  data&\multicolumn{3}{c}{$-0.125\pm0.024\,(\mathrm{stat})$}\\
  \hline
  \hline
  &EPOS-LHC & QGSJetII-04 & Sibyll 2.1 \\
  \hline
  $p$&0.00&0.08&0.06\\
  He&0.10&0.16&0.14\\
  O&0.09&0.16&0.17\\
  Fe&0.09&0.13&0.12\\[0.1cm]
$0.5\,p\,-\,0.5\,\mathrm{Fe}$&-0.37&-0.32&-0.31\\[0.1cm]
$0.8\,p\,-\,0.2\,\mathrm{He}$&0.00&0.07&0.05\\
  \hline
\end{tabular}
\end{center}

\end{table}

\begin{figure}[!t]
\includegraphics[width=0.5\textwidth]{rG_RMSlnA_EPOSLHC_8Color.pdf}
\includegraphics[width=0.5\textwidth]{rG_RMSlnA_QGSII04_8Color.pdf}
\caption{Dependence of the correlation coefficients \ensuremath{r_\mathrm{G}}\ on
  $\sigma(\ensuremath{\ln A})$ for EPOS-LHC{} (left) and QGSJetII-04 (right). Each
  simulated point corresponds to a mixture with different fractions of
  protons, helium, oxygen and iron nuclei, the relative fractions
  changing in 0.1 steps (4 points for pure compositions are grouped at
  $\sigma(\ensuremath{\ln A}) = 0$). Colors of the points indicate \ensuremath{\langle\ln A\rangle}\ of the
  corresponding simulated mixture. The shaded area shows the observed
  value for the data. Vertical dotted lines indicate the range of
  $\sigma(\ensuremath{\ln A})$ in simulations compatible with the observed
  correlation in the data.}
\label{fig:xmaxs_vs_rmslna}
\end{figure}

\begin{figure}[!t]
\begin{center}
\includegraphics[width=0.7\textwidth]{rG_Energy_Crop.pdf}
\end{center}
\caption{The correlation coefficients \ensuremath{r_\mathrm{G}}\ for data in the energy
  bins
  $\lg(E/\mathrm{eV})=18.5-18.6;\,18.6-18.7;\,18.7-18.8;\,18.8-19.0$. Numbers
  of events in each bin are given next to the data points. The gray
  band shows the measured value for data in the whole range
  \logenr{18.5}{19.0}. Predictions for the correlations \ensuremath{r_\mathrm{G}}\ in this
  range for pure proton and iron compositions, and for the extreme mix
  $0.5\,p\,-\,0.5\,\mathrm{Fe}$ from EPOS-LHC{} and QGSJetII-04 are
  shown as hatched bands (for Sibyll~2.1 values are similar to those
  of QGSJetII-04). The widths of the bands correspond to statistical
  errors.}
\label{fig:energybins}
\end{figure}

In Table~\ref{tab:rsmilla065g}, the observed \ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}\ is given along
with simulated \ensuremath{r_\mathrm{G}}\ values for pure compositions
($\sigma(\ensuremath{\ln A})=0$) and for the maximum spread of masses
$0.5\,p\,-\,0.5\,\mathrm{Fe}$ ($\sigma(\ensuremath{\ln A})\simeq2$) for all three
interaction models.  For the data, a negative correlation
of $\ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}=-0.125\pm0.024\,(\mathrm{stat})$ is found.  For proton
simulations correlations are close to zero or positive in all
models. Pure compositions of heavier primaries show even more positive
correlations ($\ensuremath{r_\mathrm{G}}\geq0.09$) than for protons.  Hence, observations
cannot be reproduced by any pure composition of mass $A \ge 1$,
irrespective of the interaction model chosen.

In the proton dip model, even small admixtures of heavier nuclei, such
as a $15-20\%$ helium fraction at the sources, were shown to upset the
agreement of the pair-production dip of protons with the observed
flux~\cite{berezinsky_dip_prl2005,berezinsky_dip_ankle_2006,wibig_dip2005,allard_dip2005}. The
values of \ensuremath{r_\mathrm{G}}\ in simulations for a mixture at Earth of
$0.8\,p\,-\,0.2\,\mathrm{He}$ are added in
Table~\ref{tab:rsmilla065g}. They are essentially unaltered compared
to the pure proton case and equally inconsistent to the observed
correlation.

Further, the correlation is found to be non-negative
$\ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}\gtrsim0$ for all $p\,-\,\mathrm{He}$ mixtures. Thus, the
presence of primary nuclei heavier than helium $A>4$ is required to
explain the data.

We also checked the case of $\mathrm{O}\,-\,\mathrm{Fe}$ mixtures,
i.e. a complete absence of light primaries. A minimum value of
$\ensuremath{r_\mathrm{G}}\approx-0.04$ is reached for mixtures produced with EPOS-LHC{}
for fractions close to $0.5\,\mathrm{O}\,-\,0.5\,\mathrm{Fe}$. With
smaller significance, light primaries therefore appear required as
well to describe the observed correlation.

In Fig.~\ref{fig:xmaxs_vs_rmslna} the dependence of the simulated
correlation \ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)}\ on the spread $\sigma(\ensuremath{\ln A})$ is shown for
EPOS-LHC{} and QGSJetII-04 (results for Sibyll~2.1 are almost
identical to those of QGSJetII-04). A comparison with the data
indicates a significant degree of mixing of primary masses.
Specifically, $\sigma(\ensuremath{\ln A})\simeq 1.35 \pm 0.35$, with values of
$\sigma(\ensuremath{\ln A})\simeq 1.1-1.6$ being consistent with expectations from
all three models. The fact that differences between models are
moderate reflects the relative insensitivity of this analysis to
details of the hadronic interactions.

In Fig.~\ref{fig:energybins} the observed values of \ensuremath{r_\mathrm{G}}\ are
presented in four individual energy bins. From simulations, only a
minor change of \ensuremath{r_\mathrm{G}}\ with energy is expected for a constant
composition.  The data are consistent with a constant \ensuremath{r_\mathrm{G}}\ with
$\chi^2 / {\rm dof} \simeq 6.1/3$ ($P\simeq 11\%$).  Allowing for an
energy dependence, a straight-line fit gives a positive slope and
$\chi^2 / {\rm dof} \simeq 3.2/2$ ($P\simeq 20\%$).  More data are
needed to determine whether a trend towards larger \ensuremath{r_\mathrm{G}}\ (smaller
$\sigma(\ensuremath{\ln A})$) with energy can be confirmed.

\section{Uncertainties}

\subsection{Cross-checks}

Several cross-checks were performed.  In all cases, the conclusions
were found to be unchanged. The cross-checks included: (i) a division
of the data set in terms of time periods, FD telescopes or zenith
angle ranges; (ii) variations of the event selection criteria; (iii)
variations of the scaling functions when transforming to the reference
zenith angle and energy; (iv) adopting other methods to calculate the
correlation coefficient~\cite{Niven_corr2012}; and (v) studying the
effect of possible `outlier' events.  Regarding (iv), the smallest
difference between the data and pure compositions is found for
EPOS-LHC{} protons and it is $5.2\sigma_{\rm stat}$ for \ensuremath{r_\mathrm{G}}\
(c.f. Table~\ref{tab:rsmilla065g}), and $\ge7\sigma_{\rm stat}$ for
Pearson and Spearman correlation coefficients. As an example of the last point
(v), events were artificially removed from the data set so as to
increase the resulting value of \ensuremath{r_\mathrm{G}}\ as much as possible, i.e., to
bring it closer to the predictions for pure compositions.  Removing 20
events in this way increased the value of \ensuremath{r_\mathrm{G}}\ by $\sim0.01$ only.
For removals of sets of 100 arbitrary events, the maximum increase was
$\sim0.02$.  This robustness of \ensuremath{r_\mathrm{G}}\ against the influence of
individual events and even sub-groups of events was a main reason for
choosing it in this analysis.

\subsection{Systematic uncertainties}

Due to the analysis method and the choice of using a correlation
coefficient, systematics are expected to play only a minor role (for
the special case of hadronic uncertainties see below): separate
systematics in the observables \ensuremath{X_\mathrm{max}}\ and \ensuremath{S(1000)}\ have no effect on
\ensuremath{r_\mathrm{G}}, and the measurement of the two observables by independent
detectors avoids correlated systematics. Even a correlated systematic
leaves \ensuremath{r_\mathrm{G}}\ invariant as long as the ranks of the events are
unchanged.  Also if there were a more subtle issue affecting the ranks
of the observed events that might have gone unnoticed so far and could
require future correction (e.g.\ updated detector calibrations or
atmospheric parameters affecting only part of the data), we note that
this typically leads to a de-correlation of the uncorrected data set,
i.e., to an underestimation of the present value of $|\ensuremath{r_\mathrm{G}}|$.
Moreover, the main conclusion about the spread of primary masses
results from the {\it difference} between data and simulations which
remains robust for anything affecting the two in a similar way such
as, for instance, during reconstruction.

As an illustration, new data sets were created from the observed one
by artificially introducing energy and zenith angle dependent `biases'
in \ensuremath{X_\mathrm{max}^{*}}\ (up to 10~g\,cm${}^{-2}$) and \ensuremath{S^*_{38}}\ (up to 10\%) (it should be
stressed that these are arbitrary modifications).  The values of \ensuremath{r_\mathrm{G}}\
changed by $\lesssim0.01$, which is well below the statistical
uncertainty.  A value of 0.01 is taken as a conservative estimate of
the systematic uncertainty.

The systematics in energy affect the energy bin that the observed
spread is assigned to, which may be shifted by $\pm14\%$.  The
difference between simulation and data is left invariant since
\ensuremath{r_\mathrm{G}}\ is practically constant with energy for a given composition.

\subsection{Uncertainties in hadronic interactions}

Current model predictions do not necessarily bracket the correct
shower behaviour. In fact, measurements of the muon content from the
Auger Observatory indicate a possible underestimation of muons in
simulations~\cite{auger_icrc2013_farrar,has_muons2015}.  Therefore we
studied whether adjustments of hadronic parameters in simulations
could bring primary proton predictions into full agreement with the
data. The focus is on protons since heavier nuclei, due to the
superposition of several nucleons and the smaller energy per nucleon,
would require even larger adjustments.

Firstly, the (outdated) pre-LHC versions of EPOS and
QGSJetII were checked.
Despite the updates, values of \ensuremath{r_\mathrm{G}}\ differ by less
than $0.02$ from the current versions.

Secondly, an {\it ad-hoc} scaling of shower muons was applied in
simulations. Different approaches were tested: a constant increase of
the muon number; a zenith-angle dependent increase; and an
accompanying increase of the electromagnetic component as motivated
from shower universality~\cite{univer_rio_2013_talk}.  For an
effective muon scaling by a factor~$\simeq1.3$ as suggested by
data~\cite{auger_icrc2013_farrar,has_muons2015} the simulated
\ensuremath{r_\mathrm{G}}\ values were reduced by $\lesssim0.03$.  While possibly slightly
decreasing the difference with the data, such a shift is insufficient
to match expectations for pure compositions with data.

Thirdly, following the approach described
in~\cite{ulrich_hmulti_prd2011} and using CONEX~\cite{conex_2006} with
the 3D option for an approximate estimation of the ground signal, the
effect on \ensuremath{r_\mathrm{G}}\ was studied when modifying some key hadronic
parameters in the shower simulations.  Increasing separately the
cross-section, multiplicity, elasticity, and pion charge ratio by a
factor growing linearly with $\lg E$ from 1.0 at $10^{15}$~eV to 1.5
at $10^{19}$~eV compared to the nominal values ($f_{19}=1.5$,
cf.~\cite{ulrich_hmulti_prd2011}), \ensuremath{r_\mathrm{G}}\ turned out to be essentially
unaffected except for the modified cross-section where the value was
decreased by $\Delta\ensuremath{r_\mathrm{G}}\approx-0.06$.  Despite the large increase of
the cross-section assumed, this shift is still insufficient to explain
the observed correlation.  Moreover, $\Delta$\ensuremath{r_\mathrm{G}}\ shows in this case
a strong dependence on zenith angle ($\simeq 0.0$ for 0$-$45$^\circ$
and $\simeq -0.1$ for 45$-$60$^\circ$) making the predictions
inconsistent with the data.  It should be noted that any such
modification is additionally constrained by other data of the Auger
Observatory such as the observed
\ensuremath{X_\mathrm{max}}\ distributions~\cite{longXmax2014} and the proton-air
cross-section at $\lg(E/{\rm
  eV})\simeq18.25$~\cite{prl2012_cross,ulrich_icrc2015}.

\section{Discussion}

A negative correlation of $\ensuremath{r_\mathrm{G}(\ensuremath{X_\mathrm{max}^{*}},\,\smilla)} = -0.125\pm0.024\,({\rm stat})$
is observed.  Simulations for any pure composition with EPOS-LHC{},
QGSJetII-04 and Si\-byll~2.1 give $\ensuremath{r_\mathrm{G}}\ge 0.00$ and are in conflict
with the data. Equally, simulations for all proton\,--\,helium
mixtures yield $\ensuremath{r_\mathrm{G}}\ge 0.00$. The observations are naturally
explained by a mixed composition including nuclei heavier than helium
$A>4$, with a spread of masses $\sigma(\ensuremath{\ln A})\simeq 1.35 \pm 0.35$.

Increasing artificially the muon component or changing some key
hadronic parameters in shower simulations leaves the findings
essentially unchanged.  Thus, even with regard to hadronic interaction
uncertainties, a scenario of a pure composition is implausible as an
explanation of our observations.  Possible future attempts in that
direction may require fairly exotic solutions. In any case, they are
highly constrained by the observations presented here as well as by
previous Auger results.

The minor dependence of the mass spread determined in this analysis
from hadronic uncertainties allows one to test the self-consistency of
hadronic interaction models when deriving the composition from other
methods or observables
(e.g.~\cite{longXmax2014,longXmax_fits2014,augerMPD2014,auger_azasy2016}).
As mentioned in the beginning, when interpreting the
\ensuremath{X_\mathrm{max}}\ distributions alone in terms of fractions of
nuclei~\cite{longXmax_fits2014}, different results are found depending
on the model: using QGSJetII-04 or Sibyll~2.1, one infers values of
$\sigma(\ln A)\approx0.7$ and would expect $\ensuremath{r_\mathrm{G}}\approx0.08$.  This is
at odds with the observed correlation and indicates shortcomings in
these two models.  Using EPOS-LHC{}, values of $\sigma(\ln
A)\approx1.2$ and $\ensuremath{r_\mathrm{G}}\approx-0.094$ are obtained, in better
agreement with the observed correlation.

The conclusion that the mass composition at the ankle is not pure but
instead mixed has important consequences for theoretical source
models.  Proposals of almost pure compositions, such as the dip
scenario, are disfavoured as the sole explanation of ultrahigh-energy
cosmic rays.  Along with the previous Auger
results~\cite{longXmax_fits2014,PAO_Xmax_JCAP2013,longXmax2014}, our
findings indicate that various nuclei, including masses $A > 4$, are
accelerated to ultrahigh energies ($>10^{18.5}$~eV) and are able to
escape the source environment.

\input{acknowledgments.tex}

\section*{Acknowledgments}

\begin{sloppypar}
The successful installation, commissioning, and operation of the Pierre Auger Observatory would not have been possible without the strong commitment and effort from the technical and administrative staff in Malarg\"ue. We are very grateful to the following agencies and organizations for financial support:
\end{sloppypar}

\begin{sloppypar}
Comisi\'on Nacional de Energ\'\i{}a At\'omica, Agencia Nacional de Promoci\'on Cient\'\i{}fica y Tecnol\'ogica (ANPCyT), Consejo Nacional de Investigaciones Cient\'\i{}ficas y T\'ecnicas (CONICET), Gobierno de la Provincia de Mendoza, Municipalidad de Malarg\"ue, NDM Holdings and Valle Las Le\~nas, in gratitude for their continuing cooperation over land access, Argentina; the Australian Research Council; Conselho Nacional de Desenvolvimento Cient\'\i{}fico e Tecnol\'ogico (CNPq), Financiadora de Estudos e Projetos (FINEP), Funda\c{c}\~ao de Amparo \`a Pesquisa do Estado de Rio de Janeiro (FAPERJ), S\~ao Paulo Research Foundation (FAPESP) Grants No.\ 2010/07359-6 and No.\ 1999/05404-3, Minist\'erio de Ci\^encia e Tecnologia (MCT), Brazil; Grant No.\ MSMT CR LG15014, LO1305 and LM2015038 and the Czech Science Foundation Grant No.\ 14-17501S, Czech Republic; Centre de Calcul IN2P3/CNRS, Centre National de la Recherche Scientifique (CNRS), Conseil R\'egional Ile-de-France, D\'epartement Physique Nucl\'eaire et Corpusculaire (PNC-IN2P3/CNRS), D\'epartement Sciences de l'Univers (SDU-INSU/CNRS), Institut Lagrange de Paris (ILP) Grant No.\ LABEX ANR-10-LABX-63, within the Investissements d'Avenir Programme Grant No.\ ANR-11-IDEX-0004-02, France; Bundesministerium f\"ur Bildung und Forschung (BMBF), Deutsche Forschungsgemeinschaft (DFG), Finanzministerium Baden-W\"urttemberg, Helmholtz Alliance for Astroparticle Physics (HAP), Helmholtz-Gemeinschaft Deutscher Forschungszentren (HGF), Ministerium f\"ur Wissenschaft und Forschung, Nordrhein Westfalen, Ministerium f\"ur Wissenschaft, Forschung und Kunst, Baden-W\"urttemberg, Germany; Istituto Nazionale di Fisica Nucleare (INFN),Istituto Nazionale di Astrofisica (INAF), Ministero dell'Istruzione, dell'Universit\'a e della Ricerca (MIUR), Gran Sasso Center for Astroparticle Physics (CFA), CETEMPS Center of Excellence, Ministero degli Affari Esteri (MAE), Italy; Consejo Nacional de Ciencia y Tecnolog\'\i{}a (CONACYT) No.\ 167733, Mexico; Universidad Nacional Aut\'onoma de M\'exico (UNAM), PAPIIT DGAPA-UNAM, Mexico; Ministerie van Onderwijs, Cultuur en Wetenschap, Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO), Stichting voor Fundamenteel Onderzoek der Materie (FOM), Netherlands; National Centre for Research and Development, Grants No.\ ERA-NET-ASPERA/01/11 and No.\ ERA-NET-ASPERA/02/11, National Science Centre, Grants No.\ 2013/08/M/ST9/00322, No.\ 2013/08/M/ST9/00728 and No.\ HARMONIA 5 -- 2013/10/M/ST9/00062, Poland; Portuguese national funds and FEDER funds within Programa Operacional Factores de Competitividade through Funda\c{c}\~ao para a Ci\^encia e a Tecnologia (COMPETE), Portugal; Romanian Authority for Scientific Research ANCS, CNDI-UEFISCDI partnership projects Grants No.\ 20/2012 and No.194/2012 and PN 16 42 01 02; Slovenian Research Agency, Slovenia; Comunidad de Madrid, Fondo Europeo de Desarrollo Regional (FEDER) funds, Ministerio de Econom\'\i{}a y Competitividad, Xunta de Galicia, European Community 7th Framework Program, Grant No.\ FP7-PEOPLE-2012-IEF-328826, Spain; Science and Technology Facilities Council, United Kingdom; Department of Energy, Contracts No.\ DE-AC02-07CH11359, No.\ DE-FR02-04ER41300, No.\ DE-FG02-99ER41107 and No.\ DE-SC0011689, National Science Foundation, Grant No.\ 0450696, The Grainger Foundation, USA; NAFOSTED, Vietnam; Marie Curie-IRSES/EPLANET, European Particle Physics Latin American Network, European Union 7th Framework Program, Grant No.\ PIRSES-2009-GA-246806; and UNESCO.
\end{sloppypar}

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}

A hypergraph $\mathcal{H}$ is a pair $(V,\mathcal{E})$ where $V$ is the vertex set and $\mathcal{E}\subseteq 2^V$ is the edge set of $\mathcal{H}$.
A \emph{matching} in  a hypergraph $\mathcal{H}$ is a set of pairwise vertex-disjoint edges, and a \emph{transversal} is a set of vertices that intersects every edge.
The \emph{matching number} of a hypergraph $\mathcal{H}$, denoted by $\nu(\mathcal{H})$, is the maximum number of edges in a matching. The \emph{transversal number} of $\mathcal{H}$, denoted by $\tau(\mathcal{H})$, is the minimum size of a transversal of $\mathcal{H}$. We can also consider the linear relaxation of these two parameters: we define the \emph{fractional matching number} $\nu^*(\mathcal{H})$ and the \emph{fractional transversal number} $\tau^*(\mathcal{H})$ as follows.
\begin{align*}
\nu^*(\mathcal{H}) &= \max \sum_{e\in \mathcal{E}(\mathcal{H})} w_e \\
\mbox{given that } & \begin{cases}
\sum_{e \ni v}\limits w_e \le 1 &\quad \mbox{ for every vertex } v \mbox{ of }\mathcal{H}  \\
w_e \ge 0 &\quad \mbox{ for every edge } e \mbox{ of }\mathcal{H},
\end{cases}
\end{align*}
and the dual of this linear program is
\begin{align*}
\tau^*(\mathcal{H}) &= \min \sum_{v\in V(\mathcal{H})} w_v \\
\mbox{given that } & \begin{cases}
\sum_{v \in e}\limits w_v \ge 1 &\quad \mbox{ for every edge } e \mbox{ of } \mathcal{H} \\
w_v \ge 0 &\quad \mbox{ for every vertex } v \mbox{ of } \mathcal{H}.
\end{cases}
\end{align*}

By the strong duality theorem, $\nu(\mathcal{H})\le \nu^*(\mathcal{H})=\tau^*(\mathcal{H})\le \tau(\mathcal{H})$ for every hypergraph $\mathcal{H}$. Given a class $\mathcal{C}$ of hypergraphs, a classical problem in combinatorial optimization is to decide whether there exists a function $f$ such that $\tau(\mathcal{H})\le f(\nu(\mathcal{H}))$ for every $\mathcal{H}\in \mathcal{C}$. If this is the case the class $\mathcal{C}$ is sometimes said to have the \emph{Erd\H os-P\'osa property}. Classical examples include the family of all cycles of a graph~\cite{ErPo65} (i.e.\ given a graph $G=(V,E)$ we consider the hypergraph with vertex set $V$ whose edges are all the cycles of $G$), and the family of all directed cycles of a directed graph~\cite{RRST96}. A desirable property is the existence of a constant $c$ such that $\tau(\mathcal{H})\le c\cdot \tau^*(\mathcal{H})$ or $\nu^*(\mathcal{H})\le c\cdot \nu(\mathcal{H})$, or (even better)
$\tau(\mathcal{H})\le c\cdot \nu(\mathcal{H})$ for every $\mathcal{H}\in \mathcal{C}$. These properties are often useful in the design of approximation algorithms using a primal-dual approach (see for instance~\cite{GW97,FHRV07}).

\medskip

Given a graph $G=(V,E)$, an integer $r\ge 0$, and a vertex $v\in V$, we denote by $B_r(v)$ the \emph{ball of radius $r$} in $G$ centered in $v$, that is\[ B_r(v) \coloneqq \sset{u\in V(G)}{d_G(u,v)\le r},\] where $d_G(u,v)$ denotes the distance between $u$ and $v$ in $G$ (we will omit the subscript $G$ when the graph is clear from the context).
We say that a hypergraph $\mathcal{H}$ is a \emph{ball hypergraph} of $G$ if $\mathcal{H}$ has vertex set $V=V(G)$ and each edge of $\mathcal{H}$ is a ball $B_r(v)$ in $G$ for some integer $r$ and some vertex $v\in V$. If all the balls forming the edges of $\mathcal{H}$ have the same radius $r$, we say that $\mathcal{H}$ is an \emph{$r$-ball hypergraph} of $G$.

\medskip

Chepoi, Estellon, and Vax{{\`e}}s~\cite{CEV07} proved the existence of a universal constant $\rho$ such that for every $r\ge 0$ and every planar graph $G$ of diameter at most $2r$, the vertices of $G$ can be covered with at most $\rho$ balls of radius $r$. This result was extended to graphs embeddable on a fixed surface with a bounded number of apices in~\cite{BC14}.
Note that $G$ has diameter at most $2r$ if and only if there are no two disjoint balls of radius $r$ in $G$.
Also, a set of balls of radius $r$ in $G$ covers all of $V(G)$ if and only if their centers intersect all balls of radius $r$ in $G$.
Thus, these results state equivalently the existence of a universal constant $\rho$ such that for every $r\ge 0$ and every planar (or more generally bounded genus) graph $G$, if the $r$-ball hypergraph $\mathcal{H}$ consisting of all balls of radius $r$ satisfies $\nu(\mathcal{H})=1$, then $\tau(\mathcal{H})\le \rho$.
With this interpretation in mind, Chepoi, Estellon, and Vax{{\`e}}s~\cite{Cam10} conjectured the following generalization in 2007 (see also~\cite{Est07}).

\begin{conj}[Chepoi, Estellon, and Vax{{\`e}}s~\cite{Cam10}]
\label{conj:chep}
There exists a constant $c$ such that for every integer $r\geq 0$, every planar graph $G$, and every $r$-ball hypergraph $\mathcal{H}$ of $G$, we have $\tau(\mathcal{H})\le c\cdot\nu(\mathcal{H})$.
\end{conj}

If one considers all metric spaces obtained as standard graph-metrics of planar graphs, then Conjecture~\ref{conj:chep} states that these metric spaces satisfy the so-called {\em bounded covering-packing property}~\cite{CEN17}.
Recently, Chepoi, Estellon, and Naves~\cite{CEN17} showed that other metric spaces do have this property, including the important case of Busemann surfaces.
(Quoting~\cite{CEN17}, the latter are roughly the geodesic metric spaces homeomorphic to $\mathbb{R}^2$ in which the distance function is convex;
they generalize Euclidean spaces, hyperbolic spaces, Riemannian manifolds of global nonpositive sectional curvatures, and CAT(0) spaces.)

Going back to Conjecture~\ref{conj:chep}, let us emphasize that a key aspect of this conjecture is that the constant $c$ is independent of the radius $r$.
If $c$ is allowed to depend on $r$, then the conjecture is known to be true.
In fact, it holds more generally for all graph classes with bounded expansion, as shown by Dvo\v r\'ak~\cite{Dvo13}.

Some evidence for Conjecture~\ref{conj:chep} was given by Bousquet and Thomass\'e~\cite{BoTh}, who proved that it holds with a polynomial bound instead of a linear one.
More generally, they proved that for every integer $t \geq 1$, there exists a constant $c_t$ such that for every integer $r\geq 0$, every $K_t$-minor free graph $G$, and every $r$-ball hypergraph $\mathcal{H}$ of $G$, we have $\tau(\mathcal{H})\le c_t\cdot\nu(\mathcal{H})^{2t+1}$.

\medskip

The main result of this paper is that Conjecture~\ref{conj:chep} is true, and furthermore it is not necessary to assume that all the balls have the same radius.
\begin{thm}[Main result]
\label{thm:main}
For every integer $t\geq 1$, there is a constant $c_t$ such that $\tau(\mathcal{H})\le c_t \cdot \nu(\mathcal{H})$ for every $K_t$-minor-free graph $G$ and every ball hypergraph $\mathcal{H}$ of $G$.
\end{thm}

A set $S$ of vertices of a graph $G$ is \emph{$r$-dominating} if each vertex of $G$ is at distance at most $r$ from $S$, and \emph{$r$-independent} if any two vertices of $S$ are at distance at least $2r+1$ apart in $G$. Note that if we take  $\mathcal{H}$ to be the $r$-ball hypergraph consisting of all balls of radius $r$ in $G$, Theorem~\ref{thm:main} has the following interesting graph-theoretic interpretation: if $G$ is $K_t$-minor-free, then the minimum size of an $r$-dominating set is at most $c_t$ times the maximum size of an $r$-independent set in $G$.

\medskip

Our proof of Theorem~\ref{thm:main} follows a bootstrapping approach.
It relies on the existence of some function $f_t$ such that $\tau(\mathcal{H})\le f_t(\nu(\mathcal{H}))$, i.e.\ on the Erd\H os-P\'osa property of the ball hypergraphs of $K_t$-minor-free graphs, which is used in the proof when $\nu(\mathcal{H})$ is not `too big'.
However, showing this property was an open problem.
This was known for $r$-ball hypergraphs, by the result of Bousquet and Thomass\'e~\cite{BoTh}, but their proof method does not extend to the case of balls of arbitrary radii.
For this reason, as a first step towards proving Theorem~\ref{thm:main}, we prove Theorem~\ref{thm:nearlinear} below establishing said Erd\H os-P\'osa property.
We also note that, while the bounding function in Theorem~\ref{thm:nearlinear} is not optimal, it is a near linear bound of the form $\tau(\mathcal{H})\le c_t \cdot \nu(\mathcal{H}) \log \nu(\mathcal{H})$ where $c_t$ is a small explicit constant polynomial in $t$.
This is in contrast with the constant $c_t$ in our proof of Theorem~\ref{thm:main} which is large, exponential in $t$.
Thus, the bound in Theorem~\ref{thm:nearlinear} is better for small values of $\nu(\mathcal{H})$.
(We note that logarithms in this paper are natural, and the base of the natural logarithm is denoted by $\mathrm{e}$.)

\begin{thm}[Near linear bound]
\label{thm:nearlinear}
  Let $G$ be a graph with no $K_t$-minor and such that every minor of $G$ has average degree at most $d$. Then for every ball hypergraph $\mathcal{H}$ of $G$, $$\tau(\mathcal{H})\le 2\mathrm{e} (t-1) \, d \cdot\nu(\mathcal{H})\cdot\log(11\mathrm{e} \, d \cdot \nu(\mathcal{H})).$$ In particular, $\tau(\mathcal{H}) \le c t^2\sqrt{\log t} \cdot \nu(\mathcal{H})\cdot \log(t \, \cdot \nu(\mathcal{H}))$ for some absolute constant $c>0$, and   if $G$ is planar then $\tau(\mathcal{H}) \le 48\,\mathrm{e}  \cdot \nu(\mathcal{H})\cdot \log(66\,\mathrm{e} \, \cdot \nu(\mathcal{H}))$.
\end{thm}

The proof of Theorem~\ref{thm:nearlinear} uses known results on the VC-dimension of ball hypergraphs of $G$ when $G$ excludes a minor, together with classical bounds relating $\tau(\mathcal{H})$ and $\tau^*(\mathcal{H})$ when $\mathcal{H}$ has bounded VC-dimension, as well as the following theorem.

\begin{thm}[Fractional version]\label{thm:frac}
Let $G$ be a graph and let $d$ be the maximum average degree of a minor of $G$. Then for every ball hypergraph $\mathcal{H}$ of $G$, we have $\nu^*(\mathcal{H})\le \mathrm{e} \,d \cdot \nu(\mathcal{H})$. \\
In particular, if $G$ is planar then $\nu^*(\mathcal{H}) \le 6\mathrm{e}  \cdot \nu(\mathcal{H})$ and if $G$ has no $K_t$-minor then $\nu^*(\mathcal{H}) \le c \cdot t\sqrt{\log t} \cdot \nu(\mathcal{H})$, for some absolute constant $c>0$.
\end{thm}

We note that results on the VC-dimension of ball hypergraphs in graphs excluding a minor have also been  used recently to obtain improved algorithms for the computation of the diameter in sparse graphs~\cite{DHV20, LP19}.

\smallskip

The proofs of Theorems~\ref{thm:main}, \ref{thm:nearlinear}, and~\ref{thm:frac} are constructive, and can be transformed into efficient algorithms producing transversals (in the case of  Theorems~\ref{thm:main} and \ref{thm:nearlinear}) or matchings (in the case of Theorem~\ref{thm:frac}) of the desired size.

\smallskip

The paper is organized as follows.
Sections~\ref{sec:struct} and~\ref{sec:tech} are devoted to technical lemmas that will be used in our proofs.
Theorems~\ref{thm:nearlinear} and~\ref{thm:frac} are proved in Section~\ref{sec:frac}.
Theorem~\ref{thm:main} is proved in Section~\ref{sec:main}.
Finally, we conclude the paper in Section~\ref{sec:conclusion} with a construction suggesting that Theorem~\ref{thm:main} does not extend way beyond proper minor-closed classes.

\section{Hypergraphs, balls, and minors}\label{sec:struct}

We will need two technical lemmas, whose proofs are very similar to the proof of~\cite[Theorem 4]{BoTh} and~\cite[Proposition 1]{CEV07}. We start with Lemma~\ref{lem:minor1}, which will be used in the proofs of Theorem~\ref{thm:frac} and Theorem~\ref{thm:main}. We first need the following definitions.

We say that two balls $B_1$ and $B_2$ are \emph{comparable} if  $B_1 \subset B_2$ or $B_2 \subset B_1$ (where $\subset$ denotes the strict inclusion), and otherwise they
are \emph{incomparable}. Note in particular that if $B_1=B_2$ then $B_1$ and $B_2$ are incomparable. Consider two intersecting and incomparable balls $B_1=B_{r_1}(v_1)$ and $B_2=B_{r_2}(v_2)$ in a graph $G$, and let $d:=d_G(v_1,v_2)$. A \emph{median vertex} of $B_1$ and $B_2$ is any vertex $u$ lying on a shortest path between $v_1$ and $v_2$, at distance $\lfloor\frac{r_1-r_2+d}{2}\rfloor$ from $v_1$ and at distance $\lceil\frac{r_2-r_1+d}{2}\rceil$ from $v_2$, or symmetrically at distance $\lceil\frac{r_1-r_2+d}{2}\rceil$ from $v_1$ and at distance $\lfloor\frac{r_2-r_1+d}{2}\rfloor$ from $v_2$. Since $B_1$ and $B_2$ intersect, we have $r_1+r_2\ge d$  and since $B_1$ and $B_2$ are incomparable, we have $r_2\le r_1+d$ and  $r_1\le r_2+d$, and in particular $\lfloor\frac{r_1-r_2+d}{2}\rfloor\ge 0$ and $\lceil\frac{r_2-r_1+d}{2}\rceil\ge 0$ (so the distances above are well defined).
Moreover, $\lfloor\frac{r_1-r_2+d}{2}\rfloor = \lfloor\frac{2r_1-r_1-r_2+d}{2}\rfloor \le r_1$ and $\lceil\frac{r_2-r_1+d}{2}\rceil = \lceil\frac{2r_2-r_1-r_2+d}{2}\rceil \le r_2$, so any median vertex of $B_1$ and $B_2$ lies in $B_1\cap B_2$. Finally, note that by the definition of a median vertex $u$ of $B_1$ and $B_2$,

\begin{itemize}
\item for every $\{i,j\}=\{1,2\}$  we have $r_j-d(v_j,u)\le r_i-d(v_i,u)+1$, and
\item if  $v_1= v_2$ (which implies $B_1=B_2$ since the balls are incomparable), then $u=v_1=v_2$.
\end{itemize}

\medskip

\begin{lemma}~\label{lem:both1}
\label{lem:minor1}
Let $G$ be a graph, let $S=\{B_i = B_{r_i}(s_i)\}_{i\in [n]}$ be a set of  $n$ pairwise incomparable balls in $G$, with pairwise distinct centers, and let $E_S \subseteq \binom{S}{2}$ be a subset of pairs of intersecting balls $\{B_i,B_j\} \subseteq S$, each of which is associated with a median vertex $x_{\{i,j\}}$ of $B_i$ and $B_j$, and such that the only balls of $S$ containing $x_{\{i,j\}}$ are $B_i$ and $B_j$. Then the graph $H=(S,E_S)$ is a minor of $G$.
\end{lemma}

\begin{proof}
Let us fix a total ordering $\prec$ on the vertices of $G$. In the proof, all distances are in the graph $G$, so we write $d(u,v)$ instead of $d_G(u,v)$ for the sake of readability.
For every pair of balls $\{B_i,B_j\} \in E_S$, we write $x_{ij}$ or $x_{ji}$ instead of $x_{\{i,j\}}$, for the sake of readability ($x_{ij}$, $x_{ji}$, and $x_{\{i,j\}}$ all correspond to the same median vertex of $B_i$ and $B_j$). We also let $P(s_i, x_{ij})$ be a shortest path from $s_i$ to $x_{ij}$, and we assume that the sequence of vertices from $s_i$ to $x_{ij}$ on the path is minimum with respect to the lexicographic order induced by $\prec$ (among all shortest paths from $s_i$ to $x_{ij}$). By the assumptions, we know that $P_{ij} \coloneqq P(s_i, x_{ij})  \cup P(s_j, x_{ij}) $ is a shortest path from $s_i$ to $s_j$.

For every $i\in [n]$, we define
\[
\mathcal{T}_i \coloneqq \bigcup_{j\,:\,\{B_i,B_j\} \in E_S} P(s_i, x_{ij}) .\]

\paragraph{\bf Claim 1.} For every $i\in [n]$, $\mathcal{T}_i$ is a tree.

\medskip

\noindent Assume for the sake of contradiction that there is a cycle $C$ in $\mathcal{T}_i$.
Observe that, by construction, if $uv$ is an edge of $\mathcal{T}_i$ then $|d(s_i,u) - d(s_i,v)|=1$.
Let $y$ be a vertex of $C$ maximizing $d(s_i,y)$, and let $z_1,z_2$ denote its two neighbors in $C$.
Then $d(s_i,z_1)=d(s_i,z_2)=d(s_i,y)-1$, and there exist $j_1,j_2$ such that $z_1y$ is an edge of $P(s_i,x_{ij_1})$ and $z_2y$ is an edge of $P(s_i,x_{ij_2})$.
Let $P_1$ and $P_2$ be the subpaths from $s_i$ to $y$ of $P(s_i,x_{ij_1})$ and $P(s_i,x_{ij_2})$, respectively. Then $P_1$ and $P_2$ are two different paths from $s_i$ to $y$, and one of them is not minimum either in terms of length, or with respect to the lexicographic order induced by $\prec$. This contradicts the definition of $P(s_i,x_{ij_1})$ and $P(s_i,x_{ij_2})$.

\medskip

\paragraph{\bf Claim 2.}
For every two pairs of balls $\{B_i,B_k\},\{B_j,B_\ell\} \in E_S$ with $i\ne j$, if $P(s_i,x_{ik})$ and $P(s_j,x_{j\ell})$ intersect in some vertex $y$ such that $d(y,x_{ik}) \le d(y,x_{j\ell })$, then $j=k$ and $y=x_{ij}$.

\medskip

\noindent
Note that $d(s_j,x_{ik})\le d(s_j,y) + d(y,x_{ik}) \le d(s_j,y) + d(y,x_{j\ell }) = d(s_j,x_{j\ell}) $.
Since $x_{j\ell}$ is a median vertex of $B_j$ and $B_\ell$, we have $d(s_j,x_{j\ell}) \le  r_j$, which implies that $d(s_j,x_{ik})\le r_j$ and thus $x_{ik} \in B_j$.
By definition, $x_{ik}$ is only contained in the balls $B_i$ and $B_k$ of $S$ and thus $j=k$. If we also have $i=\ell$, then necessarily $y=x_{ij}$.

From now on, we assume that $i \neq \ell$.
Since $P_{ij} = P(s_i, x_{ij})  \cup P(s_j, x_{ij}) $ is a shortest path containing the vertex $y$, the $s_j$--$y$ section of that path (which contains $x_{ij}$) has the same length as the $s_j$--$y$ section of $P(s_j,x_{j\ell})$.
Replacing the latter section by the former, we obtain a shortest path from $s_j$ to $x_{j\ell}$ containing $x_{ij}$, which we denote $Q(s_j,x_{j\ell})$.
As a consequence,
\[
  d(x_{j\ell}, x_{ij})=d(x_{j\ell},s_j)-d(s_j,x_{ij})\le r_j-d(s_j,x_{ij})\le r_i-d(s_i,x_{ij})+1,
\]
where the last inequality follows from the definition of $x_{ij}$.
We now use the fact that $y$ appears on the path $P(s_i,x_{ij})$ and on the $x_{ij}$--$x_{j\ell}$ section of $Q(s_j,x_{j\ell})$, and obtain
\begin{align*}
d(s_i,x_{j\ell}) &\le d(s_i,y) + d(y,x_{j\ell}) = d(s_i,x_{ij}) + d(x_{ij},x_{j\ell}) - 2 d(y,x_{ij}) \le r_i + 1 - 2 d(y,x_{ij}).
\end{align*}
Since $x_{j\ell} \notin B_i$ by definition (and so $d(s_i,x_{j\ell})>r_i$), this implies that $y=x_{ij}$, as desired.

\medskip

This claim immediately implies that for every $i,j\in [n]$ with $i \neq j$, we have $V(\mathcal{T}_i) \cap V(\mathcal{T}_j)=\{x_{ij}\}$ if $\{B_i,B_j\} \in E_S$, and $V(\mathcal{T}_i) \cap V(\mathcal{T}_j)=\emptyset$ otherwise. Another consequence is that for every $\{B_i,B_j\} \in E_S$, the vertex $x_{ij}$ is a leaf in at least one of the two trees $\mathcal{T}_i$ and $\mathcal{T}_j$ (since otherwise there exist $k \neq j$ and $\ell \neq i$ such that $x_{ij} \in P(s_i,x_{ik})$ and $x_{ij} \in P(s_j,x_{j \ell})$, which readily contradicts Claim 2 above).

In the subgraph $\bigcup_{i\in [n]}\mathcal{T}_i$ of $G$, for each $i\in [n]$ we contract each edge of $\mathcal{T}_i$ except the ones incident to a leaf of $\mathcal{T}_i$. It follows from the paragraph above that the resulting graph is precisely a graph obtained from $H=(S,E_S)$ by subdividing each edge at most once, and thus $H$ is a minor of $G$.
\end{proof}

The next result has a very similar proof\footnote{Despite our best effort, we have not been able to prove the two results at once in a satisfactory way, i.e.\ with a proof that would be both readable and shorter than the concatenation of the two existing proofs.}, but the setting is slightly different. It will be used in the proof of Theorem~\ref{thm:main}.

\begin{lemma}
\label{lem:minor2}
Let $G$ be a graph and $S=\{B_i = B_{r_i}(s_i)\}_{i\in [n]}$ be a set of $n$ pairwise vertex-disjoint  balls in $G$, and let $E_S \subseteq \binom{S}{2}$ be a subset of pairs of balls $\{B_i,B_j\} \subseteq S$, each of which is associated with a ball $B_{\{i,j\}} \notin S$ of $G$ which intersects only $B_i$ and $B_j$ in $S$. Then the graph $H=(S,E_S)$ is a minor of $G$.
\end{lemma}

\begin{proof}
  Let us fix a total ordering $\prec$ on the vertices of $G$. As before, all distances are in the graph $G$, and we write $d(u,v)$ instead of $d_G(u,v)$. For every $\{B_i,B_j\} \in E_S$ we write $B_{ij}$ or $B_{ji}$ interchangeably for $B_{\{i,j\}}$, and we denote by $x_{ij}$ the center of the ball $B_{ij}$, and by $r_{ij}$ its radius ($x_{ij}=x_{ji}$ and $r_{ij}=r_{ji}$). We can assume that the centers $x_{ij}$ are chosen so that the radii $r_{ij}$ are minimal (among all balls of $G$ not in $S$ that intersect only $B_i$ and $B_j$ in $S$).

  We let $P(s_i,x_{ij})$ be the shortest path from $s_i$ to $x_{ij}$ which minimizes the sequence of vertices from $s_i$ to $x_{ij}$ with respect to the lexicographic ordering induced by $\prec$ (among all shortest paths from $s_i$ to $x_{ij}$). Observe that $P(s_i,x_{ij})$ and $P(s_j,x_{ij})$ only intersect in $x_{ij}$ (if not, we could replace $x_{ij}$ by a vertex that is closer to $s_i$ and $s_j$ and reduce the radius $r_{ij}$ accordingly -- the new ball $B_{ij}$ would still intersect $B_i$ and $B_j$, and no other ball of $S$, and this would contradict the minimality of $r_{ij}$). We may also assume that $r_i+r_{ij}-1\le d(s_i,x_{ij})\le r_i+r_{ij}$ (otherwise we could replace $x_{ij}$ by its neighbor on $P(s_j,x_{ij})$ and decrease $r_{ij}$ by 1).

For every $i\in [n]$, we define
\[
  \mathcal{T}_i \coloneqq \bigcup_{j\,:\,\{B_i,B_j\} \in E_S} P(s_i,x_{ij}).\]

\medskip

\paragraph{\bf Claim 1.} For every $i\in [n]$, $\mathcal{T}_i$ is a tree.

\smallskip

\noindent The proof is exactly the same as that of Claim 1 in the proof of Lemma~\ref{lem:minor1} (we do not repeat it here).

\medskip

On the path $P(s_i,x_{ij})$, we let $z_{i ,i j}$ be the vertex at distance $r_i$ from $s_i$ (and  since $x_{ij}=x_{ji}$ we use  $z_{i , ij}$ and $z_{i , ji}$ interchangeably).
As we assumed above that $r_i+r_{ij}-1\le d(s_i,x_{ij})\le r_i+r_{ij}$, we also have
$r_{ij}-1 \le  d(x_{ij},z_{i,i j})\le r_{ij}$.
In particular,  $ d(x_{ij},z_{j,ij})-1 \le  d(x_{ij},z_{i,i j})\le  d(x_{ij}, z_{j, ij})+1$.

\medskip

\paragraph{\bf Claim 2.} For every two pairs of balls $\{B_i,B_k\},\{B_j,B_\ell\} \in E_S$, with $i\ne j$, if $P(s_i,x_{ik})$ and $P(s_j,x_{j\ell})$ intersect in some vertex $y$ such that $d(y,z_{i ,i k}) \le d(y,z_{j,j \ell})$, then $i=\ell$ and $y=x_{ij}$.

\medskip

We first argue that $y$ appears after $z_{j ,j\ell}$ when traversing $P(s_j,x_{j\ell})$ from $s_j$ to $x_{j\ell}$. Indeed, otherwise we would have
\[ d(s_j,z_{i ,i k}) \le  d(s_j,y) + d(y,z_{i ,i k}) \le d(s_j,y) + d(y,z_{j ,j \ell}) = d(s_j,z_{j ,j \ell})= r_j,\]
which means that $B_i$ and $B_j$ intersect, contradicting the assumptions that $i\neq j$ and all balls in $S$ are vertex-disjoint.
So $y$ lies on the $z_{j,j\ell}$--$x_{j\ell}$ section of $P(s_j,x_{j\ell})$, and we infer that
\[ d(x_{j\ell},z_{i ,i k}) \le  d(x_{j\ell},y) + d(y,z_{i ,i k})\le d(x_{j\ell},y) + d(y,z_{j ,j \ell}) = d(x_{j\ell},z_{j ,j \ell})\le r_{j\ell}.
\]
It follows that the ball $B_{j\ell}$ intersects the ball $B_i$. By the assumption, this means that $i=\ell$, and thus $s_\ell=s_i$ and $z_{j ,j \ell}=z_{j , ij}$.
We now argue that $y$ lies in the $z_{i,ik}$--$x_{ik}$ section of $P(s_i, x_{ik})$.
Suppose for a contradiction that $y$ appears strictly before $z_{i,ik}$ when traversing $P(s_i,x_{ik})$ from $s_i$ to $x_{ik}$.
By definition of $z_{i,ik}$, it then follows that $d(s_i, y) \leq r_i-1$. On the other hand
$$d(s_j,y) = d(s_j,x_{ij})- d(y,x_{ij}) = d(s_j,z_{j,ij}) + d(z_{j,ij},x_{ij})-d(y,x_{ij}).$$

Note that $r_i+r_{ij}-1\le d(s_i,x_{ij})\le d(s_i,y)+d(y,x_{ij})\le r_i-1 +d(y,x_{ij})$, and thus $d(y,x_{ij})\ge r_{ij}\ge d(z_{i,ij},x_{ij})$. We obtain that  $d(z_{j,ij},x_{ij}) \leq d(z_{i,ij},x_{ij})+1 \leq d(y, x_{ij})+1$, and it follows that $d(s_j, y) \leq d(s_j,z_{j,ij})+1 = r_j+1$.
Hence $d(s_i,s_j) \leq d(s_i,y) + d(y, s_j) \leq r_i+r_j$, so $B_i$ and $B_j$ intersect, a contradiction.
We conclude that $y$ lies in the $z_{i,ik}$--$x_{ik}$ section of $P(s_i, x_{ik})$, and thus $d(x_{ik},y)+d(y, z_{i ,i k})= d(x_{ik}, z_{i,ik})$.

Recall that by the initial assumption of the claim, combined with $i=\ell$, we have $d(y,z_{i ,i k}) \le d(y,z_{j , ij})$. Assume first that $d(y,z_{i ,i k}) =d(y,z_{j , ij})$. Then
\[d(x_{ik},z_{j , ij})\le d(x_{ik},y)+d(y, z_{j , ij}) = d(x_{ik},y)+d(y, z_{i ,i k})\le r_{ik},
\]
which implies that $B_j$ intersects $B_{ik}$.
Thus $j=k$, $P(s_i,x_{ik})=P(s_i,x_{ij})$, and $P(s_j,x_{j\ell})=P(s_j,x_{ij})$. Since these two paths have only $x_{ij}$ in common, in this case we conclude that $y=x_{ij}$.
We can now assume that $d(y,z_{i ,i k}) \le d(y,z_{j , ij}) -1$. Recall that by definition of $x_{ij}$, we have $d(x_{ij},z_{i ,i j})\ge d(x_{ij},z_{j , ij})-1$, which implies that
\[
d(y,z_{i ,i k})+d(y,x_{ij})\le d(y,z_{j , ij})-1+d(y,x_{ij})= d(z_{j , ij},x_{ij})-1\le d(z_{i , ij},x_{ij}).
\]

Since $z_{i,ik}$ and $z_{i,ij}$ are both at distance $r_i$ from $s_i$ and $P(s_i,x_{ij})$ is a shortest path from $s_i$ to $x_{ij}$, it follows that the concatenation of the $s_i$--$y$ section of $P(s_i,x_{ik})$ and the $y$--$x_{ij}$ section of $P(s_j,x_{ij})$ is a shortest path from $s_i$ to $x_{ij}$ (containing $y$). As $y$ is also on a shortest path from $s_j$ to $x_{ij}$, if we had $d(y,x_{ij})>0$, then we could replace $x_{ij}$ by $y$ and reduce $r_{ij}$ to $r_{ij}-d(y,x_{ij})$ ($B_{ij}$ would still intersect $B_i$ and $B_j$ and only these balls of $S$), which would contradict the minimality of $r_{ij}$. It follows that $y=x_{ij}$, as desired.

\medskip

As in the proof of Lemma~\ref{lem:minor1}, the claim implies that for $i \neq j\in [n]$, $\mathcal{T}_i \cap \mathcal{T}_j=\{x_{ij}\}$ if $\{B_i,B_j\} \in E_S$, and otherwise the trees $\mathcal{T}_i$ and $\mathcal{T}_j$ are vertex-disjoint. Another direct consequence is that for every $\{B_i,B_j\}\in E_S$, the vertex $x_{ij}$ is a leaf in at least one of the two trees $\mathcal{T}_i$ and $\mathcal{T}_j$. As before, we can contract the edges of each tree $\mathcal{T}_i$ not incident to a leaf of $\mathcal{T}_i$, and the resulting graph is precisely a graph obtained from $H=(S,E_S)$ by subdividing each edge at most once, and thus $H$ is a minor of $G$.
\end{proof}

\section{Hypergraphs and density}\label{sec:tech}

A \emph{partial hypergraph} of $\mathcal{H}$ is a hypergraph obtained from $\mathcal{H}$ by removing a (possibly empty) subset of the edges. In addition to hypergraphs, it will also be convenient to consider \emph{multi-hypergraphs}, i.e.\ hypergraphs $\mathcal{H}=(V,\mathcal{E})$ where $\mathcal{E}$ is a \emph{multiset} of edges.
The \emph{rank} of a hypergraph or multi-hypergraph $\mathcal{H}$ is the maximum cardinality of an edge of $\mathcal{H}$.

\medskip

We start with a useful tool, inspired by~\cite{FP10} (see also~\cite{CEM16}), itself inspired by the Crossing lemma.
Given a graph $G=(V,E)$, we denote by $\mathrm{ad}(G)$ the average degree of $G$, that is $\mathrm{ad}(G)=2|E|/|V|$.

\begin{lemma}\label{lem:hredu}
  Let $\mathcal{H}=(V,\mathcal{E})$ be a multi-hypergraph of rank at most $k\ge 2$
on $n$ vertices, and
let $E\subseteq {V\choose 2}$ be a set of pairs of vertices $\{u,v\}$
of $V$ such that there exists an edge $e_{uv}$ of $\mathcal{H}$ containing $u$
and $v$. (Note that we allow that $e_{uv}=e_{xy}$ for two different
pairs $\{u,v\}$ and $\{x,y\}$.) Then the graph $(V,E)$ contains a subgraph $H$
such that $\mathrm{ad}(H)\ge \tfrac{2|E|}{n\mathrm{e} k}$ and for every edge
$uv$ of $H$, the corresponding edge $e_{uv}$ of $\mathcal{H}$ contains no
vertex from $V(H)-\{u,v\}$.
\end{lemma}

\begin{proof}
Let $\mathbf{H}$ be the (random) graph  obtained by selecting each vertex of $\mathcal{H}$ independently with probability $1/k$, and keeping a single edge (of cardinality 2) between $u$ and $v$ whenever the only selected vertices of $e_{uv}$ are $u$ and $v$. Then we have
\begin{align*}
\esp{|V(\mathbf{H})|} &= \frac{n}{k}, \quad \et \\
\esp{|E(\mathbf{H})|} &\ge |E|\cdot \frac{1}{k^2}\pth{1-\frac{1}{k}}^{k-2} > \frac{|E|}{\mathrm{e} k^2},
\end{align*}
since $k\ge 2$. It follows that $\esp{2|E(\mathbf{H})|-\frac{2|E|}{n\mathrm{e} k}|V(\mathbf{H})|}> 0$. In particular, there exists a subgraph $H$ of $(V, E)$ such that $\mathrm{ad}(H)\ge \tfrac{2|E|}{n\mathrm{e} k}$ and for every edge $uv$ of $H$, the edge $e_{uv}$ of $\mathcal{H}$ contains no
vertex from $V(H)-\{u,v\}$, as desired.
\end{proof}

The proof actually gives a randomized algorithm producing the graph $H$. This algorithm can easily be derandomized using the method of conditional expectations, giving a deterministic algorithm running in time $O(|E|+n)$.

\medskip

Given a hypergraph $\mathcal{H}$ and  a matching $\mathcal{B}$  in $\mathcal{H}$, we define the \emph{packing-hypergraph} $\mathcal{P}(\mathcal{H},\mathcal{B})$ as the hypergraph with vertex set $\mathcal{B}$, in which a subset $\mathcal{B}'\subseteq \mathcal{B}$
is an edge if some edge of $\mathcal{H}$  intersects all the edges in $\mathcal{B}'$ and no other edge of $\mathcal{B}$.

\begin{lemma}
  \label{lem:bounded-hyper-edges}
Let $G$ be a graph such that each minor of $G$ has average degree at most $d$, let $\mathcal{H}$ be a ball hypergraph of $G$, and let $\mathcal{B}$ be a matching of size $n$ in $\mathcal{H}$. For every integer $k\ge 2$, the number of edges of cardinality at most $k$ in the packing-hypergraph $\mathcal{P}(\mathcal{H},\mathcal{B})$ is at most
\[ \pth{1+d\mathrm{e} k}^{k-1}\cdot n.\]
\end{lemma}

\begin{proof}
  Let $\mathcal{P}'$ be the partial hypergraph of $\mathcal{P}(\mathcal{H},\mathcal{B})$ induced by the edges of cardinality at most $k$. Let $H$ be the graph with vertex set $\mathcal{B}$ in which two distinct vertices are adjacent if they are contained in an edge of $\mathcal{P}'$ (i.e.\ an edge of $\mathcal{P}(\mathcal{H},\mathcal{B})$ of cardinality at most $k$). Let $m$ be the number of edges of $H$.  Applying Lemma~\ref{lem:hredu} to $\mathcal{P}'$, we obtain a subgraph $H'$ of $H$ of average degree at least $\tfrac{2m}{n\mathrm{e} k}$, and such that for any pair $x,y$ of adjacent vertices in $H'$, there is an edge of $\mathcal{P}'$ that contains $x$ and $y$ and no other vertex of $H'$. The vertices of $H'$ correspond to a subset $S$ of pairwise disjoint balls of $G$ (since $\mathcal{B}$ is a matching), and each edge of $H'$ corresponds to a ball of $G$ that intersects some pair of balls of $S$ (and does not intersect any other ball of $S$).

  By Lemma~\ref{lem:minor2}, $H'$ is a minor of $G$, so in particular $\tfrac{2m}{n\mathrm{e} k}\le \mathrm{ad}(H')\le d$, and hence $m \le \frac12 \, d\mathrm{e} k n$. It follows that $H$ contains a vertex of degree at most $d\mathrm{e} k$, and the same is true for every induced subgraph of $H$ (since we can replace $\mathcal{B}$ in the proof by any subset of $\mathcal{B}$). As a consequence, $H$ is $\lfloor d\mathrm{e} k \rfloor$-degenerate. It is a folklore result that $\ell$-degenerate graphs on $n$ vertices have at most $\binom{\ell}{t-1} n$ cliques of size $t$ (see for instance~\cite[Lemma 18]{Woo16}, where the proof gives a linear time algorithm to enumerate all the cliques of size $t$ when $t$ and $\ell$ are fixed),  and hence there are at most
 \[ n\cdot \sum_{i=1}^k \binom{\lfloor d\mathrm{e} k \rfloor}{i-1} \le n \cdot \pth{1+d\mathrm{e} k}^{k-1}\]
cliques of size at most $k$ in $H$, which is an upper bound on the number of edges of cardinality at most $k$ in $\mathcal{P}(\mathcal{H},\mathcal{B})$.
\end{proof}

Note that the proof gives an $O(n)$ time algorithm enumerating all edges of cardinality at most $k$ in the packing-hypergraph $\mathcal{P}(\mathcal{H},\mathcal{B})$, when $k$ and $d$ are fixed (note that since $H$ is $\lfloor d\mathrm{e} k \rfloor$-degenerate, it contains a linear number of edges, and thus the application of  Lemma~\ref{lem:hredu} takes time $O(n)$).

\section{Fractional packings of balls}\label{sec:frac}

We now prove Theorem~\ref{thm:frac}. The proof is inspired by ideas from~\cite{ReSh96}.

\medskip

{\noindent \emph{Proof of Theorem~\ref{thm:frac}.}
Let $\mathcal{H}$ be a ball hypergraph of $G$.  Since $\nu^*(\mathcal{H})$ is attained and is a rational number (recall that $\nu^*(\mathcal{H})$ is the solution of a linear program with integer coefficients), there exists a multiset $\mathcal{B}$ of $p$ balls of $G$, such that every vertex $v\in V(G)$ is contained in at most $q$ balls of $\mathcal{B}$, and $\nu^*(\mathcal{H})=p/q$ (see for instance~\cite{ReSh96}, where the same argument is applied to fractional cycle packings). We may assume that $q$ is arbitrarily large (by taking $k$ copies of each ball of $\mathcal{B}$, with multiplicities, for some arbitrarily large constant $k$), so in particular we may assume that $q\ge 2$. We may also assume that $G$ contains at least one edge (i.e.\ $d\ge 1$), otherwise the result clearly holds.
Enumerate all the balls in $\mathcal{B}$ as $B_1, B_2, \dots, B_p$ (and recall that since $\mathcal{B}$ is a multiset, some balls $B_i$ and $B_j$ might coincide).
We may assume that there is no pair of balls $B_i,B_j$ such that $B_i\subset B_j$ (otherwise we can replace $B_j$ by $B_i$ in $\mathcal{B}$, and we still have a fractional matching). It follows that the balls of $\mathcal{B}$ are pairwise incomparable (as defined at the beginning of Section~\ref{sec:struct}). For any two intersecting balls $B_i$ and $B_j$ we define $x_{ij}$ as a median vertex of $B_i$ and $B_j$ (also defined at the beginning of Section~\ref{sec:struct}). Recall that it implies in particular that whenever $B_i$ and $B_j$ intersect,  $x_{ij}\in B_i\cap B_j$, and if $B_i$ and $B_j$ coincide then $x_{ij}$ is the center of $B_i$ and $B_j$.

We let $\mathcal{G}$ be the intersection graph of the balls in $\mathcal{B}$, that is $V(\mathcal{G})=\mathcal{B}$ and two vertices $B_i,B_j\in \mathcal{B}=V(\mathcal{G})$ with $i\neq j$ are adjacent in $\mathcal{G}$ if and only if ${B_i\cap B_j \neq \varnothing}$.
(In particular, there is an edge linking $B_i$ and $B_j$ when $B_i$ and $B_j$ are two copies of the same ball.)
Let $m$ be the number of edges of $\mathcal{G}$.
Let $\mathcal{B}^*$ denote the multi-hypergraph with vertex set $\mathcal{B}$, where for every vertex of $G$ of the form $x_{ij}$ there is a corresponding edge consisting of the balls in $\mathcal{B}$ that contain $x_{ij}$.
Note that two distinct such vertices could possibly define the same edge, which is why edges in $\mathcal{B}^*$ could have multiplicities greater than $1$.
The multi-hypergraph $\mathcal{B}^*$ has rank at most $q$ and contains $p$ vertices. Note moreover that the number of pairs of vertices $B_i,B_j$ of $\mathcal{B}^*$ with $i\neq j$ such that there exists an edge of $\mathcal{B}^*$ containing $B_i$ and $B_j$ is precisely $m$.

By Lemma~\ref{lem:hredu} applied to the multi-hypergraph $\mathcal{B}^*$, we obtain a graph $H=(S,E_S)$ satisfying the following properties:
\begin{itemize}
\item $S\subseteq \mathcal{B}$;
\item for each edge $\{B_i,B_j\}\in E_S$, $x_{ij}$ is contained in $B_i$ and $B_j$ but in no other ball from $S$, and
\item $\mathrm{ad}(H)\ge \tfrac{2m}{p\mathrm{e} q}$.
\end{itemize}

We would like to apply Lemma~\ref{lem:minor1} to $H$ but this is not immediately possible, since some balls of $S$ might coincide (recall that $\mathcal{B}$ is a multiset), and therefore the centers of the balls of $S$ might not be pairwise distinct. However, observe that if two balls of $S$ coincide, then by definition the two corresponding vertices of $H$ have degree either 0 or 1 in $H$ (and in the latter case the two vertices are adjacent in $H$). Indeed, if two balls $B_i,B_j$ of $S$ coincide and $B_i$ is adjacent to $B_k$ in $H$ with $k \neq j$, then the only balls of $S$ containing $x_{ik}$ are $B_i$ and $B_k$, contradicting the fact that $x_{ik}$ is also in $B_j$.

Let $S_1 \subseteq S$ be the subset of balls of $S$ having multiplicity $1$ in $S$. Since no ball of $\mathcal{B}$ is a strict subset of another ball of $\mathcal{B}$, the centers of the balls of $S_1$ are pairwise distinct. As a consequence of the previous paragraph, if we consider the subgraph $H_1$ of $H$ induced by $S_1 $, then $\mathrm{ad}(H)\le \max(1,\mathrm{ad}(H_1))$.

By Lemma~\ref{lem:minor1} applied to the set of balls $S_1$ in $G$, we obtain that $H_1$ is a minor of $G$ and
thus $\mathrm{ad}(H_1)\le d$. It follows that  $\tfrac{2m}{p\mathrm{e} q}\le \mathrm{ad}(H)\le \max(1, d)\le d$ (since $d\ge 1$). This implies that the average degree $2m/p$ of $\mathcal{G}$ is at most
$\mathrm{e} \,dq$. By the Caro-Wei inequality~\cite{Caro79,Wei81} (or Tur\'an's theorem~\cite{Turan41}), it follows that $\mathcal{G}$ contains an independent set of size at least $$\frac{|V(\mathcal{G})|}{\mathrm{ad}(\mathcal{G})+1}\ge \frac{p}{\mathrm{e} \,dq+1}=\frac{\nu^*(\mathcal{H})}{\mathrm{e} \,d+1/q}.$$ An independent set in $\mathcal{G}$ is precisely a matching in $\mathcal{H}$, and thus $\nu(\mathcal{H})\ge \tfrac1{\mathrm{e}\,d+1/q}\cdot\nu^*(\mathcal{H})$ and $\nu^*(\mathcal{H})\le (\mathrm{e}\,d+1/q)\cdot\nu(\mathcal{H})$. Since we can assume that $q$ is arbitrarily large, it follows that $\nu^*(\mathcal{H})\le \mathrm{e}\,d\cdot\nu(\mathcal{H})$, as desired.

\medskip

The rest of the result follows from well known results on the average degree of graphs. On the one hand, an easy consequence of Euler's formula is that planar graphs have average degree at most 6. On the other hand, it was proved by Kostochka~\cite{Kos84} and Thomason~\cite{Tho84} that  every $K_{t}$-minor-free graph has average degree $O(t\sqrt{\log t})$. \hfill $\Box$

\bigskip

The linear program for $\nu^*$ has coefficients in $\{0,1\}$, and can thus be solved in time $O(n^3)$, since we can assume that the balls have pairwise distinct centers (and so the number of variables and inequalities is linear in the number of vertices). The associated rational coefficients $w_e$ can thus be found in time $O(n^3)$. It is then convenient to define $w_e'$ as the largest $\tfrac{\ell}{n}\le w_e$ with $\ell\in \mathbb{N}$. Note that the coefficients $(w_e')$ still satisfy the inequalities of the linear program for $\nu^*$, and their sum is at least $\nu^*-1$ since we can assume that there are at most $n$ balls (since there centers are pairwise distinct).  There is a small loss on the multiplicative constant (compared to the statement of Theorem~\ref{thm:frac}), but we can now assume that in the proof we have $q\le n$ and thus $p\le n^2$ and $m=O(n^3)$. It follows that the application of  Lemma~\ref{lem:hredu} can be done in time $O(m)=O(n^3)$, and the construction of a stable set of suitable size in $\mathcal{G}$ can also be done in time $O(m)=O(n^3)$. Therefore, the proof of Theorem~\ref{thm:frac} gives an $O(n^3)$ time algorithm constructing a matching of size $\Omega(\nu^*(\mathcal{H}))$ in $\mathcal{H}$.

\medskip

The \emph{VC-dimension} of a hypergraph $\mathcal{H}$ is the cardinality of a largest subset $X$ of vertices such that for every $X'\subseteq X$, there is an edge $e$ in $\mathcal{H}$ such that $e\cap X=X'$. Bousquet and Thomassé~\cite{BoTh} proved the following result.

\begin{thm}\label{thm:both}
  If $G$ has no $K_t$-minor, then every ball hypergraph $\mathcal{H}$ of $G$ has VC-dimension at most $t-1$.
\end{thm}

A classical result is that for hypergraphs of bounded VC-dimension, $\tau=O(\tau^*\log \tau^*)$. We will use the following precise bound of Ding, Seymour, and Winkler~\cite{DSW94}.

\begin{thm}\label{thm:dsw}
If a hypergraph $\mathcal{H}$ has VC-dimension at most $\delta$, then \[\tau(\mathcal{H})\le 2 \delta \tau^*(\mathcal{H}) \log(  11\tau^*(\mathcal{H})).\]
\end{thm}

Combining Theorems~\ref{thm:frac}, \ref{thm:both}, and \ref{thm:dsw}, and using that $\nu^*(\mathcal{H})=\tau^*(\mathcal{H})$, we obtain Theorem~\ref{thm:nearlinear} as a direct consequence.

\medskip

As before, the linear program for $\tau^*$ has coefficients in $\{0,1\}$, and can thus be solved in time $O(n^3)$, since we can assume that the balls have pairwise distinct centers (and so the number of variables and inequalities is linear in the number of vertices). The associated rational coefficients $w_v$ can thus be found in time $O(n^3)$. Using algorithmic versions of Theorem~\ref{thm:dsw} (see~\cite{HW87,Mat95}) and the coefficients $(w_v)$, a transversal of $\mathcal{H}$ of size $O(\tau^* \log \tau^*)=O(\nu \log \nu)$ can be found by a randomized algorithm sampling $O(\tau^* \log \tau^*)$ vertices according to the distribution given by $(w_v)$, or a deterministic algorithm running in time $O(n ({\tau^*}^2 \log \tau^*)^t)$. So the overall complexity of obtaining a transversal of the desired size is $O(n^3)$ (randomized) and $O(n^3+n (\tau^* \log \tau^*)^t)$ (deterministic). In the remainder of the paper, the result will be used when $\tau^*$ is a fixed constant, in which case the complexity of the deterministic algorithm is also $O(n^3)$.

\section{Linear bound}\label{sec:main}

In this section we prove Theorem~\ref{thm:main}.
Recall that by Theorem~\ref{thm:nearlinear}, there is a (monotone) function $f_t$ such that $\tau(\mathcal{H})\le f_t(\nu(\mathcal{H}))$ for every ball hypergraph $\mathcal{H}$ of a $K_t$-minor-free graph. In the proof, we write $d_t$ for the supremum of the average degree of $G$ taken over all graphs $G$ excluding $K_t$ as a minor. Recall that $d_t=O(t\sqrt{\log t})$~\cite{Kos84,Tho84}.

\medskip

Let $t\ge 1$ be an integer and let $c_t:=2\cdot (1+\tfrac32 d_t^2\mathrm{e} )^{3d_t/2}\cdot f_t(\tfrac32 d_t)$. We will prove that every ball hypergraph $\mathcal{H}$ of a $K_t$-minor-free graph satisfies $\tau(\mathcal{H})\le c_t \cdot \nu(\mathcal{H})$.

\medskip

{\noindent \emph{Proof of Theorem~\ref{thm:main}.}
We prove the result by induction on $k\coloneqq \nu(\mathcal{H})$. The result clearly holds if $k=0$ so we may assume that $k\ge 1$. If $k\le \tfrac32 d_t$ then by the definition of $f_t$ we have $\tau(\mathcal{H})\le f_t(\tfrac32 d_t)\le c_t \le c_t \cdot k$, as desired.

Assume now that $k\ge \tfrac32 d_t$ and for every ball hypergraph $\mathcal{H}'$ of a $K_t$-minor-free graph with $\nu(\mathcal{H}')<k$, we have $\tau(\mathcal{H}')\le c_t \cdot \nu(\mathcal{H}')$. Let $G$ be a $K_t$-minor-free graph and $\mathcal{H}$ be a ball hypergraph of $G$ with  $\nu(\mathcal{H})=k$. Our goal is to show that $\tau(\mathcal{H})\le c_t \cdot k$. Note that we can assume that $\mathcal{H}$ is \emph{minimal}, in the sense that no edge of $\mathcal{H}$ is contained in another edge of $\mathcal{H}$ (otherwise we can remove the larger of the two from $\mathcal{H}$, this does not change the matching number nor the transversal number).

\medskip

Consider a maximum matching $\mathcal{B}$ (of cardinality $k$) in $\mathcal{H}$. Let $\mathcal{E}_1$ be the set consisting of all the edges of $\mathcal{H}$ that intersect at most $\tfrac32 d_t$ edges of $\mathcal{B}$. Note that each edge of $\mathcal{B}$ lies in $\mathcal{E}_1$, and therefore $\mathcal{E}_1$ is non-empty. By Lemma~\ref{lem:bounded-hyper-edges}, the packing-hypergraph $\mathcal{P}(\mathcal{H},\mathcal{B})$ contains at most $(1+\tfrac32 d_t^2\mathrm{e} )^{3d_t/2}\cdot k$ edges of cardinality at most $\tfrac32 d_t$. For each such edge $e$ of $\mathcal{P}(\mathcal{H},\mathcal{B})$, consider the corresponding subset $\mathcal{B}_e$ of at most $\tfrac32 d_t$ edges of $\mathcal{B}$, and the subset $\mathcal{E}_e$ of edges of $\mathcal{H}$ that intersect each ball of $\mathcal{B}_e$, and no other ball of $\mathcal{B}$. Denoting by $\mathcal{H}_e$ the  partial hypergraph of $\mathcal{H}$ with edge set $\mathcal{E}_e$, observe that by the maximality of the matching $\mathcal{B}$ we have $\nu(\mathcal{H}_e)\le \tfrac32 d_t$  (since in $\mathcal{B}$, replacing the edges of $\mathcal{B}_e$ by a matching of $\mathcal{E}_e$ again gives a matching of $\mathcal{H}$). It follows that $\tau(\mathcal{H}_e)\le f(\tfrac32 d_t)$. And thus, if we denote by $\mathcal{H}_1$ the  partial hypergraph of $\mathcal{H}$ with edge set $\mathcal{E}_1$, we have
$$\tau(\mathcal{H}_1)\le (1+\tfrac32 d_t^2\mathrm{e} )^{3d_t/2}\cdot f(\tfrac32 d_t)\cdot  k = \tfrac12 c_t\cdot k.$$

Consider now the subset $\mathcal{E}_2$ consisting of all the edges of $\mathcal{H}$ that intersect more than $\tfrac32 d_t$ edges of $\mathcal{B}$, and let $\mathcal{H}_2$ be the  partial hypergraph of $\mathcal{H}$ with edge set $\mathcal{E}_2$. Note that $\mathcal{E}_1$ and $\mathcal{E}_2$ partition the edge set of $\mathcal{H}$ and thus $\tau(\mathcal{H})\le \tau(\mathcal{H}_1)+\tau(\mathcal{H}_2)$. Let $\mathcal{B}_2$ be a maximum matching in $\mathcal{H}_2$, and let $\ell=\nu(\mathcal{H}_2)=|\mathcal{B}_2|$.
Let $H$ be the (bipartite) intersection graph of the edges of  $\mathcal{B}\cup \mathcal{B}_2$, i.e.\ each vertex of $H$ corresponds to an edge of $\mathcal{B}\cup \mathcal{B}_2$, and two vertices are adjacent if the corresponding edges intersect. (The graph is bipartite because $\mathcal{B}$ and $\mathcal{B}_2$ are matchings.)

Note that since $H$ is bipartite, for every two distinct edges $\{B,B'\}$ and $\{C,C'\}$ of $H$, the sets $B\cap B'$ and $C\cap C'$ are disjoint. Moreover, no ball of $\mathcal{B}\cup \mathcal{B}_2$ is a subset of another ball of $\mathcal{B}\cup \mathcal{B}_2$, and thus the balls of $\mathcal{B}\cup \mathcal{B}_2$
are pairwise incomparable (as defined at the beginning of Section~\ref{sec:struct}).
So, enumerating the balls in $\mathcal{B}\cup \mathcal{B}_2$ as $B_1, B_2, \dots, B_n$, we can choose, for each edge $\{B_i,B_j\}$ of $H$, a median vertex $x_{ij}$ of $B_i$ and $B_j$ (also defined at the beginning of Section~\ref{sec:struct}). Recall that $x_{ij}\in B_i\cap B_j$, and thus it follows from the property above that the only balls of $\mathcal{B}\cup \mathcal{B}_2$ containing $x_{ij}$ are $B_i$ and $B_j$.
By Lemma~\ref{lem:minor1}, $H$ is a minor of $G$ and thus has average degree at most $d_t$. On the other hand, the vertices of $H$ corresponding to the edges of $\mathcal{B}_2$ have degree at least $\tfrac32 d_t$ in $H$, and thus
$$\tfrac32 d_t \cdot \ell\le \tfrac12 \,\mathrm{ad}(H)(k+\ell)\le \tfrac12 d_t \cdot (k+\ell),$$ where the central term counts the number of edges of $H$. It follows that $\nu(\mathcal{H}_2)=\ell\le \tfrac{k}2$, and thus by the induction hypothesis we have $\tau(\mathcal{H}_2)\le c_t\cdot \nu(\mathcal{H}_2)\le c_t \cdot \tfrac{k}2$. As a consequence, $$\tau(\mathcal{H})\le \tau(\mathcal{H}_1)+\tau(\mathcal{H}_2)\le \tfrac12c_t\cdot k+  c_t \cdot \tfrac{k}2 = c_t \cdot k,$$ which concludes the proof of Theorem~\ref{thm:main}.
\hfill $\Box$

\bigskip

The first part of the proof of Theorem~\ref{thm:main} uses Theorem~\ref{thm:nearlinear} when $\nu$ (and thus $\tau^*$, by Theorem~\ref{thm:frac}) is bounded by a function of the constant $t$, and in this case, by the discussion after the proof of Theorem~\ref{thm:nearlinear}, a transversal of the desired size can be found deterministically in time $O(n^3)$.

The second part of the proof of Theorem~\ref{thm:main} can be made constructive by performing the following small modification. We observe that we have not quite used the fact that $\mathcal{B}$ is a \emph{maximum} matching of $\mathcal{H}$, simply that it has the property that, for any edge $e$ in the packing-hypergraph $\mathcal{P}(\mathcal{H}, \mathcal{B})$ of cardinality at most $\tfrac32d_t$, the matching number of $\mathcal{H}_e$ is bounded.
As we have explained after Lemma~\ref{lem:bounded-hyper-edges}, such edges can be enumerated in linear time when $t$ is fixed. We can then compute each $\tau^*(\mathcal{H}_e)=\nu^*(\mathcal{H}_e)$ in time $O(n^3)$ and if this value is more than $\mathrm{e}\, d_t \cdot |e|$, then we can find a matching of size more than $|e|=|\mathcal{B}_e|$ in $\mathcal{H}_e$ in time $O(n^3)$ by Theorem~\ref{thm:frac}, and replace $\mathcal{B}_e$ by this larger matching in $\mathcal{B}$, thus increasing the size of $\mathcal{B}$ (this can be done at most $\nu(\mathcal{H})$ times). On the other hand, if for all the (linearly many) edges $e$ as above, we have $\tau^*(\mathcal{H}_e)\le \mathrm{e}\,d_t \cdot|e|=O({d_t}^2)$, then by Theorem~\ref{thm:nearlinear}, we can find a transversal of size $O({d_t}^2 \log d_t)$ in each hypergraph $\mathcal{H}_e$ in time $O(n^3)$. So overall we find a matching $\mathcal{B}$ that has the desired property, and a transversal of the partial hypergraph of $\mathcal{H}$ with edge set $\mathcal{E}_1$ of the desired size in time $O(\nu(\mathcal{H})\cdot n^4)$. Taking the induction step into account (which divides $\nu$ by at least 2), we obtain a deterministic algorithm constructing a transversal of size $O(\nu(\mathcal{H}))$ in $\mathcal{H}$, in time $O(\sum_{i\ge 0}\tfrac{1}{2^i}\cdot \nu(\mathcal{H})\cdot n^4)=O(\nu(\mathcal{H})\cdot n^4)$, when $t$ is a fixed constant.

\section{Conclusion}
\label{sec:conclusion}

The proof of Theorem~\ref{thm:main} gives a bound of the order of $\exp(t \log^{3/2}t)$ for the constant $c_t$. It would be interesting to improve this bound to a polynomial in $t$.

\medskip

It is also natural to wonder whether Theorem~\ref{thm:main} remains true in a  setting broader than proper minor-closed classes. Natural candidates are graphs of bounded maximum degree, graphs excluding a topological minor, $k$-planar graphs, classes with polynomial growth (meaning that the size of each ball is bounded by a polynomial function of its radius, see e.g.~\cite{KL03}), and classes with strongly sublinear separators (or equivalently, classes with polynomial expansion~\cite{DN16}). We now observe that in all these cases, the associated ball hypergraphs do not satisfy the Erd\H os-P\'osa property, even if all the balls have the same radius.
That is, we can find $r$-ball hypergraphs in these classes with bounded $\nu$ and unbounded $\tau$.
Our construction shows that this is true even in the seemingly simple case of subgraphs of a grid with all diagonals (i.e.\ strong products of two paths).

\medskip

Fix two integers $k,\ell$ with $k\geq 3$, and $\ell$ sufficiently large compared to $k$ and divisible by $2(\binom{k}{2}-1)$. Given $k$ vertices $v_0,v_1,\ldots v_{k-1}$, an $\ell$-\emph{broom with root $v_0$ and leaves $v_1,\ldots,v_{k-1}$} is a tree $T$ of maximum degree 3 with root $v_0$ and leaves $v_1,\ldots,v_{k-1}$} such that
\begin{enumerate}
\item each leaf is at distance $\ell$ from the root $v_0$,
\item the ball of radius $\ell/2$ centered in $v_0$ in $T$ is a path (called the \emph{handle} of the broom), and
  \item the distance between every two vertices of degree 3 in $T$ is sufficiently large compared to $k$.
\end{enumerate}

We now construct a graph $G_{k,\ell}$ as follows. We start with a set $X$ of $k$ vertices $x_1,\ldots,x_k$, and a path of $\binom{k}{2}$ vertices with vertex set $Y=\{y_{\{i,j\}}\,|\,1\le i<j\le k\}$, disjoint from $X$. We then subdivide each edge of the latter path $\tfrac{\ell}{2} \frac{1}{\binom{k}{2}-1} -1$ times, so that the subdivided path has length $\ell/2$. Finally, for each $1\le i \le k$, we add an $\ell$-broom $T_i$ with root $x_i$ and leaves $Y_i=\{y_{\{i,j\}}\,|\, j\ne i\}$.

\begin{figure}[htb]
 \centering
 \includegraphics[scale=1]{broom}
 \caption{An embedding of the graph $G_{4,\ell}$ in the 2-dimensional grid with all diagonals (the grid itself is not depicted for the sake of clarity).}
 \label{fig:broom}
\end{figure}

We first claim that $G_{k,\ell}$ is a subgraph of the 2-dimensional grid with all diagonals (i.e.\ the strong products of two paths).
To see this, place $X$ on a single column on the left, and $Y$ on another column on the right (in the sequence given by the path), at distance $\ell$ from the column of $X$, then draw each of the brooms in the plane (with  crossings allowed). Since the distance between two vertices of degree 3 in a broom is sufficiently large compared to  $k$, we can safely embed each topological crossing in the strong product of two edges (see Figure~\ref{fig:broom} for an example).

Let $\mathcal{H}_{k,\ell}$ be the $\ell$-ball hypergraph of $G_{k,\ell}$ obtained by considering all the balls of radius $\ell$ in $G_{k,\ell}$. We first observe that $\nu(\mathcal{H}_{k,\ell})=1$: this follows from the fact that each ball of radius $\ell$ centered in a vertex that does not belong to the handle of a broom contains all the vertices of $Y$, while every two vertices on the handles of two brooms $T_i$ and $T_j$ are at distance at most $\ell$ from $y_{\{i,j\}}$. Finally, for every two vertices $x_i$ and $x_j$ of $X$, note that $y_{\{i,j\}}$ is the unique vertex of $G_{k,\ell}$ lying at distance at most $\ell$ from $x_i$ and $x_j$, and thus $\tau(\mathcal{H}_{k,\ell})\ge \tfrac{k}2$. It follows that there is no function $f$ such that $\tau(\mathcal{H})\le f(\nu(\mathcal{H}))$ for every ball hypergraph of a subgraph of the strong product of two paths (even when all the balls in the ball hypergraph have the same radius).

\begin{acknowledgement}
We thank the two anonymous reviewers for their detailed
comments and suggestions.
\end{acknowledgement}