# New Constraints on ALP Electron and Photon Couplings from ArgoNeuT and the
MiniBooNE Beam Dump

Francesco Capozzi  Dipartimento di Scienze Fisiche e Chimiche, Università
degli Studi dell’Aquila, 67100 L’Aquila, Italy  Istituto Nazionale di Fisica
Nucleare (INFN), Laboratori Nazionali del Gran Sasso, 67100 Assergi (AQ),
Italy  Bhaskar Dutta  Mitchell Institute for Fundamental Physics and
Astronomy, Department of Physics and Astronomy, Texas A&M University, College
Station, TX 77845, USA  Gajendra Gurung  Department of Physics, University of
Texas, Arlington, TX 76019, USA  Wooyoung Jang  Department of Physics,
University of Texas, Arlington, TX 76019, USA  Ian M. Shoemaker  Center for
Neutrino Physics, Department of Physics, Virginia Tech, Blacksburg, VA 24061,
USA  Adrian Thompson  Mitchell Institute for Fundamental Physics and
Astronomy, Department of Physics and Astronomy, Texas A&M University, College
Station, TX 77845, USA  Jaehoon Yu  Department of Physics, University of
Texas, Arlington, TX 76019, USA

###### Abstract

Beam dumps and fixed-target experiments have been very sensitive probes of
such particles and other physics beyond the Standard Model (BSM) by
considering the production of new states from the primary interaction in the
beam dump. In a proton beam dump, there are many secondary interactions taking
place in electromagnetic showers which may be additional production channels
for pseudoscalar bosons or axion-like particles (ALPs). The target-less
configuration of the MiniBooNE experiment, which collected data from
$1.86\times 10^{20}$ protons impinging directly on the steel beam dump, is an
excellent test of sensitivity to these production channels of ALPs in the MeV
mass region. Using the null observation of the MiniBooNE dump mode data, we
set new constraints on ALPs coupling to electrons and photons produced through
a multitude of channels and detected via both scattering and decays in the
MiniBooNE detector volume. We find that the null result rules out parameter
space that was previously unconstrained by laboratory probes in the 10-100 MeV
mass regime for both electron and photon couplings. Lastly, we make the case
for performing a dedicated analysis with 1.25$\times 10^{20}$ POT of data
collected by the ArgoNeuT experiment, which we show to have complementary
sensitivity and set the stage for future searches.

††preprint: MI-HET-808

##  I Introduction

Particle beam dumps have proven to be ultra-sensitive probes of new physics
sectors beyond the Standard Model (BSM), where the myriad electromagnetic and
hadronic cascades produce showers of electrons, positrons, gamma rays, and
mesons; each a potential channel for BSM particle production. Studying the
beam target environment and the particle showers within is thus a crucial
first step to understanding what kind of physics is possible, and at what
energy scales. Already many searches have been performed by electron beam
dumps (E137, NA64, E141, Orsay, E774, etc. Bechis  _et al._ (1979); Bjorken
_et al._ (1988); Andreas  _et al._ (2010); Riordan  _et al._ (1987); Bross
_et al._ (1991); Banerjee  _et al._ (2019); Andreev  _et al._ (2021); Gninenko
_et al._ (2018)) and proton beam dumps at the GeV energy scale (e.g. CHARM,
NuCal, NA62, SeaQuest/SpinQuest Döbrich (2018); Berlin  _et al._ (2018); Tsai
_et al._ (2021); Andreas  _et al._ (2010)) and sub-GeV sources (e.g. CCM
Aguilar-Arevalo  _et al._ (2023), IsoDAR Alonso  _et al._ (2022), and COHERENT
Akimov  _et al._ (2023)), and others Agrawal  _et al._ (2021).

The existence of pseudoscalar bosons with small couplings to the SM are
predicted in models of broken symmetries in connection with explaining many
puzzles in nature. Axions and axion-like particles (ALPs) are central features
in the landscape of solutions, in particular, to the strong CP problem Peccei
and Quinn (1977); Wilczek (1978); Weinberg (1978); Preskill  _et al._ (1983);
Abbott and Sikivie (1983); Dine and Fischler (1983); Duffy and van Bibber
(2009); Marsh (2016); Battaglieri  _et al._ (2017) and to the dark matter
problem Panci  _et al._ (2022); Marsh (2016); Chadha-Day  _et al._ (2022), and
otherwise appear ubiquitously in string theory Svrcek and Witten (2006);
Halverson  _et al._ (2019), and the ultraviolet spectra of many other puzzle-
solving models with spontaneously broken symmetries. In many of these
scenarios, it is possible that the ALP has couplings to SM leptons and the
electromagnetic field, making the particle showers inside the beam target good
laboratory probes of ALPs, reaching up to GeV mass scales. ALPs at the MeV to
GeV mass scales are of particular interest to beam dump and fixed target
experiments and have been studied in the context of heavy axions Kelly  _et
al._ (2021); Gaillard  _et al._ (2018); Kivel  _et al._ (2022); Hook  _et al._
(2020), whose parameter space extends beyond that of traditional QCD axion
models.

In 2018 MiniBooNE collaboration performed an analysis of their targetless-mode
run Aguilar-Arevalo  _et al._ (2018a), in which they collected data associated
with $1.86\times 10^{20}$ protons on target (POT) bypassing the main beryllium
target and impinging on the steel beam dump. Expected neutrino rates for this
mode were very low, and no excess of events was observed, in contrast to the
results from the target-mode runs Aguilar-Arevalo  _et al._ (2018b, 2021). In
this work, we show that the null result from this data set is sensitive enough
to ALPs produced in electromagnetic showers in the dump to set new limits on
photon and electron couplings.

Running in a target-less mode has the effect of suppressing the fluxes of
neutrinos coming from charged meson decays. Searches for BSM particles that
have production channels orthogonal to the charged pion decay gain a big
advantage here; in the case of a thin target, the charged mesons decay in
flight after getting produced, allowing them to be focused by the magnetic
horn system. In the thick beam dump case, however, the charged pions are
stopped in the material and decay isotropically, suppressing the subsequent
neutrino background that would lie in the signal region for the BSM search.

This realization is especially important for future beam dump experiments at
higher energies, where the higher intensity of electromagnetic cascades
provide both the coupling and mass reach necessary to significantly extend the
limits tested so far by laboratory searches in the MeV to GeV mass range. We
will show that data collected by the ArgoNeuT detector Acciarri  _et al._
(2019, 2023) already has this capability, and depending on the specific
sensitivity of a dedicated analysis, null observations in this data could
already rule out parameter space unconstrained by laboratory probes to-date.

In § II we outline the production and detection channels we consider for
electromagnetically-coupled ALPs. In § III we describe the statistical
analysis performed for the MiniBooNE dump-mode data and the ArgoNeuT data
given an ALP signal hypothesis, with the resulting limits placed on the
parameter space of photon and electron couplings in § IV. Finally we conclude
in § V.

##  II BSM Production and Detection in a Beam Dump

We consider primarily ALPs produced in electromagnetic cascades inside the
beam dump or beam target environment, e.g., those that get produced from
couplings to photons and to electrons;

$\mathscr{L}_{ALP}\supset
ig_{ae}a\bar{\psi}_{e}\gamma^{5}\psi_{e}-\frac{1}{4}g_{a\gamma}aF_{\mu\nu}\tilde{F}^{\mu\nu}$
(1)

This Lagrangian, which for simplicity we will assume only one tree-level
coupling active or dominant at a time, opens up a slew of production and
detection channels available to beam target and beam dump experiments. These
have recently been investigated in refs. Dent  _et al._ (2020); Brdar  _et
al._ (2021); Dutta  _et al._ (2022); Capozzi  _et al._ (2021); Aguilar-Arevalo
_et al._ (2023); Brdar  _et al._ (2023), and we summarize them in Table 1.

Coupling | Production | Detection
---|---|---
$g_{a\gamma}$ | $\gamma\,Z\to a\,Z$ | $a\,Z\to\gamma\,Z$
$a\to\gamma\gamma$
$g_{ae}$ | $\gamma\,e^{-}\to a\,e^{-}$ | $a\,e^{-}\to\gamma\,e^{-}$
$e^{+}\,e^{-}\to a\,\gamma$ | $a\to e^{+}e^{-}$
$e^{\pm}\,Z\to e^{\pm}\,Z\,a$ | $a\,Z\to e^{+}\,e^{-}\,Z$
$e^{+}\,e^{-}\to a$
$\pi^{\pm}\to e^{\pm}\,\nu\,a$
Table 1: ALP production and detection mechanisms that are available through
couplings to electrons and photons considered in this analysis.

For ALPs coupled to electrons, the dominant final state will be $e^{+}e^{-}$
pairs appearing in the detector as single Cherenkov rings, either from the
pair being highly collinear with a separating angle less than the typical
angular resolution of the detector or if one of the electrons/positrons are
too soft. This final state appears mainly through decays for $m_{a}>2m_{e}$
and otherwise through the Bethe-Heitler lepton pair production process ($aZ\to
e^{+}e^{-}Z$) for sub-MeV ALPs, considered before to set limits on light
(pseudo)scalars appearing in a proton beam target Blumlein  _et al._ (1991,
1992). The cross-section for this process was computed in refs. Kim  _et al._
(1983, 1984) using the formalism and atomic form factors presented in ref.
Tsai (1974), and it is larger than inverse-Compton scattering
($ae^{-}\to\gamma e^{-}$) by up to an order of magnitude for ALP energies in
the 100 MeV - 1 GeV range, which is the energy region of interest for this
study.

The resonant cross section in the electron rest frame is

$\displaystyle\sigma$ $\displaystyle=\dfrac{2\pi
m_{e}g_{ae}^{2}s}{m_{a}^{2}\sqrt{s(s-4m_{e}^{2})}}\delta(E_{+}-(\frac{m_{a}^{2}}{2m_{e}}-m_{e}))$
(2) $\displaystyle\simeq\dfrac{2\pi
m_{e}g_{ae}^{2}}{m_{a}^{2}}\delta(E_{+}-(\frac{m_{a}^{2}}{2m_{e}}-m_{e})).$
(3)

To simulate the production fluxes, we first generate the SM particle fluxes
inside the MiniBooNE dump with GEANT4 using the QGSP_BERT_AllHP physics list,
then pass a high-statistics sample of each particle flux
($e^{\pm},\gamma,\pi^{\pm}$) into the alplib event
generator.111https://github.com/athompson-git/alplib The positron and electron
fluxes are shown in Fig. 1, while the photon flux is shown in Fig. 2. We show
a large phase space of the $e^{\pm}$ and $\gamma$ fluxes to illustrate the
many low-energy features that come about from processes like nuclear de-
excitation and beta decay. However, in principle, only the high energy tail
($>75$ MeV) in the forward-going region ($\theta\lesssim 10^{-2}$ rad) is
responsible for the bulk of BSM particle production that is captured within
the signal region and pointing within the solid angle of the MiniBooNE
detector. This is illustrated in Fig. 3 where we show the energy spectra
before and after an angular cut of 10 mrad. Further details of the event
selection and signal window are discussed in the following section.

For ALPs produced from electrons or positrons in resonant production
($e^{+}e^{-}\to a$), associated production ($e^{+}e^{-}\to a\gamma$), or
bremsstrahlung ($e^{\pm}Z\to e^{\pm}Za$), the energy loss of the electrons and
positrons in the material during particle transport must also be folded into
the event rate calculation. This modifies the number flux leaving the beam
dump as

$\displaystyle\dfrac{dN_{a}}{dE_{a}}$
$\displaystyle=\frac{N_{A}X_{0}}{A}(\hbar
c)^{2}\int\frac{d^{2}\Phi_{e^{+}}}{dE_{e}d\Omega_{e}}I(t,E_{+},E^{\prime})$
$\displaystyle\times\Theta_{\text{det}}\dfrac{d^{2}\sigma(E^{\prime})}{dE^{\prime}d\Omega^{\prime}}d\Omega_{e}d\Omega^{\prime}dE_{+}dtdE^{\prime}$
(4)

where $N_{A}$ is Avogadro’s number, $X_{0}$ is the radiation length of the
electrons/positrons in the dump material, and $A$ is the atomic weight.
$I(t,E_{i},E_{f})=\frac{\theta(E_{i}-E_{f})}{E_{i}\Gamma(4t/3)}(\ln
E_{i}/E_{f})^{4t/3-1}$ is the energy loss smearing function for the
electron/positron radiation length $t$ integrated up to target radiation
thickness $T$ Tsai (1986). We integrate over the solid angle of the positron
with respect to the beamline, $\Omega_{e}$, and outgoing ALP solid angle with
respect to the positron direction, $\Omega^{\prime}$, taking care to integrate
only those ALPs pointed in the direction of the detector solid angle through
the Heaviside function $\Theta_{\text{det}}$ Brdar  _et al._ (2021).

Figure 1: Electron and positron fluxes in the BNB steel beam dump generated
with GEANT4 using $10^{4}$ POT with the QGSP_BERT_AllHP physics list, here
shown as a function of the $e^{\pm}$ angle with respect to the beam axis and
kinetic energy $T$. Figure 2: Photon fluxes in the BNB steel beam dump
generated with GEANT4 using $10^{4}$ POT with the QGSP_BERT_AllHP physics
list, here shown as a function of the $\gamma$ angle with respect to the beam
axis and energy $E_{\gamma}$. Figure 3: Electron, positron, and photon fluxes
before and after angular cuts in the MiniBooNE beam dump.

##  III Data Analysis

###  III.1 MiniBooNE Dump Mode

