# A family of concordance homomorphisms from Khovanov homology

William Ballinger

###### Abstract.

By considering a version of Khovanov homology incorporating both the Lee and
$E(-1)$ differentials, we construct a $1$-parameter family of concordance
homomorphisms similar to the Upsilon invariant from knot Floer homology. This
invariant gives lower bounds on the slice genus and can be used to prove that
certain infinite families of pretzel knots are linearly independent in the
smooth concordance group.

##  1\. Introduction

The Upsilon invariant, introduced by Ozsváth, Stipsicz, and Szabó in [9], is
defined in terms of the knot Floer homology of a knot and contains a great
deal of information about the smooth concordance group. The definition,
especially as formulated by Livingston [7], can be abstracted to avoid
reference to any details of the construction of knot Floer homology, only
relying on the fact that it associates a chain complex with two independent
filtrations to any knot. This suggests an approach to creating new knot
invariants by constructing a similar filtered complex in a different setting,
which was used for example in [6] to define knot invariants using a second
filtration on a version of the Khovanov-Rozansky $\operatorname{sl}(n)$
homology. This paper will give a new way to define Upsilon-like invariants of
knots, this time using the Lee and $E(-1)$ differentials on Khovanov
($\operatorname{sl}(2)$) homology. Most of the results here should extend to
the setting of $\operatorname{sl}(n)$ homology, since analogues of the Lee and
$E(-1)$ differentials are also present there. Making this extension would
require adapting the invariance proofs from [1] to the $\operatorname{sl}(n)$
setting, so we will focus on the $\operatorname{sl}(2)$ case for simplicity
and ease of computation.

######  Theorem 1.1.

There is a knot invariant $\Phi_{K}(\alpha)$ for $K$ a knot in $S^{3}$ and
$\alpha\in[0,2]$ with the following properties:

  * •

For fixed $\alpha$, $\Phi_{K}(\alpha)$ is a real-valued concordance
homomorphism.

  * •

For fixed $K$, $\Phi_{K}(\alpha)$ is a continuous piecewise linear function of
$\alpha$.

  * •

$|\Phi_{K}(\alpha)|\leq 2g_{4}(K)\Lambda(\alpha)$, where
$\Lambda(\alpha)=1-|\alpha-1|$.

The above properties are all shared with $\Upsilon$, but notably there is no
analogue of the symmetry $\Upsilon_{K}(t)=\Upsilon_{K}(2-t)$. Another property
shared with $\Upsilon$ is that the lines forming the graph of $\Phi_{K}$ are
constrained by the Khovanov homology of $K$:

######  Theorem 1.2.

Suppose $L$ is a line meeting the graph of $\Phi_{K}$ in a segment, and let
$\ell_{0}$ and $\ell_{1}$ be the second coordinates of the intersections of
$L$ with the vertical lines $\alpha=0$ and $\alpha=1$, respectively. Then the
reduced Khovanov homology of $K$ is nonzero in homological grading
$\ell_{0}/2$ and delta grading $\ell_{1}$. In particular, $\ell_{0}$ and
$\ell_{1}$ are even integers.

For some simple knots $K$, the function $\Phi_{K}$ can be computed by directly
examining the Khovanov homology. In particular, this can be done for the three
stranded pretzel knots based on computations of their reduced Khovanov
homology due to Manion [8], leading to conclusions about their place in the
smooth concordance group.

######  Theorem 1.3.

For any two sequences $a_{k},b_{k}$ of odd integers with $2k<a_{k}<b_{k}$, the
sequence of knots $\\{P(-2k,a_{k},b_{k})\\}_{k=1}^{\infty}$ are a basis for a
$\mathbb{Z}^{\infty}$ summand of the smooth concordance group.

None of the knots appearing in this theorem are algebraically slice, and it
seems likely that this theorem, and even stronger statements, could be proven
using other concordance invariants such as the Tristam-Levine signature.
However, this would require a detailed analysis of the roots of the Alexander
polynomials of these knots while, once the basic properties of the invariant
are set up and the Khovanov homology of these knots is known, finding their
$\Phi$ invariants is a fairly simple calculation.

The invariant $\Phi_{K}$ can also be calculated for small torus knots using
their known Khovanov homologies (taken from [2]). Despite the complexity of
these homology groups, a relatively simple pattern emerges which leads to
Conjecture 6.3 on the values of $\Phi_{T_{p,q}}$ for any $p,q$.

##  2\. A bifiltered complex from a knot

In [1], for every knot $K$ a $\mathbb{Z}$-graded, $\mathbb{Z}$-filtered chain
complex over $\mathbb{Z}[x]$ $C(K)$ was defined. In this complex, the
differential lowers the grading by $3$ and multiplication by $x$ lowers it by
$2$. The following properties of $C(K)$, proven in [1], will be relavant here:

######  Proposition 2.1.

Forgetting the filtration, the homology of $C(K)$ is isomorphic to
$\mathbb{Z}[x]$, and the $E_{2}$ page of the spectral sequence coming from
$C(K)$ is the $\mathcal{F}_{3}$ Khovanov homology of $K$ as defined in [5]. If
$K$ and $K^{\prime}$ are related by a cobordism of genus $g$, there is a
filtered chain map $C(K)\to C(K^{\prime})$ whose induced map on homology is
multiplication by $(2x)^{g}$, and if $K_{-}$ and $K_{+}$ are related by a
crossing change in which $K_{-}$ has a negative crossing and $K_{+}$ a
positive crossing, there is a filtered chain map $C(K_{-})\to C(K_{+})$
inducing an isomorphism on homology.

The above identification between the $E_{2}$ page and the Khovanov homology
relates the filtration on $C(K)$ to the homological grading, and the grading
on $C(K)$ to the linear combination $q-3h$ of the quantum and homological
grading. We will call $q-3h$ the internal grading on Khovanov homology, just
as in [1].

This paper will be concerned with the quotient of $C(K)$ setting the variable
$x$ to $1$. To make the resulting invariants better behaved, we will also
change base to $\mathbb{Q}$, although any field of characteristic not $2$
would work just as well and produce a different invariant. The result is a
bifiltered chain complex incorporating both the Lee (or $d_{1}$) and $d_{-1}$
differentials into Khovanov homology.

######  Definition 2.2.

For a knot $K$, let $\operatorname{CKh}^{\pm}(K)$ be the chain complex
$(C(K)\otimes\mathbb{Q})/(x-1)$, and for integers $i,j$ let
$\operatorname{CKh}^{\pm}(K)_{i,j}(K)$ be the subgroup of
$\operatorname{CKh}^{\pm}(K)$ generated by the images of elements of $C(K)$ in
grading at least $i$ and filtration level at least $j$.

Since $x$ has degree $2$, in addition to the two filtrations
$\operatorname{CKh}^{\pm}(K)$ inherits a $\mathbb{Z}/2\mathbb{Z}$ grading from
the grading on $C(K)$. This will not be needed for establishing the formal
properties of the invariant, but can be useful in computation. This complex
has the following elementary properties, immediately from Proposition 2.1:

######  Proposition 2.3.

The differential on $\operatorname{CKh}^{\pm}(K)$ carries
$\operatorname{CKh}^{\pm}(K)_{i,j}(K)$ into
$\operatorname{CKh}^{\pm}(K)_{i-3,j}(K)$, and the homology of
$\operatorname{CKh}^{\pm}(K)$ with respect to this differential is isomorphic
to $\mathbb{Q}$. If $K$ and $K^{\prime}$ are related by a cobordism of genus
$g$, then there is a chain map
$\operatorname{CKh}^{\pm}(K)\to\operatorname{CKh}^{\pm}(K^{\prime})$ that
sends $\operatorname{CKh}^{\pm}_{i,j}(K)$ into
$\operatorname{CKh}^{\pm}_{i-2g,j}(K^{\prime})$ and induces an isomorphism on
homology. If $K_{-}$ and $K_{+}$ are related by a crossing change in which
$K_{-}$ has a negative crossing and $K_{+}$ a positive crossing, there is a
filtered chain map
$\operatorname{CKh}^{\pm}(K_{-})\to\operatorname{CKh}^{\pm}(K_{+})$ inducing
an isomorphism on homology.

Since the differential on $\operatorname{CKh}^{\pm}(K)$ lowers the first of
the filtrations, this isn’t quite a filtered chain complex in the usual sense.
However, most of what one might like to do to a filtered chain complex can
still be done here. In particular, collapsing the two filtrations to one along
a one-parameter family of directions produces a family of concordance
homomorphisms $\Phi_{K}(\alpha)$ for $\alpha\in[0,2]$ very similar to the
$\Upsilon$ invariant from Heegaard Floer homology.

######  Theorem 2.4.

For each $\alpha\in[0,2]$, $\Phi_{K}(\alpha)$ is a real valued concordance
homomorphism, and $\Phi_{K}$ is a piecewise linear function of $K$. At the
endpoints, $\Phi_{K}(0)=\Phi_{K}(2)=0$, and the slopes of $\Phi_{K}$ at $0$
and $2$ are $s(K)$ and $-t(K)$, respectively.

Just like $\Upsilon$, the invariant $\Phi$ gives lower bounds on the slice
genus of $K$.

######  Theorem 2.5.

$|\Phi(K,\alpha)|\leq 2g_{4}(K)\min(\alpha,2-\alpha)$

Note that, although the slice genus bound from $\Upsilon$ has the same shape
as this one, in the case of $\Upsilon$ the symmetry
$\Upsilon_{K}(t)=\Upsilon_{K}(2-t)$ means that all of the information is
contained in the bound over the interval $[0,1]$. In the case of $\Phi$,
however, it is possible that the bound on the interval $[1,2]$ has additional
information, although this does not occur in any known example.

##  3\. Preliminaries on homological algebra

######  Definition 3.1.

A semibifiltered complex is a chain complex $(C,d)$ over a field together with
an increasing $\mathbb{Z}\oplus\mathbb{Z}$-filtration $C_{i,j}$ of $C$, with
no assumption on how the differential $d$ interacts with the complex. A
semibifiltered complex is $(m,n)$-bounded if $d(C_{i,j})\subset C_{i+m,j+n}$.

In general, we will consider filtered chain maps between semibifiltered
complexes, but not require that homotopies between these maps be filtered. In
particular, a homotopy equivalence of semibifiltered complexes $C,C^{\prime}$
consists of filtered chain maps $C\to C^{\prime}$ and $C^{\prime}\to C$, such
that both composite maps are chain homotopic to the identity via not-
necessarily-filtered homotopies. With this definition, the homotopy
equivalence class of $\operatorname{CKh}^{\pm}(K)$ as a semibifiltered complex
is an invariant of the concordance class of $K$.

From an $(m,n)$-bounded semibifiltered complex $(C,d)$, one can construct
associated graded complexes with respect to both filtrations, producing a
$\mathbb{Z}\oplus\mathbb{Z}$-graded chain complex whose differential has
degree $(m,n)$. Similarly, one can take the associated graded complex with
respect to only the second filtration, producing a $\mathbb{Z}$-graded,
$\mathbb{Z}$ filtered chain complex whose differential has degree $n$ with
respect to the grading and changes the filtration by at least $m$. Call the
first of these constructions the associated graded complex, and the second the
vertical associated graded complex. Note that these concepts depend on the
choice of $(m,n)$ \- If $C$ is $(m,n)$-bounded, then it is also
$(m^{\prime},n^{\prime})$-bounded for any $m^{\prime}\leq m$ and
$n^{\prime}\leq n$, but treating $C$ as an $(m^{\prime},n^{\prime})$-bounded
complex and taking the associated graded generally results in a complex with
vanishing differential.

A straightforward homological perturbation argument proves the following:

######  Lemma 3.2.

Any $(m,n)$-bounded semibifiltered complex $(C,d)$ is homotopy equivalent to
an $(m,n)$-bounded semibifiltered complex $(C^{\prime},d)$ such that the
associated graded module of $C^{\prime}$ is isomorphic to the homology of the
associated graded complex of $(C,d)$. Furthermore, the vertical associated
graded complex of $(C^{\prime},d)$ depends only on the vertical associated
graded complex of $(C,d)$.

