11institutetext: Université Paris Cité, CNRS, Astroparticule et Cosmologie,
F-75013 Paris, France

# Constraining f(R) gravity with cross-correlation of galaxies and cosmic
microwave background lensing

Raphaël Kou 11 Calum Murray 11 James G. Bartlett 11

(Received / Accepted)

We look for signatures of the Hu-Sawicki $f(R)$ modified gravity theory,
proposed to explain the observed accelerated expansion of the universe; in
observations of the galaxy distribution, the cosmic microwave background
(CMB), and gravitational lensing of the CMB. We study constraints obtained by
using observations of only the CMB primary anisotropies, before adding the
galaxy power spectrum and its cross-correlation with CMB lensing. We show that
cross-correlation of the galaxy distribution with lensing measurements is
crucial to breaking parameter degeneracies, placing tighter constraints on the
model. In particular, we set a strong upper limit on $\log\lvert
f_{R_{0}}\lvert<-4.61$ at $95\%$ confidence level. This means that while the
model may explain the accelerated expansion, its impact on large-scale
structure closely resembles General Relativity. Studies of this kind with
future data sets will probe smaller potential deviations from General
Relativity.

###### Key Words.:

Cosmology – dark energy – Gravitational lensing: weak – Galaxies – large-scale
structure of Universe – Cosmic background radiation

##  1 Introduction

The cause of the late-time accelerated expansion of the Universe is one of the
most profound problems facing modern cosmology (Riess et al., 1998; Perlmutter
et al., 1999). Many theories have been proposed to explain this phenomena, the
most popular due to its apparent simplicity is $\Lambda$, the cosmological
constant. However, the interpretation of the cosmological constant as the
energy of the vacuum results in theoretical predictions that are at least 55
orders of magnitude too large (e.g., Carroll et al., 2004; Solà, 2013),
motivating the study of alternative explanations. One possibility is new
gravitational physics (Carroll et al., 2004). In addition to causing the
accelerated expansion, modifications to gravity may alter structure formation
in the Universe. We constrain a particular model of $f(R)$ gravity, which can
explain the accelerated expansion of the Universe, using observations of
galaxy clustering, weak gravitational lensing of the cosmic microwave
background (CMB), and temperature and polarization information from the CMB.

Deviations from General Relativity (GR) are tightly constrained on the scales
of our Solar System (Everitt et al., 2011; Will, 2014). Therefore, models of
modified gravity must at the same time satisfy these constraints on small-
scales, whilst modifying gravity on large scales to explain the cosmic
acceleration. Carroll et al. (2004) presented a general class of models that
can drive cosmic acceleration, by replacing the linear dependence of the
Einstein-Hilbert action on the Ricci scalar $R$ with a non-linear function of
$R$ ($R\rightarrow R+f(R)$). Hu & Sawicki (2007) (in the following, HS)
presented a class of $f(R)$ models capable of explaining the cosmic
acceleration and evading the strong Solar System constraints through a
chameleon mechanism (Khoury & Weltman, 2004; Navarro & Van Acoleyen, 2007;
Faulkner et al., 2007).

Constraints have been placed on HS $f(R)$ gravity using many different
complementary observations. Such observations constrain $f_{R_{0}}$, the value
of the cosmological field today, that we introduce in more detail in Sect. 2.
In particular, on cosmological scales HS $f(R)$ has been constrained by
Cataneo et al. (2015), who obtained the constraint $\log\lvert
f_{R_{0}}\lvert<-4.79$ at the $95\%$ confidence level, using cluster number
counts in addition to CMB, supernovae and BAO data. Hu et al. (2016) also
found $\log\lvert f_{R_{0}}\lvert<-4.5$ using the CMB (temperature,
polarisation and lensing), supernovae, BAO and galaxy weak lensing
measurements. Hojjati et al. (2016) obtained the upper bound $\log\lvert
f_{R_{0}}\lvert<-4.15$ at the $95\%$ confidence level using similar
observations.

The strongest constraints come from galactic scales. Naik et al. (2019) were
able to exclude $\log\lvert f_{R_{0}}\lvert>-6.1$ using galaxy rotation
curves, and Desmond & Ferreira (2020) excluded $\log\lvert
f_{R_{0}}\lvert>-7.85$ based on the analysis of galaxy morphology.
Astrophysical and cosmological constraints on HS $f(R)$ gravity can also be
found in the review by Lombriser (2014). Finally, Casas et al. (2023)
forecasts the constraints that will be achievable using observations from
Euclid. Despite the strong constraints on HS $f(R)$ gravity from galactic
studies, it is still a useful model to explore deviations from GR on
cosmological scales.

Many different tools have been developed to predict the matter power spectrum
in HS $f(R)$ gravity. Boltzmann codes that calculate the linear matter power
spectrum are mgcamb (Zhao et al., 2009; Hojjati et al., 2011; Zucca et al.,
2019; Wang et al., 2023) and MGCLASS (Sakr & Martinelli, 2022). There are
several simulation based emulators of the matter-power spectrum into the mildy
non-linear regime (Winther et al., 2019; Ramachandra et al., 2021; Arnold et
al., 2022; Sáez-Casares et al., 2023), and ReACT (Bose et al., 2020, 2023),
which uses a halo model reaction framework validated on N-body simulations.

In the following section we review HS $f(R)$ gravity. In Sect. 3 we introduce
the observations used in our analysis, and then in Sect. 4 we overview our
methodology; the estimation of the angular power spectrum, our covariance
matrix estimation, and our likelihood. Results are presented in Sect. 5,
before the conclusions in Sect. 6.

##  2 Hu-Sawicki f(R) gravity

In $f(R)$ theories of gravity, the Einstein-Hilbert action is modified such
that $R\rightarrow R+f(R)$; therefore, the action becomes,

$\displaystyle S=\int
d^{4}x\sqrt{-g}\left[\frac{R+f(R)}{2\kappa^{2}}+\mathcal{L}_{m}\right],$ (1)

where $R$ is the Ricci scalar, $\kappa=8\pi G$ with $G$ the gravitational
constant (and the speed of light set to $1$), $g$ is the determinant of the
spacetime metric, $\mathcal{L}_{m}$ is the matter Lagrangian, and $f$ is a
function of the Ricci scalar. In HS (Hu & Sawicki, 2007), $f(R)$ follows a
broken power law,

$\displaystyle f(R)=-m^{2}\frac{c_{1}(R/m^{2})^{n}}{c_{2}(R/m^{2})^{n}+1},$
(2)

where $m$ is a mass scale given by $m^{2}=\kappa^{2}\bar{\rho}_{m}/3$ with
$\bar{\rho}_{m}$ the mean matter density of the Universe, and $c_{1}$, $c_{2}$
and $n$ are three dimensionless constants. The derivative of $f$ with respect
to the Ricci scalar $R$ is denoted,

$\displaystyle
f_{R}=\frac{df(R)}{dR}=-\frac{nc_{1}\left(\frac{R}{m^{2}}\right)^{n-1}}{\left(c_{2}\left(\frac{R}{m^{2}}\right)^{n}+1\right)^{2}},$
(3)

and can be interpreted as a new scalar field. Hu & Sawicki (2007) showed that
a background close to $\Lambda$CDM can be recovered by imposing,

$\displaystyle\frac{c_{1}}{c_{2}}=6\frac{\Omega_{\Lambda}}{\Omega_{m}},$ (4)

where $\Omega_{\Lambda}$ and $\Omega_{m}$ are the present-day dark energy and
matter densities (divided by the critical density) in the $\Lambda$CDM
cosmology. Imposing this relation, there remain only two free parameters in
Eq. (2): $n$ and either $c_{1}$ or $c_{2}$. In the high curvature regime
($R\gg m^{2}$), which Oyaizu (2008) showed to be the appropriate regime, Eq.
(3) can be written as,

$\displaystyle
f_{R}=-n\frac{c_{1}}{c_{2}^{2}}\left(\frac{m^{2}}{R}\right)^{n+1},$ (5)

which, evaluated at the present-day background, leads to,

$\displaystyle\frac{c_{1}}{c_{2}^{2}}=-\frac{1}{n}f_{R_{0}}\left(\frac{R_{0}}{m^{2}}\right)^{n+1}.$
(6)

The $f_{R_{0}}$ parameter denotes the background value of $f_{R}$ at the
present time, which we choose as our free parameter to constrain the model of
HS $f(R)$. Additionally, we fix $n=1$.

For the small values of $f_{R_{0}}$ probed in this work, the background
expansion of the Universe is indistinguishable between $f(R)$ and that of a
cosmological constant. Instead, we constrain $f(R)$ through its impact on the
growth of structure. This can be seen by looking at the modified Poisson
equation in $f(R)$,

$\nabla^{2}\Phi=\frac{\kappa}{2}a^{2}\delta\rho_{m}-\frac{1}{2}\nabla^{2}f_{R},$
(7)

where $a$ is the cosmological scale factor and
$\delta\rho_{m}\equiv\rho_{m}-\bar{\rho}_{m}$. We see directly that $f_{R}/2$
can be seen as the potential of the modified gravity force. As mentioned in
the introduction, this modified Poisson equation approaches the GR expression
within the Solar System through the chameleon mechanism (Khoury & Weltman,
2004; Hu & Sawicki, 2007).

It is worth noting that unlike other theories of modified gravity, HS $f(R)$
has little effect on the propagation of light in the weak-field limit (for
example Hojjati et al., 2016).

##  3 Data

###  3.1 BOSS galaxies

We use the DR12 data release of the BOSS survey from the SDSS collaboration
(Alam et al., 2015). This large-scale spectroscopic survey was divided into
two subsamples, LOWZ and CMASS. LOWZ contains galaxies at low redshift, up to
approximately $z\simeq 0.45$, while CMASS contains higher redshift galaxies,
(roughly up to $z\simeq 0.8$) and was constructed to create a sample of
galaxies with approximately constant stellar mass. As in Loureiro et al.
(2019), we restrict these samples to $0.15<z<0.45$ and $0.45<z<0.8$ for LOWZ
and CMASS, respectively, such that the two samples do not overlap in redshift.
This choice allows us to neglect the covariance between galaxies of LOWZ and
CMASS. Using these redshift ranges, and after masking regions of low
completeness, the two samples contain $366,576$ and $751,067$ galaxies. The
redshift distribution of the two samples is shown in Fig. 1.

Figure 1: CMASS (blue) and LOWZ (orange) redshift distributions.

The mask and map making is identical to that within Kou & Bartlett (2023),
which follows Reid et al. (2016) and Loureiro et al. (2019). We transform the
MANGLE111https://space.mit.edu/$\sim$molly/mangle/ (Swanson et al., 2008)
acceptance and veto masks, provided with the galaxy catalogs, into high
resolution binary masks in HEALPix222http://healpix.sf.net (Górski et al.,
2005; Zonca et al., 2019) format with $\textrm{N}_{\textrm{SIDE}}=8192$. The
acceptance mask represents the completeness of the observations, while the
veto mask excludes regions that could not be observed. A first cut is made to
exclude regions with completeness below $0.7$, before degrading the resolution
of the mask to $\textrm{N}_{\textrm{SIDE}}=4096$. A second cut is then
applied, such that pixels with completeness below $0.8$ are rejected. Finally,
the galaxy maps are computed by summing the weighted number of galaxies in
each pixel, divided by the completeness of the pixel. The weight
$w_{\textrm{tot}}$ that is applied to each galaxy takes into account a number
of observational effects, including fibre collisions, redshift failures,
stellar density and seeing conditions (more details can be found in Ross et
al., 2012). The galaxy overdensity map is,

$\displaystyle\delta_{p}=\left(\frac{n_{p}}{\bar{n}}-1\right),$ (8)

where,