The final states of concern in our search for ALPs in the MiniBooNE detector
are photon-like events and electron-like events, listed in Table 1. We have
adopted the same selection cuts made in the $\nu-e$ analysis of the MiniBooNE
dump mode data for these states. Here we study the detector response with true
simulated information to analyze the efficiency of the electron-like event
selection from reconstructed events inside the detector. For the analysis of
the Monte Carlo generated data, after the preliminary cuts have been applied,
the first round of the reconstructed events is fit under the one-track
electron and muon hypothesis. Each fit returns the likelihood of the
corresponding hypothesis: $\mathcal{L}_{e}$ and $\mathcal{L}_{\mu}$. Those
events satisfying the $\log(\mathcal{L}_{e}/\mathcal{L}_{\mu})>-0.05$ continue
the next round of reconstruction. In the second round, reconstructed events
are fit under the general two-photon hypothesis. Similarly, the events should
satisfy $\log(\mathcal{L}_{\pi^{0}}/\mathcal{L}_{e})<0$. The efficiencies of
these two cuts using simulated data as functions of electron visible energy
and electron scattering angle are shown in Fig. 4. The selection efficiencies
as a function of the visible energy, $E^{vis}_{e}$, are fitted as an
arctangent function ($p_{0}\arctan(p_{1}x)+p_{2}$). The selection efficiencies
as a function of the cosine of the angle with respect to the beam axis,
$\cos\theta_{e}$, are fitted as a straight line ($p_{0}+p_{1}x$) except for
the forward region of $\log(\mathcal{L}_{e}/\mathcal{L}_{\mu})$ which has a
second-order polynomial fit ($p_{0}+p_{1}x+p_{2}x^{2}$). Uncertainties from
the goodness-of-fit on the efficiency curve as a function of $E_{e}^{vis}$ and
$\cos\theta_{e}$ are constrained to be less than $20\%$, so their impact on
the exclusions over the model parameter space shown in the following section
will not be qualitatively different.

(a) Selection efficiency as a function of $E^{vis}_{e}$.

(b) Selection efficiency as a function of $\cos\theta_{e}$.

Figure 4: Selection efficiency of the electron-like events from reconstructed
events inside the MiniBooNE detector.

In addition to these log-likelihood efficiencies, we also take into account
the cut on the reconstructed vertex radius of 500 cm, which effectively
reduces the MiniBooNE volume to a sphere of 10 m in diameter. Other cuts, such
as the number of tank and veto hits, and the Scintillation / Cherenkov ratios
we assume to have perfect signal efficiency for the detection channels in
Table 1. However, we do check that the $\gamma\gamma$, $e^{+}e^{-}$, and
$\gamma e^{-}$ final states from axion interactions and decays are collinear
enough to be identified as a single electron-like Cherenkov ring in the
detector. This also ensures that the cut on the di-gamma invariant mass
$m_{\gamma\gamma}\leq 80$ MeV is passed by selection for our ALP signals.

Figure 5: Left: visible energy spectrum from ALP production and scattering in
photon coupling channels, where a mass of $m_{a}=0.5$ MeV at couplings of
$g_{a\gamma}\sim\mathcal{O}(10^{-5})$ GeV-1 mainly contribute to the decay
channel $a\to\gamma\gamma$. Right: visible energy spectra from electron
coupling channels, with the solid red histogram showing the predicted spectra
below the decay threshold $m_{a}=2m_{e}$, while the dashed red histogram shows
the spectrum for a larger mass which is resonantly produced and dominantly
produces a $a\to e^{+}e^{-}$ decay signature.

Lastly, we bin the ALP signal Monte Carlo events into visible energy and
cosine bins between $75\leq E_{\gamma}\leq 850$ MeV and $\cos\theta\geq 0.9$
(taking $E_{\gamma}=E_{e}^{vis}$ for the electron-like visible energy
measurement). Since inverse Primakoff scattering is characterized by a forward
outgoing photon, while inverse Compton scattering is characterized by a
forward outgoing electron and a soft off-forward photon (typically below the
lower energy cut), these scattering channels are well within the selection
region for most choices of the couplings and the ALP mass. Example spectra for
photon and electron coupling channels are shown in Fig. 5, where we have
convolved the predicted event rates with the efficiency functions described
above. For the case of ALPs undergoing inverse Primakoff scattering in the
detector, $aZ\to\gamma Z$, we integrate over the visible energy and outgoing
angle of the final state photon;

$\frac{d^{2}R}{dE_{\gamma}d\Omega_{\gamma}}=N_{T}\int\frac{dN_{a}}{dE_{a}}\frac{d^{2}\sigma(E_{a})}{dE_{\gamma}d\Omega_{\gamma}}\epsilon(E_{\gamma})\epsilon(\Omega_{\gamma})dE_{a}$
(5)

where $\epsilon(E_{\gamma})$ and
$\epsilon(\Omega_{\gamma})=\epsilon(\cos\theta_{\gamma})$ are equivalent to
the visible energy and cosine efficiencies, respectively, of the electron-like
signals shown in Fig. 4. Here, recall the differential event rate
$dN_{a}/dE_{a}$ passing into the detector from Eq. II.

Integrating Eq. 5 over energy bin edges $[75,100,150,200,250,300,500,850]$ (in
MeV) and cosine bin edges $[0.9,0.95,0.99,1.0]$ yields the ALP signal $s_{i}$
in each bin $i$ as a function of the mass and couplings. In the case of
decays, instead of the differential cross section in Eq. 5 we use the
probability of decays occurring inside the detector

$P_{decay}=e^{-\ell/(\tau v_{a})}\left[1-e^{-\Delta\ell/(\tau
v_{a})}\right]\,$ (6)

where $\tau v_{a}$ is the ALP decay length in the lab frame, $\ell$ is the
baseline distance between the ALP production in the dump, and $\Delta\ell$ is
the fiducial path length in the detector during which the decay must take
place.

For the other detection channel final states ($2\gamma$, $1\gamma 1e^{-}$, or
$e^{+}e^{-}$), both final state particles leave visible energy in the
detector, so we need to ensure that they are collinear enough to be
reconstructed as a single Cherenkov ring in the detector. We check the angular
distribution of the final state and cut events if two final state particles
are separated by more than 5 degrees.

We use a binned log-Poisson likelihood to obtain the confidence limits;

$\ln
L(\vec{\theta})=\sum_{i=1}^{7}d_{i}\ln\big{[}s_{i}(\vec{\theta})+b_{i}\big{]}-\big{[}s_{i}(\vec{\theta})+b_{i}\big{]}-\ln\big{[}\Gamma(d_{i}+1)\big{]}$
(7)

for data $d_{i}$, backgrounds $b_{i}$, and signal $s_{i}(\vec{\theta})$, where
$\vec{\theta}=(m_{a},g_{a\gamma})$ in the case of dominant ALP-photon coupling
and $\vec{\theta}=(m_{a},g_{ae})$. The CLs are then given by finding regions
of constant delta-log-likelihood,

$-2\Delta\ln L\equiv 2(\ln L(\theta)-\ln L(\theta)_{min}),$ (8)

in the relevant model parameter space $\vec{\theta}$.

###  III.2 ArgoNeuT

ArgoNeuT Acciarri  _et al._ (2019) collected data from $1.25\times 10^{20}$
POT impinging on the NuMI target, with its LArTPC detector situated 1.04 km
downstream of the target while the beamline was in anti-neutrino mode Adamson
_et al._ (2016). With a fiducial volume of $0.40\times 0.47\times 0.90$ cm3,
the angular acceptance of the detector coverage corresponds to roughly 0.325
mrad in solid angle. We perform a similar simulation with GEANT4 using the
QGSP_BERT_AllHP physics list to model the particle cascades inside the NuMI
beam target environment (120 GeV protons on graphite). The ALP flux is
calculated in the same way explained in the case of the MiniBooNE dump. From
the GEANT4 flux distributions of $e^{\pm}$ and $\gamma$ in the solid angle of
ArgoNeuT, shown in Fig. 6, we estimate the ALP flux produced from 1.25$\times
10^{20}$ POT during data collection.

Figure 6: Electron, positron, and photon fluxes at the NuMI target whose
directions point within the solid angle of the ArgoNeuT detector.

A dedicated search for heavy ALPs decaying to di-muon pairs was performed by
the ArgoNeuT collaboration Acciarri  _et al._ (2023), exhibiting an event
topology with very low background expectations. However, here we are
interested in different types of event topologies: $e^{+}e^{-}$,
$e^{-}\gamma$, $2\gamma$ and $1\gamma$ (see Table 1), for which a dedicated
analysis is missing. Therefore, we will not perform a likelihood analysis. We
will just provide the contours in the parameter space for which the following
number of signal ALP events would be observed in ArgoNeuT: 3, 20, and 100.
These numbers are equal to the Poisson error of $\sim$ 10, 400, and $10^{4}$
background events, respectively.

##  IV Results

The constraints on the ALP-photon coupling $g_{a\gamma}$ as a function of the
ALP mass $m_{a}$ derived from MiniBooNE beam dump mode data is shown in Fig.
7. The $1\sigma$ and $2\sigma$ CLs are shown individually using the delta-log-
likelihood method, and we find that the MiniBooNE data sets new laboratory
limits on the ALP coupling for masses below 100 keV or so, where previously
astrophysics (HB star cooling and SN1987a Lucente  _et al._ (2020), see also
refs. Jaeckel  _et al._ (2007); Khoury and Weltman (2004); Masso and Redondo
(2005, 2006); Dupays  _et al._ (2007); Mohapatra and Nasri (2007); Brax  _et
al._ (2007); DeRocco  _et al._ (2020)) had placed the only constraints ahead
of beam dump constraints Jaeckel and Spannowsky (2016); Blümlein  _et al._
(1992)222The measurement of the explosion energy of SN1987A can have tension
to the cosmological triangle region unless the star cooling process is
significantly different from the standard picture Caputo  _et al._ (2022). and
recently, constraints set by the CCM120 engineering run Aguilar-Arevalo  _et
al._ (2023). Limits set by the ArgoNeuT null result from 1.25$\times 10^{20}$
POT of collected data are shown in blue, benchmarking the signal event rate at
3, 20, and 100 events in the absence of a dedicated analysis with backgrounds
and proper event selection. Comparing the shape of the exclusion contours
between MiniBooNE and ArgoNeuT, one can see the impact of the longer baseline
between beam target and detector at ArgoNeuT ($\sim 1$ km) versus MiniBooNE
($489$ m) shifting the sensitivity contour to larger masses reflecting longer
ALP lifetimes for $a\to\gamma\gamma$ decay.

In this space, we also show the parameter space associated with QCD Axion
model benchmarks spanned between the dashed black lines. Here the range of
couplings and masses are shown for Kim-Shifman-Vainshtein-Zakharov (KSVZ)
benchmark models Kim (1979); Shifman  _et al._ (1980), where the range is
defined by taking the anomaly number ratios of $E/N=44/3$ to $E/N=2$ in the
model. The correlations between the QCD axion mass and its effective couplings
are taken from ref. Di Luzio  _et al._ (2020) (see also Appendix A). While the
constraints shown here are purely on the photon-ALP couplings, independent
constraints on the ALP-gluon couplings in these model variants are stringent
and would indirectly rule out much of the parameter space Alonso-Álvarez  _et
al._ (2019). These bands are of course only representative of these
traditional QCD models shown for a sense of scale. QCD axions that are invoked
to solve the strong CP problem which have parametrically heavier or lighter
masses in other non-traditional models are also possible Elahi  _et al._
(2023); Gaillard  _et al._ (2018); Kivel  _et al._ (2022); Hook  _et al._
(2020).

Figure 7: Constraints on $g_{a\gamma}$ set by the MiniBooNE dump-mode run at
$2\sigma$ C.L. are shown, while the expected limits set by ArgoNeuT are shown
for several benchmark signal rates.

We set limits in the same way on the electron-ALP coupling $g_{ae}$ as a
function of the ALP mass in Fig. 8. The parameter space associated with Dine-
Fischler-Srednicki-Zhitnitsky (DFSZ) benchmark models Zhitnitsky (1980); Dine
_et al._ (1981a, b); Dine and Fischler (1983), for which couplings to
electrons would be dominant relative to the photon couplings, the span between
the dashed black lines. Again, we show this span of model parameter space for
reference although the constraints shown here from pure $g_{ae}$-driven
channels are conservative and indirect constraints on the DFSZ gluon couplings
would be more stringent. In the electron coupling, we find that MiniBooNE dump
mode tests parameter space already ruled out by existing laboratory searches
(e.g. NA64, E137, and other beam dumps). Although, in the mass range $\sim 10$
MeV the resonant channel $e^{+}e^{-}\to a$ produces a highly peaked signal
which becomes visible inside the energy region of interest, $75<E_{vis}<850$
MeV (see Fig. 5). This is because the resonant energy tracks the square of the
ALP mass, as $E_{a}=m_{a}^{2}/(2m_{e})$, producing the first visible peak
within this energy range for $m_{a}\simeq 10$ MeV. The MiniBooNE dump mode
becomes highly sensitive to ALP signals here for those masses but is
consistent with the existing E137 constraints in this region. The subtle
undulating features in the CL contours from $m_{a}=10-30$ MeV then reflect the
signal rising and falling to accommodate the two data points in the 3rd and
6th energy bins in Fig. 5.

Figure 8: Constraints on $g_{ae}$ set by the MiniBooNE dump-mode run at
$2\sigma$ C.L. are shown, while the expected limits set by ArgoNeuT are shown
for several benchmark signal rates.

ArgoNeuT sensitivity to this coupling is fairly powerful in the $m_{a}>2m_{e}$
mass range and would exclude new parameter space ahead of the limits set by
the CCM120 engineering run between $m_{a}=1$ MeV and $m_{a}=5$ MeV. This is
owed in part to the energy scale and long distance from the detector to the
target being ideal to probe long ALP lifetimes, and also the relatively larger
$e^{\pm}$ fluxes produced in the NuMI target (Fig. 6). This exclusion would be
possible even for a benchmark signal rate of 100 events, corresponding roughly
to a Poisson background of $10^{4}$ events without taking into account signal
efficiency. This sensitivity is lost in the scattering limit for
$m_{a}<2m_{e}$ where NA64 missing energy and CCM120, where being at much
closer proximity to the production site, $\ell\sim 20$ m plays a bigger role,
set the leading constraints.

##  V Outlook

The analysis of the MiniBooNE dump mode data shows significant sensitivity to
dark sector states produced by the secondary electromagnetic cascades in the
BNB dump environment. By utilizing the off-target configuration and examining
the interactions of $1.86\times 10^{20}$ protons with the steel beam dump, we
have expanded the existing constraints on ALPs in the 10-100 MeV mass regime
that couple to photons. Simultaneously, despite a small exposure and fiducial
detector mass, the null observations of ArgoNeuT could potentially rule out
parameter space for ALPs in the same mass range coupling to electrons, due to
the higher beam energy.