The complex $\operatorname{CKh}^{\pm}(K)$ is $(-3,0)$-bounded, and the
homology of its associated graded complex is precisely the underlying vector
space of the rational Khovanov chain complex, as originally defined. This
lemma can therefore produce a model of $\operatorname{CKh}^{\pm}(K)$ with
underlying vector space equal to the Khovanov chain complex. This is finite
dimensional and already much more convinient for computations, but an even
further simplification is possible:

######  Lemma 3.3.

The complex produced from $\operatorname{CKh}^{\pm}(K)$ via Lemma 3.2 is in
fact $(-3,1)$-bounded, and its associated graded complex as a $(-3,1)$-bounded
semibifiltered complex is precisely the Khovanov complex of $K$.

###### Proof.

To say that a $(-3,0)$-bounded complex is $(-3,1)$-bounded is exactly to say
that the differential of it’s vertical associated graded complex vanishes. By
the second part of Lemma 3.2, this can be checked looking only at the vertical
associated graded complex of $\operatorname{CKh}^{\pm}(K)$, which (directly
from the definition in [1]) is precisely a direct sums of shifts of copies of
$\operatorname{CKh}^{\pm}(U)$ where $U$ is an unlink with a varying number of
components. The homology of such a complex is the reduced Lee homology of this
unlink, and the homology of it’s associated graded complex is the reduced
Khovanov homology of this unlink, so since these have the same rank all higher
vertical differentials vanish. Finally, the differential of the associated
graded complex of this $(-3,-1)$-bounded complex is precisely the differential
on the $E_{1}$-page of the spectral sequence considered in [1], where it is
shown that this is the differential of the Khovanov complex. ∎

Therefore, applying Lemma 3.2 once more proves the following, which enables
most of the computations to follow:

######  Lemma 3.4.

$\operatorname{CKh}^{\pm}(K)$ is chain homotopy equivalent to a
$(-3,1)$-bounded semibifiltered complex $(C,d)$ such that the associated
graded module of the filtration on $C$ is isomorphic to the Khovanov homology
$\operatorname{Kh}(K)$, with its internal and homological gradings.

$1$
---
$q^{2}h$
---
$q^{6}h^{3}$
---
$q^{4}h$
---
$q^{6}h$
---
$q^{12}h^{5}$
---
$q^{18}h^{7}$
---
Figure 1. The allowed differentials in the model for
$\operatorname{CKh}^{\pm}(K)$ provided by Lemma 3.4. The complex
$\operatorname{CKh}^{\pm}(K)$ has a model whose underlying vector space is the
reduced Khovanov homology of $K$ with rational coefficients, and the
differential of an element in the grading labelled $1$ in the diagram lies in
the gradings marked by dots in the shaded regions. This diagram takes into
account the fact that the differential must increase the homological grading
$h$ by at least $1$, decrease the internal grading $q-3h$ by at most $3$, and
change the parity of the internal grading, as well as the fact that no
differential of degree $h$ will be present due to the last application of
Lemma 3.2 passing from the Khovanov complex to the Khovanov homology. The
terms of the differential in the red region will be exactly the Lee
differential of $K$, and similarly the terms in the blue region will be the
$E(-1)$ differential of $K$.

##  4\. Invariants of filtered complexes

Let $C$ be a decreasing $\mathbb{R}$-filtered vector space with filtered
pieces $\\{C_{t}\\}_{t\in\mathbb{R}}$ and $d$ a differential on $C$, with no
assumption on how $d$ interacts with the filtration. If the homology of
$(C,d)$ is one dimensional, define $m(C)$ to be the supremum of all $t$ for
which there is an element $\gamma$ in $C_{t}$ with $d\gamma=0$ and $[\gamma]$
nonzero in homology.

######  Lemma 4.1.

For $C$, $C^{\prime}$ as above, $m(C\otimes C^{\prime})=m(C)+m(C^{\prime})$.

###### Proof.

For $t\in\mathbb{R}$, define $C_{>t}$ to be the union of $C_{s}$ for all
$s>t$. Since the homology of $C$ is one-dimensional, any two chains
representing nonzero homology classes have homologous scalar multiples.
Therefore, the quantity $m(C)$ is characterized by the fact that, for all
$t<m(C)$, there is $\gamma\in C_{t}$ with $d\gamma=0$ and $\gamma\not\in
d(C)+C_{>m(C)}$. Fix $t<m(C)$ and $t^{\prime}<m(C^{\prime})$, and elements
$\gamma$ and $\gamma^{\prime}$ with this property. Then
$\gamma\otimes\gamma^{\prime}\in C_{t}\otimes C_{t^{\prime}}\subset(C\otimes
C^{\prime})_{t+t^{\prime}}$, and is not contained in the subspace

$d(C)\otimes C^{\prime}+C_{>m(C)}\otimes C^{\prime}+C\otimes
d(C^{\prime})+C\otimes C^{\prime}_{>m(C^{\prime})}$

Now, $d(C\otimes C^{\prime})$ is a subspace of $d(C)+d(C^{\prime})$, and
$C_{>m(C)}\otimes C^{\prime}+C\otimes C^{\prime}_{>m(C^{\prime})}$ is a
subspace of $(C\otimes C^{\prime})_{>m(C)+m(C^{\prime})}$, so
$\gamma\otimes\gamma^{\prime}$ is not contained in $d(C\otimes
C^{\prime})+(C\otimes C^{\prime})_{>m(C)+m(C^{\prime})}$, so taking $t$ and
$t^{\prime}$ arbitrarily close to $m(C)$ and $m(C^{\prime})$, respectively,
finishes the proof. ∎

If now $(C,d)$ is a semibifiltered complex with one-dimensional homology, then
for any $\alpha\in[0,2]$ we can collapse the filtration to one
$\mathbb{R}$-filtration and apply the above construction: let

$C^{\alpha}_{t}=\sum_{\alpha m+(2-\alpha)n\geq t}C_{m,n},$

and let $M(C,\alpha)=m(C^{\alpha})$. Then by the additivity of $m$,
$M(C\otimes C^{\prime},\alpha)=M(C,\alpha)+M(C^{\prime},\alpha)$.

The complex $\operatorname{CKh}^{\pm}(K)$ is semibifiltered with one-
dimensional homology, so the above definition applies:

######  Definition 4.2.

For a knot $K$ and $\alpha\in[0,2]$, let
$\Phi_{K}(\alpha)=M(\operatorname{CKh}^{\pm}(K),\alpha)$.

Applying this construction to an appropriate version of knot Floer homology
produces the Upsilon invariant. Via arguments similar to Theorem 8.1 in [7],
analogues of the integrality properties of Upsilon can be proven in this more
general context.

######  Proposition 4.3.

Suppose that $(C,d)$ is a semibifiltered complex with $C$ finite dimensional.
Then the function $M(C,-)$ is continuous and piecewise-linear, and it’s graph
is contained in the union of the lines passing through $(0,2j)$ and $(2,2i)$
as $(i,j)$ ranges over the support of the associated graded module to $C$.

###### Proof.

For fixed $\alpha$, the quantity $M(C,\alpha)$ must lie in the support of the
associated graded module to the collapsed filtration $C^{\alpha}$ since
otherwise any chain lying in filtration level $M(C,\alpha)$ would in fact lie
in a deeper level. As $\alpha$ varies, the support of this associated module
traces out the lines in the statement, so it remains only to prove that
$M(C,-)$ is a continuous function of $\alpha$. For a fixed chain $\gamma\in
C$, let $M(\gamma,\alpha)$ be the largest $t$ for which $\gamma$ is contained
in $C^{\alpha}_{t}$. This will be the minumum of several linear functions
corresponding to the support of $\gamma$, so will be continuous and piecewise
linear. The quantity $M(C,\alpha)$ is the maximum of $M(\gamma,\alpha)$ over
all $\gamma$ representing a nonzero homology class. Since each
$M(\gamma,\alpha)$ is contained in the lines corresponding to the support of
$C$, of which there are finitely many, there are only finitely many possible
values for $M(\gamma,\alpha)$. Therefore, $M(C,\alpha)$ is the maximum of
finitely many continuous functions, so is itself continuous. ∎

Combining this with Lemma 3.4 immediately proves Theorem 1.2.

The quantity $M(C,\alpha)$ behaves in a predictable way under chain maps,
which will be important to establish the basic properties of $\Phi_{K}$.

######  Lemma 4.4.

If $C$ and $C^{\prime}$ are semibifiltered complexes and there is a filtered
chain map $f:C\to C^{\prime}$ inducing an isomorphism on homology, then
$M(C,\alpha)\leq M(C^{\prime},\alpha)$.

###### Proof.

For any $t<M(C,\alpha)$, there is a chain $\gamma\in C^{\alpha}_{t}$
representing a nonzero homology class. Then
$f(\gamma)\in(C^{\prime})^{\alpha}_{t}$, so $t\leq M(C^{\prime},\alpha)$. By
taking $t$ approaching $M(C,\alpha)$, then $M(C,\alpha)\leq
M(C^{\prime},\alpha)$. ∎

###  4.1. Basic Properties of $\Phi_{K}(\alpha)$

This section contains proofs of most of the theorems stated in the
introduction, as well as a few additional facts needed for later computations.

######  Proposition 4.5.

$\Phi$ is a concordance homomorphism.

###### Proof.