$\displaystyle
n_{p}=\left\\{\begin{array}[]{ll}\frac{1}{C_{\textrm{pix}}^{p}}\sum_{i\in
p}w_{\textrm{tot}}^{i}&\mbox{if }C_{\textrm{pix}}^{p}>0.8\\\
0&\mbox{otherwise},\end{array}\right.$ (11)

where $C_{\textrm{pix}}^{p}$ is the completeness in pixel $p$.

###  3.2 CMB temperature and polarization observations

We use observations of the CMB temperature and polarization anisotropies from
the Planck satellite, which observed the CMB for about $29$ months and covered
the full sky. In this work, we directly make use of the likelihood code
provided (Planck Collaboration et al., 2020b) and whose cosmological results
were analyzed in Planck Collaboration et al. (2020a).

###  3.3 CMB lensing convergence map

The observed CMB fluctuations are distorted as the CMB photons traverse the
Universe because of gravitational lensing. An observational consequence of
this is the correlation between different multipoles in both the temperature
and polarization anisotropies, which would not be present in the unlensed CMB.
The CMB lensing potential can therefore be reconstructed from such
correlations (see Lewis & Challinor (2006) for a comprehensive review).

We use the CMB lensing convergence map released by Planck Collaboration et al.
(2020c). This map was obtained using a minimum variance quadratic estimator
based on temperature and polarization maps. This map covers about $67\%$ of
the sky and led to the detection of lensing at $40\sigma$. The map is provided
with resolution $N_{\textrm{SIDE}}=4096$, together with the associated mask
with $N_{\textrm{SIDE}}=2048$.

##  4 Methodology

###  4.1 Theoretical angular power spectra

We calculate the matter power spectrum in $f(R)$ using two different codes,
MGCLASS and ReACT.

MGCLASS (Sakr & Martinelli, 2022) is a modified version of the Boltzmann code
CLASS (Blas et al., 2011) in which the equations of the linear perturbation
theory are changed to take into account modifications to gravity. It can
therefore be used to predict the linear matter power spectrum.

ReACT (Bose et al., 2020, 2023) gives predictions for the non-linear matter
power spectrum in beyond $\Lambda$CDM cosmologies, including $w\textrm{CDM}$,
$f(R)$ and DGP gravity. ReACT uses a halo model based approach described in
Cataneo et al. (2019) such that,

$\displaystyle
P_{\textrm{NL}}(k,z)=\mathcal{R}(k,z)P_{\textrm{NL}}^{\textrm{pseudo}}(k,z),$
(12)

where $P_{\textrm{NL}}$ is the non-linear matter power spectrum in modified
gravity, and $P_{\textrm{NL}}^{\textrm{pseudo}}$ is the so-called non-linear
“pseudo-power spectrum”. This pseudo-power spectrum is defined as a
$\Lambda$CDM power spectrum with initial conditions chosen such that the
$\Lambda$CDM linear matter power spectrum matches the modified gravity linear
matter power spectrum at a given redshift. This choice was made in order to
ensure that the halo mass function in $\Lambda$CDM and in the modified gravity
theory are similar (which is anticipated since they have been defined to have
exactly the same linear matter power spectrum).

The remaining term in Eq. (12), $\mathcal{R}$ is called the reaction and
describes how the $\Lambda$CDM matter power spectrum changes due to the
modifications to gravity. The reaction is calculated using the halo model and
1-loop perturbation theory. More details can be found in Cataneo et al. (2019)
and Bose et al. (2023). When using ReACT to predict the non-linear modified
gravity matter power spectrum, it is required to provide a reliable non-linear
$\Lambda$CDM matter power spectrum, for which we use the halo model based
HMCode (Mead et al., 2015).

Figure 2: Effect of changing the value of $\log\lvert f_{R_{0}}\lvert$ on the
auto-power spectrum of CMASS, with all other parameters fixed. The bottom
panel shows the difference relative to the non-linear power spectrum in
$\Lambda$CDM, together with the $1\sigma$ uncertainties of CMASS. Plain lines
are obtained using ReACT and the dashed lines with MGCLASS. The grey dotted
line shows the limit between the linear and non-linear regimes. We limit our
analysis to the linear regime, but show the theoretical predictions with
ReACT. We do not show the predictions with MGCLASS, which fail in this regime.

For our observations we compute the galaxy auto power spectrum
$C_{\ell}^{gg}$, the CMB lensing convergence auto power spectrum
$C_{\ell}^{\kappa\kappa}$ and the cross-correlation between the two
$C_{\ell}^{\kappa g}$. We also compute the CMB temperature and polarization
power spectra, which are sensitive to $f(R)$ gravity through the integrated
Sachs-Wolfe effect (ISW) and gravitational lensing. The CMB temperature,
polarization and convergence power spectra are predicted by MGCLASS.

For the galaxy auto and cross power spectra, we use the matter power spectrum
prediction from either ReACT or MGCLASS. The angular power spectra are then
modeled using the Limber approximation (Limber, 1953),

$\displaystyle C_{\ell}^{gg}$
$\displaystyle=\int\frac{dz}{c}\frac{H(z)}{\chi^{2}(z)}W_{g}^{2}(z)P_{m}\left(k=\frac{\ell}{\chi(z)},z\right)$
(13) $\displaystyle C_{\ell}^{\kappa g}$
$\displaystyle=\int\frac{dz}{c}\frac{H(z)}{\chi^{2}(z)}W_{g}(z)W_{\kappa}(z)P_{m}\left(k=\frac{\ell}{\chi(z)},z\right),$
(14)

where $H(z)$ is the Hubble parameter at redshift $z$, $c$ is the speed of
light, $\chi$ is the comoving distance, $P_{m}$ is the matter power spectrum,
and $k$ is the comoving wavenumber. Finally, $W_{g}$ and $W_{\kappa}$ are the
galaxy and CMB lensing kernels,

$\displaystyle W_{g}(z)$
$\displaystyle=\frac{b_{g}}{n_{\textrm{tot}}}\frac{dn}{dz}$ (15)
$\displaystyle W_{\kappa}(z)$
$\displaystyle=\frac{3}{2}\Omega_{m}H_{0}^{2}\frac{(1+z)}{H(z)}\frac{\chi(z)}{c}\left(\frac{\chi(z_{*})-\chi(z)}{\chi(z_{*})}\right).$
(16)

Here, $b_{g}$ is the galaxy bias, $(1/n_{\textrm{tot}})(dn/dz)$ is the
normalized galaxy redshift distribution, $H_{0}$ is the present value of $H$,
$\Omega_{m}$ is the matter density parameter, and $z_{*}$ is the redshift of
the surface of last scattering.

In Fig. 2 we show the effect of changing $\log\lvert f_{R_{0}}\lvert$ on the
galaxy angular power spectrum, using the galaxy redshift distribution of CMASS
(see Sect. 3 for more details). It can be seen that HS $f(R)$ gravity
increases the formation of structure on small scales, leading to more power in
the angular power spectrum at larger multipoles. For a given value of
$\log\lvert f_{R_{0}}\lvert$, MGCLASS predicts slightly more power than ReACT,
except at the highest multipoles, where power might be missing in the
prediction of MGCLASS as MGCLASS only predicts the linear matter power
spectrum. This is also the reason why we do not show the predictions using
MGCLASS after the dotted grey line marking the transition into the non-linear
regime. The non-linear regime is not used in our analysis as we do not use a
theoretical model that can reliably model the galaxy bias in this regime.

###  4.2 Angular power spectra estimation

The angular cross-correlation power spectrum of two fields $A$ and $B$ is
defined as,

$\displaystyle\langle a_{\ell
m}b^{*}_{\ell^{\prime}m^{\prime}}\rangle=\delta_{\ell\ell^{\prime}}\delta_{mm^{\prime}}C_{\ell}^{AB},$
(17)

where $a_{\ell m}$ and $b_{\ell^{\prime}m^{\prime}}$ are respectively the
spherical harmonic coefficients of fields $A$ and $B$, $b^{*}$ denotes the
complex conjugate of $b$, $\delta$ is the Kronecker symbol, and
$\langle\,\rangle$ is the ensemble average. Given full sky coverage, this
power spectrum can be estimated using,

$\displaystyle\hat{C}_{\ell}^{AB}=\frac{1}{2\ell+1}\sum_{m=-\ell}^{\ell}a_{\ell
m}b_{\ell m}^{*}.$ (18)

In practice, however, fields $A$ and $B$ are not observed on the full sky, but
on a limited sky fraction defined by their masks $\mathcal{W}^{A}$ and
$\mathcal{W}^{B}$, such that what we really observe is
$\tilde{A}(\mathbf{\hat{n}})=\mathcal{W}^{A}(\mathbf{\hat{n}})A(\mathbf{\hat{n}})$
and
$\tilde{B}(\mathbf{\hat{n}})=\mathcal{W}^{B}(\mathbf{\hat{n}})B(\mathbf{\hat{n}})$.
It can then be shown (Hivon et al., 2002; Brown et al., 2005) that taking the
ensemble average of Eq. (18) with the observed fields $\tilde{A}$ and
$\tilde{B}$ gives,

$\displaystyle\langle\hat{C}_{\ell}^{\tilde{A}\tilde{B}}\rangle=\sum_{\ell^{\prime}}M_{\ell\ell^{\prime}}C_{\ell}^{AB},$
(19)

where $M_{\ell\ell^{\prime}}$ is a coupling matrix that depends on the masks
$\mathcal{W}^{A}$ and $\mathcal{W}^{B}$. It is then possible to recover an
unbiased estimate of $C_{\ell}^{AB}$ by inverting the coupling matrix.

In our analysis we use the public code
NaMaster333https://github.com/LSSTDESC/NaMaster(Alonso et al., 2019) to
estimate the power spectra of CMASS and LOWZ, as well as their cross-
correlation with the CMB lensing convergence map from Planck. For the CMB
lensing auto-correlation, we take directly the Planck lensing likelihood. We
also apodize the CMB lensing mask with a scale of $10$ arcmin, and we have
verified that the estimated power spectra do not depend on the apodization
scale.

###  4.3 Noise removal

The measured galaxy angular power spectrum is biased by the shot-noise
contribution. Therefore, this contribution is subtracted from the estimated
power spectrum. The galaxy shot noise is given by,

$\displaystyle N_{\ell}^{gg}=\frac{4\pi f_{\textrm{sky}}}{N},$ (20)

where $N$ is the weighted number of galaxies in each sample.

###  4.4 Scale cuts

As mentioned in Sect. 4.1, for our cosmological constraints we only use power
spectra in the linear regime. This limitation mainly comes from the fact that
we use a linear galaxy bias and that this simple modeling is not reliable in
the non-linear regime. To determine the maximum multipole that can be used, we
follow the approach of Loureiro et al. (2019). Namely, we use the fiducial
cosmology of Planck Collaboration et al. (2020a) and predict the theoretical
linear and non-linear power spectra in the $\Lambda$CDM model. The non-linear
power spectra uses halofit (Smith et al., 2003; Takahashi et al., 2012) to
model the non-linear matter power spectrum and we keep using a linear galaxy
bias. We then determine the transition between the linear and non-linear
regimes to correspond to the largest multipole $\ell_{\textrm{max}}$ such that
the relative difference between the linear and non-linear power spectra is
inferior to $5\%$. The determined scales are presented in Tab. 1. In practice
we use $\ell_{\textrm{max}}=200$ for CMASS, $\ell_{\textrm{max}}=100$ for
LOWZ, and $\ell_{\textrm{max}}=400$ for CMB lensing.

Angular power spectrum | $\ell_{\textrm{max}}$
---|---
$C_{\ell}^{gg,\textrm{CMASS}}$ | $202$
$C_{\ell}^{\kappa g,\textrm{CMASS}}$ | $208$
$C_{\ell}^{gg,\textrm{LOWZ}}$ | $106$
$C_{\ell}^{\kappa g,\textrm{LOWZ}}$ | $108$
$C_{\ell}^{\kappa\kappa}$ | $418$
Table 1: Scale cuts for each power spectrum such that the relative difference
between the linear and non-linear power spectra is inferior to $5\%$.

Finally, since we use the Limber approximation, which is not valid on large
scales, we limit our study to multipoles above $\ell_{\textrm{min}}=20$.

###  4.5 Covariance matrix

We use a Gaussian covariance matrix following Saraf et al. (2022). This allows
us to incorporate non-overlapping regions of the sky within our cross-
correlation analysis,

${\rm
Cov}_{LL^{\prime}}^{AB,CD}=\frac{\delta_{LL^{\prime}}}{(2\ell_{L}+1)\Delta\ell
f_{\textrm{sky}}^{AB}f_{\textrm{sky}}^{CD}}\biggl{[}f_{\textrm{sky}}^{AC,BD}\left(C_{L}^{AC}+N_{L}^{AC}\right)\\\
\times\left(C_{L}^{BD}+N_{L}^{BD}\right)+f_{\textrm{sky}}^{AD,BC}\left(C_{L}^{AD}+N_{L}^{AD}\right)\left(C_{L}^{BC}+N_{L}^{BC}\right)\biggr{]},$
(21)

where $A$,$B$,$C$,$D$ label one of the two galaxy density fields $g$ or the
CMB lensing convergence field $\kappa$, and $f_{\textrm{sky}}^{AB}$ is the sky
fraction common to fields $A$ and $B$.

We estimate an initial covariance matrix using Eq. (21) with the observed
power spectra. This covariance matrix is used to fit our theoretical model to
the observations, and we then determine a second covariance matrix using the
best fit theoretical power spectra from the first analysis. This procedure
reduces our sensitivity to the noise in the estimated power spectra.

###  4.6 Likelihood

Our log-likelihood is the sum of the log-likelihood of the galaxy power
spectra and the galaxy – CMB lensing cross-correlations, which we denote here
as $\ln{\mathcal{L}^{2\times 2\,\textrm{pt}}}$, the Planck log-likelihood for
temperature and polarization (Planck Collaboration et al., 2020b)
$\ln{\mathcal{L}^{\textrm{Planck}}}$, and the Planck CMB lensing Planck
Collaboration et al. (2020c) likelihood $\ln{\mathcal{L}^{\textrm{Planck
lensing}}}$,

$\displaystyle\ln{\mathcal{L}}=\ln{\mathcal{L}^{2\times
2\,\textrm{pt}}}+\ln{\mathcal{L}^{\textrm{Planck}}}+\ln{\mathcal{L}^{\textrm{Planck
lensing}}}.$ (22)

The name $2\times 2$ pt comes from the fact that it is the combination of two
different types of two point statistics ($C_{\ell}^{gg}$ and $C_{\ell}^{\kappa
g}$). The third two point statistic is the Planck lensing power spectrum,
$C_{\ell}^{\kappa\kappa}$, making our analysis a $3\times 2$ pt analysis in
combination with the Planck temperature and polarisation likelihood.

We adopt a Gaussian for the $2\times 2$ pt likelihood,

$\displaystyle\ln{\mathcal{L}^{2\times
2\,\textrm{pt}}}=-\frac{1}{2}\left[\left(X(\theta)-X^{\textrm{obs}}\right)^{T}C^{-1}\left(X(\theta)-X^{\textrm{obs}}\right)\right],$
(23)

where $X^{T}$ denotes the transpose of vector $X$, $\theta$ is the parameter
vector, $C$ is the covariance matrix, and $X$ is a concatenation of power
spectra such that,

$\displaystyle X=\left(C_{\ell}^{gg,\textrm{CMASS}},C_{\ell}^{\kappa
g,\textrm{CMASS}},C_{\ell}^{gg,\textrm{LOWZ}},C_{\ell}^{\kappa
g,\textrm{LOWZ}}\right).$ (24)

The likelihood $\mathcal{L}^{\textrm{Planck}}$ contains the likelihood for the
TT, TE and EE power spectra. We have neglected the covariance between
$C_{\ell}^{\kappa\kappa}$ and $C_{\ell}^{\kappa g}$ (as is done, for instance,
in Abbott et al., 2023), which is motivated by the fact that the
$C_{\ell}^{\kappa\kappa}$ is estimated on a much larger sky fraction than
$C_{\ell}^{\kappa g}$, and that CMB lensing power comes mainly from redshifts
greater than $0.8$, where we do not have any galaxy in either of the two
samples.

###  4.7 Priors

We use flat priors for all of the cosmological parameters, namely
$\omega_{m}$, $\omega_{b}$, $h$, $\tau_{\textrm{reio}}$, $\log{10^{10}A_{s}}$,
$n_{s}$, as well as for the two galaxy bias parameters, for LOWZ and CMASS,
and $\log\lvert f_{R_{0}}\lvert$, for which we impose $-7<\log\lvert
f_{R_{0}}\lvert<0$. We use the recommended priors for the calibration and
nuisance parameters required by Planck’s likelihood. In total, we end up with
$30$ free parameters (the $6$ parameters of $\Lambda$CDM, $\log\lvert
f_{R_{0}}\lvert$, $2$ galaxy bias parameters and $21$ calibration and nuisance
parameters). We then use the MCMC (Monte Carlo Markov Chain) sampler
emcee444https://emcee.readthedocs.io/ (Foreman-Mackey et al., 2013) to sample
the resulting posterior distributions.

###  4.8 Computing prior-independent constraints

As will be seen in Sect. 5, in many cases we are only able to put upper bounds
on $\log\lvert f_{R_{0}}\lvert$. It is then non-trivial to estimate the $95\%$
constraint on $\log\lvert f_{R_{0}}\lvert$, since the percentile depends
strongly on the lower value of the prior. This arises because the posterior on
$\log\lvert f_{R_{0}}\lvert$ at low values is non zero (and almost flat).
Therefore, without a lower bound on the prior, very low values of $\log\lvert
f_{R_{0}}\lvert$ would be explored, rather than more interesting regions of
the posterior, which would in turn be poorly sampled. This choice of lower
limit for $\log\lvert f_{R_{0}}\lvert$ changes the estimated
$95^{\textrm{th}}$ percentile.

In order to resolve this issue, we follow the approach of Piga et al. (2023),
who rely on Gordon & Trotta (2007). We consider the ratio of the marginalized
posterior and our prior,

$\displaystyle b(x;d,p)=\frac{\mathcal{P}(x\lvert d,p)}{p(x)},$ (25)

where $x$ is the parameter we wish to constrain (in our case $\log\lvert
f_{R_{0}}\lvert$), $d$ is the data, $p$ the prior, and $\mathcal{P}$ the
posterior. Then, for two different values of $x$, say $x_{1}$ and $x_{2}$, we
apply Bayes theorem to obtain,

$\displaystyle\frac{b(x_{1};d,p)}{b(x_{2};d,p)}=\frac{\mathcal{L}(d\lvert
x_{1})}{\mathcal{L}(d\lvert x_{2})}=B(x_{1},x_{2}),$ (26)

where $B$ is the Bayes factor and $\mathcal{L}(d\lvert x)$ is the marginalized
likelihood of the data for $x$. The Bayes factor, which quantifies the support
for the model with $x=x_{1}$ over the model with $x=x_{2}$, is therefore prior
independent.

Gordon & Trotta (2007) showed that $B(x_{1},x_{2})=2.5$ means that the model
with $x=x_{1}$ is favored compared to the model with $x=x_{2}$ at $95\%$. We
then fix $x_{1}$ to its lower bound of $\log\lvert f_{R_{0}}\lvert=-7$ and
find the value of $x_{2}$ such that $B(x_{1},x_{2})=2.5$. In this way, we are
able to compute $95\%$ confidence intervals which do not depend on the prior.
We check this is indeed the case in Sect. 5.2.4, where we vary the prior used
in the analysis.

##  5 Results

Figure 3: Marginalized posterior of $\log\lvert f_{R_{0}}\lvert$ using
observations of Planck modeled with MGCLASS. TTTEEE refers to the temperature
and polarization power spectra of Planck, “lensing” to the addition of the CMB
lensing power spectrum, and $A_{\textrm{lens}}$ to the inclusion of the
lensing amplitude (see the text for details).

In this section we present our results for different combinations of
observations, with different choices of binnings, theoretical power spectra
and nuisance parameters. The upper limits we place on $\log\lvert
f_{R_{0}}\lvert$ are shown in Tab. 2 and, the corner plot for the fiducial
$3\times 2$ pt + CMB analysis, obtained thanks to the use of
GetDist555https://getdist.readthedocs.io/ (Lewis, 2019), is shown in Fig. 6.

###  5.1 Results from CMB only

We first look at the constraints obtained on $\log\lvert f_{R_{0}}\lvert$ when
using only observations of the CMB. All these constraints are obtained using
MGCLASS, as ReACT can only make predictions for the matter power spectrum at
redshifts $z<2.5$.

Firstly, we use the CMB temperature and polarization power spectra. They are
sensitive to $f(R)$ gravity through the imprint of the integrated Sachs–Wolfe
effect and gravitational lensing. Lensing is the dominant effect and causes a
smoothing of the acoustic peaks (for more detail, see Lewis & Challinor,
2006). This is distinct from the CMB lensing convergence reconstruction
described in Sect. 3.3. Since $f(R)$ increases the power in the lensing
potential, $f(R)$ models will have a larger smoothing effect on the CMB.

With just the CMB temperature and polarization observations, we find a strong
preference for a non-zero value of $f_{R_{0}}$ at more than $3\sigma$: a best-
fit value of $\log\lvert f_{R_{0}}\lvert=-2.35$, with the bounds
$-3.09<\log\lvert f_{R_{0}}\lvert<-1.88$ at $95\%$ and $-5.76<\log\lvert
f_{R_{0}}\lvert<-1.64$ at $99.7\%$ confidence levels. The marginalized
posterior for $\log\lvert f_{R_{0}}\lvert$ is shown in Fig. 3, where we see a
clear peak at $\log\lvert f_{R_{0}}\lvert=-2.35$. This is not a new result and
has been shown by other authors, for example Dossett et al. (2014) and Hojjati
et al. (2016).

However, when we add the CMB lensing power spectrum, which is estimated from
the mode mixing in the primary CMB (as described in Sect. 3.3), the large
values of $\log\lvert f_{R_{0}}\lvert$ are excluded, and instead we set an
upper limit on $\log\lvert f_{R_{0}}\lvert$: $\log\lvert
f_{R_{0}}\lvert<-2.31$ at $95\%$ confidence (computed following the approach
described in Sect. 4.8).

Figure 4: Degeneracy between $A_{\textrm{lens}}$ and $\log\lvert
f_{R_{0}}\lvert$ for CMB temperature and polarization only (blue); CMB
temperature, polarization and lensing (green); and when $A_{\textrm{lens}}$ is
considered as a systematic effect and is applied only to the primary CMB
anisotropies (magenta). The contours correspond to the $68^{\textrm{th}}$ and
$95^{\textrm{th}}$ percentiles of the posterior samples.

We clearly see that the CMB lensing convergence power spectrum is consistent
with GR and low $\log\lvert f_{R_{0}}\lvert$ values, while the smoothing of
the acoustic peaks in the CMB temperature and polarization anisotropies
prefers a higher value of $\log\lvert f_{R_{0}}\lvert$. This issue (or
tension) is closely related to the Planck $A_{\textrm{lens}}$ tension (Planck
Collaboration et al., 2020a).

The $A_{\textrm{lens}}$ parameter was introduced in Calabrese et al. (2008) as
a phenomenological parameter scaling the CMB lensing potential amplitude as,

$\displaystyle C_{\ell}^{\phi\phi}\rightarrow
A_{\textrm{lens}}C_{\ell}^{\phi\phi}.$ (27)

It therefore changes the amplitude of the CMB lensing convergence power
spectrum, and also the smoothing in the temperature and polarization power
spectra. It was shown in Planck Collaboration et al. (2020a) that the CMB
lensing convergence power spectrum is perfectly compatible with
$A_{\textrm{lens}}=1$, which is not the case of the temperature and
polarization power spectra. For instance, the $1\sigma$ constraint that Planck
Collaboration et al. (2020a) find using the TT,TE,EE+low E likelihood is
$A_{\textrm{lens}}=1.180\pm 0.065$, which is in tension with
$A_{\textrm{lens}}=1$ at $2.8\sigma$. Interestingly, the $\log\lvert
f_{R_{0}}\lvert$ tension is larger than the $A_{\textrm{lens}}$ tension. This
suggests that the modification of the lensing potential by HS $f(R)$ better
describes the smoothing of the CMB than the simple rescaling of the potential
with $A_{\textrm{lens}}$.

We further elucidate the relation between $A_{\textrm{lens}}$ and $\log\lvert
f_{R_{0}}\lvert$ by running the Planck CMB TTTEEE likelihood with both
parameters. Figure 3 shows the result as the blue curve. The constraints on
$\log\lvert f_{R_{0}}\lvert$ are broadened, with low values of $\log\lvert
f_{R_{0}}\lvert$ now acceptable, and compatible with GR. The posterior,
however, remains consistent with higher values of $\log\lvert
f_{R_{0}}\lvert$. Figure 4 illustrates the degeneracy between
$A_{\textrm{lens}}$ and $\log\lvert f_{R_{0}}\lvert$.

The green and magenta curves in Fig. 3 show the posteriors obtained when
adding the CMB lensing convergence power spectrum likelihood. The difference
between the two curves is that for the magenta curve, the effect of
$A_{\textrm{lens}}$ is only applied to the temperature and polarization power
spectra; in this case, we are modeling $A_{\textrm{lens}}>1$ not as a physical
effect, but rather as an unknown systematic in the observations. In both
cases, the posteriors agree with GR, and we can put an upper limit on the
value of $\log\lvert f_{R_{0}}\lvert$.

We show the degeneracy between $\log\lvert f_{R_{0}}\lvert$ and
$A_{\textrm{lens}}$ in these two cases in Fig. 4. When $A_{\textrm{lens}}$ is
treated as a systematic (magenta contours), we recover high
$A_{\textrm{lens}}$ values because the convergence power spectrum constrains
$\log\lvert f_{R_{0}}\lvert$ to low values where it cannot reproduce the
smoothing observed in the acoustic peaks. These results clearly show that HS
$f(R)$ gravity cannot explain the $A_{\textrm{lens}}$ tension, in agreement
with the findings of Hojjati et al. (2016).

###  5.2 Results from combined CMB and $3\times 2$ pt observations

Figure 5: Marginalized posterior of $\log\lvert f_{R_{0}}\lvert$ using
observations of CMB temperature and polarization, and the $3\times 2$ pt
observables (CMB lensing, galaxy distribution and their cross-correlation).
The CMB observations including the CMB lensing auto power spectrum are always
modeled using MGCLASS, while the galaxy power spectra and the galaxy – CMB
lensing cross-correlations are modeled with ReACT (red) or MGCLASS (black).
Figure 6: Constraints and degeneracies on all parameters when using
observations of the CMB and $3\times 2$ pt observables, modeled with MGCLASS
(blue) or ReACT (red). The contours correspond to the $68^{\textrm{th}}$ and
$95^{\textrm{th}}$ percentiles of the posterior samples.

We now present our fiducial analysis, the combination of the CMB (temperature
and polarization power spectra) and the $3\times 2$ pt analysis (CMB
convergence power spectrum, galaxy power spectrum and the cross-correlation
between the two). In this section, the value of $A_{\textrm{lens}}$ is fixed
to $1$ if not stated otherwise.

Figure 5 gives the marginalized posterior of $\log\lvert f_{R_{0}}\lvert$
obtained when using either MGCLASS (black curve) or ReACT (red curve) when
modeling the $2\times 2$ pt observables ($C_{\ell}^{gg}$ and $C_{\ell}^{\kappa
g}$) and we recall that the CMB lensing convergence auto power spectrum is
always modeled using MGCLASS. The $95\%$ confidence level constraints are
$\log\lvert f_{R_{0}}\lvert<-4.12$ and $\log\lvert f_{R_{0}}\lvert<-4.61$ with
MGCLASS and ReACT, respectively. These constraints are consistent with GR and
are much tighter than when using only the CMB observations. This also excludes
HS $f(R)$ as an explanation of the $A_{\textrm{lens}}$ tension.

The difference between MGCLASS and ReACT is also evident in Fig. 2. MGCLASS
only predicts the linear matter power spectrum, whereas ReACT predicts the
non-linear power spectrum. Although our scale cuts were chosen to minimise the
effects of non-linear structure formation, it seems likely that the origin of
this difference here arises from the mildly non-linear regime where the
MGCLASS predictions have less power than those of ReACT. Therefore, our
MGCLASS constraint is likely too conservative and hence not as strong as it
should be.

Figure 6 shows the marginalized two-dimensional posteriors on all parameters
when using MGCLASS (blue) or ReACT (red). We see that the posteriors agree
well for most parameters. We also see that $\log\lvert f_{R_{0}}\lvert$
exhibits a degeneracy with the galaxy bias parameters. This arises because
both parameters change the amplitude of the galaxy power spectra. The
parameters are not completely degenerate, however, as $\log\lvert
f_{R_{0}}\lvert$ also changes the shape of the power spectra, and the cross-
correlation separates the two effects to a certain extent, as explored in the
following subsection.

We show in Fig. 7 the measured angular power spectra (orange) and the
theoretical best fit (blue) using MGCLASS. The model fits well the data except
at the largest scales for the cross-correlation between the CMB lensing of
Planck and the galaxies of CMASS, where the amplitude of the theoretical power
spectrum is larger than the amplitude of the observation. This result has been
observed in previous studies (Pullen et al., 2016; Singh et al., 2017; Kou &
Bartlett, 2023). We see that HS $f(R)$ is unable to resolve this problem.

Figure 7: Measured angular power spectra (orange) and best fit (blue) obtained
using MGCLASS, as a function of multipole. The grey dashed line represents the
limit between the linear and non-linear regimes. We only used multipoles above
this limit in this analysis. Note the different multipole ranges for CMASS and
LOWZ.

Figure 8: Marginalized constraints on $\log\lvert f_{R_{0}}\lvert$ and the
galaxy bias of CMASS, when using CMB observations and the full $3\times 2$ pt
observables (blue) or only the galaxy and CMB lensing auto power spectra
(red). It can be seen that adding the galaxy – CMB lensing cross-correlation
reduces the degeneracy between the two parameters. Those contours correspond
to the $68^{\textrm{th}}$ and $95^{\textrm{th}}$ percentiles of the posterior
samples.

The constraints on $\log\lvert f_{R_{0}}\lvert$ are consistent and competitive
with previous studies using galaxy clustering observations, such as Hu et al.
(2016). Their tightest constraint is $\log\lvert f_{R_{0}}\lvert<-4.5$ when
combining observations of the CMB (temperature, polarization, lensing),
supernovae, baryon acoustic oscillation (BAO) measurements (including, but not
limited to, BAO measurements of LOWZ and CMASS) and galaxy weak lensing shear
correlation functions estimated from the Canada-France-Hawaii Telescope
Lensing Survey (Heymans et al., 2013). The cross-correlation of galaxy – CMB
lensing spectra enables us to obtain competitive constraints with a reduced
data-set.

####  5.2.1 Benefit of the cross-correlation

In order to isolate the advantage of the cross-correlation, we performed the
analysis without the cross-correlation power spectra. The cross-correlation is
primarily useful in reducing the degeneracy between $\log\lvert
f_{R_{0}}\lvert$ and the galaxy bias parameters. The degeneracy is reduced as
$C_{\ell}^{gg}$ is proportional to $b_{g}^{2}$ while $C_{\ell}^{\kappa g}$ is
proportional to $b_{g}$ (see Eq. 15 and Eq. 16). This effect is seen in Fig. 8
where the red contours do not contain the cross-correlation and the blue
contours do. As a result, the $95\%$ constraint obtained without the cross-
correlation is $\log\lvert f_{R_{0}}\lvert<-2.95$, compared to $\log\lvert
f_{R_{0}}\lvert<-4.12$ with the cross-correlation, i.e., more than an order of
magnitude improvement.

####  5.2.2 Result including $A_{\textrm{lens}}$ as a systematic

As was shown in Sect. 5.1, HS $f(R)$ cannot explain the $A_{\textrm{lens}}$
tension. When the $2\times 2$ pt observations are added, $\log\lvert
f_{R_{0}}\lvert$ is constrained to even smaller values, ruling out further
this kind of modified gravity resolution to the $A_{\textrm{lens}}$ tension.
Since it has been suggested that $A_{\textrm{lens}}$ could be due to a
systematic error (Planck Collaboration et al., 2020a), rather than a physical
effect, we also perform our analysis with $A_{\textrm{lens}}$ on the CMB
temperature and polarization power spectra only. We expect this to give
tighter constraints, because $A_{\textrm{lens}}$ can explain the excess of
smoothing in the CMB temperature and polarization power spectra without the
need for a large value of $\log\lvert f_{R_{0}}\lvert$. The resulting
marginalized contours on $A_{\textrm{lens}}$ and $\log\lvert f_{R_{0}}\lvert$
are shown in Fig. 9. As expected, $A_{\textrm{lens}}>1$ is preferred.
Unsurprisingly, the $95\%$ constraint of $\log\lvert f_{R_{0}}\lvert<-4.24$ is
tighter than the fiducial constraint ($\log\lvert f_{R_{0}}\lvert<-4.12$).

Figure 9: Marginalized constraints on $\log\lvert f_{R_{0}}\lvert$ and
$A_{\textrm{lens}}$, where $A_{\textrm{lens}}$ is considered as a systematic
effect and is only applied to the CMB temperature and polarization
anisotropies. Here, the $3\times 2$ pt observables are included, but are not
affected by $A_{\textrm{lens}}$. A value of $A_{\textrm{lens}}>1$ is still
preferred. The contours correspond to the $68^{\textrm{th}}$ and
$95^{\textrm{th}}$ percentiles of the posterior samples.

####  5.2.3 Effect of the binning scheme

We examine how changing the binning scheme impacts our constraints. In
particular, we defined three binning schemes, namely $\Delta\ell=10$,
$\Delta\ell=20$ (the fiducial case) and a unequal binning scheme with average
$\overline{\Delta\ell}=35$. The marginalized posteriors on $\log\lvert
f_{R_{0}}\lvert$ obtained with the three different binning schemes are
presented in Fig. 10. We see that the constraints become tighter as
$\Delta\ell$ decreases. The use of narrow multipole bin-widths makes it
possible to better use the shape of the power spectra to constrain $f(R)$
gravity. The $95\%$ confidence constraints are $\log\lvert
f_{R_{0}}\lvert<-4.18$, $\log\lvert f_{R_{0}}\lvert<-4.12$, and $\log\lvert
f_{R_{0}}\lvert<-3.84$ for $\Delta\ell=10$, $\Delta\ell=20$, and
$\overline{\Delta\ell}=35$, respectively. All of our constraints are
summarized in Tab. 2.

Figure 10: Marginalized posterior of $\log\lvert f_{R_{0}}\lvert$ using MGCLASS depending on the binning scheme used. The constraints become tighter as $\Delta\ell$ decreases. Case | Upper limit at $95\%$ confidence level
---|---
CMB + $C_{\ell}^{\kappa\kappa}$ | $-2.31$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $A_{\textrm{lens}}$ | $-2.35$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $A_{\textrm{lens}}$ in CMB only | $-2.46$
Fiducial: CMB + $C_{\ell}^{\kappa\kappa}$ \+ $C_{\ell}^{gg}$ \+ $C_{\ell}^{\kappa g}$ (with MGCLASS and $\Delta\ell=20$) | $-4.12$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $C_{\ell}^{gg}$ \+ $C_{\ell}^{\kappa g}$ with ReACT | $-4.61$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $C_{\ell}^{gg}$ \+ $C_{\ell}^{\kappa g}$, $\Delta\ell=10$ | $-4.18$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $C_{\ell}^{gg}$ \+ $C_{\ell}^{\kappa g}$, $\overline{\Delta\ell}=35$ | $-3.84$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $C_{\ell}^{gg}$ | $-2.95$
CMB + $C_{\ell}^{\kappa\kappa}$ \+ $C_{\ell}^{gg}$ \+ $C_{\ell}^{\kappa g}$ \+ $A_{\textrm{lens}}$ in CMB only | $-4.24$
Table 2: Constraints on $\log\lvert f_{R_{0}}\lvert$ obtained in the different
cases. CMB here refers to the temperature and polarization power spectra. The
CMB alone, which is not included within this table, gives an incongruous
constraint, reflecting the $A_{\textrm{lens}}$ tension, and is discussed in
the text in Sect. 5.1.

####  5.2.4 Effect of the priors

Figure 11: Posteriors of $\log\lvert f_{R_{0}}\lvert$ normalized by the
average value of the plateau using flat priors between $-7$ and $0$ (orange)
or between $-9$ and $0$ (blue). The red dashed lines correspond to the $95\%$
confidence level.

Our $95\%$ confidence intervals rely on the approach described in Sect. 4.8,
which aims at building prior-independent confidence intervals. In order to
check that our constraints indeed are prior independent, we ran a second MCMC
analysis in the fiducial setup, with a flat prior, $-9<\log\lvert
f_{R_{0}}\lvert<0$ (instead of the previous $-7<\log\lvert
f_{R_{0}}\lvert<0)$. The posteriors (normalized by the average value of the
plateau) are shown in Fig. 11. It can be seen that the $95\%$ constraint is
largely insensitive to the lower bound on the prior. More precisely, the
constraint using the new prior is $\log\lvert f_{R_{0}}\lvert<-4.17$, which is
close to the limit $\log\lvert f_{R_{0}}\lvert<-4.12$ that we found with the
previous prior.

The approach described in Sect. 4.8 indeed produces constraints independent of
the adopted prior. In contrast, if we directly use the $95^{\textrm{th}}$
percentile of the samples, the values associated to each prior (lower bound at
$-7$ or $-9$) would be, respectively, $-3.93$ and $-4.27$. This dependence on
the choice of prior demonstrates the danger in determining the constraints
directly from the sample percentiles; for instance, we extract a tighter
constraint when the lower bound of the prior is lower. This finding is
intuitive, since by decreasing the lower bound of the prior, we allow the MCMC
walkers to explore lower values in parameter space; the posterior distribution
thus shifts towards lower parameter values and, consequently, the
$95^{\textrm{th}}$ percentile becomes lower as well.

##  6 Conclusion

Modified gravity is a possible explanation for the observed accelerated
expansion of the Universe (Carroll et al., 2004). Hu-Sawicki (HS) $f(R)$
gravity (Hu & Sawicki, 2007) is an attractive example, motivating the search
for other possible observational signatures of the model. We searched for such
signatures as deviations from the predictions of General Relativity for large-
scale structure observations in a combined analysis of CMB, galaxy, and CMB
lensing measurements.

If the HS $f(R)$ model is to explain the accelerated expansion, the key
parameter is $\log\lvert f_{R_{0}}\lvert$. Primary CMB observations alone
constrain this parameter through the ISW effect and smoothing of the
temperature and polarization anisotropies by gravitational lensing. In
agreement with previous analyses, we find that measurements by Planck prefer
high values of $\log\lvert f_{R_{0}}\lvert$, which would imply a remarkable
deviation from General Relativity (see Sect. 5.1). However, this preference
disappears when the CMB lensing convergence power spectrum is added,
reflecting tension between the effects of lensing on the primary anisotropies
and the reconstructed lensing power spectrum. This tension is closely related
to the problem known as $A_{\textrm{lens}}$. We illustrate this by exhibiting
the degeneracy between $\log\lvert f_{R_{0}}\lvert$ and $A_{\textrm{lens}}$.
This analysis also demonstrates that HS $f(R)$ cannot by itself resolve this
tension.

Setting $A_{\textrm{lens}}=1$ and adding galaxy power spectra from BOSS and
their cross-correlation with CMB lensing, we then constrain $\log\lvert
f_{R_{0}}\lvert<-4.61$ at $95\%$ confidence (Sect. 5.2). This is our central
result. It means that while HS $f(R)$ may still explain the accelerated
expansion, there is no signature of the model in current observations of
large-scale structure; the model predictions do not substantially deviate from
those of General Relativity.

We also showed that the cross-correlation of galaxy and lensing measurements
is essential in breaking the degeneracy between galaxy bias and $\log\lvert
f_{R_{0}}\lvert$. Its addition improves the constraint on $\lvert
f_{R_{0}}\lvert$ by more than an order of magnitude (Sect. 5.2.1).

This paper is the first to make use of the cross-correlation between CMB
lensing and galaxy measurements to constrain HS $f(R)$ gravity. It paves the
way for future large-scale galaxy surveys to place more stringent constraints,
benefiting from lower noise and using galaxy lensing in addition to CMB
lensing.

###### Acknowledgements.

We thank Benjamin Bose for his help in using the ReACT code. We acknowledge
the use of the python libraries matplotlib (Hunter, 2007), numpy (Harris et
al., 2020) and scipy (Virtanen et al., 2020). Some of the results in this
paper have been derived using the healpy and HEALPix packages (Górski et al.,
2005)

## References

  * Abbott et al. (2023) Abbott, T. M. C., Aguena, M., Alarcon, A., et al. 2023, Phys. Rev. D, 107, 023531
  * Alam et al. (2015) Alam, S., Albareti, F. D., Allende Prieto, C., et al. 2015, ApJS, 219, 12
  * Alonso et al. (2019) Alonso, D., Sanchez, J., Slosar, A., & LSST Dark Energy Science Collaboration. 2019, MNRAS, 484, 4127
  * Arnold et al. (2022) Arnold, C., Li, B., Giblin, B., Harnois-Déraps, J., & Cai, Y.-C. 2022, MNRAS, 515, 4161
  * Blas et al. (2011) Blas, D., Lesgourgues, J., & Tram, T. 2011, J. Cosmology Astropart. Phys., 2011, 034
  * Bose et al. (2020) Bose, B., Cataneo, M., Tröster, T., et al. 2020, MNRAS, 498, 4650
  * Bose et al. (2023) Bose, B., Tsedrik, M., Kennedy, J., et al. 2023, MNRAS, 519, 4780
  * Brown et al. (2005) Brown, M. L., Castro, P. G., & Taylor, A. N. 2005, MNRAS, 360, 1262
  * Calabrese et al. (2008) Calabrese, E., Slosar, A., Melchiorri, A., Smoot, G. F., & Zahn, O. 2008, Phys. Rev. D, 77, 123531
  * Carroll et al. (2004) Carroll, S. M., Duvvuri, V., Trodden, M., & Turner, M. S. 2004, Phys. Rev. D, 70, 043528
  * Casas et al. (2023) Casas, S., Cardone, V. F., Sapone, D., et al. 2023, arXiv e-prints, arXiv:2306.11053
  * Cataneo et al. (2019) Cataneo, M., Lombriser, L., Heymans, C., et al. 2019, Mon. Not. Roy. Astron. Soc., 488, 2121
  * Cataneo et al. (2015) Cataneo, M., Rapetti, D., Schmidt, F., et al. 2015, Phys. Rev. D, 92, 044009
  * Desmond & Ferreira (2020) Desmond, H. & Ferreira, P. G. 2020, Phys. Rev. D, 102, 104060
  * Dossett et al. (2014) Dossett, J., Hu, B., & Parkinson, D. 2014, J. Cosmology Astropart. Phys., 2014, 046
  * Everitt et al. (2011) Everitt, C. W. F., Debra, D. B., Parkinson, B. W., et al. 2011, Phys. Rev. Lett., 106, 221101
  * Faulkner et al. (2007) Faulkner, T., Tegmark, M., Bunn, E. F., & Mao, Y. 2007, Phys. Rev. D, 76, 063505
  * Foreman-Mackey et al. (2013) Foreman-Mackey, D., Hogg, D. W., Lang, D., & Goodman, J. 2013, PASP, 125, 306
  * Gordon & Trotta (2007) Gordon, C. & Trotta, R. 2007, MNRAS, 382, 1859
  * Górski et al. (2005) Górski, K. M., Hivon, E., Banday, A. J., et al. 2005, ApJ, 622, 759
  * Harris et al. (2020) Harris, C. R., Millman, K. J., van der Walt, S. J., et al. 2020, Nature, 585, 357
  * Heymans et al. (2013) Heymans, C., Grocutt, E., Heavens, A., et al. 2013, MNRAS, 432, 2433
  * Hivon et al. (2002) Hivon, E., Górski, K. M., Netterfield, C. B., et al. 2002, ApJ, 567, 2
  * Hojjati et al. (2016) Hojjati, A., Plahn, A., Zucca, A., et al. 2016, Phys. Rev. D, 93, 043531
  * Hojjati et al. (2011) Hojjati, A., Pogosian, L., & Zhao, G.-B. 2011, J. Cosmology Astropart. Phys., 2011, 005
  * Hu et al. (2016) Hu, B., Raveri, M., Rizzato, M., & Silvestri, A. 2016, MNRAS, 459, 3880
  * Hu & Sawicki (2007) Hu, W. & Sawicki, I. 2007, Phys. Rev. D, 76, 064004
  * Hunter (2007) Hunter, J. D. 2007, Computing in Science & Engineering, 9, 90
  * Khoury & Weltman (2004) Khoury, J. & Weltman, A. 2004, Phys. Rev. D, 69, 044026
  * Kou & Bartlett (2023) Kou, R. & Bartlett, J. G. 2023, A&A, 675, A149
  * Lewis (2019) Lewis, A. 2019, arXiv e-prints, arXiv:1910.13970
  * Lewis & Challinor (2006) Lewis, A. & Challinor, A. 2006, Phys. Rep, 429, 1
  * Limber (1953) Limber, D. N. 1953, ApJ, 117, 134
  * Lombriser (2014) Lombriser, L. 2014, Annalen der Physik, 264, 259
  * Loureiro et al. (2019) Loureiro, A., Moraes, B., Abdalla, F. B., et al. 2019, MNRAS, 485, 326
  * Mead et al. (2015) Mead, A. J., Peacock, J. A., Heymans, C., Joudaki, S., & Heavens, A. F. 2015, MNRAS, 454, 1958
  * Naik et al. (2019) Naik, A. P., Puchwein, E., Davis, A.-C., Sijacki, D., & Desmond, H. 2019, MNRAS, 489, 771
  * Navarro & Van Acoleyen (2007) Navarro, I. & Van Acoleyen, K. 2007, J. Cosmology Astropart. Phys., 2007, 022
  * Oyaizu (2008) Oyaizu, H. 2008, Phys. Rev. D, 78, 123523
  * Perlmutter et al. (1999) Perlmutter, S., Aldering, G., Goldhaber, G., et al. 1999, ApJ, 517, 565
  * Piga et al. (2023) Piga, L., Marinucci, M., D’Amico, G., et al. 2023, J. Cosmology Astropart. Phys., 2023, 038
  * Planck Collaboration et al. (2020a) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020a, A&A, 641, A6
  * Planck Collaboration et al. (2020b) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020b, A&A, 641, A5
  * Planck Collaboration et al. (2020c) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020c, A&A, 641, A8
  * Pullen et al. (2016) Pullen, A. R., Alam, S., He, S., & Ho, S. 2016, MNRAS, 460, 4098
  * Ramachandra et al. (2021) Ramachandra, N., Valogiannis, G., Ishak, M., Heitmann, K., & LSST Dark Energy Science Collaboration. 2021, Phys. Rev. D, 103, 123525
  * Reid et al. (2016) Reid, B., Ho, S., Padmanabhan, N., et al. 2016, MNRAS, 455, 1553
  * Riess et al. (1998) Riess, A. G., Filippenko, A. V., Challis, P., et al. 1998, AJ, 116, 1009
  * Ross et al. (2012) Ross, A. J., Percival, W. J., Sánchez, A. G., et al. 2012, MNRAS, 424, 564
  * Sáez-Casares et al. (2023) Sáez-Casares, I., Rasera, Y., & Li, B. 2023, arXiv e-prints, arXiv:2303.08899
  * Sakr & Martinelli (2022) Sakr, Z. & Martinelli, M. 2022, J. Cosmology Astropart. Phys., 2022, 030
  * Saraf et al. (2022) Saraf, C. S., Bielewicz, P., & Chodorowski, M. 2022, MNRAS, 515, 1993
  * Singh et al. (2017) Singh, S., Mandelbaum, R., & Brownstein, J. R. 2017, MNRAS, 464, 2120
  * Smith et al. (2003) Smith, R. E., Peacock, J. A., Jenkins, A., et al. 2003, MNRAS, 341, 1311
  * Solà (2013) Solà, J. 2013, in Journal of Physics Conference Series, Vol. 453, Journal of Physics Conference Series, 012015
  * Swanson et al. (2008) Swanson, M. E. C., Tegmark, M., Blanton, M., & Zehavi, I. 2008, MNRAS, 385, 1635
  * Takahashi et al. (2012) Takahashi, R., Sato, M., Nishimichi, T., Taruya, A., & Oguri, M. 2012, ApJ, 761, 152
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261
  * Wang et al. (2023) Wang, Z., Hamidreza Mirpoorian, S., Pogosian, L., Silvestri, A., & Zhao, G.-B. 2023, arXiv e-prints, arXiv:2305.05667
  * Will (2014) Will, C. M. 2014, Living Reviews in Relativity, 17, 4
  * Winther et al. (2019) Winther, H. A., Casas, S., Baldi, M., et al. 2019, Phys. Rev. D, 100, 123540
  * Zhao et al. (2009) Zhao, G.-B., Pogosian, L., Silvestri, A., & Zylberberg, J. 2009, Phys. Rev. D, 79, 083513
  * Zonca et al. (2019) Zonca, A., Singer, L., Lenz, D., et al. 2019, Journal of Open Source Software, 4, 1298
  * Zucca et al. (2019) Zucca, A., Pogosian, L., Silvestri, A., & Zhao, G. B. 2019, J. Cosmology Astropart. Phys., 2019, 001


# Homogeneous sets in hypergraphs with forbidden order-size pairs

Maria Axenovich Karlsruhe Institute of Technology, Karlsruhe, Germany,
<EMAIL_ADDRESS>Research supported in part by the DFG grant FKZ AX
93/2-1. Dhruv Mubayi University of Illinois at Chicago, Chicago, USA,
<EMAIL_ADDRESS>Research partially supported by NSF grants DMS-1763317,
1952767, 2153576, a Humboldt research award and a Simons fellowship. Lea Weber
Karlsruhe Institute of Technology, Karlsruhe, Germany<EMAIL_ADDRESS>
###### Abstract

The well-known Erdős-Hajnal conjecture states that for any graph $F$, there
exists $\epsilon>0$ such that every $n$-vertex graph $G$ that contains no
induced copy of $F$ has a homogeneous set of size at least $n^{\epsilon}$. We
consider a variant of the Erdős-Hajnal problem for hypergraphs where we forbid
a family of hypergraphs described by their orders and sizes. For graphs, we
observe that if we forbid induced subgraphs on $m$ vertices and $f$ edges for
any positive $m$ and $0\leq f\leq\binom{m}{2}$, then we obtain large
homogeneous sets. For triple systems, in the first nontrivial case $m=4$, for
every $S\subseteq\\{0,1,2,3,4\\}$, we give bounds on the minimum size of a
homogeneous set in a triple system where the number of edges spanned by every
four vertices is not in $S$. For all $S$ we determine if the growth rate is
polylogarithmic. Several open problems remain.

##  1 Introduction

For an integer $r\geq 2$, an $r$-graph or $r$-uniform hypergraph is a pair
$H=(V,E)$, where $V=V(H)$ is the set of vertices and
$E=E(H)\subseteq\binom{V}{r}$ is the set of edges. A $2$-graph is simply a
graph. A homogeneous set is a set of vertices that is either a clique or a
coclique (independent set). For an $r$-graph $H$, let $h(H)$ be the size of a
largest homogeneous set. Given $r$-graphs $F,H$, say that $H$ is $F$-free if
$H$ contains no isomorphic copy of $F$ as an induced subgraph. We say that an
$r$-graph $F$ has the Erdős-Hajnal-property or simply EH-property if there is
a constant $\epsilon=\epsilon_{F}>0$ such that every $n$-vertex $F$-free
$r$-graph $H$ satisfies $h(H)\geq n^{\epsilon}$. A conjecture of Erdős and
Hajnal [12] states that any $2$-graph has the EH-property. The conjecture
remains open, see for example a survey by Chudnovsky [7], as well as [1, 4,
16], to name a few. When $F$ is a fixed graph and $G$ is an $F$-free
$n$-vertex graph, Erdős and Hajnal proved that $h(G)\geq 2^{c\sqrt{\log n}}$.
This was recently improved to $h(G)\geq 2^{c\sqrt{\log n\log\log n}}$ by
Bucić, Nguyen, Scott, and Seymour [6].

The Erdős-Hajnal conjecture fails for $r$-graphs, $r\geq 3$, already when $F$
is a clique of size $r+1$. Indeed, well-known results on off-diagonal
hypergraph Ramsey numbers show that there are $n$-vertex $r$-graphs that do
not have a clique on $r+1$ vertices and do not have cocliques on $f_{r}(n)$
vertices, where $f_{r}$ is an iterated logarithmic function (see [22] for the
best known results). Moreover, the following result (Claim 1.3. in [18]) tells
us exactly which $r$-graphs, $r\geq 3$, have the EH-property. Here $D_{2}$ is
the unique $3$-graph on $4$ vertices with exactly $2$ edges.

######  Theorem 1 (Gishboliner and Tomon [18]).

Let $r\geq 3$. If $F$ is an $r$-graph on at least $r+1$ vertices and $F\neq
D_{2}$, then there is an $F$-free $r$-graph $H$ on $n$ vertices such that
$h(H)=(\log n)^{O(1)}$.

It is natural to consider the EH-property for families of $r$-graphs instead
of a single $r$-graph. In this paper, we consider families determined by a
given set of orders and sizes. Several special cases of this have been
extensively studied over the years (see, e.g. [11]). For $0\leq
f\leq\binom{m}{r}$, we call an $r$-graph $F$ on $m$ vertices and $f$ edges an
$(m,f)$-_graph_ and we call the pair $(m,f)$ the order-size pair for $F$. Say
that $H$ is $(m,f)$-free if it contains no induced copy of an $(m,f)$-graph.
If $Q=\\{(m_{1},f_{1}),\ldots,(m_{t},f_{t})\\}$, say that $H$ is $Q$-free if
$H$ is $(m_{i},f_{i})$-free for all $i=1,\ldots,t$.

######  Definition 1.

Given $r\geq 2$ and $Q=\\{(m,f_{1}),\ldots,(m,f_{t})\\}$, let
$h(n,Q)=h_{r}(n,Q)$ be the minimum of $h(H)$, taken over all $n$-vertex
$Q$-free $r$-graphs $H$. Say that $Q$ has the EH-property if there exists
$\epsilon=\epsilon_{Q}>0$ such that $h(n,Q)>n^{\epsilon}$.

For example $h_{3}(n,\\{(4,0),(4,2)\\})=k$ means that any $n$-vertex $3$-graph
in which any $4$ vertices induce $1$, $3$, or $4$ edges has a homogenous set
of size $k$, and there is an $r$-graph $H$ as above with $h(H)=k$. We may omit
the subscript $r$ in the notation $h_{r}(n,Q)$ if it is obvious from context.
When $Q=\\{(m,f)\\}$ we use the simpler notation $h(n,m,f)$ instead of
$h(n,\\{(m,f)\\})$. Let us make two simple observations:

$h_{r}(n,Q)\leq h_{r}(n,Q^{\prime})\qquad\text{ if}\qquad Q\subseteq
Q^{\prime},$ (1)

$h_{r}(n,Q)=h_{r}(n,\overline{Q})\qquad\text{ where
}\qquad\overline{Q}=\left\\{\left(m,{m\choose r}-f\right):(m,f)\in
Q\right\\}.$ (2)

Our first result concerns 2-graphs, where we show that forbidding a single
order-size pair already guarantees large homogeneous sets.

######  Proposition 1.

For any integers $m,f$ with $m\geq 2$ and $0\leq f\leq\binom{m}{2}$ there
exists $c>0$ such that $h_{2}(n,m,f)>c\,n^{1/(m-1)}$.

It seems a challenging problem to give good upper bounds on $h_{2}(n,m,f)$.
For example, determining $h_{2}(n,m,{m\choose 2})$ is equivalent to
determining off-diagonal Ramsey numbers.

Our remaining results are in the hypergraph case $r=3$ and $m=4$. We shall be
considering sets $Q$ of pairs $(4,i)$ for $i\in\\{0,1,2,3,4\\}$. We do not
need to consider sets $Q$ that contain both $(4,0)$ and $(4,4)$ because
Ramsey’s theorem guarantees that for sufficiently large $n$ we cannot avoid
both of them. Using complementation (2), this leaves us with the following
sets:

  * •

$\\{(4,0)\\}$, $\\{(4,1)\\}$, $\\{(4,2)\\}$;

  * •

$\\{(4,0),(4,1)\\}$, $\\{(4,0),(4,2)\\}$, $\\{(4,0),(4,3)\\}$,
$\\{(4,1),(4,2)\\}$, $\\{(4,1),(4,3)\\}$; and

  * •

$\\{(4,0),(4,1),(4,2)\\}$, $\\{(4,0),(4,1),(4,3)\\}$,
$\\{(4,0),(4,2),(4,3)\\}$, $\\{(4,1),(4,2),(4,3)\\}$.

We address $h(n,Q)$ for each of these choices of $Q$.

We quickly obtain bounds for the first case using results in Ramsey theory
(note again that $h(n,4,f)=h(n,4,4-f)$). Recall that the Ramsey number
$R_{k}(s,t)$ is the minimum $n$ such that every red/blue edge-coloring of the
complete $n$-vertex $k$-graph yields either a monochromatic red $s$-clique or
a monochromatic blue $t$-clique. It is known [8] that $2^{ct\log t}\leq
R_{3}(4,t)\leq 2^{c^{\prime}t^{2}\log t}$. This yields positive constants $c$
and $c^{\prime}$, such that

$c^{\prime}\left(\frac{\log n}{\log\log
n}\right)^{1/2}<h_{3}(n,4,0)<c\frac{\log n}{\log\log n}.$ (3)

A more recent result of Fox and He [15] constructs $n$-vertex $3$-graphs with
every four vertices spanning at most two edges and independence number at most
$c\log n/\log\log n$. Together with (1) this yields positive a constant $c$,
such that

$h_{3}(n,4,1)\leq h_{3}(n,\\{(4,0),(4,1)\\})<c\frac{\log n}{\log\log n}.$ (4)

For the remaining cases when $|Q|=1$ we obtain bounds using recent results by
Fox and He [15] and by Gishboliner and Tomon [18]. Recall that
$f(n)=(1+o(1))g(n)$ means that there is a function $e(n)$ such that
$\lim_{n\rightarrow\infty}e(n)\rightarrow 0$ and $f(n)=g(n)+e(n)g(n)$.

######  Proposition 2.

There are positive constants $c_{1},c_{2}$ such that

$h_{3}(n,4,1)>c_{1}\,\left(\frac{\log n}{\log\log n}\right)^{1/2}$ (5)

and

$n^{c_{2}}<h_{3}(n,4,2)<(1+o(1))n^{1/2}.$ (6)

It is unclear if either bound for $h(n,4,1)$ above represents the correct
order of magnitude, but the lower bound certainly seems far off.

######  Problem 1.

Improve the exponent $1/2$ in the lower bound on $h_{3}(n,4,1)$.

Our next results address the case when $|Q|=2$. For the first case we have
constants $c,c^{\prime}>0$ such that

$c\,\frac{\log n}{\log\log n}<h_{3}(n,\\{(4,0),(4,1)\\}<c^{\prime}\frac{\log
n}{\log\log n}.$

The lower bound follows (after applying (2)) from an old result of Erdős and
Hajnal [11]. This is the first instance of a (different) conjecture of Erdős
and Hajnal [11] about the growth rate of generalized hypergraph Ramsey numbers
that correspond to our setting of $h(n,Q)$, where
$Q=\\{(m,f),(m,f+1),\ldots,(m,\binom{m}{r})\\}$. Recent results of the second
author and Razborov [21] on this problem determine, for each $m>r\geq 4$, the
minimum $f$ such that $h_{r}(n,Q)<c\log^{a}n$ for some $a$ and
$Q=\\{(m,f),\ldots,(m,\binom{m}{r})\\}$. When $r=3$, the minimum $f$ was
determined by Conlon, Fox, and Sudakov [8] for $m$ being a power of $3$ and
for growing $m$, as well as some other values.

For the second case when $|Q|=2$, we have $h_{3}(n,\\{(4,0),(4,2)\\})>n^{c}$
as follows immediately from (1) and (6). However, the value of $c$ obtained
from [18] is very small (less than 0.005). We improve this below to $1/5$ and
also obtain bounds for the other cases.

######  Theorem 2.

There is a positive constant $c_{1}$ such that for $n>5$

$h_{3}(n,\\{(4,0),(4,2)\\})>c_{1}\,n^{1/5},$ (7)

$h_{3}(n,\\{(4,0),(4,3)\\})>c_{1}\,n^{1/3},$ (8)

$c_{1}(n\log n)^{1/3}<h_{3}(n,\\{(4,1),(4,2)\\})<(1+o(1)){n}^{1/2},\mbox{ and
}$ (9)

$\frac{1}{2}\log n\leq h_{3}(n,\\{(4,1),(4,3)\\})<4(\log n)^{2}.$

We note the upper bound

$h_{3}(n,\\{(4,0),(4,2)\\})\leq h_{3}(n,\\{(4,0),(4,1),(4,2)\\})<c\sqrt{n\log
n}$

that we will see below. Apart from this we were not able to obtain nontrivial
upper bounds in (7) or (8). Improving the bounds in (7), (8) and (9) seems to
be an interesting open problem.

######  Problem 2.

Prove or disprove that

  * •

$h_{3}(n,\\{(4,0),(4,2)\\})=n^{1/2+o(1)}$,

  * •

$h_{3}(n,\\{(4,0),(4,3)\\})=n^{1+o(1)}$,

  * •

$h_{3}(n,\\{(4,1),(4,2)\\})=n^{1/2+o(1)}$.

Finally, we consider the case when $|Q|=3$. If $Q=\\{(4,0),(4,1),(4,2)\\}$,
then a $\overline{Q}$-free 3-graph is a partial Steiner system (STS), and it
is well known [13, 23, 5] that the minimum independence number of an
$n$-vertex partial STS has order of magnitude $\sqrt{n\log n}$. Thus
$h_{3}(n,Q)$ has order of magnitude $\sqrt{n\log n}$. If
$Q=\\{(4,1),(4,2),(4,3)\\}$, and $n\geq 4$, then it is a simple exercise to
show that any $Q$-free 4-graph on at least four vertices is a clique or
coclique and therefore $h_{3}(n,Q)=n$ for $n\geq 4$. The two remaining cases
are covered below.

######  Theorem 3.

Let $n\geq 4$. Then $h_{3}(n,\\{(4,0),(4,2),(4,3)\\})=n-1$ and

$h_{3}(n,\\{(4,0),(4,1),(4,3)\\})=\begin{cases}\frac{n}{2}&\text{if $n\equiv
0$ (mod 6)}\\\ \lceil\frac{n+1}{2}\rceil&\text{if $n\not\equiv 0$ (mod
6).}\end{cases}$

In Section 2 we prove Proposition 1 and in Section 3 we prove our results for
triple systems.

##  2  Graphs

In this section we prove Proposition 1. For a graph $G$, let $\omega(G)$ and
$\alpha(G)$ denote the size of a largest clique and coclique, respectively.

Proof of Proposition 1. We shall use induction on $m$ with basis $m=2$. In
this case $f\in\\{0,1\\}$. Note that $h(n,2,0)=h(n,2,1)=n=n^{1}=n^{1/(m-1)}$,
since forbidden graphs are either a non-edge or an edge. Consider an
$(m,f)$-free graph $G$ on $n$ vertices, $m\geq 3$, and assume that the
statement of the proposition holds for smaller values of $m$. We can also
assume that $G$ is not a complete graph, an empty graph, a cycle, or the
complement of a cycle, since we are done in these cases. Consider $\Delta$ and
$\overline{\Delta}$, the maximum degree of $G$ and of the complement
$\overline{G}$ of $G$, respectively. Using Brooks’ theorem, the chromatic
number of $G$ and of $\overline{G}$ is at most $\Delta$ and
$\overline{\Delta}$, respectively. Thus, $\alpha(G)\geq n/\Delta$ and
$\omega(G)\geq n/\overline{\Delta}$. Therefore, we can assume that $\Delta\geq
n^{(m-2)/(m-1)}$ and $\overline{\Delta}\geq n^{(m-2)/(m-1)}$, otherwise we are
done. Thus, there is a vertex with at least $n^{(m-2)/(m-1)}$ edges incident
to it and there is a vertex with at least $n^{(m-2)/(m-1)}$ non-edges incident
to it.

Assume first that $f\leq m-1$. Consider a vertex $v$ with at least
$n^{(m-2)/(m-1)}$ non-edges incident to it, i.e., with a set $X$ of vertices
each non-adjacent to $v$, $|X|\geq n^{(m-2)/(m-1)}$. Since $G$ is
$(m,f)$-free, $G[X]$ is $(m-1,f)$-free. Thus, by induction $h(G)\geq
h(G[X])\geq|X|^{1/(m-2)}\geq n^{1/(m-1)}.$

Now assume that $f\geq m$. Consider a vertex $v$ with at least
$n^{(m-2)/(m-1)}$ edges incident to it, i.e., with a set $X$ of vertices each
adjacent to $v$, $|X|\geq n^{(m-2)/(m-1)}$. Since $G$ is $(m,f)$-free, $G[X]$
is $(m-1,f-(m-1))$-free. Thus, by induction $h(G)\geq
h(G[X])\geq|X|^{1/(m-2)}\geq n^{1/(m-1)}.$ ∎

##  3 Triple systems

In this section we prove Proposition 2, Theorem 2 and Theorem 3. We will need
the following notions and result for our proofs. For an $r$-graph $H$ and one
of its vertices $v$, we define the link graph of $v$ to be the $(r-1)$-graph
$L(v)$ whose vertex set is $V(H)\setminus\\{v\\}$ and edge set is
$\\{e\subseteq V(H)\setminus\\{v\\}:e\cup\\{v\\}\in E(H)\\}$. When denoting
edges in $3$-graphs, we often shall omit parentheses and commas, for example
instead of writing $\\{x,y,z\\}$ we simply shall write $xyz$. For a $2$-graph
$G$, let $L(G)$ be the $3$-graph with vertex set $V(G)\cup\\{v\\}$, $v\not\in
V(G)$ and edge set $\\{uvw:uw\in E(G)\\}$. Finally, when we consider a
$3$-graph $H$, the link graph of a vertex $u\in V(H)$ restricted to a vertex
set $S$, denoted $L_{S}(u)$ is a graph on vertex set $S$ and edge set
$\\{vw:v,w\in S,uvw\in E(H)\\}$. A clique on $s$ vertices is denoted $K_{s}$.

We shall use the following theorem.

######  Theorem 4 (Fox and He [15], Thm. 1.4).

For all $t,s\geq 3$, any $3$-graph on more than $(2t)^{st}$ vertices contains
either a coclique on $t$ vertices or $L(K_{s})$.

###  3.1 Forbidden sets of size $1$

Proof of Proposition 2. First we consider the case $Q=\\{(4,1)\\}$.

To prove the lower bound on $h(n,4,1)$, we shall consider the complementary
setting and an arbitrary $n$-vertex $(4,3)$-free $3$-graph $H$. We shall apply
Theorem 4 with largest possible $t=s$ such that $(2t)^{st}<n$. In this case
$t=s\geq c(\log n/\log\log n)^{1/2}$. If $H$ has a coclique of size $t$, then
$h(H)\geq t$ and we are done. Otherwise $H$ contains a subgraph isomorphic to
$L=L(K_{s})$. Let $V(L)=\\{v\\}\cup V$, where all edges are incident to $v$,
$v\not\in V$. Note that $V$ induces a clique in $H$, otherwise $v$ and three
vertices of $V$ not inducing an edge give a $(4,3)$-subgraph. Thus, $h(H)\geq
s-1$. In each case $h(H)\geq c(\log n/\log\log n)^{1/2}$.

Now, we consider the case $Q=\\{(4,2)\\}$. The lower bound on $h(n,4,2)$
follows from a result of Gishboliner and Tomon [18]. The upper bound is
obtained by taking an affine plane of order $q$. More precisely, given a
sufficiently large $n$, choose a prime $q$ such that $n^{1/2}<q\leq
n^{1/2}+n^{0.29}$; such $q$ exists by density results about primes (see, e.g.,
[3]). Let $A(2,q)$ be the affine plane of order $q$. Let $H$ be the 3-graph
whose vertex set is some $n$-element subset of the point set of $A(2,q)$, and
whose edge set is the set of triples that are contained in some line in
$A(2,q)$. Let $S$ be a set of four vertices in $H$. If two lines each contain
at least three points in $S$, then they have two points in common, which is
impossible, hence at most one line contains at least three points in $S$. This
means that $S$ induces 0, 1 or 4 edges, and consequently, $H$ is $(4,2)$-free.
The largest clique in $H$ is the vertex set of a line, and has size at most
$q$. The largest coclique in $H$ is a cap set in $A(2,q)$ which is well known
to have size at most $q+2$. Hence $h(H)\leq q+2<n^{1/2}+n^{0.3}$ for
sufficiently large $n$. ∎

###  3.2 Forbidden sets of size $2$

We will need the following special cases of results of de-Caen [9] on the
hypergraph Turán problem and of Kostochka, Mubayi, and Verstraëte [20] on
independent sets in sparse hypergraphs.

######  Theorem 5 (de-Caen [9]).

Suppose that $n>k\geq 3$ and $H$ is an $n$-vertex 3-graph with more than
$(1-{k-1\choose 2}^{-1})(n^{3}/6)$ edges. Then $H$ contains a clique of size
$k$.

######  Theorem 6 (Kostochka, Mubayi, and Verstraëte [20]).

Suppose that $H$ is an $n$-vertex 3-graph in which every pair of vertices lies
in at most $d$ edges, where $0<d<n/(\log n)^{27}$. Then $H$ has an independent
set of size at least $c\sqrt{(n/d)\log(n/d)}$ where $c$ is an absolute
constant.

Proof of Theorem 2.

Case $Q=\\{(4,0),(4,2)\\}$.
Using complementation, we consider a $\\{(4,2),(4,4)\\}$-free $3$-graph $H$ on
$n$ vertices. Assume $n$ is sufficiently large. We shall show that $h(H)\geq
Cn^{1/5}$, for some constant $C>0$. For a vertex $v$ in $H$, let $K$ be a
clique in the link graph $L(v)$ of $v$. Then $K$ is a coclique in $H$, for an
edge within $K$ in $H$ together with $v$ yields a 4-clique in $H$. We will use
this observation repeatedly. Suppose that the complement of $H$ has
$(1-\gamma)(n^{3}/6)$ edges for some $0<\gamma<1$ and $k\geq 3$ is defined via

$\frac{1}{{k\choose 2}}\leq\gamma<\frac{1}{{k-1\choose 2}}.$

Then by Theorem 5, $H$ has a coclique of size at least $k$. If $k>n^{1/5}$,
then we are done so assume from now that $k<n^{1/5}$. As $H$ has at least
$\gamma n^{3}/6-n^{2}/2$ edges, by averaging, $H$ has two vertices $v,w$ whose
common neighborhood $S$ has size at least $\gamma n-4$. If $L_{S}(v)$ has an
induced $C_{4}$, then it induces a $4$-clique in $H$, for otherwise we obtain
a $(4,2)$-subgraph in $H$. Hence $L_{S}(v)$ has no induced $C_{4}$ and by
known results (see, e.g. [19]) it has a homogeneous set $T$ of size at least
$c|S|^{1/3}$. If $T$ is a clique in $L_{S}(v)$, then by our observation, $T$
is a coclique in $H$. If $T$ is a coclique in $L_{S}(v)$, then $T$ is a clique
in $L_{S}(w)$ for otherwise we obtain a $(4,2)$-subgraph in $H$ with $v,w$ and
two vertices in $T$. Again the observation implies that $T$ is a coclique in
$H$. Hence in both cases $T$ is a coclique in $H$ and $h(H)\geq|T|\geq
c|S|^{1/3}\geq(c/2)(\gamma n)^{1/3}$. Since $k<n^{1/5}$, we have
$\gamma>n^{-2/5}$ and $h(H)>(c/2)n^{1/5}$ completing the proof.

Case $Q=\\{(4,0),(4,3)\\}$.
We shall again consider the complementary case. Suppose that $H$ is a
$3$-graph on $n$ vertices that is $\\{(4,1),(4,4)\\}$-free. We will prove that
$h(H)\geq n^{1/3}$. Let $y$ be an arbitrary vertex of $H$ and consider the
link graph $L(y)$ of $y$.

Assume that there is an induced $2K_{2}$ in $L(y)$, i.e., that there is a set
$X$ of four vertices inducing exactly two disjoint edges in $L(y)$. Any three
vertices in $X$ form an edge in $H$, otherwise these three vertices and $y$
span exactly one edge in $H$, a contradiction. Thus, $X$ spans exactly $4$
edges in $H$, a contradiction. Thus, $L(y)$ is $2K_{2}$-free. In the graph
case it is known, that $2K_{2}$ has the Erdős-Hajnal property, and in
particular that any $n$-vertex graph with no induced $2K_{2}$ contains a
homogeneous set of size $cn^{1/3}$ (see e.g. [19]). Thus, $h(L(y))\geq
cn^{1/3}$.

Note that a $3$-clique in $L(y)$ is not an edge in $H$, since otherwise there
is a $4$-clique in $H$. Similarly, a $3$-coclique in $L(y)$ is not an edge in
$H$, since otherwise together with $y$ it induces a $(4,1)$-subgraph of $H$.
Thus, any set of vertices that is a clique in $L(y)$ or an independent set in
$L(y)$ is an independent set in $H$. Thus, $h(H)\geq h(L(y))\geq cn^{1/3}$
completing the proof.

Case $Q=\\{(4,1),(4,2)\\}$.
We now prove $c_{1}(n\log n)^{1/3}\leq
h(n,\\{(4,1),(4,2)\\})=h(n,\\{(4,3),(4,2)\\})\leq n^{1/2}+cn^{0.3}.$ The upper
bound follows immediately from the construction used in the upper bound in (6)
so we turn to the lower bound. Using (2), consider an $n$-vertex $3$-graph $H$
that is $\\{(4,2),(4,3)\\}$-free where $n$ is sufficiently large. Let $u,v$ be
a pair of vertices in $H$ whose common neighborhood $S$ has maximum size
$d>0$. Given vertices $x,y\in S$, the edges $xyu$ and $xyv$ are both in $H$
else $\\{u,v,x,y\\}$ induces a $(4,2)$ or $(4,3)$-graph. Next, any three
vertices $x,y,z\in S$, must form an edge of $H$ otherwise $\\{u,x,y,z\\}$
induces a $(4,3)$-graph. Therefore $S$ induces a clique in $H$ of size $d$. If
$d>n^{0.4}$, say, then we are done as $h(H)\geq d$. Recalling that $n$ is
large enough, we may assume that $d\leq n^{0.4}<n/(\log n)^{27}$. Now Theorem
6 yields a coclique in $H$ of size at least $c\sqrt{(n/d)\log n}$ for some
positive constant $c$. Consequently, there is a constant $c^{\prime}$ such
that

$h(H)\geq\max\,\\{d,\,c\sqrt{(n/d)\log n}\\}>c^{\prime}\,(n\log n)^{1/3}.$

Replacing $c^{\prime}$ by a possibly smaller constant $c_{1}$ yields the
result for all $n>4$.

Note that the set of maximal cliques in any $\\{(4,2),(4,3)\\}$-free 3-graph
$H$ forms a linear (maybe non-uniform) hypergraph $\mathcal{H}$. Thus,
determining $h(H)$ amounts to finding $\max\\{t,|X|\\}$, where $t$ is the size
of a larges hyperedge and $X$ is a largest set of vertices in $\mathcal{H}$
with no three in the same hyperedge.

Case $Q=\\{(4,1),(4,3)\\}$.
Finally, we prove $\frac{1}{2}\log n\leq h(n,\\{(4,1),(4,3)\\})\leq 4(\log
n)^{2}$. For the lower bound let $H$ be an $n$-vertex $Q$-free $3$-graph. Pick
a vertex $v$ in $H$ and consider its link graph $L(v)$. Since
$R_{2}(t,t)<4^{t-1}$ (see Erdős and Szekeres [14]), we see that $L(v)$ has a
clique or coclique $K$ of size at least $\frac{1}{2}\log n$. In the first
case, $K$ is a clique in $H$, else we find a $(4,3)$-subgraph in $H$, and in
the second case, $K$ is a coclique in $H$, else we find a $(4,1)$-subgraph in
$H$.

We now turn to the upper bound. Let $\chi$ be a red/blue coloring of an
$n$-vertex complete graph on vertex set $V$ in which every monochromatic
clique has size at most $2\log n$. Such a coloring exists by the classical
result of Erdős [10]. Let $H$ be the $3$-graph on vertex set $V$ whose edge
set consists of all triples of vertices that induce a triangle with one or
three red edges under $\chi$.

Consider four vertices $x,y,z,$ and $w$ of $H$ and assume that $xyz$ is an
edge in $H$. Then the triangle $xyz$ has one or three red edges under $\chi$.
Assume that $xy$ is red. We need to treat two cases when $xz$ and $yz$ are
blue and when $xz$ and $yz$ are red. In each of these cases, consider the
fourth vertex $w$ and possible colors on the edges from $w$ to $x,y$ and $z$.
In each of these cases $\\{x,y,z,w\\}$ induces exactly two or exactly four
edges. Thus, any four vertices of $H$ induce none, two, or four edges. So, $H$
is $Q$-free. Consider a homogeneous set $S$ in $H$. If it is a clique, all
triangles with vertices in $S$ have exactly one or three red edges under
$\chi$. Thus, the graph induced by $S$ is a pairwise vertex disjoint union of
red cliques. Either one of these red cliques has size at least $\sqrt{|S|}$
or, by taking a single vertex from each of these red cliques we see that there
is a blue clique of size at least $\sqrt{|S|}$ under $\chi$. Since each
monochromatic clique in the coloring $\chi$ has size at most $2\log n$, we
have that $|S|\leq 4(\log n)^{2}$. Similarly, if $S$ is an independent set in
$H$, all triangles with vertices in $S$ have exactly one or three blue edges
under $\chi$ and again we get that $|S|\leq 4(\log n)^{2}$.∎

###  3.3 Forbidden sets of size $3$

We will need the following structural characterization of $Q$-free $3$-graphs
for $Q=\\{(4,1),(4,3),(4,4)\\}$.

######  Theorem 7 (Frankl and Füredi [17]).

Let $H$ be an $\\{(4,1),(4,3),(4,4)\\})$-free $3$-graph. Then $H$ is
isomorphic to one of the following $3$-graphs:

  1. 1.

A blow-up of the $6$ vertex $3$-graph $H^{\prime}$ with vertex set
$V(H^{\prime})=[6]$ and edge set
$E(H^{\prime})=\\{123,124,345,346,561,562,135,146,236,245\\}$. Here for the
blow-up we replace every vertex of $H^{\prime}$ by an independent set, and
whenever we have $3$ vertices from three distinct of those sets, they induce
an edge if and only if the corresponding vertices in $H^{\prime}$ do.

  2. 2.

The $3$-graph whose vertices are the points of a regular $n$-gon where $3$
vertices span an edge if and only if the corresponding points span a triangle
whose interior contains the center of the $n$-gon.

Proof of Theorem 3.

Case $Q=\\{(4,1),(4,3),(4,4)\\}$.
We are to prove that

$h(n,\\{(4,0),(4,1),(4,3)\\})=h(n,Q)=\begin{cases}\frac{n}{2}&\text{if
$n\equiv 0$ (mod 6)}\\\ \lceil\frac{n+1}{2}\rceil&\text{if $n\not\equiv 0$
(mod 6)}.\end{cases}$

First, let us prove that the second 3-graph $H$ in Theorem 7 has independence
number exactly $\lceil{(n+1)/2)}\rceil$. Assume the vertex set is $[n]$ and
the vertices are labeled by consecutive integers in clockwise orientation. The
lower bound is by taking $\lceil{(n+1)/2)}\rceil$ consecutive vertices on the
$n$-gon and noting that no three of them contain the center in their interior.
For the upper bound, let us see how many vertices can lie in an independent
set containing $1$. When $n$ is odd, the triangle formed by
$\\{1,i,(n-1)/2+i\\}$ contains the center and hence is an edge. Therefore we
may pair the elements of $[n]\setminus\\{1\\}$ as
$(2,(n+3)/2),(3,(n+5)/2),\ldots,((n+1)/2,n)$ and note that each pair can have
at most one vertex in an independent set containing 1. Hence the maximum size
of an independent set containing 1 is at most $(n+1)/2$ and by vertex
transitivity of $H$, the independence number of $H$ is at most $(n+1)/2$. For
$n$ even we consider the $n/2-1$ pairs $(2,n/2+1),(3,n/2+2),\ldots,(n/2,n-1)$
and add the vertex $n$ to get an upper bound $n/2+1=\lceil{(n+1)/2)}\rceil$.