Stopped-pion experiments at $\sim$GeV scale proton beam dumps also have the
capability to probe new physics in the secondary electromagnetic showers,
expanding in complementary regions of model parameter space to the higher
energy, longer baseline beam dump experiments situated at the NuMI, BNB, or
LBNF beams. Future beam dump searches may be possible to fully probe QCD axion
parameter space for MeV masses, such as a proposed dump mode or target-less
running mode for DUNE Brdar  _et al._ (2023). A dedicated target-less mode was
shown to test electron-ALP couplings down to $g_{ae}\sim 10^{-6}$ for
$m_{a}<2m_{e}$ and down to $g_{ae}\sim 10^{-9}$ from ALP decays to
$e^{+}e^{-}$ pairs with a limited 3 month to 1-year exposure.

## Acknowledgments

We are grateful to Ornella Palamara for the helpful discussions regarding the
potential for dedicated ALP studies at ArgoNeuT. The work of IMS is supported
by DOE under the award number DE-SC0020250. The work of BD and AT is supported
by the DOE Grant No. DE-SC0010813. Portions of this research were conducted
with the advanced computing resources provided by Texas A&M High-Performance
Research Computing. The work of GG, WJ, and JY is supported by the U.S.
Department of Energy under Grant No. DE-SC0011686. We thank the Center for
Theoretical Underground Physics and Related Areas (CETUP*) and SURF for
facilitating portions of this research.

## References

  * Bechis  _et al._ (1979) D. J. Bechis, T. W. Dombeck, R. W. Ellsworth, E. V. Sager, P. H. Steinberg, L. J. Teig, J. K. Yoh, and R. L. Weitz, Phys. Rev. Lett. 42, 1511 (1979), [Erratum: Phys.Rev.Lett. 43, 90 (1979)].
  * Bjorken  _et al._ (1988) J. D. Bjorken, S. Ecklund, W. R. Nelson, A. Abashian, C. Church, B. Lu, L. W. Mo, T. A. Nunamaker, and P. Rassmann, Phys. Rev. D 38, 3375 (1988).
  * Andreas  _et al._ (2010) S. Andreas, O. Lebedev, S. Ramos-Sanchez, and A. Ringwald, JHEP 08, 003 (2010), arXiv:1005.3978 [hep-ph] .
  * Riordan  _et al._ (1987) E. M. Riordan _et al._ , Phys. Rev. Lett. 59, 755 (1987).
  * Bross  _et al._ (1991) A. Bross, M. Crisler, S. H. Pordes, J. Volk, S. Errede, and J. Wrbanek, Phys. Rev. Lett. 67, 2942 (1991).
  * Banerjee  _et al._ (2019) D. Banerjee _et al._ (NA64 Collaboration), Phys. Rev. Lett. 123, 121801 (2019).
  * Andreev  _et al._ (2021) Y. M. Andreev _et al._ , Phys. Rev. D 104, L091701 (2021), arXiv:2108.04195 [hep-ex] .
  * Gninenko  _et al._ (2018) S. N. Gninenko, D. V. Kirpichnikov, M. M. Kirsanov, and N. V. Krasnikov, Phys. Lett. B 782, 406 (2018), arXiv:1712.05706 [hep-ph] .
  * Döbrich (2018) B. Döbrich (NA62), Frascati Phys. Ser. 66, 312 (2018), arXiv:1807.10170 [hep-ex] .
  * Berlin  _et al._ (2018) A. Berlin, S. Gori, P. Schuster, and N. Toro, Phys. Rev. D 98, 035011 (2018), arXiv:1804.00661 [hep-ph] .
  * Tsai  _et al._ (2021) Y.-D. Tsai, P. deNiverville, and M. X. Liu, Phys. Rev. Lett. 126, 181801 (2021), arXiv:1908.07525 [hep-ph] .
  * Aguilar-Arevalo  _et al._ (2023) A. A. Aguilar-Arevalo _et al._ (The CCM Collaboration), Phys. Rev. D 107, 095036 (2023).
  * Alonso  _et al._ (2022) J. Alonso _et al._ , Phys. Rev. D 105, 052009 (2022), arXiv:2111.09480 [hep-ex] .
  * Akimov  _et al._ (2023) D. Akimov _et al._ (COHERENT), Phys. Rev. Lett. 130, 051803 (2023), arXiv:2110.11453 [hep-ex] .
  * Agrawal  _et al._ (2021) P. Agrawal _et al._ , Eur. Phys. J. C 81, 1015 (2021), arXiv:2102.12143 [hep-ph] .
  * Peccei and Quinn (1977) R. D. Peccei and H. R. Quinn, Phys. Rev. Lett. 38, 1440 (1977).
  * Wilczek (1978) F. Wilczek, Phys. Rev. Lett. 40, 279 (1978).
  * Weinberg (1978) S. Weinberg, Phys. Rev. Lett. 40, 223 (1978).
  * Preskill  _et al._ (1983) J. Preskill, M. B. Wise, and F. Wilczek, Phys. Lett. B 120, 127 (1983).
  * Abbott and Sikivie (1983) L. Abbott and P. Sikivie, Phys. Lett. B 120, 133 (1983).
  * Dine and Fischler (1983) M. Dine and W. Fischler, Phys. Lett. B 120, 137 (1983).
  * Duffy and van Bibber (2009) L. D. Duffy and K. van Bibber, New J. Phys. 11, 105008 (2009), arXiv:0904.3346 [hep-ph] .
  * Marsh (2016) D. J. E. Marsh, Phys. Rept. 643, 1 (2016), arXiv:1510.07633 [astro-ph.CO] .
  * Battaglieri  _et al._ (2017) M. Battaglieri _et al._ , in  _U.S. Cosmic Visions: New Ideas in Dark Matter College Park, MD, USA, March 23-25, 2017_ (2017) arXiv:1707.04591 [hep-ph] .
  * Panci  _et al._ (2022) P. Panci, D. Redigolo, T. Schwetz, and R. Ziegler, (2022), arXiv:2209.03371 [hep-ph] .
  * Chadha-Day  _et al._ (2022) F. Chadha-Day, J. Ellis, and D. J. E. Marsh, Sci. Adv. 8, abj3618 (2022), arXiv:2105.01406 [hep-ph] .
  * Svrcek and Witten (2006) P. Svrcek and E. Witten, JHEP 06, 051 (2006), arXiv:hep-th/0605206 .
  * Halverson  _et al._ (2019) J. Halverson, C. Long, B. Nelson, and G. Salinas, Phys. Rev. D 100, 106010 (2019), arXiv:1909.05257 [hep-th] .
  * Kelly  _et al._ (2021) K. J. Kelly, S. Kumar, and Z. Liu, Phys. Rev. D 103, 095002 (2021), arXiv:2011.05995 [hep-ph] .
  * Gaillard  _et al._ (2018) M. K. Gaillard, M. B. Gavela, R. Houtz, P. Quilez, and R. Del Rey, Eur. Phys. J. C 78, 972 (2018), arXiv:1805.06465 [hep-ph] .
  * Kivel  _et al._ (2022) A. Kivel, J. Laux, and F. Yu, JHEP 11, 088 (2022), arXiv:2207.08740 [hep-ph] .
  * Hook  _et al._ (2020) A. Hook, S. Kumar, Z. Liu, and R. Sundrum, Phys. Rev. Lett. 124, 221801 (2020), arXiv:1911.12364 [hep-ph] .
  * Aguilar-Arevalo  _et al._ (2018a) A. A. Aguilar-Arevalo _et al._ (MiniBooNE DM), Phys. Rev. D 98, 112004 (2018a), arXiv:1807.06137 [hep-ex] .
  * Aguilar-Arevalo  _et al._ (2018b) A. A. Aguilar-Arevalo _et al._ (MiniBooNE), Phys. Rev. Lett. 121, 221801 (2018b), arXiv:1805.12028 [hep-ex] .
  * Aguilar-Arevalo  _et al._ (2021) A. A. Aguilar-Arevalo _et al._ (MiniBooNE), Phys. Rev. D 103, 052002 (2021), arXiv:2006.16883 [hep-ex] .
  * Acciarri  _et al._ (2019) R. Acciarri _et al._ (ArgoNeuT), Phys. Rev. D 99, 012002 (2019), arXiv:1810.06502 [hep-ex] .
  * Acciarri  _et al._ (2023) R. Acciarri _et al._ (ArgoNeuT), Phys. Rev. Lett. 130, 221802 (2023), arXiv:2207.08448 [hep-ex] .
  * Dent  _et al._ (2020) J. B. Dent, B. Dutta, D. Kim, S. Liao, R. Mahapatra, K. Sinha, and A. Thompson, Phys. Rev. Lett. 124, 211804 (2020), arXiv:1912.05733 [hep-ph] .
  * Brdar  _et al._ (2021) V. Brdar, B. Dutta, W. Jang, D. Kim, I. M. Shoemaker, Z. Tabrizi, A. Thompson, and J. Yu, Phys. Rev. Lett. 126, 201801 (2021), arXiv:2011.07054 [hep-ph] .
  * Dutta  _et al._ (2022) B. Dutta, D. Kim, S. Liao, J.-C. Park, S. Shin, L. E. Strigari, and A. Thompson, JHEP 01, 144 (2022), arXiv:2006.09386 [hep-ph] .
  * Capozzi  _et al._ (2021) F. Capozzi, B. Dutta, G. Gurung, W. Jang, I. M. Shoemaker, A. Thompson, and J. Yu, Phys. Rev. D 104, 115010 (2021), arXiv:2108.03262 [hep-ph] .
  * Brdar  _et al._ (2023) V. Brdar, B. Dutta, W. Jang, D. Kim, I. M. Shoemaker, Z. Tabrizi, A. Thompson, and J. Yu, Phys. Rev. D 107, 055043 (2023), arXiv:2206.06380 [hep-ph] .
  * Blumlein  _et al._ (1991) J. Blumlein _et al._ , Z. Phys. C 51, 341 (1991).
  * Blumlein  _et al._ (1992) J. Blumlein _et al._ , Int. J. Mod. Phys. A 7, 3835 (1992).
  * Kim  _et al._ (1983) B. Kim, C. Stamm, and R. Rodenberg, Physics Letters B 122, 87 (1983).
  * Kim  _et al._ (1984) B. Kim, B. Cho, S. Oh, C. Stamm, and R. Rodenberg, Nuclear Physics B 242, 189 (1984).
  * Tsai (1974) Y.-S. Tsai, Rev. Mod. Phys. 46, 815 (1974).
  * Tsai (1986) Y.-S. Tsai, Phys. Rev. D 34, 1326 (1986).
  * Adamson  _et al._ (2016) P. Adamson _et al._ , Nucl. Instrum. Meth. A 806, 279 (2016), arXiv:1507.06690 [physics.acc-ph] .
  * Lucente  _et al._ (2020) G. Lucente, P. Carenza, T. Fischer, M. Giannotti, and A. Mirizzi, JCAP 12, 008 (2020), arXiv:2008.04918 [hep-ph] .
  * Jaeckel  _et al._ (2007) J. Jaeckel, E. Masso, J. Redondo, A. Ringwald, and F. Takahashi, Phys. Rev. D 75, 013004 (2007), arXiv:hep-ph/0610203 [hep-ph] .
  * Khoury and Weltman (2004) J. Khoury and A. Weltman, Phys. Rev. Lett. 93, 171104 (2004), arXiv:astro-ph/0309300 [astro-ph] .
  * Masso and Redondo (2005) E. Masso and J. Redondo, JCAP 0509, 015 (2005), arXiv:hep-ph/0504202 [hep-ph] .
  * Masso and Redondo (2006) E. Masso and J. Redondo, Phys. Rev. Lett. 97, 151802 (2006), arXiv:hep-ph/0606163 [hep-ph] .
  * Dupays  _et al._ (2007) A. Dupays, E. Masso, J. Redondo, and C. Rizzo, Phys. Rev. Lett. 98, 131802 (2007), arXiv:hep-ph/0610286 [hep-ph] .
  * Mohapatra and Nasri (2007) R. N. Mohapatra and S. Nasri, Phys. Rev. Lett. 98, 050402 (2007), arXiv:hep-ph/0610068 [hep-ph] .
  * Brax  _et al._ (2007) P. Brax, C. van de Bruck, and A.-C. Davis, Phys. Rev. Lett. 99, 121103 (2007), arXiv:hep-ph/0703243 [HEP-PH] .
  * DeRocco  _et al._ (2020) W. DeRocco, P. W. Graham, and S. Rajendran, Phys. Rev. D 102, 075015 (2020), arXiv:2006.15112 [hep-ph] .
  * Jaeckel and Spannowsky (2016) J. Jaeckel and M. Spannowsky, Phys. Lett. B 753, 482 (2016), arXiv:1509.00476 [hep-ph] .
  * Blümlein  _et al._ (1992) J. Blümlein _et al._ , International Journal of Modern Physics A 07, 3835 (1992), https://doi.org/10.1142/S0217751X9200171X .
  * Caputo  _et al._ (2022) A. Caputo, G. Raffelt, and E. Vitagliano, Phys. Rev. D 105, 035022 (2022), arXiv:2109.03244 [hep-ph] .
  * Kim (1979) J. E. Kim, Phys. Rev. Lett. 43, 103 (1979).
  * Shifman  _et al._ (1980) M. Shifman, A. Vainshtein, and V. Zakharov, Nuclear Physics B 166, 493 (1980).
  * Di Luzio  _et al._ (2020) L. Di Luzio, M. Giannotti, E. Nardi, and L. Visinelli, Phys. Rept. 870, 1 (2020), arXiv:2003.01100 [hep-ph] .
  * Alonso-Álvarez  _et al._ (2019) G. Alonso-Álvarez, M. B. Gavela, and P. Quilez, Eur. Phys. J. C 79, 223 (2019), arXiv:1811.05466 [hep-ph] .
  * Elahi  _et al._ (2023) F. Elahi, G. Elor, A. Kivel, J. Laux, S. Najjari, and F. Yu, (2023), arXiv:2301.08760 [hep-ph] .
  * Zhitnitsky (1980) A. R. Zhitnitsky, Sov. J. Nucl. Phys. 31, 260 (1980).
  * Dine  _et al._ (1981a) M. Dine, W. Fischler, and M. Srednicki, Physics Letters B 104, 199 (1981a).
  * Dine  _et al._ (1981b) M. Dine, W. Fischler, and M. Srednicki, Phys. Lett. B 104, 199 (1981b).
  * Giannotti  _et al._ (2017) M. Giannotti, I. G. Irastorza, J. Redondo, A. Ringwald, and K. Saikawa, JCAP 10, 010 (2017), arXiv:1708.02111 [hep-ph] .