The complex $C(K)$ from [1] satisfies
$C(K_{1}\\#K_{2})=C(K_{1})\otimes_{\mathbb{Z}[x]}C(K_{2})$, so
$\operatorname{CKh}^{\pm}(K_{1}\\#K_{2})\cong\operatorname{CKh}^{\pm}(K_{1})\otimes_{\mathbb{Q}}\operatorname{CKh}^{\pm}(K_{2})$.
Additivity of $\Phi$ now follows from Lemma 4.1. To see that $\Phi$ is a
concordance invariant, use Lemma 4.4 and the fact that the complexes
$\operatorname{CKh}^{\pm}(K)$ for concordant knots admit filtered chain maps
inducing isomorphisms on homology in either direction by Proposition 2.3. ∎

######  Proposition 4.6.

For any knot $K$, the values $\Phi_{K}(0)$ and $\Phi_{K}(2)$ are both $0$, and
the slopes $\Phi_{K}^{\prime}(0)$ and $\Phi_{K}^{\prime}(2)$ are $s(K)$ and
$-t(K)$, respectively.

###### Proof.

In the model for $\operatorname{CKh}^{\pm}(K)$ provided by Lemma 3.4, the
vertical associated graded complex of $\operatorname{CKh}^{\pm}(K)$ is
precisely the reduced Khovanov homology of $K$ together with all differentials
of the Lee spectral sequence, so the homology of this vertical associated
graded complex is $\mathbb{Q}$ in homological degree $0$ and $0$ in all other
homological degrees, and with respect to the filtration by the internal degree
there is a generator for the homology contained in filtration level $s(K)$ but
not in any deeper level of the filtration. Let
$\gamma_{0}\in\operatorname{CKh}^{\pm}(K)_{s(K),0}$ be any lift of a chain
generating the homology of the verical associated graded complex. Since
$\gamma$ is a chain in the vertical associated graded,
$d\gamma_{0}\in\operatorname{CKh}^{\pm}(K)_{*,2}$, and since the homology of
the vertical associated graded in degree $2$ vanishes, there is a
$\gamma_{1}\in\operatorname{CKh}^{\pm}(K)_{*,1}$ with
$d\gamma_{0}+d\gamma_{1}\in\operatorname{CKh}^{\pm}(K)_{*,3}$. Continuing in
this way to push remaining terms depper into the filtration, and using the
fact that this model of $\operatorname{CKh}^{\pm}(K)$ is finite dimensional,
we produce a chain
$\gamma\in\operatorname{CKh}^{\pm}(K)_{s(K),0}+\operatorname{CKh}^{\pm}(K)_{*,1}$
generating the homology of $\operatorname{CKh}^{\pm}(K)$ which, again using
finite dimensionality, in fact lies in
$\operatorname{CKh}^{\pm}(K)_{s(K),0}+\operatorname{CKh}^{\pm}(K)_{m,1}$ for
some $m$. Therefore, $\Phi_{K}(\alpha)\geq s(K)\alpha$ for small enough
$\alpha$, and the reverse inequality follows from applying the same argument
to $-K$. Similarly, the horizontal associated graded complex of
$\operatorname{CKh}^{\pm}(K)$ (taking associated graded with respect to just
the first filtration) is exactly the reduced complex $\bar{C}(K)$ from [1],
since taking associated graded changes the relation $x=1$ to $x=0$, so
applying this same argument proves the statement about the right endpoint
slope. ∎

The version of the Lee spectral sequence from the above proof is not exactly
the same as the one used by Rasmussen [10] to define the $s$ invariant, but is
instead a reduced version of the Lee spectral sequence. The version used in
[10] can be instead obtained by replacing the relation $x-1$ by $x^{2}-1$ and
shifting all quantum gradings up by $1$ (and again taking the vertical
associated graded to remove $E(-1)$ differentials). The unreduced complex has
two dimensional homology with generators in filtration levels $s(K)-1$ and
$s(K)+1$, and the necessary generator of the reduced homology in filtration
level $s(K)$ just comes from further quotienting the unreduced complex by
$x-1$ to get the reduced complex, and taking the image of the generator in
filtration level $s(K)-1$. This will land in filtration level $s(K)$ in the
reduced complex, due to the grading shift.

######  Proposition 4.7.

If $K_{-}$ and $K_{+}$ differ by a crossing change in which $K_{-}$ has a
negative crossing and $K_{+}$ has a positive crossing, then
$\Phi_{K_{-}}(\alpha)\leq\Phi_{K_{+}}(\alpha)$ for any $\alpha\in[0,2]$.

###### Proof.

By Proposition 2.3, in this situation there is a filtered chain map
$\operatorname{CKh}^{\pm}(K_{-})\to\operatorname{CKh}^{\pm}(K_{+})$ that
induces an isomorphism on homology. The inequality then follows from Lemma 4.4
∎

##  5\. Twisting ribbon surfaces and the slice genus bound

Arguments similar to those of the previous section suffice to prove a slice
genus bound $g_{4}(K)\geq\Phi_{K}(\alpha)/\alpha$, by considering the
cobordism maps on $C(K)$ and the filtered maps they induce on
$\operatorname{CKh}^{\pm}(K)$. This is identical to the bound stated in
Theorem 2.5 when $0\leq\alpha\leq 1$, but is significantly weaker when
$1\leq\alpha\leq 2$. To prove the stronger bound, more complex arguments are
needed that involve modifying the knot to simplify it’s Khovanov homology and
using Proposition 4.7 to control the change in $\Phi$.

Let $\Sigma\subset S^{3}$ be a ribbon surface of genus $g$, with a handle
decomposition consisting of $k$ discs and $k+2g-1$ disjoint bands. Via slides
among the bands, we may assume that the ribbon graph formed by these discs and
bands has the same combinatorial type as the one visible in Figure 2. For
$n\geq 0$, let $\Sigma_{n}$ be the surface obtained from $\Sigma$ by inserting
$n$ full positive twists into each band of $\Sigma$, and let
$K_{n}=\partial\Sigma_{n}$.

######  Proposition 5.1.

For fixed $\alpha$, the quantity $\Phi_{K_{n}}(\alpha)$ is monotonically
decreasing in $n$, and if $\alpha\neq 1$ then
$\lim_{n\to\infty}\Phi_{K_{n}}(\alpha)=-2g\Lambda(\alpha)$.

Theorem 2.5 follows quickly from this result, and the core of its proof
involves understanding the delta graded Khovanov homology of $K_{n}$ for large
$n$. Here and throughout this paper, the grading convention $\delta=q-2h$ for
the delta grading is used.

######  Lemma 5.2.

In any fixed homological grading, the Khovanov homology of $K_{n}$ is
supported only in delta grading $-2g$ for sufficiently large $n$. Furthermore,
there is a finite range of delta gradings that contains the entire support of
the Khovanov homology of any $K_{n}$.

###### Proof.

First, to see that $\operatorname{Kh}(K_{n})$ is homologically thin in small
homological gradings for large $n$, consider the knot $K_{\infty}\subset
M=\\#^{k+2g-1}S^{2}\times S^{2}$ formed by performing a $0$-surgery on a
meridian of each of the bands of rhe ribbon surface $\Sigma$, and the Khovanov
homology $\operatorname{Kh}(K_{\infty})$ as defined by Willis in [12]. By
Theorem 2.2 in [12], for sufficiently large $n$ the Khovanov homologies
$\operatorname{Kh}(K_{n})$ and $\operatorname{Kh}(K_{\infty})$ agree in any
given homological degree. Therefore, it suffices to show that
$\operatorname{Kh}(K_{\infty})$ is supported in delta grading $-2g$. However,
by isotopies involving sliding the knot $K_{\infty}$ over surgery curves for
$M$, the bands of $\Sigma$ can be passed through eachother and the boundaries
of the discs, so $K_{\infty}$ is isotopic to the knot shown in Figure 2, which
in particular depends only on $g$ and not on the embedding of $\Sigma$. Using
again the fact that $\operatorname{Kh}(K_{\infty})$ agrees in any fixed
homological grading with the result of replacing each $0$-surgery with a large
but finite number of twists but in this new diagram,
$\operatorname{Kh}(K_{\infty})$ agrees with the Khovanov homology of the
connected sum of pretzel knots $\\#^{g}P(2n+1,2n+1,1)$ for large enough $n$ in
any fixed homological grading. This knot is alternating and has signature
$-2g$, so $\operatorname{Kh}(\\#^{g}P(2n+1,2n+1,1))$ is supported in delta
grading $-2g$ for any $n$ and the same is true of
$\operatorname{Kh}(K_{\infty})$.

To see that the homologies $\operatorname{Kh}(K_{n})$ are supported in a
uniformly bounded range of delta gradings, bounds based on the spanning tree
complex for Khovanov homology suffice. $K_{0}$ has a diagram $D_{0}$
containing $k+2g-1$ distinguished negative crossings, corresponding to the
bands in the handle decomposition of $\Sigma$, such that resolving these
crossings produces an unlink with $k$ components and diagrams $D_{n}$ of each
$K_{n}$ can be obtained from $D_{0}$ by replacing each of these crossings with
$2n+1$ negative crossings arranged in a row as in Figure 3. Let $n_{-}$,
$n_{+}$, $O_{A}$, and $O_{B}$ be the number of negative crossings, positive
crossings, circles in the all-A resolution, and circles in the all-B
resolution of $D_{0}$. Then $D_{n}$ has $n_{-}+2n$ negative crossings, $n_{+}$
positive crossings, $O_{A}$ circles in the all-A resolution, and $O_{B}+2n$ in
the all-B resolution. Therefore, the reduced Khovanov homologies of all of the
$K_{n}$ are supported in delta gradings between $O_{A}-n_{+}-1$ and
$-O_{B}+n_{-}+1$, via the bounds proven in [3] using a spanning tree complex.

∎

$g$
---
$k-1$
---
Figure 2. The general form to which $K_{\infty}$ can be isotoped. The black
curve is the knot, and the grey curves are the ($0$-framed) surgery circles
giving $S^{2}\times S^{1}$. $2n+1$
---
Figure 3. The local model for the twisting producing $K_{n}$ from $K=K_{0}$.

######  Corollary 5.3.

For any $\epsilon>0$, there is an $N$ for which, whenever $n\geq N$ and
$|\alpha-1|>\epsilon$, the invariant $\Phi_{K_{n}}(\alpha)$ is equal to
$-2g\Lambda(\alpha)$.

###### Proof.

By the previous Lemma, there is a constant $M$ for which the reduced Khovanov
homologies of the knots $K_{n}$ are supported in delta gradings between $-M$
and $M$ and, by taking $n$ large enough, can be taken to be supported in delta
grading $-2g$ in any finite range of homological gradings.

By Theorem 1.2, then, the graphs of $\Phi_{K_{n}}$ for sufficiently large $n$
are contained in the a union of lines that all either pass through $(1,-2g)$
or meet the line $\alpha=1$ between $-M$ and $M$ and have slope as large as
desired. A sufficiently steep line meeting $\alpha=1$ between $-M$ and $M$
cannot pass through $(0,0)$ or $(2,0)$, so since
$\Phi_{K_{n}}(0)=\Phi_{K_{n}}(2)=0$, near the endpoints the graph of
$\Phi_{K_{n}}$ must follow either the line $(\alpha,-2g\alpha)$ or
$(\alpha,-2g(2-\alpha))$. Since $\Phi_{K_{n}}$ is continuous, the graph must
follow these lines at least until they meet another one of the supporting
lines. If this happens for at a point with $\alpha\neq 1$, it must be because
one of the initial lines meets one of the very steep lines. By taking these
additional lines steep enough, this can be restricted to happen only in a
small neighborhood of $\alpha=1$. ∎

###### Proof of Proposition 5.1.

$K_{n+1}$ is obtained from $K_{n}$ by changing a positive crossing to a
negative one (since the two strands in a band are oppositely oriented) so
Proposition 4.7 shows that $\Phi_{K_{n}}(\alpha)$ is monotonically decreasing,
and Corollary 5.3 shows that $\Phi_{K_{n}}(\alpha)$ is eventually equal to
$-2g\Lambda(\alpha)$ if $\alpha\neq 1$. ∎

###### Proof of Theorem 2.5.

If $K$ has slice genus $g$, then it is concordant to a knot bounding a ribbon
surface of genus $g$, so since $\Phi$ is a concordance invariant we may assume
that $K$ bounds a ribbon surface of genus $g$. With $K_{n}$ as in Proposition
5.1, then, for any $\alpha\neq 1$

$\Phi_{K}(\alpha)=\Phi_{K_{0}}(\alpha)\geq\lim_{n\to\infty}\Phi_{K_{n}}(\alpha)=-2g\Lambda(\alpha),$

and the same must be true for $\alpha=1$ since $\Phi_{K}$ is a continuous
function of $\alpha$. The theorem now follows from applying this inequality to
both $K$ and $-K$. ∎

##  6\. Pretzel calculations and a conjecture on torus knots

######  Proposition 6.1.

If $K$ is the pretzel knot $P(-2n,a,b)$ with $a$ and $b$ odd and $0<2n<a,b$,
then the only singularities of $\Phi_{K}(\alpha)$ are at $\alpha=1$ and
$\alpha=\frac{8n}{8n+2}$. The change in the slope of $\Phi_{K}(\alpha)$ at
$\alpha=\frac{8n}{8n+2}$ is exactly

$\Delta\Phi^{\prime}_{K}\left(\frac{8n}{8n+2}\right)=-8n-2$

###### Proof.

By Manion’s computations of the reduced Khovanov homology of pretzel knots
[8], the reduced homology of $K$ is supported in delta gradings $a+b$ and
$a+b-2$ (note that here we use the convention $\delta=q-2h$, which differs
from Manion’s by a factor of $2$). In the higher delta grading the homology is
supported between homological gradings $0$ and $4n+1$, and in the lower delta
grading the homology is supported in homological gradings at least $4n$.
Furthermore, the homology group in delta grading $a+b$ and homological grading
$4n+1$ has rank $1$, as does the homology group in delta grading $a+b-2$ and
homological grading $4n$. Using the model provided by Lemma 3.4, this is
enough to fully compute $\operatorname{CKh}^{\pm}(K)$. For each of the Lee and
$E(-1)$ differentials, there is only one possibility consistent with the facts
that the overall homology is one dimensional and the surviving generator is in
homological or internal grading $0$. There is no room in the reduced Khovanov
homology of $K$ for any differentials going deeper into both filtrations, and
only one way up to isomorphism of the resulting complex to match the
generators of the Lee and $E(-1)$ complexes to make $d^{2}=0$, so the
differential on $\operatorname{CKh}^{\pm}(K)$ is just the sum of the Lee and
$E(-1)$ differentials. Overall, the complex $\operatorname{CKh}^{\pm}(K)$ is
shown in figure 4; it is the direct sum of one main staircase complex with
copies of shifts of the boxed contractible complex. The boxed complex is
homotopy equivalent to $0$, so in fact $\operatorname{CKh}^{\pm}(K)$ is
homotopy equivalent to the main complex $C$ in Figure 4. This means that
$\Phi_{K}(\alpha)=M(C,\alpha)$, which can be computed to be

$\Phi_{K}(\alpha)=\begin{cases}(a+b)\alpha&0\leq\alpha\leq\frac{8n}{8n+2}\\\
8n+(a+b-8n-2)\alpha&\frac{8n}{8n+2}\leq\alpha\leq 1\\\
(a+b-2)(2-\alpha)&1\leq\alpha\leq 2\end{cases}$

∎

######  Lemma 6.2.

For any knot $K$, the quantity $\Delta\Phi^{\prime}_{K}(\alpha)(1-\alpha)$ is
always an even integer.

###### Proof.

By Theorem 1.2, this is a difference between two delta gradings in which the
reduced Khovanov homology of $K$ is supported. The parities of the delta and
quantum gradings are equal, and the reduced Khovanov homology of a knot is
supported in even quantum gradings. ∎

###### Proof of Theorem 1.3.

For $n\geq 0$ an integer, let

$i_{n}(K)=\frac{\Delta\Phi^{\prime}_{K}\left(\frac{8n}{8n+2}\right)}{8n+2}.$

By Lemma 6.2, this is always an integer, and since $i_{n}$ depends linearly on
$\Phi$ it is a concordance homomorphism. Finally, by Proposition 6.1,
$i_{n}(P(-2k,a,b))=-1$ if $n=k$ and is zero otherwise. ∎

$q^{3a+3b-4}h^{a+b-1}$
---
$q^{a+b}$
---
$q^{a+b+8n+2}h^{4n+1}$
---
$q^{a+b+8n-2}h^{4n}$
---
$q^{3a+3b-6}h^{a+b-2}$
---
Figure 4. The complex $\operatorname{CKh}^{\pm}(P(-2n,a,b))$ is the direct sum
of the larger complex in this figure with several shifts of the smaller, boxed
complex. All arrows shown are terms in the diferential of
$\operatorname{CKh}^{\pm}(P(-2n,a,b))$, with the ones in blue coming from the
$E(-1)$ spectral sequence and the ones in red coming from the Lee spectral
sequence. Some gradings in the larger complex are given by the exponents of
$q$ and $h$ (the standard quantum and homological gradings), and the rest may
be inferred from the fact that all $E(-1)$ differentials present have degree
$q^{6}h^{2}$ and, apart from the one between gradings $q^{a+b+8n-2}h^{4n}$ and
$q^{a+b+8n+2}h^{4n+1}$, the Lee differentials have degree $q^{2}h$.

Similar techniques may be used to compute the invariant $\Phi$ for individual
small knots, although not yet for any other infinte family of non-thin knots.
However, looking at the values of $\Phi$ on small torus knots, a clear pattern
emerges leading to a conjecture for the value of $\Phi$ on all torus knots:

######  Conjecture 6.3.

For the torus knot $T_{n,n+1}$, the jump in the slope
$\Delta\Phi^{\prime}_{T_{n,n+1}}(\alpha)$ is equal to $0$ except when
$\alpha=\frac{2+2k}{2+3k}$ for $0\leq k<n$ and $k$ of the same parity as $n$,
when it is $-4-6k$. Together with the fact that $s(T_{n,n+1})=n(n-1)$, this
determines $\Phi_{T_{n,n-1}}$. For other torus knots, $\Phi$ is determined by
the recurrence

$\Phi_{T_{p,q+p}}=\Phi_{T_{p,q}}+\Phi_{T_{p,p+1}}$

This conjecture can be confirmed for small $p,q$ using computer calculations
of $\operatorname{Kh}(T_{p,q})$ from [2], and similarly for $p=2,3$ and any
$q$ since the Khovanov homologies of these knots are known (see [11] for the
$(3,q)$ case). It is also consistent with the calculations of
$t(T_{p,q})=-\Phi^{\prime}_{T_{p,q}}(2)$ from [1]. The conjectured recurrence
relation $\Phi_{T_{p,q+p}}=\Phi_{T_{p,q}}+\Phi_{T_{p,p+1}}$ is known to be
satisfied by the Upsilon invariant [4], but the values of the two invariants
on $T_{n,n+1}$ are different. Explaining the recurrence satisfied by both
$\Upsilon$ and (conjecturally) $\Phi$ would be an interesting exploration into
the relationships between knot Floer homology and Khovanov homology.

## References

  * [1] William Ballinger, _Concordance invariants from the $E(-1)$ spectral sequence on Khovanov homology_, arXiv preprint arXiv:2004.10807 (2020).
  * [2] Dror Bar-Natan, Scott Morrison, et al., _The knot atlas_ , (2005).
  * [3] Oliver T Dasbach and Adam M Lowrance, _Turaev genus, knot signature, and the knot homology concordance invariants_ , Proceedings of the American Mathematical Society (2011), 2631–2645.
  * [4] Peter Feller and David Krcatovich, _On cobordisms between knots, braid index, and the Upsilon-invariant_ , Mathematische Annalen 369 (2017), no. 1-2, 301–329.
  * [5] Mikhail Khovanov, _Link homology and Frobenius extensions_ , arXiv preprint math/0411447 (2004).
  * [6] Lukas Lewark and Andrew Lobb, _Upsilon-like concordance invariants from $\operatorname{sl}_{n}$ knot cohomology_, Geometry & Topology 23 (2019), no. 2, 745–780.
  * [7] Charles Livingston, _Notes on the knot concordance invariant upsilon_ , Algebraic & Geometric Topology 17 (2017), no. 1, 111–130.
  * [8] Andrew Manion, _The Khovanov homology of 3-strand pretzels, revisited_ , New York J. Math 24 (2018), 1076–1100.
  * [9] Peter S Ozsváth, András I Stipsicz, and Zoltán Szabó, _Concordance homomorphisms from knot Floer homology_ , Advances in Mathematics 315 (2017), 366–426.
  * [10] Jacob Rasmussen, _Khovanov homology and the slice genus_ , Inventiones mathematicae 182 (2010), no. 2, 419–447.
  * [11] Paul Turner, _A spectral sequence for Khovanov homology with an application to (3, q)–torus links_ , Algebraic & Geometric Topology 8 (2008), no. 2, 869–884.
  * [12] Michael Willis, _Khovanov homology for links in $\\#^{r}(S^{2}\times S^{1})$_, arXiv preprint arXiv:1812.06584 (2019).


# Erdős-Rogers functions for arbitrary pairs of graphs

Dhruv Mubayi Department of Mathematics, Statistics and Computer Science,
University of Illinois, Chicago, IL 60607. Email<EMAIL_ADDRESS>Research
partially supported by NSF Awards DMS-1952767 and DMS-2153576 and a Simons
Fellowship. Jacques Verstraëte Department of Mathematics, University of
California, San Diego, CA, 92093-0112 USA. Email<EMAIL_ADDRESS>Research supported by NSF award DMS-1952786.

###### Abstract

Let $f_{F,G}(n)$ be the largest size of an induced $F$-free subgraph that
every $n$-vertex $G$-free graph is guaranteed to contain. We prove that for
any triangle-free graph $F$,

$f_{F,K_{3}}(n)=f_{K_{2},K_{3}}(n)^{1+o(1)}=n^{\frac{1}{2}+o(1)}.$

Along the way we give a slight improvement of a construction of Erdős-Frankl-
Rödl for the Brown-Erdős-Sós $(3r-3,3)$-problem when $r$ is large.

In contrast to our result for $K_{3}$, for any $K_{4}$-free graph $F$
containing a cycle, we prove there exists $c_{F}>0$ such that

$f_{F,K_{4}}(n)>f_{K_{2},K_{4}}(n)^{1+c_{F}}=n^{\frac{1}{3}+c_{F}+o(1)}.$

For every graph $G$, we prove that there exists $\varepsilon_{G}>0$ such that
whenever $F$ is a non-empty graph such that $G$ is not contained in any blowup
of $F$, then $f_{F,G}(n)=O(n^{1-\varepsilon_{G}})$. On the other hand, for
graph $G$ that is not a clique, and every $\varepsilon>0$, we exhibit a
$G$-free graph $F$ such that $f_{F,G}(n)=\Omega(n^{1-\varepsilon})$.

##  1 Introduction

Say that a graph is $F$-free if it contains no subgraph isomorphic to $F$.
Denote by $f_{F,G}(n)$ the maximum $m$ such that every $n$-vertex $G$-free
graph contains an induced $F$-free subgraph on at least $m$ vertices. Hence
the assertion $f_{F,G}(n)<b$ means that there exists an $n$ vertex $G$-free
graph $H$ such that every vertex subset of $H$ of size $b$ contains a copy of
$F$. The case $F=K_{s}$ and $G=K_{t}$ is the Erdős-Rogers [7] function
$f_{s,t}(n)$. Classical results in Ramsey Theory [1, 10] give
$r(3,t)=\Theta(t^{2}/\log t)$, which shows
$f_{K_{2},K_{3}}(n)=\Theta(\sqrt{n\log n})$. We prove that roughly the same
holds for $f_{F,K_{3}}(n)$ for any triangle-free graph $F$:

######  Theorem 1.

For any triangle-free graph $F$ containing at least one edge,

$f_{F,K_{3}}(n)=n^{\frac{1}{2}+O(\sqrt{\frac{\log\log n}{\log
n}})}=f_{K_{2},K_{3}}(n)^{1+o(1)}.$

Our bound in Theorem 1 is much larger than
$f_{K_{2},K_{3}}(n)=\Theta(\sqrt{n\log n})$, and therefore the following
problem seems natural.

######  Problem 1.

Find a triangle free $F$ for which
$f_{F,K_{3}}(n)/f_{K_{2},K_{3}}(n)\rightarrow\infty$.

A large pseudorandom triangle free graph with many edges seems an obvious
choice for $F$ in Problem 1. Perhaps the simpler $F=K_{t,t}$ is another
example. More generally, for each $s\geq 3$, one can ask whether there exists
a $K_{s}$-free $F$ for which
$f_{F,K_{s}}(n)/f_{K_{s-1},K_{s}}(n)\rightarrow\infty$.

Unlike the case of triangles, it appears that for $s\geq 4$, it is difficult
to determine for each $K_{s}$-free graph $F$ a constant $c=c(F)$ such that
$f_{F,K_{s}}(n)=n^{c+o(1)}$. The second author and Mattheus [14] proved
$f_{K_{2},K_{4}}(n)=n^{1/3+o(1)}$ whereas it is well-known that
$f_{K_{3},K_{4}}=n^{1/2+o(1)}$. We [16] recently proved
$f_{K_{3},K_{4}}(n)=O(\sqrt{n}\log n)$ and the proof can be extended to prove
that for every $K_{4}$-free graph $F$, we have $f_{F,K_{4}}(n)=O(\sqrt{n}\log
n)$. Perhaps this can be improved for triangle-free $F$ as follows.

######  Problem 2.

Is it true that for every triangle-free graph $F$ there exists
$\varepsilon=\varepsilon_{F}>0$ such that
$f_{F,K_{4}}(n)<n^{1/2-\varepsilon}$?

Regardless of whether Problem 2 has an affirmative answer, one might suspect
that there exists a sequence of triangle-free graphs where the exponent tends
to $1/2$. We propose the following.

######  Problem 3.

Prove (or disprove) that $f_{K_{t,t},K_{4}}(n)=n^{1/2+o_{t}(1)}$.

The method of proof of Theorem 5 yields
$f_{K_{t,t},K_{4}}(n)>n^{2/5-o_{t}(1)}$.

Our next result shows that for $s\geq 4$, we can find substantially larger
$F$-free sets in $K_{s}$-free graphs than their conjectured [15] minimum
independence number, which is $n^{1/(s-1)+o(1)}$.

######  Theorem 2.

Let $s\geq 4$ and let $F$ be any graph containing a cycle. Then there exists a
constant $c_{F}>0$ such that

$f_{F,K_{s}}(n)=\Omega(n^{\frac{1}{s-1}+c_{F}}).$

If $F$ is a cycle, then this bound is almost tight for $K_{4}$, using the
following proposition. Write $r(H,t)$ for the ramsey number of $H$ versus a
clique on $t$ vertices.

######  Proposition 1.

For any graphs $F$ and $G$,

$f_{F,G}(r(G,t)-1)<r(F,t).$

Indeed, let $H$ be a $G$-free graph on $r(G,t)-1$ vertices with no independent
set of size $t$. Then the maximum $F$-free subset of $H$ has size less than
$m:=r(F,t)$ for any set of $m$ vertices in $H$ must contain either a copy of
$F$ or an independent set of size $t$.

When $F=C_{2k}$ or $F=C_{2k-1}$ we have $r(F,t)=O(t^{k/(k-1)}/(\log
t)^{1/(k-1)})$ ([12, 20]). Moreover, recent results of [14], yield
$r(K_{4},t)=\Omega(t^{3}/\log^{4}t)$. Putting these together in Proposition 1
yields

$f_{F,K_{4}}(n)=O(n^{\frac{k}{3k-3}}(\log n)^{\frac{4k-3}{3k-3}})\qquad\hbox{
for }\qquad\hbox{ $F\in\\{C_{2k},C_{2k-1}\\}$}.$ (1)

The constant in Theorem 2 satisfies $c_{F}=\Theta(1/k)$ for $F=C_{k}$ and with
(1) this gives

$f_{C_{k},K_{4}}(n)=f_{K_{2},K_{4}}(n)^{1+\Theta(\frac{1}{k})+o(1)}=n^{\frac{1}{3}+\Theta(\frac{1}{k})+o(1)}.$
(2)

This shows that there are graphs $F$ for which $f_{F,K_{4}}(n)$ does not have
the same exponent as $f_{K_{2},K_{4}}(n)$ or $f_{K_{3},K_{4}}(n)$, in contrast
to the case of $f_{F,K_{3}}(n)=f_{K_{2},K_{3}}(n)^{1+o(1)}$ from Theorem 1.
Using the graphs constructed in [14], and following the analysis along the
lines of Janzer and Sudakov [9], Balogh et al. [2] improved the upper bound in
(1) slightly in the case of even cycles, by showing

$f_{C_{2k},K_{4}}(n)=O(n^{\frac{k}{3k-2}}(\log n)^{\frac{6k}{3k-2}}).$

They also showed for complete multipartite graphs

$f_{K_{s_{1},...,s_{r}},K_{r+2}}(n)=O(n^{\frac{2s-3}{4s-5}}(\log n)^{3}),$

where $s=\sum s_{i}$. In the special case of 4-cycles this gives
$f_{C_{4},K_{4}}(n)=O(n^{5/11})$.

We now address general Erdős-Rogers functions $f_{F,G}(n)$. For a given $G$,
the first natural question is when $f_{F,G}(n)$ can be $n^{1-o(1)}$ as
$|V(F)|\rightarrow\infty$. A blowup of a graph $F$ is obtained by replacing
each vertex $v$ of $F$ with an independent set $I_{v}$ and adding all edges
between $I_{u}$ and $I_{v}$ whenever $\\{u,v\\}\in E(F)$. The graph $F$ is a
homomorphic image of $G$ if and only if some blowup of $F$ contains $G$.
Consequently, we say that $F$ is $\mbox{hom}(G)$-free if no blowup of $F$
contains $G$. For instance, if $G$ is bipartite and $F$ contains at least one
edge, then blowups of $F$ contain arbitrarily large complete bipartite graphs,
and therefore $F$ is not $\mbox{hom}(G)$-free. This condition turns out to
determine when Erdős-Rogers functions $f_{F,G}(n)$ can approach $n^{1-o(1)}$
as $|V(F)|\rightarrow\infty$:

######  Theorem 3.

For every graph $G$, there exists $\varepsilon_{G}>0$ such that if $F$ is any
$\mbox{hom}(G)$-free graph containing at least one edge, then

$f_{F,G}(n)=O(n^{1-\varepsilon_{G}}).$

On the other hand, if $G$ is not a clique, then for any $\varepsilon>0$ there
exists a $G$-free graph $F$ such that $f_{F,G}(n)=\Omega(n^{1-\varepsilon})$.

If $G$ is a clique, then every $G$-free graph is also $\mbox{hom}(G)$-free,
hence the first part of Theorem 3 applies to all $G$-free graphs $F$ when $G$
is a clique. As mentioned earlier, in the case $G=K_{4}$, it turns out
$f_{F,G}(n)=O(n^{1/2}\cdot\log n)$ due to our results in [16], so we may take
$\varepsilon_{K_{4}}\geq 1/2$. It appears to be difficult to determine the
largest possible value of $\varepsilon_{G}$ for each graph $G$ in Theorem 3.

##  2 Proof of Theorem 1

Ajtai, Komlós and Szemerédi [1] and Shearer [17] proved that
$r(3,t)=O(t^{2}/\log t)$. Using the random triangle-free process, Kim [10]
(see also Fiz Pontiveros, Griffths and Morris [8] and Bohman and Keevash [4])
showed $r(3,t)=\Omega(t^{2}/\log t)$, thereby determining the order of
magnitude of $r(3,t)$. Consequently, for any non-empty graph $F$,

$f_{F,K_{3}}(n)\geq f_{K_{2},K_{3}}(n)=\Theta(\sqrt{n\log n}).$

To prove Theorem 1 we employ a construction of Erdős, Frankl and Rödl [6] of a
linear triangle-free $R$-uniform $N$-vertex hypergraph. In the appendix, we
give present a minor modification of their construction which gives a bound
that is better than the bound from [6] when $R>\log N$; they prove a lower
bound $N^{2}/e^{O(\log R\sqrt{\log N})}$ while our bound is
$N^{2}/e^{O(\sqrt{\log R\log N})}$.

######  Theorem 4.

(Proposition A in Appendix) For any $R,N\geq 3$ and $N\geq R\geq\log N$, there
exists an $N$-vertex $R$-uniform hypergraph $H$ with the following properties:

$\mathrm{(i)}$ |  $|E(H)|\geq N^{2}/R^{8\sqrt{\log_{R}N}}$
---|---
$\mathrm{(ii)}$ |  $H$ is linear, that is, for any distinct edges $e,f\in H$, $|e\cap f|\leq 1$.
$\mathrm{(iii)}$ |  $H$ is triangle-free, that is, for any three distinct edges $e,f,g\in H$, if $|e\cap f|=|f\cap g|=|g\cap e|=1$ then $|e\cap f\cap g|=1$.

Proof of Theorem 1. We are to prove that

$f_{F,K_{3}}(n)=n^{\frac{1}{2}+O(\sqrt{\frac{\log\log n}{\log n}})}.$

Let $t=|V(F)|$. We apply Theorem 4 with $R=\lceil 3t\log t\log N\rceil$, where
$t=|V(F)|$. Then (i) yields

$|E(H)|\geq\frac{N^{2}}{R^{8\sqrt{\log_{R}N}}}=N^{2-O(\sqrt{\frac{\log\log
N}{\log N}})}.$ (3)

Let $G$ be the graph whose vertex set is $E(H)$ and where $E(G)=\\{e,f\in
E(H):e\cap f\neq\emptyset\\}$. For each vertex $v\in V(H)$, the set
$K_{v}=\\{e\in E(H):v\in e\\}$ induces a clique in $G$. If for some distinct
$v,w\in V(H)$ there exist distinct $e,f\in K_{v}\cap K_{w}$, then by
definition $v,w\in e\cap f$, which contradicts that $H$ is linear. Therefore
$|V(K_{v})\cap|V(K_{w})|\leq 1$ for all distinct $v,w\in V(H)$, and the
cliques $K_{v}$ are edge-disjoint in $G$. Similarly, since $H$ is triangle-
free, every triangle in $G$ is contained in a clique $K_{v}$ for some $v\in
V(H)$.

Independently for $v\in V(H)$, let $\chi_{v}:V(K_{v})\rightarrow V(F)$ be a
random coloring of $K_{v}$. Next, we remove all edges $\\{x,y\\}$ of
$G[K_{v}]$ such that $\chi_{v}(x)=\chi_{v}(y)$ or
$\chi_{v}(x)\chi_{v}(y)\not\in E(F)$. In other words, we have placed a blowup
of a copy of $F$ in each set $K_{v}$.

Since $F$ contains no triangle, the resulting graph $G^{*}$ is triangle-free.
We now prove that $G^{*}$ has no $F$-free induced subgraph with at least $N$
vertices. To see this, fix a set $Z$ of $N$ vertices of $G^{*}$. The
probability that $Z$ is an $F$-free set of $G^{*}$ is

${\mathbb{P}}(Z)\leq\prod_{v\in
V(H)}t\cdot\Bigl{(}1-\frac{1}{t}\Bigr{)}^{|K_{v}\cap Z|}.$

Since $H$ is $R$-uniform,

$\sum_{v\in V(H)}|K_{v}\cap Z|=\sum_{e\in Z}|e|=R|Z|=RN.$

Using $(1-x)^{y}\leq e^{-xy}$ for $0\leq x\leq 1$ and $y\geq 1$,

${\mathbb{P}}(Z)\leq t^{N}\Bigl{(}1-\frac{1}{t}\Bigr{)}^{RN}\leq e^{N\log
t-RN/t}<N^{-2N}.$

The number of sets of size $N$ in $G^{*}$ is no more than

${N^{2}\choose N}\leq\frac{N^{2N}}{N!}.$

Therefore the expected number of $F$-free sets $Z$ of size $N$ in $G^{*}$ is
less than $1/N!$. We may therefore select $G^{*}$ so as to contain no $F$-free
subgraph with at least $N$ vertices. Since $G^{*}$ is triangle-free, and
$n:=|V(G^{*})|=|E(H)|$, the bound (3) gives

$f_{F,K_{3}}(n)<N=n^{\frac{1}{2}+O(\sqrt{\frac{\log\log n}{\log n}})}.$

This proves the theorem. ∎

##  3 Proof of Theorem 2: Large $C_{k}$-free subsets

To prove Theorem 2, it is sufficient to prove the following theorem:

######  Theorem 5.

For any graph $F$ containing a cycle $C_{k}$, there exists
$\epsilon_{k}>1/100k$ such that

$f_{F,K_{4}}(n)=\Omega(n^{\frac{1}{3}+\epsilon_{k}}).$

To see that this implies Theorem 2, let $H$ be a $K_{s}$-free graph where
$s\geq 5$. If $H$ has maximum degree $d$, then by Turán’s Theorem, $H$ has an
independent set of size at least $n/(d+1)$, and the neighborhood of a vertex
of degree $d$ induces a $K_{s-1}$-free subgraph. By induction, setting
$\alpha_{k}(4)=1/3+\epsilon_{k}$, for $s\geq 5$, there exists
$\alpha=\alpha_{k}(s-1)>1/(s-2)$ such that this $K_{s-1}$-free subgraph has an
$F$-free subgraph with $\Omega(d^{\alpha_{k}(s-1)})$ vertices. Therefore we
have an $F$-free subgraph of size at least

$\Omega(\max\Bigl{\\{}d^{\alpha_{k}(s-1)},\frac{n}{d+1}\Bigr{\\}}).$

Setting

$\alpha_{k}(s)=1-\frac{1}{1+\alpha_{k}(s-1)},$

since $\alpha_{k}(4)>1/3$ for all $k\geq 3$, by induction we have

$\alpha_{k}(s)>1-\frac{1}{1+\frac{1}{s-2}}=\frac{1}{s-1}$

as required. Moreover, if $\alpha_{k}(s-1)\geq 1/(s-2)+\epsilon$ where
$\epsilon\leq 1$, the calculation above yields

$\displaystyle\alpha_{k}(s)\geq 1-\frac{s-2}{s-1+\epsilon(s-2)}$
$\displaystyle=\frac{1}{s-1}+\epsilon\left(\frac{(s-3)+\frac{1}{s-1}}{s-1+\epsilon(s-2)}\right)$
$\displaystyle>\frac{1}{s-1}+\epsilon\left(\frac{s-3}{2(s-1)}\right)$
$\displaystyle\geq\frac{1}{s-1}+\frac{\epsilon}{4}.$

With $\alpha_{k}(4)>1/3+1/100k$, this gives
$\alpha_{k}(s)=1/(s-1)+\Omega_{s}(1/k)$ as $k\rightarrow\infty$.

We will prove Theorem 5 as follows: a given $K_{4}$-free graph $H$ either has
few $k$-cycles going through every vertex or has a vertex that lies in many
$k$-cycles. In the former case, we apply standard results about hypergraph
independent sets (Lemma 3) to obtain a large $C_{k}$-free subset. In the
latter case, we show that $H$ contains a dense bipartite graph and then use
the dependent random choice technique to extract from this a large independent
set in one of the parts. These assertions are stated in the next three lemmas.

For sets $X,Y$ of vertices in a graph $G$, let $e(X,Y)$ denote the number of
edges $\\{x,y\\}\in E(G)$ such that $x\in X$ and $y\in Y$.

######  Lemma 1.

Let $G$ be a graph of maximum degree $d$, and let $\delta>0$. Suppose the
number of cycles of length $k$ containing a vertex $v_{0}\in V(G)$ is at least
$\delta d^{k-1}$. Then there exist sets $X,Y\subseteq V(G)$ such that
$e(X,Y)\geq\delta|X||Y|/(2\log_{2}d)^{k}$ and $|X|,|Y|\geq\delta
d/(\log_{2}d)^{k-3}$.

###### Proof.

Let $\mathcal{C}$ be the set of $k$-cycles containing $v_{0}$. For each
$\sigma\in\mathcal{C}$, pick an ordering
$(\sigma_{0},\sigma_{1},\dots,\sigma_{k-1},\sigma_{0})$ of the vertices of
$\sigma$, where $\\{\sigma_{i},\sigma_{i+1}\\}\in E(\sigma)$ with subscripts
modulo $k$. Let $X_{i}=\\{\sigma_{i}:\sigma\in\mathcal{C}\\}$ for $1\leq i\leq
k-1$. Then for $2\leq i\leq k-2$ there exist sets $X_{i}^{\prime}\subseteq
X_{i}$ and $a_{i}\in\\{1,2,\dots,d\\}$ such that every vertex of
$X_{i}^{\prime}$ has at least $a_{i}/2$ and at most $a_{i}$ neighbors in
$X_{i-1}^{\prime}$, and the number of cycles $\sigma\in\mathcal{C}$ with
$\sigma_{i}\in X_{i}^{\prime}$ is at least $\delta d^{k-1}/(\log_{2}d)^{k-3}$.
This can be done iteratively, starting by splitting $X_{2}$ into sets $X_{2j}$
such that every vertex of $X_{2j}$ has at least $d/2^{j+1}$ and at most
$d/2^{j}$ neighbors in $X_{1}$, for $0\leq j\leq\log_{2}d$, and considering an
$X_{2}^{\prime}=X_{2j}$ for which at least $|\mathcal{C}|/(\log_{2}d)$ of the
cycles use an edge between $X_{1}$ and $X_{2}^{\prime}$. Call this collection
of cycles $\mathcal{C}_{2}$. Then repeat the argument for the pair
$X_{2}^{\prime}$ and $X_{3}$, with collection of cycles $\mathcal{C}_{2}$ so
there exists $X_{3}^{\prime}\subseteq X_{3}$ and
$\mathcal{C}_{3}\subset\mathcal{C}_{2}$ with
$|\mathcal{C}_{3}|\geq|\mathcal{C}_{2}|/\log_{2}d$. We continue to obtain
$X_{i}^{\prime}\subseteq X_{i}$ for all $i\leq k-2$ and set
$\mathcal{C}^{\prime}:=\mathcal{C}_{k-2}$. Then

$|\mathcal{C}^{\prime}|\geq\frac{|\mathcal{C}|}{(\log_{2}d)^{k-3}}\geq\frac{\delta
d^{k-1}}{(\log_{2}d)^{k-3}}$

and for every $\sigma\in\mathcal{C}^{\prime}$ we have $\sigma_{i}\in
X_{i}^{\prime}$ for $i\leq k-2$.

Let $X=X_{k-2}^{\prime}$ and $Y=X_{k-1}^{\prime}$. The number of cycles in
$\mathcal{C}^{\prime}$ containing an edge $\\{x,y\\}$ with $x\in X$ and $y\in
Y$ is at most $a_{2}\cdots a_{k-2}\leq d^{k-3}$ as the maximum degree is $d$.
Consequently,

$|\mathcal{C}^{\prime}|\leq e(X,Y)\cdot a_{2}\cdots a_{k-2}\leq e(X,Y)\cdot
d^{k-3}$

and

$d\cdot\min\\{|X|,|Y|\\}\geq
e(X,Y)\geq\frac{|\mathcal{C}^{\prime}|}{d^{k-3}}\geq\frac{\delta
d^{2}}{(\log_{2}d)^{k-3}}.$

Therefore $\min\\{|X|,|Y|\\}\geq\delta d/(\log_{2}d)^{k-3}$.

Next we prove that $e(X,Y)\geq\delta|X||Y|/(2\log_{2}d)^{k}$. By construction,
for $2\leq i\leq k-2$,

$\frac{a_{i}}{2}|X_{i}^{\prime}|\leq e(X_{i}^{\prime},X_{i-1}^{\prime})\leq
d|X_{i-1}^{\prime}|$

and therefore $a_{i}\leq 2d|X_{i-1}^{\prime}|/|X_{i}^{\prime}|$. Since
$|X_{1}^{\prime}|\leq|N(v_{0})|\leq d$ and $|Y|\leq|N(v_{0})|\leq d$,

$a_{2}a_{3}\cdots
a_{k-2}\leq\prod_{i=2}^{k-2}2d\frac{|X_{i-1}^{\prime}|}{|X_{i}^{\prime}|}=(2d)^{k-3}\frac{|X_{1}^{\prime}|}{|X_{k-2}^{\prime}|}=(2d)^{k-3}\frac{|X_{1}^{\prime}|}{|X|}\leq\frac{(2d)^{k-1}}{|X||Y|}.$

Consequently,

$e(X,Y)\geq\frac{|\mathcal{C}^{\prime}|}{a_{2}\dots
a_{k-2}}\geq\frac{|\mathcal{C}^{\prime}||X||Y|}{(2d)^{k-1}}\geq\frac{\delta}{2^{k-1}(\log_{2}d)^{k-3}}|X||Y|$

completing the proof. ∎

The following lemma is a standard consequence of the dependent random choice
method and we omit the proof.

######  Lemma 2.

Let $\gamma\geq 0$, $s\geq 1$, and let $X$ and $Y$ be disjoint sets of
vertices in a graph, such that $e(X,Y)\geq\gamma|X||Y|$. Then for any $s\geq
1$, there exists a set $Z\subseteq Y$ such that

$|Z|\geq\frac{1}{2}\gamma^{s}|Y|$

and every pair of vertices in $Z$ has at least $\gamma|X||Y|^{-1/s}$ neighbors
in $X$.

Finally we need the following standard result about independent sets in
hypergraphs first proved by Spencer [19].

######  Lemma 3.

For every $k\geq 2$, every $n$-vertex $k$-uniform hypergraph with average
degree $d>0$ has an independent set of size at least $(1-1/k)n/d^{1/(k-1)}$.

We now have the necessary ingredients to prove Theorem 5.

Proof of Theorem 5. For $k\geq 3$, let

$\epsilon_{k}=\frac{1}{100(k-1)}.$

Let $H$ be an $n$-vertex $K_{4}$-free graph with maximum degree $d$. We will
find a $C_{k}$-free subset of vertices in $H$ of size at least
$n^{1/3+\epsilon_{k}}$. Suppose that $\triangle$ is the maximum number of
copies of $C_{k}$ that a vertex is in. Define

$\delta:=\frac{\triangle}{d^{k-1}}.$

We now obtain two different bounds on the maximum $C_{k}$-free set.

Bound 1. Let $\mathcal{H}$ be the $k$-uniform hypergraph with
$V(\mathcal{H})=V(H)$ and $E(\mathcal{H})=\\{V(C_{k}):C_{k}\subseteq H\\}$.
Then $\mathcal{H}$ has maximum degree (and hence average degree) at most
$\triangle$ and Lemma 3 implies that $H$ has an independent set of size at
least

$\Omega\left(\frac{n}{\triangle^{\frac{1}{k-1}}}\right)=\Omega\left(\frac{n}{\delta^{\frac{1}{k-1}}d}\right).$

Bound 2. Let $v_{0}\in V(H)$ lie in $\triangle=\delta d^{k-1}$ copies of
$C_{k}$. By Lemma 1, there exist sets $X,Y\subseteq V(H)$ such that

$e(X,Y)\geq\frac{\delta}{(2\log_{2}d)^{k}}|X||Y|=:\gamma|X||Y|,$

where $|X|\geq|Y|\geq\gamma d$. By Lemma 2 applied with $s=3$, there exists
$Z\subseteq Y$ with

$|Z|\geq\frac{1}{2}\gamma^{3}|Y|$

such that every pair of vertices in $Z$ has at least
$\gamma|X||Y|^{-1/3}\geq\gamma|Y|^{2/3}$ common neighbors in $X$. If $Z$ is
not an independent set in $H$, then there exists $\\{x,y\\}\in E(H)$ with
$x,y\in Z$. Since $H$ is $K_{4}$-free, $N(x)\cap N(y)$ is an independent set
in $H$ of size at least $\gamma|Y|^{2/3}\geq\gamma^{5/3}d^{2/3}$. Otherwise,
$Z$ is an independent set in $H$ of size at least
$\frac{1}{2}\gamma^{3}|Y|\geq\frac{1}{2}\gamma^{4}d$. In particular, $H$ has a
$C_{k}$-free induced subgraph of size at least

$h(d,\gamma)=\min\left\\{\gamma^{5/3}d^{2/3},\frac{1}{2}\gamma^{4}d\right\\}.$

It is also the case that $G$ always contains an independent set with at least
$n/(d+1)$ vertices, by Turán’s Theorem. If $d\leq n^{2/3-\epsilon_{k}}$, this
gives an independent set of size $n^{1/3+\epsilon_{k}}$ in $G$. If $d\geq
n^{2/3+2\epsilon_{k}}$, then since the neighborhood of a vertex of degree $d$
induces a triangle-free graph, this neighborhood contains an independent set
of size at least $d^{1/2}\geq n^{1/3+\epsilon_{k}}$ in $G$. Therefore we
assume $n^{2/3-\epsilon_{k}}\leq d\leq n^{2/3+2\epsilon_{k}}$. In that case,
by Bounds 1 and 2, we obtain a $C_{k}$-free set of size at least

$\Omega\left(\max\left\\{\frac{n}{\delta^{\frac{1}{k-1}}d},h(d,\gamma)\right\\}\right).$

If $\delta<n^{-1/25}$, then Bound 1 is at least

$\Omega\left(\frac{n}{\delta^{\frac{1}{k-1}}d}\right)=\Omega\left(n^{\frac{1}{3}+\frac{1}{25(k-1)}-2\epsilon_{k}}\right)=\Omega(n^{\frac{1}{3}+\epsilon_{k}})$

as $\epsilon_{k}<1/75(k-1)$. So we may assume that $\delta\geq n^{-1/25}$,
and, as $n$ is sufficiently large, we may assume that
$\gamma=\delta/(2\log_{2}d)^{k}>n^{-1/24}$. In this case, $\epsilon_{k}<1/100$
and $d>n^{2/3-\epsilon_{k}}$ yield

$\gamma^{\frac{5}{3}}d^{\frac{2}{3}}>n^{\frac{-5}{72}+\frac{4}{9}-\frac{2\epsilon_{k}}{3}}>n^{\frac{1}{3}+\epsilon_{k}}\qquad\hbox{
and
}\qquad\gamma^{4}d>n^{-\frac{1}{6}+\frac{2}{3}-\epsilon_{k}}>2n^{\frac{1}{3}+\epsilon_{k}}$

and therefore $h(d,\gamma)>n^{1/3+\epsilon_{k}}$, completing the proof. ∎

##  4 Proof of Theorem 3

A sunflower is a collection of sets every pair of which have the same
intersection, called the core. We need the well-known Erdos-Rado sunflower
lemma in the form below.

######  Lemma 4.

Fix $t,m>0$. Every $t$-uniform hypergraph with more than $t!(m-1)^{t}$ edges
has a sunflower of size $m$.

Proof of Theorem 3. Let $|V(G)|=k$. We may assume that $G$ is not acyclic,
since otherwise $G$ would be contained in a blowup of $F$. Consider an $n$ by
$n$ bipartite graph $H$ without cycles of length at most $2k$ and where every
vertex has degree $d=n^{\frac{1}{3k}}$. Such graphs exist, for example the
bipartite Ramanujan graphs of Lubotzky, Phillips and Sarnak [13], or even a
random $d$-regular graph (if we are not fussy about the constant in the
exponent). We now employ the methods of [15, 5]. Let $H^{\prime}$ be the
restriction of the square of $H$ to one part of $H$, so that $H^{\prime}$ has
$n$ vertices, and is a union of $n$ edge-disjoint cliques
$K^{1},K^{2},\dots,K^{n}$ of order $d$. Since $G$ is not acyclic, every copy
of $G$ in $H^{\prime}$ is contained in one of those cliques. In each of the
cliques, take a random coloring with elements of $V(F)$, and put an edge
between any two color classes corresponding to an edge of $F$. Since $F$ is
$\mbox{hom}(G)$-free, this random graph $H^{*}$ is $G$-free. We claim
(similarly to the proof of Theorem 1), that every set of at least
$(2n|V(F)|\log|V(F)|)/d$ vertices of $H^{*}$ induces a copy of $F$. The
probability that such a set $X$ does not induce a copy of $F$ is at most

$\prod_{i=1}^{n}|V(F)|\cdot\Bigl{(}1-\frac{1}{|V(F)|}\Bigr{)}^{|X\cap
V(K^{i})|}.$

Now we use

$\sum_{i=1}^{n}|X\cap V(K_{i})|=d|X|$

and therefore the expected number of such $X$ is at most

${n\choose|X|}\cdot|V(F)|^{n}\Bigl{(}1-\frac{1}{|V(F)|}\Bigr{)}^{d|X|}<e^{|X|\log
n-d|X|/|V(F)|+n\log|V(F)|}.$

This is vanishing since $d|X|/|V(F)|>2n\log|V(F)|$. Therefore

$f_{F,G}(n)=O(n/d)=O(n^{1-\frac{1}{3k}})=O(n^{1-\frac{1}{3|V(G)|}})$

and we may take $\varepsilon_{G}=1/3|V(G)|$ in Theorem 3.

We now prove the second statement of the theorem. Let $r:=|V(G)|-1$. If $G$ is
acyclic, then any $n$-vertex $G$-free graph has an independent set $I$ of size
linear in $n$, and $I$ is certainly $F$-free for any nonempty $F$ so we are
done. If $G$ is not 2-connected, then let $F=K_{r}$ so that $F$ is clearly
$G$-free. Suppose that $H$ is an $n$-vertex $G$-free graph. Then no two
$r$-cliques in $H$ have a point in common, for otherwise the subgraph of $H$
induced by their union contains $G$. Indeed, we can pick some vertex in the
intersection of the two cliques to be a cut vertex of $G$, and then easily
embed $G$ in the union of the two cliques (the embedding is even easier if $G$
is not connected). Consequently, the $r$-cliques in $H$ are pairwise vertex
disjoint. Then $H$ has a $K_{r}$-free induced subgraph of size at least
$(1-1/r)n$ and we are done.

We may henceforth assume that $G$ is 2-connected. Since $G$ is not a clique,
let $v,w$ be nonadjacent vertices in $G$. Let $G^{+}$ be the graph obtained
from $G$ by adding all edges that are not already in $G$ between $\\{v,w\\}$
and $N_{G}(v)\cup N_{G}(w)$. So $G^{+}\supset G$, and $v$ and $w$ are clones
in $G^{+}$. Let $G^{*}=G^{+}-\\{w\\}$ and let
$G^{**}=G^{+}-\\{v,w\\}=G^{*}-\\{v\\}$. So $G^{*}$ has $r$ vertices and
$G^{**}$ has $r-1$ vertices.

Assume that $t$ is sufficiently large in terms of $r$ and set
$\delta=1/5r^{2}$. Apply Proposition B to obtain a $t$-vertex $r$-uniform
hypergraph $F^{*}$ with girth larger than $r+1$, and the property that for
every $s$-set $S$ with $t^{1-\delta}\leq s\leq t-1$, the number of edges in
$F^{*}$ with exactly $r-1$ vertices in $S$ is at least

$\frac{1}{10}{s\choose r-1}(t-s)t^{1-r+\frac{1}{2r}}>{s\choose
r-1}(t-s)t^{1-r+\frac{1}{3r}}=:q_{s}.$

Inside each hyperedge $e$ of $F^{*}$, place randomly a copy of $G^{*}$. More
precisely, among all $r!$ ways to map the vertices of $G^{*}$ to $e$, we pick
one with probability $1/r!$. Let $F$ be the resulting graph with
$V(F)=V(F^{*})$ and $E(F)$ comprises the graph edges in all copies of $G^{*}$
that lie in edges of $F^{*}$.

As $G$ has $r+1$ vertices, and $F^{*}$ is $r$-uniform, there is no copy of $G$
in $F$ that lies entirely within an edge of $F^{*}$. If a copy of $G$ in $F$
has two vertices $x,y$ that do not lie in the same edge of $F^{*}$, then,
since $G$ is 2-connected, there is a cycle in $G$ containing $x$ and $y$ and
this cycle yields a hypergraph cycle in $F^{*}$ of length at most $r+1$ which
does not exist by construction. We conclude that $F$ is $G$-free.

Furthermore, we claim that for any $s$-set $S$ in $F$, with $t^{1-\delta}\leq
s\leq t-1$, there exists an edge $e$ of $F^{*}$ with $r-1$ vertices in $S$ and
one vertex in $V(F^{*})-S$ such that

the copy of $G^{*}$ placed inside $e$ induces a copy of $G^{**}$ within $e\cap
S$. (4)

Indeed, (4) follows from the following argument. For each of the $q_{s}$ edges
$e$ of $F^{*}$ with exactly one vertex outside $S$, the probability that $e$
fails (4) is at most $1-1/r!$. Since any two such edges $e,e^{\prime}$ share
at most one vertex by the girth property of $F^{*}$, the probability that all
of these $q_{s}$ edges $e$ fail (4) is at most $(1-1/r!)^{q_{s}}$.
Consequently, the probability that there exists an $s$-set for which there is
no $e$ satisfying (4) is at most

$\sum_{s=t^{1-\delta}}^{t-1}{t\choose
s}e^{-q_{s}/r!}=\sum_{s=t^{1-\delta}}^{t-1}{t\choose
t-s}e^{-q_{s}/r!}<t{t\choose t-s}e^{-q_{s}/r!}<e^{\log t+(t-s)\log
t-q_{s}/r!}<1.$

The final inequality holds as $\delta=1/5r^{2}$ implies

$1-r+\frac{1}{3r}+(1-\delta)(r-1)>0.$

Hence we may assume that for all $s$-sets $S$ with $t^{1-\delta}\leq s\leq
t-1$ there exists an edge $e$ of $F^{*}$ with $r-1$ vertices in $S$ and one
vertex in $V(F^{*})-S$ which satisfies (4).

Now let $H$ be any $G$-free $n$-vertex graph. We are to find an $F$-free set
of size $\Omega(n^{1-\varepsilon})$. Let $R=r!+1$ and

$T=t!\left(R{t-1\choose r-1}-1\right)^{t}.$

Set $b=t^{1-\delta}$. We claim the number of copies of $F$ in $H$ is at most

$T{n\choose b}.$ (5)

If (5) holds, then there are at most $O(n^{b})$ copies of $F$ in $H$ and we
finish the proof as follows. Consider the $t$-uniform hypergraph $\mathcal{H}$
with $V(\mathcal{H})=V(H)$ and $E(\mathcal{H})=\\{V(F):F\subseteq H\\}$. The
average degree of $\mathcal{H}$ is $O(n^{b-1})$. By Lemma 3, $\mathcal{H}$
contains an independent set $I$ of size $\Omega(n^{1-(b-1)/(t-1)})$. Since
$(b-1)/(t-1)<t^{1-\delta}/(t-1)<\varepsilon$ for large $t$, we conclude that
$I$ is an $F$-free set of size at least $\Omega(n^{1-\varepsilon})$.

We now prove (5). Assume to the contrary. Then to each copy of $F$ we may
associate any $b$-subset of its vertices. By pigeonhole, there exists a set
$C$ of $b$ vertices in $H$ and at least $T$ copies of $F$, say
$F_{1},F_{2},\dots,F_{T}$ for which $V(F_{i})\cap V(F_{j})\supseteq C$.
Amongst these sets of size $t$, Lemma 4 gives a sunflower of size
$R{t-1\choose r-1}$ with core $S\supseteq C$. As $t^{1-\delta}\leq|S|\leq
t-1$, by (4), for each of these $R{t-1\choose r-1}$ copies $A$ of $F$, there
is a vertex $v_{A}$ outside $S$ that forms an edge $e_{A}$ in $A$ with $r-1$
vertices in $S$ and $v_{A}$ plays the role of vertex $v$ in the copy of
$G^{*}$ within $e_{A}$ (in other words, $e^{\prime}_{A}=e_{A}-\\{v_{A}\\}$
induces a copy of $G^{**}$). By pigeonhole, there exists a set
$e^{\prime}\subseteq S$ of size $r-1$ and vertices
$v_{1},v_{2},\ldots,v_{R}\not\in S$ such that
$e_{i}=e^{\prime}\cup\\{v_{i}\\}$ is an edge of $F^{*}$ for all $i\in[R]$ and
$v_{i}$ plays the role of $v$ in the copy of $G^{*}$ in $e_{i}$ (in other
words, $e^{\prime}$ induces a copy of $G^{**}$). Since $R>r!$, we can find
vertices, say $v_{1},v_{2}$, such that the copies of $G^{**}$ within
$e^{\prime}$ for both $v_{1}$ and $v_{2}$ are identical. This copy of $G^{**}$
together with $v_{1}$ and $v_{2}$ is a copy of $G^{+}$. We conclude
$H\supseteq G^{+}\supseteq G$, a contradiction. ∎

##  5 Appendix

######  Proposition A.

(Erdős-Frankl-Rödl) For any $N,R\geq 3$ such that $N\geq R\geq\log N$, there
exists a linear triangle-free $N$-vertex $R$-uniform hypergraph $H$ with

$|E(H)|\geq\frac{N^{2}}{R^{8\sqrt{\log_{R}N}}}.$

###### Proof.

The construction is based on the construction of Behrend [3] of a dense subset
of $\\{1,2,\dots,n\\}$ with no three-term arithmetic progression. For
completeness, we describe this construction here, which is slightly better
than the construction of Erdős, Frankl and Rödl [6]. Let $A$ be the set of
positive integer points on the sphere of radius $r$ in $\mathbb{R}^{d}$. For
any choice of positive integers $x_{1},x_{2},\dots,x_{d-4}\leq r/\sqrt{d}$,
there exist positive integers $x_{d-3},x_{d-2},x_{d-1},x_{d}$ such that
$x_{1}^{2}+x_{2}^{2}+\dots+x_{d}^{2}=r^{2}$ by Lagrange’s four squares
theorem. Therefore

$|A|\geq\Bigl{(}\frac{r}{\sqrt{d}}\Bigr{)}^{d-4}.$

Let $X_{i}=[ir]^{d}$. Then define an $R$-uniform $R$-partite hypergraph $H$
where $V(H)$ consists of $X_{1}\cup X_{2}\cup\dots\cup X_{R}$ and let
$E(H)=\\{x,x+a,x+2a,\dots,x+(R-1)a\\}$ where $a\in A$ and $x\in X_{1}$. Then

$|V(H)|=N\leq R^{d+1}r^{d}\quad\quad\mbox{ and
}\quad\quad|E(H)|=|A||X_{1}|\geq\frac{r^{2d-4}}{\sqrt{d}^{d-4}}.$

Put $d=\lfloor\sqrt{\log_{R}N}\rfloor<\log N\leq R$ and $r=R^{d}$. Then
$r^{4}\leq R^{4d}$ and $d^{d}<R^{d}$ and hence

$|E(H)|\geq\frac{N^{2}}{R^{2d+2}r^{4}d^{\frac{d-4}{2}}}\geq\frac{N^{2}}{R^{8d}}>\frac{N^{2}}{R^{8\sqrt{\log_{R}N}}}.$

This establishes (i). If $e=\\{x,x+a,x+2a,\dots,x+(R-1)a\\}$ and
$f=\\{y,y+b,y+2b,\dots,y+(R-1)b\\}$ intersect in two vertices of $H$, say
$x+ia=y+ib$ and $x+ja=y+jb$, then $x=y$ and $a=b$, establishing (ii). If $e,f$
and $g=\\{z,z+c,z+2c,\dots,z+(R-1)c\\}$ have $|e\cap f|=|f\cap g|=|g\cap
e|=1$, then we may assume $x+ia=y+ib$ and $y+jb=z+jc$ and $z+kc=x+ka$ for some
distinct $i,j,k\in\\{0,1,2,\dots,R-1\\}$ and $a,b,c\in A$. This implies
$i(b-a)+j(c-b)+k(a-c)=0$ which means $(k-i)a+(i-j)b+(j-k)c=0$. Since the
sphere is strictly convex, $a,b,c$ cannot all lie in a line, and hence we
conclude two of $i,j,k$ are identical, a contradiction. This proves (iii). ∎

For the next proposition, we need some definitions. A cycle of length two in a
hypergraph is a set of two edges that share at least two vertices. A cycle of
length $\ell>2$ is a collection of $\ell$ distinct vertices
$v_{1},v_{2},\ldots,v_{\ell}$ and $\ell$ distinct edges
$e_{1},\ldots,e_{\ell}$ where $e_{i}\cap e_{i+1}=\\{v_{i+1}\\}$ (indices
modulo $\ell$) and $e_{i}\cap e_{j}=\emptyset$ otherwise. So an $\ell$-cycle
in an $r$-uniform hypergraph ($\ell>2$) has $\ell$ edges and $\ell(r-1)$
vertices (these are often called loose cycles). Say that a hypergraph $H$ has
girth $g$ if the length of the shortest cycle in $H$ is $g$.

######  Proposition B.

Fix $r\geq 2$ and $\delta=1/5r^{2}$. For $t$ sufficiently large, there exists
a $t$-vertex $r$-uniform hypergraph $F^{*}$ with girth at least $r+2$ such
that for every $s$-subset $S$ with $t^{1-\delta}<s<t$, the number of edges
with exactly one vertex outside $S$ is at least

$\frac{1}{10}{s\choose r-1}(t-s)t^{1-r+\frac{1}{2r}}.$ (6)

###### Proof.

Consider the binomial random $r$-uniform hypergraph $H\sim H^{(r)}(t,p)$ with
$t$ vertices where each edge appears independently with probability
$p=t^{1-r+\frac{1}{2r}}$. For each $2\leq\ell\leq r+1$, Let $C_{\ell}$ denote
the cycle of length $\ell$ (this is unique except for $\ell=2$) and let
$\mathcal{B_{\ell}}$ denote a maximal collection of edge-disjoint copies of
$C_{\ell}$ in $H$. Form $F^{*}$ by starting with $H$ and deleting all $\ell$
edges from every copy of $C_{\ell}$ in $\mathcal{B_{\ell}}$ for all
$2\leq\ell\leq r+1$. Then, by the maximality of $\mathcal{B_{\ell}}$, the
remaining hypergraph $F^{*}$ has girth at least $r+2$. We will now show that
with high probability $F^{*}$ has the required property.

Pick $S\subset V(F^{*})$ of size $s$ where $t^{1-\delta}<s<t$. Call an edge in
$H$ with exactly one vertex outside $S$ an $S$-edge. Let $X=X_{S}$ be the
number of $S$-edges, let $Y_{\ell}=Y_{S,\ell}$ be the number of copies of
$C_{\ell}$ that contain at least one $S$-edge and let $Z_{\ell}=Z_{S,\ell}$ be
the maximal number of pairwise edge-disjoint copies of $C_{\ell}$, each
containing at least one $S$-edge. Obviously, $Z_{\ell}\leq Y_{\ell}$. Define
the event

$A_{\ell}=A_{S,\ell}=\\{X>10r\ell\,Z_{\ell}\\}.$

We note that if $A_{S,\ell}$ holds for every appropriate $S$, and
$2\leq\ell\leq r+1$, then the number of $S$-edges in $F^{*}$ is at least

$X-\sum_{\ell=2}^{r+1}\ell\,Z_{\ell}\geq|X|-\sum_{\ell=2}^{r+1}\frac{|X|}{10r}>(0.9)|X|.$

Moreover, ${\mathbb{E}}(X)={s\choose r-1}(t-s)p$, so if it is also the case
that $X>{\mathbb{E}}(X)/2$, then the number of $S$-edges in $F^{*}$ is at
least $(0.4){\mathbb{E}}(X)$ and $S$ satisfies (6).

We see that

${\mathbb{E}}(Y_{\ell})<{s\choose r-1}(t-s)t^{\ell(r-1)-r}p^{\ell}.$

As $p=t^{1-r+\frac{1}{2r}}$ and $\ell\leq r+1$, we have
$p^{\ell}t^{\ell(r-1)-r}\ll p$. Therefore
${\mathbb{E}}(Y_{\ell})\ll{\mathbb{E}}(X)$. Now

${\mathbb{P}}(\overline{A_{\ell}})={\mathbb{P}}(X\leq
10r\ell\,Z_{\ell})\leq{\mathbb{P}}\left(X\leq\frac{{\mathbb{E}}(X)}{2}\right)+{\mathbb{P}}\left(Z_{\ell}\geq\frac{{\mathbb{E}}(X)}{20r\ell}\right).$

Krivelevich [11, Claim 1] proved that in this setup, for any constant $c>0$,

${\mathbb{P}}(Z_{\ell}\geq c\,{\mathbb{E}}(Y_{\ell}))<e^{-c\,(\log
c-1){\mathbb{E}}(Y_{\ell})}.$

Using this and ${\mathbb{E}}(Y_{\ell})\ll{\mathbb{E}}(X)$ we have

${\mathbb{P}}\left(Z_{\ell}\geq\frac{{\mathbb{E}}(X)}{20r\ell}\right)={\mathbb{P}}\left(Z_{\ell}\geq\frac{{\mathbb{E}}(X)}{20r\ell\,{\mathbb{E}}(Y_{\ell})}{\mathbb{E}}(Y_{\ell})\right)<e^{\frac{-{\mathbb{E}}(X)}{20r\ell}(\log(\frac{{\mathbb{E}}(X)}{20r\ell\,{\mathbb{E}}(Y_{\ell})})-1)}<e^{-{\mathbb{E}}(X)}.$

The standard Chernoff bound gives
${\mathbb{P}}(X\leq{\mathbb{E}}(X)/2)<e^{-{\mathbb{E}}(X)/8}$ so altogether we
obtain ${\mathbb{P}}(\overline{A_{\ell}})<e^{-{\mathbb{E}}(X)/9}$. Using the
union bound, the probability that there exists an $S$ that fails (6) is at
most

$\sum_{s=t^{1-\delta}}^{t-1}{t\choose s}e^{-{s\choose r-1}(t-s)p/9}<e^{\log
t+(t-s)\log t-{s\choose r-1}(t-s)p/9}.$

The power of $t$ in $s^{r-1}p$ is at least $1-r+1/2r+(1-\delta)(r-1)>0$ as
$\delta<1/2r^{2}$ and hence the quantity above vanishes for large $t$. We
conclude that (6) holds in $F^{*}$ with high probability. ∎

## References

  * [1] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Comb. Theory (Series A), 29 (1980), 354–360.
  * [2] J. Balogh, C. Chen, H. Luo, On the maximum size of $F$-free induced subgraphs in $K_{t}$-free graphs, preprint
  * [3] F. A. Behrend, On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 23 (1946), 331–332.
  * [4] T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process, Random Struct. Alg. 58 (2021), 221–293.
  * [5] D. Conlon, S. Mattheus, D. Mubayi, J. A. Verstraëte, Ramsey numbers and the Zarankiewicz problem, Bull. Lond. Math. Soc. 56, 6 (2024), 2014–2023.
  * [6] P. Erdős, P. Frankl, V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2, (1986), 113–121.
  * [7] P. Erdős, C. A. Rogers, The construction of certain graphs, Canad. J. Math 14 (1962), 702–707.
  * [8] G. Fiz Pontiveros, S. Griffiths and R. Morris The triangle-free process and the Ramsey numbers, Mem. Amer. Math. Soc., 263 (2020), 125pp.
  * [9] O. Janzer, B. Sudakov, Improved bounds for the Erdős-Rogers $(s,s+2)$-problem, Preprint (2023) https://arxiv.org/pdf/2307.05441.pdf.
  * [10] J. H. Kim, The Ramsey Number $R(3,t)$ has order of magnitude $t^{2}/\log t$, Random Structures and Algorithms 7 (1995), 173–207.
  * [11] M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities, Random Structures Algorithms 7 (1995), 145–155.
  * [12] Y. Li, W. Zang, The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers, Journal of Combinatorial Optimization, Springer, vol. 7(4), pages 353–359.
  * [13] A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277.
  * [14] S. Mattheus, J. A. Verstraëte, The asymptotics of $r(4,t)$, Annals of Math. 199 (2024), no. 2 919–941
  * [15] D. Mubayi, J. A. Verstraete, A note on pseudorandom Ramsey graphs, J. Eur. Math. Soc. (JEMS) 26 (2024), no. 1, 153-161.
  * [16] D. Mubayi, J. A. Verstraëte, On the order of Erdős-Rogers functions, https://arxiv.org/abs/2401.02548
  * [17] J. Shearer, On the independence number of sparse graphs, Random Structures and Algorithms 7 (1995), 269–271.
  * [18] J. Shearer, A note on the independence number of triangle-free graphs, Discrete Mathematics 46 no 1. (1983) 83–87.
  * [19] J. Spencer, Turán’s theorem for $k$-graphs, Discrete Mathematics 2 no. 2, (1972), 183–186.
  * [20] B. Sudakov, A note on odd cycle-complete graph Ramsey numbers. Electron. J. Combin. 9 (2002), no. 1, Note 1, 4 pp.