Next we observe that the $6$-vertex 3-graph $H^{\prime}$ in Theorem 7 has
independence number exactly $3$ (we omit the short case analysis needed for
the proof). Hence if we blow-up each vertex of $H^{\prime}$ into sets of the
same size, then we obtain $n$-vertex $3$-graphs with independence number
exactly $n/2$ whenever $n\equiv 0$ (mod 6). This concludes the proof of the
upper bound.

For the lower bound, let $H$ be $Q$-free. Then by Theorem 7, $H$ is isomorphic
to one of the two graphs described in Theorem 7. If $H$ is isomorphic to the
second graph, then we have already shown that its independence number is at
least $(n+1)/2$, so assume that $H$ is isomorphic to the blow-up of the
$6$-vertex $10$-edge $3$-graph $H^{\prime}$. There are $10$ non-edges in
$H^{\prime}$. Let $V_{1},\ldots,V_{6}$ be the blown up vertex sets. Since
every vertex $i\in[6]$ in $H^{\prime}$ is contained in exactly $5$ non-edges,
we obtain

$5n=5\sum\limits_{i\in[6]}|V_{i}|=\sum\limits_{j_{1}j_{2}j_{3}\not\in
E(H)}|V_{j_{1}}|+|V_{j_{2}}|+|V_{j_{3}}|.$