##  Appendix A QCD Axion Models

The correlations between the QCD axion mass and its effective couplings are
given below, taken from ref. Di Luzio  _et al._ (2020). We simply reiterate
those correlations here for the convenience of the reader. The relation
between the Peccei-Quinn breaking scale $f_{a}$ and the axion mass is

$f_{a}=\bigg{(}\frac{5.691\times
10^{6}\textrm{eV}}{m_{a}}\bigg{)}\textrm{GeV}$ (9)

To find the correlations between the axion mass and its effective couplings to
photons in the Kim-Shifman-Vainshtein-Zakharov (KSVZ) benchmark model Kim
(1979); Shifman  _et al._ (1980) is then given by Eq. 10;

$\displaystyle g_{a\gamma}$
$\displaystyle=\frac{m_{a}}{\textrm{GeV}}\bigg{(}0.203\frac{E}{N}-0.39\bigg{)}$
(10)

We then consider a range of model parameter space by considering anomaly
number ratios of $E/N=44/3$ to $E/N=2$. This defines a band in
$(m_{a},g_{a\gamma})$ parameter space in which the QCD axion’s couplings and
mass may reside.

For the Dine-Fischler-Srednicki-Zhitnitsky (DFSZ) benchmark model Zhitnitsky
(1980); Dine  _et al._ (1981a, b); Dine and Fischler (1983), for which
couplings to electrons would be dominant relative to the photon couplings, we
take

$g_{ae}=\dfrac{m_{e}C_{ae}(m_{a},\tan\beta)}{f_{a}}$ (11)

where the coefficient $C_{ae}$ is dependent on the rotation angle $\beta$ for
the vacuum expectation values of the extended Higgs sector in DFSZI and DFSZII
models;

$\displaystyle\textrm{DFSZ(I):\, \, }C_{ae}$
$\displaystyle=-\frac{1}{3}\sin^{2}\beta+\textrm{loop factors}$ (12)
$\displaystyle\textrm{DFSZ(II):\, \, }C_{ae}$
$\displaystyle=\frac{1}{3}\sin^{2}\beta+\textrm{loop factors}$ (13)

Here we take $\tan\beta$ values between 0.25 and 120, which equates to
$\sin\beta=0.242536$ and $\sin\beta=0.999965$, respectively Giannotti  _et
al._ (2017).


# Edge-coloring a graph $G$ so that every copy of a graph $H$ has an odd color
class

Patrick Bennett 111Department of Mathematics, Western Michigan University,
Kalamazoo, MI<EMAIL_ADDRESS>Emily Heath 222Department of
Mathematics, Iowa State University, Ames, IA<EMAIL_ADDRESS>Research
partially supported by NSF RTG Grant DMS-1839918. Shira Zerbib 333Department
of of Mathematics, Iowa State University, Ames, IA<EMAIL_ADDRESS>Research partially supported by NSF Grant DMS-1953929.

###### Abstract

Recently, Alon [1] introduced the notion of an $H$-code for a graph $H$: a
collection of graphs on vertex set $[n]$ is an $H$-code if it contains no two
members whose symmetric difference is isomorphic to $H$. Let $D_{H}(n)$ denote
the maximum possible cardinality of an $H$-code, and let
$d_{H}(n)=D_{H}(n)/2^{n\choose 2}$. Alon observed that a lower bound on
$d_{H}(n)$ can be obtained by attaining an upper bound on the number of colors
needed to edge-color $K_{n}$ so that every copy of $H$ has an odd color class.

Motivated by this observation, we define $g(G,H)$ to be the minimum number of
colors needed to edge-color a graph $G$ so that every copy of $H$ has an odd
color class. We prove $g(K_{n},K_{5})\leq n^{o(1)}$ and
$g(K_{n,n},C_{4})=n/2+o(n)$. The first result shows
$d_{K_{5}}(n)\geq\frac{1}{n^{o(1)}}$ and was obtained independently in [12].

##  1 Introduction

Given a graph $G$ and a subgraph $H$, let $g(G,H)$ be the minimum number of
colors needed to edge-color $G$ so that every copy of $H$ sees some color an
odd number of times. The problem of determining $g(G,H)$ is a natural question
motivated by recent work of Alon [1] introducing the related notion of graph-
codes.

Let $V=[n]$ and let ${\cal H}$ be a family of graphs on the set of vertices
$[n]$ which is closed under isomorphism. A collection of graphs ${\cal F}$ on
$[n]$ is called an ${\cal H}$-code if it contains no two members whose
symmetric difference is a graph in ${\cal H}$. For the special case that
${\cal H}$ contains all copies of a single graph $H$ on $[n]$ this is called
an $H$-code. Let $D_{{\cal H}}(n)$ denote the maximum possible cardinality of
an ${\cal H}$-code, and let

$d_{{\cal H}}(n)=\frac{D_{{\cal H}}(n)}{2^{n\choose 2}}$

be the maximum possible fraction of the total number of graphs on $[n]$ in an
${\cal H}$-code. If ${\cal H}$ consists of all graphs isomorphic to one graph
$H$, denote $d_{{\cal H}}(n)$ by $d_{H}(n)$.

In the case where ${\cal H}$ consists of all graphs with independence number
at most 2, a result of Ellis, Filmus and Friedgut [10] shows that $d_{{\cal
H}}(n)=1/8$ for $n\geq 3$. Berger and Zhao [5] proved the analogous result for
the family ${\cal H}$ of graphs with independence number at most 3, showing
that $d_{{\cal H}}(n)=1/64$ for all $n\geq 4$. In [2], Alon, Gujgiczer,
Körner, Milojević, and Simonyi studied $D_{{\cal H}}(n)$ and $d_{{\cal H}}(n)$
for several families ${\cal H}$, such as disconnected graphs, graphs that are
not 2-connected, non-Hamiltonian graphs, graphs that contain or do not contain
a spanning star, graphs that contain an induced or non-induced copy of a fixed
graph $T$, and graphs that do not contain such a subgraph. Alon [1] also
studied the cases for cliques, stars, and matchings.

In [1], Alon mentions that the case ${\cal H}={\cal K}$, where ${\cal K}$ is
the family of all cliques, is of particular interest. This case is motivated
by a conjecture of Gowers (see [14, 1]). Further, he comments that
$d_{K_{4}}(n)\geq\frac{1}{n^{o(1)}}.$ This result follows from the existence
of an edge-coloring of $K_{n}$ by $n^{o(1)}$ colors with no copy of $K_{4}$ in
which every color appears an even number of times; that is,
$g(K_{n},K_{4})\leq n^{o(1)}$. A coloring with this property was given in [7],
modifying constructions in [8, 16]. In our first result, we show that the same
coloring has the property that there exists no copy of $K_{5}$ in which every
color appears an even number of times. We prove:

######  Theorem 1.1.

We have $g(K_{n},K_{5})\leq n^{o(1)}$.

This, together with a similar argument to that in [1], implies the following.

######  Theorem 1.2.

We have $d_{K_{5}}(n)\geq\frac{1}{n^{o(1)}}.$

Very recently, Ge, Xu, and Zhang [12] also independently obtained this result
using a similar method. They further note that $g(K_{n},K_{5})\geq\Omega(\log
n)$.

As is observed in [1], if every member of ${\cal H}$ has an odd number of
edges then $d_{{\cal H}}(n)\geq\frac{1}{2}$, as the family of all graphs on
$[n]$ with an even number of edges forms an ${\cal H}$-code. Thus, when
considering cliques, the next interesting case is the case of $H=K_{8}$. We do
not know if the same coloring, or some generalization of it, has the property
that there exists no copy of $K_{8}$ in which every color appears an even
number of times. As our method relies on case analysis, it will be hard to
generalize it to the case of $K_{8}$.

An upper bound on $g(K_{n},K_{p})$ for larger $p$ follows from recent work of
Bennett, Delcourt, Li, and Postle [3] on the _generalized Ramsey number_
$f(n,p,q)$, that is, the minimum number of colors needed to color $E(K_{n})$
so that every copy of $K_{p}$ sees at least $q$ colors. Until recently, the
best upper bound on $f(n,p,q)$ for general $p,q$ was the original bound of
Erdős and Gyárfás [11] obtained using the Lovász Local Lemma. Bennett, Dudek,
and English [4] used a random greedy process to improve this bound by a
logarithmic factor for values of $q$ and $p$ with $q\leq(p^{2}-26p+55)/4$. In
[3], their result is extended to all values of $p$ and $q$ except at the
values $q=\binom{p}{2}-p+2$ and
$q=\binom{p}{2}-\left\lfloor\frac{p}{2}\right\rfloor+2$, where the local lemma
bound is known to be tight.

######  Theorem 1.3 (Bennett, Delcourt, Li, Postle [3]).

For fixed positive integers $p,q$ with $p-2$ not divisible by
$\binom{p}{2}-q+1$, we have

$f(n,p,q)=O\left(\left(\frac{n^{p-2}}{\log
n}\right)^{\frac{1}{\binom{p}{2}-q+1}}\right).$

In fact, Theorem 1.3 is generalized in [3] to give an analogous upper bound in
a list-coloring setting for any subgraph (not only cliques) and in hypergraphs
with higher uniformity. Note that Theorem 1.3 with $q=\binom{p}{2}/2+1$
implies that

$g(K_{n},K_{p})=O\left(\left(\frac{n^{p-2}}{\log
n}\right)^{2/\binom{p}{2}}\right).$

Indeed, any $(p,\frac{1}{2}\binom{p}{2}+1)$-coloring of $K_{n}$ has the
stronger condition that some color must appear exactly once in each
$p$-clique.

Our second result focuses on the question of determining $g(K_{n,n},C_{4})$.
In order to prove an upper bound, we will construct a coloring using the
“forbidden submatching method” recently introduced by Delcourt and Postle [9]
and independently by Glock, Joos, Kim, Kühn, and Lichev [13] as “conflict-free
hypergraph matchings.” In [15], Joos and Mubayi use the variant of the method
from [13] along with a probabilistic argument to show that
$f(K_{n,n},C_{4},3)=\frac{2}{3}n+o(n)$. Note that this implies
$g(K_{n,n},C_{4})\leq\frac{2}{3}n+o(n)$. We use a similar approach to show the
stronger upper bound of $g(K_{n,n},C_{4})\leq\frac{1}{2}n+o(n)$. As such,
combined with a short proof that $g(K_{n,n},C_{4})>n/2$, we obtain the
following result.

######  Theorem 1.4.

We have $g(K_{n,n},C_{4})=\frac{1}{2}n+o(n).$

The rest of the paper is organized as follows. In Section 2, we prove Theorem
1.2. In Section 3, we give the necessary preliminaries to state the main tool
for the proof of Theorem 1.4, namely the theorem on forbidden submatchings
given in [13]. Finally, in Section 4, we prove Theorem 1.4.

##  2 Proof of Theorem 1.1

A _$(p,q)$ -coloring_ of $K_{n}$ is an edge-coloring in which each $p$-clique
receives at least $q$ colors. In 2015, Conlon, Fox, Lee, and Sudakov [8]
constructed a $(p,p-1)$-coloring with $n^{o(1)}$ colors. In 2017, Cameron and
Heath [6] used a modified version of their $(5,4)$-coloring as part of their
construction of a $(5,5)$-coloring with $n^{1/3+o(1)}$ colors. We will prove
that this “Modified CFLS” $(5,4)$-coloring using $n^{o(1)}$ colors guarantees
that every $K_{5}$ contains some color an odd number of times.

Let $n=2^{m^{2}}$ for some positive integers $m$. We will view the vertices of
$K_{n}$ as binary strings of length $m^{2}$; that is, $V=\\{0,1\\}^{m^{2}}$.
For each $v\in V$, let $v^{(i)}$ denote the $i$th block of bits of length $m$
in $v$, so

$v=\left(v^{(1)},v^{(2)},\ldots,v^{(m)}\right),$

where each $v^{(i)}\in\\{0,1\\}^{m}$.

Note that we can assign a linear order to the vertices by considering each to
be an integer represented in binary and taking the standard ordering of these
integers. That is, $x<y$ if and only if the first bit of difference between
$x$ and $y$ is zero in $x$ and one in $y$. Furthermore, each $m$-block of our
vertices can be viewed as a binary representation of an integer from 0 to
$2^{m}-1$, so the $m$-blocks can be ordered in the same way.

Let $x,y\in V$ such that $x<y$. Let $i$ be the first index for which
$x^{(i)}\neq y^{(i)}$, and for each $k\in[m]$, let $i_{k}$ be the first index
at which a bit of $x^{(k)}$ differs from the corresponding bit of $y^{(k)}$,
or $i_{k}=0$ if $x^{(k)}=y^{(k)}$. In addition, for each $k\in[m]$, let

$\delta_{k}=\begin{cases}+1&x^{(k)}\leq y^{(k)},\\\
-1&x^{(k)}>y^{(k)}.\end{cases}$

The _Modified CFLS coloring_ assigns to the edge $xy$ the color

$\varphi(xy)=\left(\left(i,\\{x,y\\}\right),i_{1},i_{2},\ldots,i_{m},\delta_{1},\delta_{2},\ldots,\delta_{m}\right).$

It was shown in [6] that the number of colors in the Modified CFLS coloring is
$2^{O(\sqrt{\log n}\log\log n)}.$ We will now show that if $K_{n}$ is edge-
colored by the Modified CFLS coloring then every copy of $K_{5}$ has an odd
color class.

Let $E(K_{n})$ be colored by the Modified CFLS coloring $\varphi$ given by
Cameron and Heath [6]. Then every copy of $K_{5}$ contains at least 4 distinct
colors. If a copy of $K_{5}$ contains at least six colors, then clearly some
color appears in this $K_{5}$ exactly once, giving us the odd color we desire.
Therefore, we only need to consider copies of $K_{5}$ which contain four or
five colors under $\varphi$. The case where $K_{5}$ contains exactly four
colors is easy to understand; indeed, Cameron and Heath [7] characterized the
colorings of $K_{5}$ with exactly four colors which can appear under
$\varphi$.