By the pigeonhole principle, there is a non-edge $i_{1}i_{2}i_{3}$, such that
$|V_{i_{1}}|+|V_{i_{2}}|+|V_{i_{3}}|\geq n/2$. Our bound follows by observing
that for any non-edge $i_{1}i_{2}i_{3}$ in the original $3$-graph $H^{\prime}$
the set $V_{i_{1}}\cup V_{i_{2}}\cup V_{i_{3}}$ is an independent set. This
gives an independent set of size at least $n/2$, and if $n\not\equiv 0$ (mod
6), then equality cannot hold throughout (a short case analysis, which we
omit, is needed to prove this) and we obtain an independent set of size
strictly greater than $n/2$ as required.

Case $Q=\\{(4,0),(4,2),(4,3)\\}$.
We now prove $h(n,\\{(4,0),(4,2),(4,3)\\})=n-1,$ for $n\geq 4$. Let $H$ be a
$3$-graph that is a clique on $n-1$ vertices and a single isolated vertex,
then $H$ is $Q$-free, giving us the upper bound.

For the lower bound, let $H$ be a $Q$-free $3$-graph on $n$ vertices, $n\geq
4$. Assume that $H$ is not a clique and not a coclique. We shall show that $H$
is a clique and a single isolated vertex. Consider a maximal clique $S$ in
$H$. Since $|S|<n$, there is a vertex $v\in V(H)\setminus S$. From the
maximality of $S$, $L_{S}(v)$ is not a clique. If $L_{S}(v)$ contains an edge,
then we have that for some vertices $x,y,y^{\prime}$, $xy\in E(L_{S}(v))$ and
$xy^{\prime}\not\in E(L_{S}(v))$. But then $\\{v,x,y,y^{\prime}\\}$ induces a
$(4,2)$ or a $(4,3)$-graph, a contradiction. Thus, $L_{S}(v)$ is an empty
graph, i.e., there is no edge in $H$ containing $v$ and two vertices of $S$.
Now assume there exists a second vertex $v^{\prime}\in
V(H)\setminus(S\cup\\{v\\})$. Then by the same argument as above, $v^{\prime}$
is also not contained in any edge with two vertices from $S$. Consider triples
$vv^{\prime}x$, $x\in S$. Since $|S|\geq 3$, by the pigeonhole principle there
are two vertices $x,x^{\prime}\in S$ such that either
$vv^{\prime}x,vv^{\prime}x^{\prime}\in E(H)$ or
$vv^{\prime}x,vv^{\prime}x^{\prime}\not\in E(H)$. Then
$\\{v,v^{\prime},x,x^{\prime}\\}$ induces $2$ or $0$ edges respectively, a
contradiction. Thus, $|S|=n-1$ and $v$ is an isolated vertex. ∎