######  Theorem 2.1.

Let $p\geq 3$ and let the edges of $K_{n}$ be colored with the Modified CFLS
$(p,p-1)$-coloring. The only $p$-cliques that contain exactly $p-1$ distinct
edge-colors are isomorphic (as edge-colored graphs) to one of the edge-colored
$p$-cliques given in the definition below.

######  Definition 2.2.

Given an edge-coloring $f:E(K_{n})\rightarrow C$, we say that a subset
$S\subseteq V(K_{n})$ has a _leftover structure under $f$_ if either $|S|=1$
or there exists a bipartition of $S$ into nonempty sets $A$ and $B$ for which

  * •

$A$ and $B$ each have a leftover structure under $f$;

  * •

$f(A)\cap f(B)=\emptyset$; and

  * •

there is a fixed color $\alpha\in C$ such that $f(a,b)=\alpha$ for all $a\in
A$ and all $b\in B$, and $\alpha\notin f(A)$ and $\alpha\notin f(B)$.

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$

Figure 1: The three leftover colorings of $K_{5}$ with four colors under
$\varphi$

In particular, there are only three such leftover configurations in the $p=5$
setting, shown in Figure 1 below. Note that in each case, there is a color
which appears exactly once. Thus, it suffices to consider colorings of $K_{5}$
with exactly five colors.

Assume towards a contradiction that $\varphi$ permits some coloring of $K_{5}$
with exactly 5 colors, each appearing an even number of times. Call these
colors $\alpha,\beta,\gamma,\pi,$ and $\theta$. Then each color class is
either a matching of two disjoint edges or a path with two adjacent edges. We
say that such colorings of $K_{5}$ are 2-2-2-2-2 colorings.

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$ (a)

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$ (b)

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$ (c)

Figure 2: Forbidden configurations under $\varphi$ with four vertices

######  Lemma 2.3.

No vertex in a 2-2-2-2-2 coloring of $K_{5}$ can be incident to edges of only
two colors.

###### Proof.

If there was such a vertex, then the other four vertices would form a copy of
$K_{4}$ with three colors appearing twice each. But, each such coloring of
$K_{4}$ is one of the configurations shown in Figure 2, which were shown to be
forbidden under $\varphi$ in [6]. ∎

Now we will prove a series of lemmas showing that several other common
configurations (in Figure 3) are forbidden under $\varphi$. Throughout these
proofs, when referring to some color $\alpha$, we will let $\alpha_{0}$ denote
the 0-coordinate of the color (of the form $(i,\\{x,y\\})$) and let
$\alpha_{k}$ denote the $k$-coordinate of the color, that is, the index of the
first bit of difference between the $k$th blocks. Furthermore, if
$x,y\in\\{0,1\\}^{m^{2}}$ are two vectors and $x^{(k)}=y^{(k)}$ (where
$x^{(k)}$ is the $k$th $m$-block of $x$), then we say that $x$ and $y$ _agree
at $k$_; otherwise, we say $x$ and $y$ _disagree at $k$_.

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$ (a)

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$ (b)

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$ (c)

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$ (d)

$\bullet$$a$$\bullet$$b$$\bullet$$c$$\bullet$$d$$\bullet$$e$ (e)

Figure 3: Forbidden configurations under $\varphi$ with five vertices

######  Lemma 2.4.

The configuration with five distinct vertices $a,b,c,d,e\in V$ for which
$\varphi(be)=\varphi(cd)$, $\varphi(ab)=\varphi(de)$, and
$\varphi(bc)=\varphi(ae)$, as in Figure 3(a), is forbidden.

###### Proof.

Assume towards a contradiction that for distinct vertices $a,b,c,d,e$, we have
$\varphi(be)=\varphi(cd)=\alpha$, $\varphi(ab)=\varphi(de)=\beta$, and
$\varphi(bc)=\varphi(ae)=\gamma$. Let $\alpha_{0}=(i,\\{x,y\\})$. First
suppose $b^{(i)}=c^{(i)}=x$ and $e^{(i)}=d^{(i)}=y$. Then $\beta_{i}=0$ since
$d$ and $e$ agree at $i$, and $\gamma_{i}=0$ since $b$ and $c$ agree at $i$.
But then $a^{(i)}=x$ (because $\varphi(ab)=\beta$, $\beta_{i}=0$ and
$b^{(i)}=x$), and similarly $a^{(i)}=y$ (because $\varphi(ae)=\gamma$,
$\gamma_{i}=0$ and $e^{(i)}=y$), a contradiction since $x\neq y$. So, instead
suppose that $b^{(i)}=d^{(i)}=x$ and $c^{(i)}=e^{(i)}=y$. Then $\beta_{i}=t$,
the first index of difference between $d^{(i)}=x$ and $e^{(i)}=y$. Similarly,
$\gamma_{i}=t$. Let $a^{(i)}=w$. Then since $\varphi(ab)=\beta$ and
$\beta_{i}=t$, we know $x_{j}=w_{j}$ for all $1\leq j\leq t-1$ and $x_{t}\neq
w_{t}$. Similarly, since $\varphi(ae)=\gamma$ and $\gamma_{i}=t$, we have
$y_{j}=w_{j}$ for all $1\leq j\leq t-1$ and $y_{t}\neq w_{t}.$ But since
$\\{x_{t},y_{t}\\}=\\{0,1\\}$, this leaves no choice for $w_{t}$, a
contradiction. ∎

######  Lemma 2.5.

The configuration with five distinct vertices $a,b,c,d,e\in V$ for which
$\varphi(ac)=\varphi(bc)$, $\varphi(ab)=\varphi(bd)$,
$\varphi(ad)=\varphi(de)$, and $\varphi(ae)=\varphi(ec)$, as in Figure 3(b),
is forbidden.

###### Proof.

Assume for contradiction that for distinct vertices $a,b,c,d,e$, we have
$\varphi(ac)=\varphi(bc)=\alpha$, $\varphi(ab)=\varphi(bd)=\beta$,
$\varphi(ad)=\varphi(de)=\gamma$, and $\varphi(ae)=\varphi(ec)=\pi$. Let
$\alpha_{0}=(i,\\{x,y\\})$, and let $c^{(i)}=x$ and $a^{(i)}=b^{(i)}=y$. Then
$\beta_{i}=0$ since $a$ and $b$ agree at $i$, which implies $d^{(i)}=y$ as
well. Now we conclude $\gamma_{i}=0$ since $a$ and $d$ agree at $i$, which
implies $e^{(i)}=y$ too. But now $\pi_{i}=0$ since $a$ and $e$ agree at $i$,
while also $\pi_{i}\neq 0$ since $c$ and $e$ disagree at $i$, a contradiction.
∎

######  Lemma 2.6.

Any 2-2-2-2-2 coloring of $K_{5}$ with a rainbow 5-cycle and at least one
matching, as in Figure 3(c), is forbidden under $\varphi$.

###### Proof.

Assume towards a contradiction that for distinct vertices $a,b,c,d,e\in V$, we
have $\varphi(be)=\varphi(cd)=\alpha$, $\varphi(ab)=\beta$,
$\varphi(bc)=\gamma$, $\varphi(de)=\pi$, and $\varphi(ea)=\theta$. Note that
since this is a 2-2-2-2-2 coloring of $K_{5}$, we have
$\\{\varphi(bd),\varphi(ce)\\}=\\{\beta,\theta\\}$, since otherwise we would
find a copy of the forbidden configuration shown in Figure 2(a) using the
colors $\\{\alpha,\gamma\\}$ or $\\{\alpha,\pi\\}$. This implies
$\\{\varphi(ac),\varphi(ad)\\}=\\{\pi,\gamma\\}$.

Suppose first that $\varphi(bd)=\beta$ and $\varphi(ce)=\theta$. If
$\varphi(ac)=\pi$ and $\varphi(ad)=\gamma$, we find the forbidden
configuration shown in Figure 3(a) in colors $\\{\alpha,\gamma,\pi\\}$. If
instead $\varphi(ac)=\gamma$ and $\varphi(ad)=\pi$, then we find the forbidden
configuration shown in Figure 3(b) in colors $\\{\beta,\gamma,\pi,\theta\\}$.
So, we must have $\varphi(bd)=\theta$ and $\varphi(ce)=\beta$, and we get the
forbidden configuration shown in Figure 3(a) in colors
$\\{\alpha,\beta,\theta\\}$, a contradiction. ∎

######  Lemma 2.7.

The configuration with five distinct vertices $a,b,c,d,e\in V$ for which
$\varphi(bc)=\varphi(de)$, $\varphi(ad)=\varphi(cd)$, and
$\varphi(ab)=\varphi(ac)$ as in Figure 3(d), is forbidden.

###### Proof.

Assume towards a contradiction that for distinct vertices $a,b,c,d,e$, we have
$\varphi(bc)=\varphi(de)=\alpha$, $\varphi(ad)=\varphi(cd)=\beta$, and
$\varphi(ab)=\varphi(ac)=\gamma$. Let $\alpha_{0}=(i,\\{x,y\\})$. First
suppose $b^{(i)}=e^{(i)}=x$ and $c^{(i)}=d^{(i)}=y$. Then $\beta_{i}=0$ since
$b$ and $c$ agree at $i$, and hence $a^{(i)}=y$ as well. But now
$\gamma_{i}=0$ since $a$ and $c$ agree at $i$ while also $\gamma_{i}\neq 0$
since $a$ and $b$ disagree at $i$, a contradiction. So, it must be the case
that $b^{(i)}=d^{(i)}=x$ and $c^{(i)}=e^{(i)}=y$.

Now $\beta_{i}=t$, the first index of difference between $c^{(i)}=y$ and
$d^{(i)}=x$. Say $a^{(i)}=w$. Since $\varphi(ad)=\beta$, we know that
$x_{j}=w_{j}$ for all $1\leq j\leq t-1$ and $x_{t}\neq w_{t}$. Then since
$x_{t}\neq y_{t}$ as well, we have $w_{t}=y_{t}$. Furthermore, $\beta_{i}=t$
implies that $w_{j}=x_{j}=y_{j}$ for all $1\leq j\leq t-1$, so the first index
of difference between $w$ and $y$ must be greater than $t$. Now consider
$\gamma_{i}$. Since $\varphi(ac)=\gamma$, we know $\gamma_{i}>t$. But
$\varphi(ab)=\gamma$ implies that $\gamma_{i}=t$, a contradiction. ∎

######  Lemma 2.8.

The configuration with five distinct vertices $a,b,c,d,e\in V$ for which
$\varphi(ab)=\varphi(be)$, $\varphi(bc)=\varphi(ac)$,
$\varphi(cd)=\varphi(bd)$, $\varphi(de)=\varphi(ce)$, and
$\varphi(ae)=\varphi(ad)$, as in Figure 3(e), is forbidden.

###### Proof.

Assume towards a contradiction that for distinct vertices $a,b,c,d,e$, we have
$\varphi(ab)=\varphi(be)=\alpha$, $\varphi(bc)=\varphi(ac)=\beta$,
$\varphi(cd)=\varphi(bd)=\gamma$, $\varphi(de)=\varphi(ce)=\pi$, and
$\varphi(ae)=\varphi(ad)=\theta$. Let $\alpha_{0}=(i,\\{x,y\\})$, and let
$a^{(i)}=e^{(i)}=x$ and $b^{(i)}=y$. Then $\theta_{i}=0$ since $a$ and $e$
agree at $i$, which implies $d^{(i)}=x$ as well. Similarly, $\pi_{i}=0$ since
$d$ and $e$ agree at $i$, which forces $c^{(i)}=x$. But now $\gamma_{i}=0$
because $c$ and $d$ agree at $i$, while $\gamma_{i}\neq 0$ since $b$ and $d$
disagree at $i$, a contradiction. ∎

Finally, we are ready to show that every 2-2-2-2-2 coloring of $K_{5}$ is
forbidden by $\varphi$. We will do this by splitting our proof into cases
based on the number of matchings and paths in a 2-2-2-2-2 configuration.

######  Lemma 2.9.

There is no 2-2-2-2-2 configuration in $\varphi$ in which all five color
classes are paths of length 2.

###### Proof.

Assume for contradiction that such a coloring of $K_{5}$ exists under
$\varphi$. First, we will show that this $K_{5}$ must contain a rainbow cycle.
To this end, note that each monochromatic path of length 2 is contained in two
5-cycles in our $K_{5}$. So if all the 5 colors are length 2 paths, there are
at most 10 cycles in $K_{5}$ that are not rainbow. But since there are 12
distinct 5-cycles in $K_{5}$, there must be at least two 5-cycles containing
no monochromatic path; that is, there must be some rainbow cycle.

Consider this rainbow cycle and suppose $\varphi(ab)=\alpha$,
$\varphi(bc)=\beta$, $\varphi(cd)=\gamma$, $\varphi(de)=\pi$, and
$\varphi(ea)=\theta$. Since the color class of $\alpha$ forms a length 2 path,
there are two cases up to symmetry: either $\varphi(be)=\alpha$, or
$\varphi(bd)=\alpha$.

First suppose $\varphi(be)=\alpha$. Note that
$\varphi(bd)\in\\{\gamma,\pi\\}$, because by Lemma 2.3, $b$ must be adjacent
to edges of at least three colors, and we know each color class is a path.
This forces $\varphi(ad)=\theta$ because $d$ must be adjacent to edges of at
least three colors by Lemma 2.3, and since $\beta$ forms a path. If
$\varphi(bd)=\pi$, then $\\{\varphi(ac),\varphi(ce)\\}=\\{\beta,\gamma\\}$,
contradicting Lemma 2.3 at $c$. So, it must be the case that
$\varphi(bd)=\gamma$ and $\\{\varphi(ac),\varphi(ce)\\}=\\{\beta,\pi\\}$.
Since $\pi$ forms a path, this implies $\varphi(ac)=\beta$ and
$\varphi(ce)=\pi$. However, this is the forbidden configuration in Figure
3(e), so we reach a contradiction.

Now instead suppose $\varphi(bd)=\alpha$. By Lemma 2.3, and because $\gamma$
must form a path, we have $\varphi(be)\in\\{\pi,\theta\\}$. Then
$\varphi(ce)\in\\{\beta,\gamma\\}$ since Lemma 2.3 requires at least three
colors on the edges incident to $e$. This forces $\varphi(ac)=\theta$, which
in turns implies $\varphi(be)=\pi$. Finally, since $\beta$ must be a path, we
have $\varphi(ad)=\gamma$ and $\varphi(ce)=\beta$. But now we again have the
forbidden configuration in Figure 3(e), a contradiction. ∎

######  Lemma 2.10.

There is no 2-2-2-2-2 configuration in $\varphi$ in which one color classes is
a matching and the rest are paths.

###### Proof.

Assume towards a contradiction that distinct vertices $a,b,c,d,e\in V$ form a
2-2-2-2-2 coloring of $K_{5}$ where one color class is a matching and four are
paths. Let $\varphi(ab)=\varphi(cd)=\alpha$. Consider the path in color
$\beta$. If $e$ is incident to two edges of color $\beta$, then by Lemma 2.3,
the other two edges incident to $e$ must receive distinct colors, say $\gamma$
and $\pi$. Now the fifth color $\theta$ must appear on a path in the subgraph
induced by $\\{a,b,c,d\\}$. But this forms a forbidden configuration as in
Figure 2(a) in colors $\theta$ and $\alpha$, a contradiction. Since the same
argument applies to $\gamma$, $\pi$, and $\theta$, we know $e$ is incident to
edges of four distinct colors. However, there is only one such configuration
in which the color classes of $\beta,\gamma,\pi$, and $\theta$ are all paths,
and it is the forbidden configuration shown in Figure 3(b), so we again reach
a contradiction. ∎

######  Lemma 2.11.

There is no 2-2-2-2-2 configuration in $\varphi$ in which two color classes
are matchings and three are paths.

###### Proof.

Assume for contradiction that distinct vertices $a,b,c,d,e\in V$ form a
2-2-2-2-2 coloring of $K_{5}$ with matchings in colors $\alpha$ and $\beta$
and paths in colors $\gamma,\pi,\theta$. If $\alpha$ and $\beta$ form an
alternating path, say $\varphi(ab)=\varphi(cd)=\alpha$ and
$\varphi(bc)=\varphi(de)=\beta$, then consider the edge $bd$. Without loss of
generality, $\varphi(bd)=\gamma$. If $\varphi(be)=\gamma$ or
$\varphi(ad)=\gamma$, then there is a copy of the forbidden configuration in
Figure 2(a). So, the other edge of color $\gamma$ must be one of $ac,ce,$ or
$ae$. But in these cases, $\gamma$ would form a matching rather than a path, a
contradiction.

Now suppose $\alpha$ and $\beta$ form an alternating cycle, say
$\varphi(ab)=\varphi(cd)=\alpha$ and $\varphi(bc)=\varphi(ad)=\beta$. Since
all remaining edges receives colors in $\\{\gamma,\pi,\theta\\}$, we know that
the two edges incident to $e$ must receive the same color. Without loss of
generality, say $\varphi(ae)=\varphi(be)=\gamma$. Lemma 2.3 implies that $\pi$
and $\theta$ each appear on one of the edges $ce$ and $de$. Furthermore, since
the color classes of $\pi$ and $\theta$ are paths, we may assume that
$\varphi(ac)=\varphi(ce)=\pi$ and $\varphi(bd)=\varphi(de)=\theta$. But now
the colors $\alpha,\gamma$, and $\pi$ form a forbidden configuration as in
Figure 3(d), a contradiction. ∎

######  Lemma 2.12.

There is no 2-2-2-2-2 configuration in $\varphi$ in which three color classes
are matchings and two are paths.

###### Proof.

Assume for contradiction that distinct vertices $a,b,c,d,e\in V$ form a
2-2-2-2-2 coloring of $K_{5}$ with three color classes that are matchings and
two color classes that are paths. Let $\varphi(ab)=\varphi(bc)=\alpha$ and
$\varphi(ac)=\beta$. Then either $\beta$ is a path, or a matching.

First suppose $\beta$ forms a path. Without loss of generality,
$\varphi(cd)=\beta$. Then $ad$ receives some third color, say
$\varphi(ad)=\gamma$, and $\gamma$ forms a matching. We cannot have
$\varphi(ec)=\gamma$ without forming a forbidden configuration as in Figure
2(a) with colors $\\{\beta,\gamma\\}$, so $\varphi(be)=\gamma$ is forced. Now
the remaining three edges incident to $e$ should be colored with the two
colors $\pi$ and $\theta$, contradicting the fact that $\pi$ and $\theta$ both
form a matching each.

Therefore, $\beta$ must form a matching. Since we must avoid the forbidden
configuration in Figure 2(a), the other edge colored $\beta$ cannot be
incident to $b$, which implies $\varphi(de)=\beta$. Consider where the second
monochromatic path, say in color $\gamma$, can occur. If $b$ is not incident
to an edge of color $\gamma$, then we find a forbidden configuration as in
Figure 2(a) in colors $\\{\beta,\gamma\\}$. So, $b$ must be incident to an
edge of color $\gamma$, say $\varphi(bd)=\gamma$. By Lemma 2.3,
$\varphi(be)\neq\gamma$, so either $cd$ or $ad$ also receive color $\gamma$.

In both cases, there are three remaining edges incident to $e$ which must be
colored with $\\{\pi,\theta\\}$, but both $\pi$ and $\theta$ form matchings in
the $K_{5}$, a contradiction. ∎

######  Lemma 2.13.

There is no 2-2-2-2-2 configuration in $\varphi$ in which four color classes
are matchings and one is a path.

###### Proof.

Assume towards a contradiction that distinct vertices $a,b,c,d,e\in V$ form a
2-2-2-2-2 coloring of $K_{5}$ with a path in color $\alpha$ and four
matchings. Let $\varphi(ab)=\varphi(bc)=\alpha$, and say $\varphi(bc)=\beta$.
Then $\beta$ cannot appear on the edges $bd$ or $be$, otherwise there is a
copy of the forbidden configuration in Figure 2(a). So, since $\beta$ forms a
matching, we must have $\varphi(de)=\beta$. Now the remaining six edges in
this $K_{5}$ form a copy of $K_{2,3}$ on vertex set $\\{a,b,c\\}\cup\\{d,e\\}$
which must be colored with three colors, but this cannot occur when all three
color classes are matchings of size two. ∎

######  Lemma 2.14.

There is no 2-2-2-2-2 configuration in $\varphi$ in which all five color
classes are matchings.

###### Proof.

Assume towards a contradiction that distinct vertices $a,b,c,d,e\in V$ form a
2-2-2-2-2 coloring of $K_{5}$ where each color class is a matching. Without
loss of generality, assume $\varphi(ab)=\varphi(cd)=\alpha$ and
$\varphi(bc)=\beta$. Then up to symmetry, there are two cases: either
$\varphi(ad)=\beta$ or $\varphi(de)=\beta$.

Consider the case $\varphi(ad)=\beta$. Let $\varphi(ae)=\gamma$. Then since
$\gamma$ is a matching, we must have $\varphi(bd)=\gamma$ as well. But then
the remaining two colors cannot both form matchings, since two of the edges
$be,ce,$ and $de$ must receive the same color by pigeon-hole principle.

Thus, we may assume $\varphi(de)=\beta$ instead. Let $\varphi(ae)=\gamma$.
Then since $\gamma$ must form a matching, we have $\varphi(bd)=\gamma$ as
well. However, this forms the forbidden configuration shown in Figure 3(a), a
contradiction. ∎

Combining the results of Lemmas 2.9-2.14 shows that $\varphi$ forbids all
2-2-2-2-2 colorings of $K_{5}$. Therefore, any $K_{5}$ which appears under
$\varphi$ must contain some color an odd number of times. ∎

##  3 Forbidden submatching method

We will use the simplified version presented in [15] of the conflict-free
hypergraph matching theorem from [13] to prove Theorem 1.4. In order to state
this theorem, we will need to introduce some terminology and notation.

Given a hypergraph ${\cal H}$ and a vertex $v\in V({\cal H})$, its _degree_
$\deg_{{\cal H}}(v)$ is the number of edges in ${\cal H}$ containing $v$. The
maximum degree and minimum degree of ${\cal H}$ are denoted by $\Delta({\cal
H})$ and $\delta({\cal H})$, respectively. For $j\geq 2$, $\Delta_{j}({\cal
H})$ denotes the maximum number of edges in ${\cal H}$ which contain a
particular set of $j$ vertices, over all such sets.

In addition, for a (not necessarily uniform) hypergraph ${\cal C}$ and an
integer $k$, let ${\cal C}^{(k)}$ be the set of edges in ${\cal C}$ of size
$k$. For a vertex $u\in V({\cal C})$, let ${\cal C}_{u}$ denote the hypergraph
$\\{C\backslash\\{u\\}\mid C\in E({\cal C}),u\in C\\}$.

Given a hypergraph ${\cal H}$, a hypergraph ${\cal C}$ is a _conflict system_
for ${\cal H}$ if $V({\cal C})=E({\cal H})$. A set of edges $E\subset{\cal H}$
is _${\cal C}$ -free_ if $E$ contains no subset $C\in{\cal C}$. Given integers
$d\geq 1$, $\ell\geq 3$, and ${\varepsilon}\in(0,1)$, we say ${\cal C}$ is
_$(d,\ell,{\varepsilon})$ -bounded_ if ${\cal C}$ satisfies the following
conditions:

  1. (C1)

$3\leq|C|\leq\ell$ for all $C\in{\cal C}$;

  2. (C2)

$\Delta({\cal C}^{(j)})\leq\ell d^{j-1}$ for all $3\leq j\leq\ell$;

  3. (C3)

$\Delta_{j^{\prime}}({\cal C}^{(j)})\leq d^{j-j^{\prime}-{\varepsilon}}$ for
all $2\leq j^{\prime}<j\leq\ell$.

Finally, given a $(d,\ell,{\varepsilon})$-bounded conflict system ${\cal C}$
for a hypergraph ${\cal H}$, we will define a type of weight function which
can be used to guarantee that the almost-perfect matching given by Theorem 3.1
below satisfies certain quasirandom properties. We say a function
$w:\binom{{\cal H}}{j}\rightarrow[0,\ell]$ for $j\in\mathbb{N}$ is a _test
function_ for ${\cal H}$ if $w(E)=0$ whenever $E\in\binom{{\cal H}}{j}$ is not
a matching, and we say $w$ is _$j$ -uniform_. For a function
$w:A\rightarrow\mathbb{R}$ and a finite set $X\subset A$, let
$w(X):=\sum_{x\in X}w(x)$. If $w$ is a $j$-uniform test function, then for
each $E\subset{\cal H}$, let $w(E)=w(\binom{E}{j})$. Given $j,d\in\mathbb{N}$,
${\varepsilon}>0$, and a conflict system ${\cal C}$ for hypergraph ${\cal H}$,
we say a $j$-uniform test function $w$ for ${\cal H}$ is
_$(d,{\varepsilon},{\cal C})$ -trackable_ if $w$ satisfies the following
conditions:

  1. (W1)

$w({\cal H})\geq d^{j+{\varepsilon}}$;

  2. (W2)

$w(\\{{E\in\binom{{\cal H}}{j}:E\supseteq E^{\prime}\\})\leq w({\cal
H}})/d^{j^{\prime}+{\varepsilon}}$ for all $j^{\prime}\in[j-1]$ and
$E^{\prime}\in\binom{{\cal H}}{j^{\prime}}$;

  3. (W3)

$|({\cal C}_{e})^{(j^{\prime})}\cap({\cal C}_{f})^{(j^{\prime})}|\leq
d^{j^{\prime}-{\varepsilon}}$ for all $e,f\in{\cal H}$ with
$w(\\{E\in\binom{{\cal H}}{j}:e,f\in E\\})>0$ and all $j^{\prime}\in[\ell-1]$;

  4. (W4)

$w(E)=0$ for all $E\in\binom{{\cal H}}{j}$ that are not ${\cal C}$-free.

######  Theorem 3.1 ([13], Theorem 3.3).

For all $k,\ell\geq 2$, there exists ${\varepsilon}_{0}>0$ such that for all
${\varepsilon}\in(0,{\varepsilon}_{0})$, there exists $d_{0}$ such that the
following holds for all $d\geq d_{0}$. Suppose ${\cal H}$ is a $k$-regular
hypergraph on $n\leq\exp(d^{{\varepsilon}^{3}})$ vertices with
$(1-d^{-{\varepsilon}})d\leq\delta({\cal H})\leq\Delta({\cal H})\leq d$ and
$\Delta_{2}({\cal H})\leq d^{1-{\varepsilon}}$. Suppose ${\cal C}$ is a
$(d,\ell,{\varepsilon})$-bounded conflict system for ${\cal H}$, and suppose
${\cal W}$ is a set of $(d,{\varepsilon},{\cal C})$-trackable test functions
for ${\cal H}$ of uniformity at most $\ell$ with $|{\cal
W}|\leq\exp(d^{{\varepsilon}^{3}})$. Then, there exists a ${\cal C}$-free
matching ${\cal M}\subset{\cal H}$ of size at least
$(1-d^{-{\varepsilon}^{3}})n/k$ with $w({\cal M})=(1\pm
d^{-{\varepsilon}^{3}})d^{-j}w({\cal H}))$ for all $j$-uniform $w\in{\cal W}$.

We will say that a hypergraph ${\cal H}$ with
$(1-d^{-{\varepsilon}})d\leq\delta({\cal H})\leq\Delta({\cal H})\leq d$ is
_almost $d$-regular._

##  4 Proof of Theorem 1.4

First, observe that $g(K_{n,n},C_{4})>n/2$. Indeed, let $V(K_{n,n})=X\cup Y$
and suppose the edges of $K_{n,n}$ are colored with at most $n/2$ colors. Then
for each vertex $x\in X$, there are at least $n/2$ pairs $u,v\in Y$ such that
$xu$ and $xv$ receive the same color. Since there are $\binom{n}{2}$ pairs of
vertices in $Y$, the pigeonhole principle implies that there must be two
vertices $x,z\in X$ such that $xu$ and $xv$ share a color and $zu$ and $zv$
share a color, giving a copy of $C_{4}$ with no color appearing an odd number
of times.