##  4 Concluding Remarks

Fix integers $m>r$. Say that a set $Q$ of order size pairs
$\\{(m,f_{1}),\ldots,(m,f_{t})\\}$ is Erdős-Hajnal (EH) if there exists
$\epsilon=\epsilon_{Q}$ such that $h_{r}(n,Q)>n^{\epsilon}$. As $|Q|$ grows,
the collection of $Q$-free $r$-graphs is more restrictive, and hence
$h_{r}(n,Q)$ grows (assuming that large $Q$-free $r$-graphs are not forbidden
to exist by Ramsey’s theorem). The case when $h_{r}(n,Q)=\Omega(n)$ was
treated by the first author and Balogh [2] when $r=2$. A natural question then
is to ask what is the smallest $t$ such that every $Q$ of size $t$ is EH. Call
this minimum value $EH_{r}(m)$. Our results for $r=3$ show that for $m=4$, all
$Q$ of size 3 are EH, but there are $Q$ of size 2 which are not EH.
Consequently, $EH_{3}(4)=3$.

In order to further study $EH_{r}(m)$, we need another definition. Given
integers $m\geq r\geq 3$, let $g_{r}(m)$ be the number of edges in an
$r$-graph on $m$ vertices obtained by first taking a partition of the $m$
vertices into almost equal parts, then taking all edges that intersect each
part, and then recursing this construction within each part. For example,
$g_{3}(7)=13$ since we start with a complete 3-partite 3-graph with part sizes
$2,2,3$ and then add one edge within the part of size 3. It is known (see,
e.g. [21]) that as $r$ grows we have