From now on, we remove the ceiling function notation in order to make the
proof easier to read. However, whenever $n$ is odd, when we write
$\frac{n}{2}$ we mean $\lceil\frac{n}{2}\rceil$.

In order to prove the upper bound in Theorem 1.4, we will construct a coloring
of $K_{n,n}$ in two stages. The coloring in the first stage will use $k=n/2$
colors to color a majority of the edges of $K_{n,n}$. To determine this
coloring, we define appropriate hypergraphs ${\cal H}$ and ${\cal C}$ for
which a ${\cal C}$-free matching in ${\cal H}$ corresponds to a partial
coloring of $K_{n,n}$ with monochromatic copies of $C_{6}$. Each copy of
$C_{4}$ in the resulting coloring sees some color an odd number of times.

Theorem 4.1 below guarantees that our choices of ${\cal H}$ and ${\cal C}$
satisfy the requirements for applying the forbidding submatching method to
find the desired matching. In the second stage of the coloring, we then
randomly color the remaining uncolored edges using a new set of $o(n)$ colors.

######  Theorem 4.1.

There exists $\delta>0$ such that for all sufficiently large $n$ in terms of
$\delta$, there is an edge-coloring of a subgraph $F\subset K_{n,n}$ with at
most $n/2$ colors and the following properties:

  1. 1.

Every color class is a union of vertex-disjoint copies of $C_{6}$.

  2. 2.

Every copy of $C_{4}$ in $F$ intersects some color class in an odd number of
edges.

  3. 3.

The graph $L=K_{n,n}\setminus E(F)$ has maximum degree at most $n^{1-\delta}$.

  4. 4.

Let $V(K_{n,n})=X\cup Y$. For each $(x,y)\in X\times Y$, the number of edges
$x^{\prime}y^{\prime}\in E(L)$ with $x^{\prime}\in X\backslash\\{x\\}$,
$y^{\prime}\in Y\backslash\\{y\\}$ such that $xy^{\prime}$ and $yx^{\prime}$
receive the same color is at most $4n^{1-\delta}$.

###### Proof.

Let $U=\binom{X\cup Y}{2}$ and $V=\bigcup_{i\in[\frac{n}{2}]}V_{i}$, where
each $V_{i}$ is a copy of $X\cup Y$. We will denote the copy of $v\in X\cup Y$
in $V_{i}$ by $v^{i}$. Let ${\cal H}$ be the 18-uniform hypergraph with vertex
set $U\cup V$ and edges $e_{i}$ for each copy $e$ of $C_{6}$ in $K_{n,n}$ and
$i\in[\frac{n}{2}]$ defined as follows. Given a 6-cycle
$e=x_{1}y_{1}x_{2}y_{2}x_{3}y_{3}$ with $x_{j}\in X$ and $y_{j}\in Y$, let
${\cal H}$ contain the edge

$e_{i}=\\{x_{1}y_{1},y_{1}x_{2},x_{2}y_{2},y_{2}x_{3},x_{3}y_{3},y_{3}x_{1}\\}\cup\\{x_{1}x_{2},x_{2}x_{3},x_{1}x_{3},y_{1}y_{2},y_{2}y_{3},y_{1}y_{3}\\}\cup\\{x_{1}^{i},x_{2}^{i},x_{3}^{i},y_{1}^{i},y_{2}^{i},y_{3}^{i}\\}.$

Note that a matching in ${\cal H}$ corresponds to a set of edge-disjoint
monochromatic copies of $C_{6}$ in $K_{n,n}$. Furthermore, no vertex in the
matching appears in two cycles of the same color. Thus, a matching in ${\cal
H}$ yields an edge-coloring of a subgraph of $K_{n,n}$ with at most
$\frac{n}{2}$ colors which satisfies property (1) above.

The hypergraph ${\cal H}$ is essentially $d$-regular for $d=\frac{1}{2}n^{5}$.
Indeed, we can check that for each vertex $u$ in ${\cal H}$,
$d-O(n^{4})\leq\deg_{{\cal H}}(u)\leq d$. First, suppose $u\in V_{i}$ for some
$i$. There are $n^{3}\binom{n}{2}-O(n^{4})$ ways to pick an edge in ${\cal H}$
containing $u$, since there are $\binom{n}{2}$ choices for the neighbors of
$u$ and $n-O(1)$ choices for each of the remaining vertices along the cycle.
If instead $u=xy$ for some $x\in X$ and $y\in Y$, then there are
$\frac{1}{2}n$ ways to pick a color of an edge containing $xy$ and
$n^{4}-O(n^{3})$ ways to pick the remaining vertices along the cycle.
Similarly, if $u=xx^{\prime}$ for $x,x^{\prime}\in X$ (or $yy^{\prime}$ for
$y,y^{\prime}\in Y$), there are $\frac{1}{2}n^{5}-O(n^{4})$ edges in ${\cal
H}$ containing the edge. Thus, in each case, we have $\deg_{{\cal
H}}(u)=\frac{1}{2}n^{5}-O(n^{4})$.

Furthermore, we have $\Delta_{2}({\cal H})\leq d^{1-{\varepsilon}}$ for all
${\varepsilon}\in(0,\frac{1}{6})$, since each pair of vertices $u,v\in V({\cal
H})$ is contained in at most $O(n^{4})$ edges in ${\cal H}$.

Next we define a conflict system ${\cal C}$ for ${\cal H}$ with edges of size
3 and 4. Let $V({\cal C})=E({\cal H})$, and let the edges of ${\cal C}$
correspond to copies of $C_{4}$ in $K_{n,n}$ formed by two monochromatic
matchings of size 2. We will call these edges of ${\cal C}$ _conflicts_ , and
they correspond to sets of three or four monochromatic cycles in $K_{n,n}$.
That is, given four vertices $x,x^{\prime}\in X$ and $y,y^{\prime}\in Y$,
colors $i,j\in[\frac{n}{2}]$ and edges
$e_{i},e_{i}^{\prime},f_{j},f_{j}^{\prime}\in E({\cal H})$ (not necessarily
distinct) with $xy\in e_{i}$, $x^{\prime}y^{\prime}\in e^{\prime}_{i}$,
$xy^{\prime}\in f_{j}$, and $x^{\prime}y\in f^{\prime}_{j}$, we have
$\\{e_{i},e^{\prime}_{i},f_{j},f^{\prime}_{j}\\}\in E({\cal C})$. Note that we
do not need to consider conflicts of size 2: it is possible to have two
monochromatic copies $e,e^{\prime}$ of $C_{6}$ that form a copy of $C_{4}$
with alternating colors, however such $e,e^{\prime}$ would have to share two
vertices in $X$ (and two vertices in $Y$), and thus cannot appear together in
a matching of ${\cal H}$.

We will show that $\Delta({\cal C}^{(3)})=O(d^{2})$ and $\Delta({\cal
C}^{(4)})=O(d^{3})$. To this end, fix $e_{i}\in V({\cal C})$. Note that any
conflict in ${\cal C}^{(3)}$ containing $e_{i}$ must either have the form
$\\{e_{i},e_{i}^{\prime},f_{j}\\}$ or $\\{e_{i},f_{j},f^{\prime}_{j}\\}$ for
some copies $e^{\prime},f,f^{\prime}$ of $C_{6}$ in $K_{n,n}$ and some color
$j\in[\frac{n}{2}]\backslash\\{i\\}$. In either case, there are $O(n)$ ways to
pick $j$. If the edge has the form $\\{e_{i},e_{i}^{\prime},f_{j}\\}$, then
there are $O(n^{6})$ ways to pick $e^{\prime}$ and then $O(n^{2})$ ways to
pick $f$. If instead the edge has the form $\\{e_{i},f_{j},f_{j}^{\prime}\\}$,
then there are $O(n^{4})$ ways to pick $f$ and $O(n^{4})$ ways to pick
$f^{\prime}$. Thus, in either case, $d_{{\cal C}}(e_{i})=O(n^{9})$, and we
have $\Delta({\cal C}^{(3)})=O(d^{2})$. Similarly, any conflict in ${\cal
C}^{(4)}$ containing $e_{i}$ must have the form
$\\{e_{i},e^{\prime}_{i},f_{j},f^{\prime}_{j}\\}$ for some copies
$e,e^{\prime},f,f^{\prime}$ of $C_{6}$ and some color $j\in[\frac{n}{2}]$, so
there are $O(n)$ choices for $j$, $O(n^{6})$ choices for $e^{\prime}$, and
$O(n^{4})$ choices for each of $f$ and $f^{\prime}$. Thus, $\Delta({\cal
C}^{(4)})=O(n^{15})=O(d^{3})$.

In addition, we have $\Delta_{2}({\cal C}^{(3)})<d^{1-{\varepsilon}}$ for all
${\varepsilon}\in(0,\frac{1}{6})$. Indeed, the number of conflicts in ${\cal
C}^{(3)}$ containing two fixed vertices $e_{i},e_{i}^{\prime}\in V({\cal C})$
is $O(n^{3})$, since there are $O(n)$ ways to pick another color and
$O(n^{2})$ ways to pick two more vertices for the third edge in the conflict.
Similarly, the number of conflicts in ${\cal C}^{(3)}$ containing two fixed
vertices $e_{i},f_{j}\in V({\cal C})$ is $O(n^{4})$, which is the number of
ways to pick four more vertices for the third edge in the conflict. Similarly,
we have $\Delta_{2}({\cal C}^{(4)})<d^{2-{\varepsilon}}$ for all
${\varepsilon}\in(0,\frac{1}{6})$. The number of conflicts in ${\cal C}^{(4)}$
containing two fixed vertices $e_{i},e_{i}^{\prime}\in V({\cal C})$ is
$O(n^{9})$ since there are $O(n)$ choices for a second color and $O(n^{4})$
choices for each of $f$ and $f^{\prime}$ to complete the conflict, and the
number of conflicts in ${\cal C}^{(4)}$ containing two fixed vertices
$e_{i},f_{j}\in V({\cal C})$ is $O(n^{9})$ since there are $O(n^{5})$ choices
for $e^{\prime}$ and $O(n^{4})$ choices for $f^{\prime}$ to complete the
conflict. Finally, $\Delta_{3}({\cal C}^{(4)})<d^{1-{\varepsilon}}$, because
given three vertices $e_{i},e^{\prime}_{i},f_{j}\in V({\cal C})$, there are
$O(n^{4})$ choices for $f^{\prime}$ to complete a conflict. Therefore, ${\cal
C}$ is a $(d,O(1),{\varepsilon})$-bounded conflict system for ${\cal H}$ for
all $\varepsilon\in(0,\frac{1}{6})$.

Note that we could apply Theorem 3.1 at this point to obtain a conflict-free
matching $M$ in ${\cal H}$ which would correspond to a coloring of a subgraph
$F$ of $K_{n,n}$ satisfying properties (1) and (2) of Theorem 4.1. In order to
obtain a coloring which also satisfies properties (3) and (4) of Theorem 4.1,
we now introduce appropriate test functions.

First, we define a set of 1-uniform test functions as in [15]. For each $v\in
X\cup Y$, let $S_{v}\subset U$ be the set of edges incident to $v$ in
$K_{n,n}$. Let $w_{v}:E({\cal H})\rightarrow\\{0,2\\}$ be the weight function
which assigns to each edge $e_{i}\in E({\cal H})$ the size of its intersection
with $S_{v}$. Then we have

$w_{v}({\cal H})=\sum_{e_{i}\in{\cal H}}w_{v}(e_{i})=\sum_{f\in
S_{v}}\deg_{{\cal H}}(f)=nd-O(n^{5})\geq d^{1+{\varepsilon}},$

satisfying condition (W1). In addition, conditions (W2)-(W4) are trivially
satisfied since $w_{v}$ is 1-uniform, so $w_{v}$ is a $(d,{\varepsilon},{\cal
C})$-trackable test function for all ${\varepsilon}\in(0,\frac{1}{6})$ and
$v\in X\cup Y$.

Let $\delta<{\varepsilon}^{3}\log_{n}(\frac{1}{2}n^{5})$. Note that applying
Theorem 3.1 with these test functions would yield a ${\cal C}$-free matching
$M\subset{\cal H}$ such that for each $v\in X\cup Y$,

$w_{v}(M)>(1-d^{-{\varepsilon}^{3}})d^{-1}w_{v}({\cal H})>(1-n^{-\delta})n.$

Thus, for each $v\in X\cup Y$, there are at most $n^{1-\delta}$ edges in
$K_{n,n}$ incident to $v$ which do not belong to any edge in $M$. Hence,
property (3) is satisfied, as the graph $L$ containing the uncolored edges has
maximum degree $\Delta(L)\leq n^{1-\delta}$.

In order to guarantee that property (4) is also satisfied, we will define four
more types of test functions. The first two will help us to show that for each
$(x,y)\in X\times Y$, there are at most $n^{1-\delta}$ edges
$x^{\prime}y^{\prime}\in E(L)$ with $x^{\prime}\in X\backslash\\{x\\}$ and
$y^{\prime}\in Y\backslash\\{y\\}$ such that $xy^{\prime}$ and $yx^{\prime}$
are in distinct edges of the same color in the matching $M\subset{\cal H}$.
The next two will help us to show that for each $(x,y)\in X\times Y$, there
are at most $n^{1-\delta}$ edges in the matching that contain both $x$ and
$y$, and hence at most $3n^{1-\delta}$ graph edges $x^{\prime}y^{\prime}\in
E(L)$ with $x^{\prime}\in X\backslash\\{x\\}$ and $y^{\prime}\in
Y\backslash\\{y\\}$ such that $xy$ and $x^{\prime}y^{\prime}$ are contained in
the same edge of the matching.

For each pair of vertices $(x,y)\in X\times Y$, let

${\cal
P}_{x,y}=\left\\{\\{e_{i},e^{\prime}_{i}\\}:i\in\left[\frac{n}{2}\right],V(e)\cap
V(e^{\prime})=\emptyset,x\in V(e),y\in V(e^{\prime})\right\\}.$

Note that

$|{\cal P}_{x,y}|=\frac{n}{2}\cdot\frac{1}{2}n^{5}\cdot\frac{1}{2}n^{5}\pm
O(n^{10})=\frac{1}{8}n^{11}\pm O(n^{10})>d^{2+{\varepsilon}}.$

For each $(x,y)\in X\times Y$, define $w_{x,y}$ to be the indicator weight
function for the pairs in ${\cal P}_{x,y}$. Since each pair in ${\cal
P}_{x,y}$ is a matching of size 2 in ${\cal H}$, $w_{x,y}$ is a 2-uniform test
function. We will show that $w_{x,y}$ is $(d,{\varepsilon},{\cal
C})$-trackable for all ${\varepsilon}\in(0,\frac{1}{6})$, but first we will
define a set of 3-uniform test functions.

For each pair of vertices $(x,y)\in X\times Y$, let

${\cal
T}_{x,y}=\left\\{\\{e_{i},e^{\prime}_{i},f_{j}\\}:\\{e_{i},e^{\prime}_{i}\\}\in{\cal
P}_{x,y},j\in\left[\frac{n}{2}\right]\backslash\\{i\\},|V(f)\cap V(e)\cap
Y|=1,|V(f)\cap V(e^{\prime})\cap X|=1\right\\}.$

Thus, the triples in ${\cal T}_{x,y}$ are matchings of size 3 in ${\cal H}$.
Note that

$|{\cal T}_{x,y}|=9(d\pm O(n^{4}))|{\cal P}_{x,y}|.$

Similarly to above, define for each $(x,y)\in X\times Y$ the function
$w^{\prime}_{x,y}$ to be the indicator weight function for triples in ${\cal
T}_{x,y}$. This is a 3-uniform test function for ${\cal H}$.

Assuming that these test functions $w_{x,y}$ and $w^{\prime}_{x,y}$ are
$(d,{\varepsilon},{\cal C})$-trackable, we can apply Theorem 3.1 to obtain a
matching $M$ in ${\cal H}$ such that

$w_{x,y}(M)=\left|\binom{M}{2}\cap{\cal
P}_{x,y}\right|\leq(1+d^{-{\varepsilon}^{3}})d^{-2}|{\cal
P}_{x,y}|\leq(1+n^{-2\delta})\frac{n}{2}$

and

$w^{\prime}_{x,y}(M)=\left|\binom{M}{3}\cap{\cal
T}_{x,y}\right|\geq(1-d^{-{\varepsilon}^{3}})d^{-3}|{\cal
T}_{x,y}|\geq(1-n^{-2\delta})\frac{9n}{2}.$

Note that each edge $x^{\prime}y^{\prime}\in E(L)$ with $xy^{\prime}$ and
$x^{\prime}y$ appearing in distinct edges of ${\cal H}$ of the same color
corresponds to an edge of ${\cal H}$ in a triple of ${\cal T}_{x,y}$ extending
some pair from ${\cal P}_{x,y}$. Thus, we can bound the number of such
$x^{\prime}y^{\prime}$ as follows:

$9\left|\binom{M}{2}\cap{\cal P}_{x,y}\right|-\left|\binom{M}{3}\cap{\cal
T}_{x,y}\right|\leq n^{1-\delta}.$

Therefore, in order to prove the first case of property (4), we must verify
that $w_{x,y}$ and $w^{\prime}_{x,y}$ are $(d,{\varepsilon},{\cal
C})$-trackable for ${\varepsilon}\in(0,\frac{1}{6})$. For this we must check
conditions (W1)-(W4) for both functions.

Condition (W1) for $w_{x,y}$ is satisfied since $w_{x,y}({\cal H})=|{\cal
P}_{x,y}|>d^{2+{\varepsilon}}$. To check condition (W2), fix an edge
$e_{i}\in{\cal H}$. The number of edges $e^{\prime}_{i}$ which form a pair in
${\cal P}_{x,y}$ with $e_{i}$ is at most
$O(n^{5})<n^{11}/d^{1+{\varepsilon}}$. For condition (W3), note that the only
pairs of edges $\\{e,f\\}\in\binom{{\cal H}}{2}$ for which
$w_{x,y}(\\{e,f\\})>0$ are pairs $\\{e_{i},e^{\prime}_{i}\\}$ with $x\in
e_{i}$ and $y\in e^{\prime}_{i}$. Given such a pair, the number of triples of
edges in ${\cal H}$ which can form a conflict with $e_{i}$ or $e^{\prime}_{i}$
is at most $O(n\cdot n^{6}\cdot n^{3}\cdot
n^{3})=O(n^{13})<d^{3-{\varepsilon}}.$ Finally, condition (W4) is vacuously
true, so $w_{x,y}$ is $(d,{\varepsilon},{\cal C})$-trackable.

We now verify that $w^{\prime}_{x,y}$ is $(d,{\varepsilon},{\cal
C})$-trackable for ${\varepsilon}\in(0,\frac{1}{6})$ as well. Condition (W1)
holds because $w^{\prime}_{x,y}({\cal H})=|{\cal
T}_{x,y}|=\Theta(n^{16})>d^{3+{\varepsilon}}$. To see that condition (W2)
holds, fix $e_{i}\in{\cal H}$. There are $O(n^{11})<w^{\prime}_{x,y}({\cal
H})/d^{1+{\varepsilon}}$ triples in ${\cal T}_{x,y}$ containing $e_{i}$ since
we must either pick a second color $j$, six more vertices for
$e_{i}^{\prime}$, and four more vertices for $f_{j}$ to form a triple
$\\{e_{i},e_{i}^{\prime},f_{j}\\}$ or a second color $j$, five more vertices
for $f_{j}$, and five more vertices for $f_{j}^{\prime}$ to form a triple
$\\{e_{i},f_{j},f_{j}^{\prime}\\}$. And, for each pair of edges
$\\{e_{i},e_{i}^{\prime}\\}$ or $\\{e_{i},f_{j}\\}$ in ${\cal H}$, there are
$O(n^{5})<w^{\prime}_{x,y}({\cal H})/d^{2+{\varepsilon}}$ triples containing
this pair. For condition (W3), fix a pair of edges $\\{e,f\\}\in\binom{{\cal
H}}{2}$ which are in at least one triple together in ${\cal T}_{x,y}$. Either
we have $\\{e,f\\}=\\{e_{i},e^{\prime}_{i}\\}$ or
$\\{e,f\\}=\\{e_{i},f_{j}\\}$. In the first case, as above, there are
$O(n^{13})$ triples of edges in ${\cal H}$ which form a conflict with either
$e_{i}$ or $e^{\prime}_{i}$. In the second case, there are at most
$O(n^{14})<d^{3-{\varepsilon}}$ conflicts containing $e_{i}$ which use only
the colors $i$ and $j$, and this bounds the number of triples which form a
conflict with either $e_{i}$ or $f_{j}$. Thus, condition (W3) holds. Finally,
condition (W4) is vacuously true.

We now define for each $(x,y)\in X\times Y$ another pair of test functions to
guarantee that there are at most $n^{1-\delta}$ edges in the matching
$M\in{\cal H}$ which contain both $x$ and $y$. Set

${\cal S}_{x}=\left\\{e_{i}:i\in\left[\frac{n}{2}\right],x\in V(e)\right\\}$

and

${\cal D}_{x,y}=\left\\{e_{i}:i\in\left[\frac{n}{2}\right],x\in V(e),y\notin
V(e)\right\\}.$

Let $u_{x}$ and $u^{\prime}_{x,y}$ be the indicator functions for ${\cal
S}_{x}$ and ${\cal D}_{x,y}$, respectively. Note that $u_{x}({\cal H})=|{\cal
S}_{x}|=\frac{1}{2}n\cdot\frac{1}{2}n^{5}\pm O(n^{5})$, and similarly
$u^{\prime}_{x,y}=|{\cal D}_{x,y}|=\frac{1}{4}n^{6}\pm O(n^{5})$. Thus,
property (W1) holds for both $u_{x}$ and $u^{\prime}_{x,y}$. Furthermore,
(W2)-(W4) are vacuously true since these are 1-uniform test functions, hence
both are $(d,{\varepsilon},{\cal C})$-trackable for
${\varepsilon}\in(0,\frac{1}{6})$.

Applying Theorem 3.1 with all of these test functions gives a ${\cal C}$-free
matching $M\subset{\cal H}$ such that for each $x\in X$,

$u_{x}(M)\leq(1+d^{-{\varepsilon}^{3}})d^{-1}u_{x}({\cal
H})\leq(1+n^{-2\delta})\frac{n}{2},$

and for each $y\in Y$,

$u^{\prime}_{x,y}(M)\geq(1-d^{-{\varepsilon}^{3}})d^{-1}|{\cal
D}_{x,y}|\geq(1-n^{-2\delta})\frac{n}{2}.$

Therefore, the number of edges in $M$ which contain both $x$ and $y$ is at
most $u_{x}(M)-u^{\prime}_{x,y}(M)\leq n^{1-\delta}$, as desired. Thus, the
coloring obtained from $M$ satisfies property (4). ∎

We now proceed with the proof of Theorem 1.4. Applying Theorem 4.1 with
$2\delta$ in place of $\delta$, we obtain a partial coloring of $K_{n,n}$
using at most $n/2$ colors for which the uncolored subgraph $L$ of $K_{n,n}$
has maximum degree at most $n^{1-2\delta}$. To color these remaining edges, we
randomly color with a new set $P$ of $k=n^{1-\delta}$ colors, with each edge
in $L$ receiving a color in $P$ with equal probability $1/k$, independently of
the other edges. We will show using the symmetric local lemma that such a
coloring exists which creates no 2-colored $C_{4}$, and hence,
$g(K_{n,n},C_{4})\leq n/2+n^{1-\delta}$.

To this end, we define three types of “bad events,” without which every
$C_{4}$ in our coloring will contain some color exactly once. First, for each
pair of adjacent edges $e,f\in E(L)$ and each color $i\in P$, let $A_{e,f,i}$
be the event that $e$ and $f$ receive the same color $i$. Note that
$\mathbb{P}[A_{e,f,i}]=k^{-2}$. Next, for each 4-cycle $D$ in $L$, let $B_{D}$
be the event that $D$ is properly-colored with two colors from $P$. Then
$\mathbb{P}[B_{D}]\leq 2k^{-2}$. Finally, for each color $i\in P$ and each
4-cycle $D=xyx^{\prime}y^{\prime}$ in $K_{n,n}$ with
$xy,x^{\prime}y^{\prime}\in E(L)$ and $xy^{\prime},x^{\prime}y\in E(F)$ where
$xy^{\prime}$ and $x^{\prime}y$ received the same color in the first coloring,
let $C_{D,i}$ be the event that $xy$ and $x^{\prime}y^{\prime}$ both receive
color $i$. Then $\mathbb{P}[C_{D,i}]=k^{-2}$. Let ${\cal E}$ be the collection
of all bad events of the types $A_{e,f,i}$, $B_{D}$, and $C_{D,i}$.

Fix an event $E\in{\cal E}$. Note that $E$ is mutually independent from the
set of all events $E^{\prime}$ which do not involve any of the same edges as
$E$ in $L$. We call such events edge-disjoint from $E$. There are at most
$8\Delta(L)k\leq 8k^{2}n^{-\delta}$ events of the form $A_{e,f,i}$ which are
not edge-disjoint from $E$. In addition, there are at most
$4(\Delta(L))^{2}\leq k^{2}n^{-\delta}$ events $B_{D}$ and, by property (4) of
Theorem 4.1, at most $4(4n^{1-2\delta})k\leq 16k^{2}n^{-\delta}$ events
$C_{D,i}$ which are not edge-disjoint from $E$. Thus, in total, $E$ is
mutually independent of all but at most $25k^{2}n^{-\delta}$ events in ${\cal
E}$. By the local lemma, since $25k^{2}n^{-\delta}\cdot 2k^{-2}\leq 1/4$,
there is a coloring of $L$ which contains none of the events in ${\cal E}$, as
desired. ∎

## References

  * [1] Noga Alon.  Graph-codes.  arXiv:2301.13305, 2023.
  * [2] Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, and Gábor Simonyi.  Structured codes of graphs.  SIAM Journal on Discrete Mathematics, 2022.
  * [3] Patrick Bennett, Michelle Delcourt, Lina Li, and Luke Postle.  On generalized Ramsey numbers in the sublinear regime.  arXiv:2212.10542, 2022.
  * [4] Patrick Bennett, Andrzej Dudek, and Sean English.  A random coloring process gives improved bounds for the Erdős–Gyárfás problem on generalized Ramsey numbers.  arXiv:2212.06957, 2022.
  * [5] Aaron Berger and Yufei Zhao.  $k_{4}$-intersecting families of graphs.  arxiv:2103.12671, 2021.
  * [6] Alex Cameron and Emily Heath.  A $(5,5)$-colouring of ${K}_{n}$ with few colours.  Combinatorics, Probability and Computing, 27(6):892–912, 2018.
  * [7] Alex Cameron and Emily Heath.  New upper bounds for the Erdős–Gyárfás problem on generalized Ramsey numbers.  Combinatorics, Probability and Computing, 32(2):349–362, 2023\.
  * [8] David Conlon, Jacob Fox, Choongbum Lee, and Benny Sudakov.  The Erdős–Gyárfás problem on generalized Ramsey numbers.  Proceedings of the London Mathematical Society, 110(1):1–18, 2015\.
  * [9] Michelle Delcourt and Luke Postle.  Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings.  arXiv:2204.08981, 2022.
  * [10] David Ellis, Yuval Filmus, and Ehud Friedgut.  Triangle-intersecting families of graphs.  Journal of the European Mathematical Society, 14:841–885, 2010\.
  * [11] Paul Erdős and András Gyárfás.  A variant of the classical Ramsey problem.  Combinatorica, 17(4):459–467, 1997.
  * [12] Gennian Ge, Zixiang Xu, and Yixuan Zhang.  A new variant of the Erdős–Gyárfás problem on $k_{5}$.  arXiv:2306.14682, 2023.
  * [13] Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, and Lyuben Lichev.  Conflict-free hypergraph matchings.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2991–3005. SIAM, 2023.
  * [14] W. T. Gowers.  https://gowers.wordpress.com/2009/11/14/the-first-unknown-case-of-polynomial-dhj/.
  * [15] Felix Joos and Dhruv Mubayi.  Ramsey theory constructions from hypergraph matchings.  arXiv:2208.12563, 2022.
  * [16] Dhruv Mubayi.  Edge-coloring cliques with three colors on all 4-cliques.  Combinatorica, 18(2):293–296, 1998.