$g_{r}(m)=(1+o(1))\frac{r!}{r^{r}-r}{m\choose r}.$

Note that $\frac{r!}{r^{r}-r}$ approaches 0 as $r$ grows. The second author
and Razborov [21] proved that for all fixed $m>r>3$, there are $n$-vertex
$r$-graphs which are $Q$-free, $Q=\\{(m,i):g_{r}(m)<i\leq{m\choose r}\\}$,
with $h(G)=O(\log n)$. In other words, there exists $Q$ of size ${m\choose
r}-g_{r}(m)$ which is not EH. This proves that $EH_{r}(m)\geq{m\choose
r}-g_{r}(m)+1$.

Erdős and Hajnal [11] proved that for all $m>r\geq 3$, the set
$Q=\\{(m,i):g_{r}(m)\leq i\leq{m\choose r}\\}$ is EH. In other words, they
proved that every $n$-vertex $r$-graph in which every set of $m$ vertices
spans less then $g_{r}(m)$ edges has an independent set of size at least
$n^{\epsilon}$, where $\epsilon$ depends only on $r$ and $m$. This is a
particular set $Q$ of size ${m\choose r}-g_{r}(m)+1$ that is EH and we
speculate that every other set $Q$ of this size is also EH.

######  Problem 3.

Prove or disprove that for all $m>r>2$,

$EH_{r}(m)={m\choose r}-g_{r}(m)+1.$

We end by noting that $EH_{3}(4)=3={4\choose 3}-g_{3}(4)+1$.

## References

  * [1] N. Alon, J. Pach, and J. Solymosi. Ramsey-type theorems with forbidden subgraphs, Paul Erdős and his mathematics, Combinatorica 21 (2001), no. 2, 155–170.
  * [2] M. Axenovich and J. Balogh. Graphs having small number of sizes on induced k-subgraphs, SIAM J. Discrete Math. 21, no. 1, (2007) 264–272.
  * [3] R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes, II. Proceedings of the London Mathematical Society 83 (2001) (3): 532–562.
  * [4] N. Bousquet, A. Lagoutte, and S. Thomassé. The Erdős-Hajnal conjecture for paths and antipaths, Journal of Combinatorial Theory, Series B 113 (2015) 261–264.
  * [5] M. de Brandes, K. Phelps, and V. Rödl. Coloring Steiner triple systems, SIAM Journal on Algebraic Discrete Methods 3.2 (1982) 241–249.
  * [6] M. Bucić, T. Nguyen, A. Scott, and P. Seymour. A loglog step towards Erdős-Hajnal, arXiv preprint arXiv:2301.10147 (2023).
  * [7] M. Chudnovsky. The Erdős-Hajnal conjecture – a survey, Journal of Graph Theory 75 (2014) 178–190.
  * [8] D. Conlon, J. Fox, and B. Sudakov. Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), no. 1, 247–266.
  * [9] D. de Caen. Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combin. 16 (1983), 5–10.
  * [10] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc.53(1947), 292–294.
  * [11] P. Erdős and A. Hajnal. On Ramsey like theorems, Problems and results,  Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) , pp. 123–140, Inst. Math. Appl., Southendon-Sea, 1972.
  * [12] P. Erdős and A. Hajnal. Ramsey-type theorems, Discrete Applied Mathematics 25 (1989) 37–52.
  * [13] P. Erdős, A. Hajnal, and B. Rothschild. On chromatic number of graphs and set-systems, Acta Math. Hungar 16 (1966) 61–99.
  * [14] P. Erdős and G. Szekeres. A combinatorial problem in geometry, Compositio Mathematica, 2, (1935) 463–470.
  * [15] J. Fox and X. He. Independent sets in hypergraphs with a forbidden link, Proceedings of the London Mathematical Society. 123(4), (2021) 384–409.
  * [16] J. Fox, J. Pach, and A. Suk. Erdős-Hajnal conjecture for graphs with bounded VC-dimension,  33rd International Symposium on Computational Geometry, Art. No. 43, 15 pp., LIPIcs. Leibniz Int. Proc. Inform., 77, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2017).
  * [17] P. Frankl and Z. Füredi. An exact result for 3-graphs, Discrete Math. 50 no. 2-3, (1984) 323–328.
  * [18] L. Gishboliner and I. Tomon. On 3-graphs with no four vertices spanning exactly two edges, arXiv:2109.04944 (2022).
  * [19] A. Gyárfás. Reflections on a problem of Erdős and Hajnal, The Mathematics of Paul Erdős II. Springer, New York, NY, (2013) 135–141.
  * [20] A. Kostochka, D. Mubayi, and J. Verstraëte. On independent sets in hypergraphs, Random Structures and Algorithms 44 (2014), no. 2, 224.239.
  * [21] D. Mubayi and A. Razborov. Polynomial to exponential transition in Ramsey theory, Proceedings of the London Mathematical Society 122.1 (2021) 69–92.
  * [22] D. Mubayi and A. Suk. New lower bounds for hypergraph Ramsey numbers, Bull. Lond. Math. Soc. 50 (2018), no. 2, 189–201.
  * [23] K. Phelps and V. Rödl. Steiner triple systems with minimum independence number, Ars Combin 21 (1986) 167–172.