# Forbidden subgraphs and complete partitions

John Byrne Department of Mathematical Sciences, University of Delaware.
<EMAIL_ADDRESS>Michael Tait Department of Mathematics & Statistics,
Villanova University. Research partially supported by NSF grants DMS-2011553
and DMS-2245556<EMAIL_ADDRESS>Craig Timmons Department of
Mathematics and Statistics, California State University, Sacramento. Research
partially supported by Sac State (P3) Program<EMAIL_ADDRESS>
###### Abstract

A graph is called an $(r,k)$-graph if its vertex set can be partitioned into
$r$ parts of size at most $k$ with at least one edge between any two parts.
Let $f(r,H)$ be the minimum $k$ for which there exists an $H$-free
$(r,k)$-graph. In this paper we build on the work of Axenovich and Martin,
obtaining improved bounds on this function when $H$ is a complete bipartite
graph, even cycle, or tree. Some of these bounds are best possible up to a
constant factor and confirm a conjecture of Axenovich and Martin in several
cases. We also generalize this extremal problem to uniform hypergraphs and
prove some initial results in that setting.

##  1 Introduction

Let $r$, $k$, and $m$ be positive integers with $r\geq m\geq 2$. We write
$[r]$ for $\\{1,2,\dots,r\\}$ and $\binom{[r]}{m}$ for all subsets of $[r]$
with $m$ elements. An $m$-uniform hypergraph $G$ is an _$(r,k)$ -hypergraph_
if there is a partition of $V(G)$ into sets $V_{1},V_{2},\dots,V_{r}$ such
that $|V_{i}|\leq k$ for $1\leq i\leq r$, and for all
$\\{i_{1},i_{2},\dots,i_{m}\\}\in\binom{[r]}{m}$ there is an $e\in E(G)$ such
that $|e\cap V_{i_{j}}|=1$ for $1\leq j\leq m$.

Given an $(r,k)$-graph $G$, if each $V_{i}$ induces a connected subgraph, then
contracting each $V_{i}$ to a single vertex shows that $K_{r}$ is a minor of
$G$. Consequently, an $(r,k)$-graph with partition $V_{1},\dots,V_{r}$ is
sometimes called a $k$-split of $K_{r}$. A more general notion of $k$-splits
exists and the study of splits goes back to Heawood [26]. Graph splits were
originally mostly studied with respect to topological properties (see for
example [14]). More recently, the study of splits has been considered from an
extremal perspective. There are several interesting questions one can ask,
such as the largest complete minor in an $H$-free graph [6, 31] or in a graph
without a sparse cut [30].

In another direction, if each $V_{i}$ is an independent set, then the parts
$V_{1},\dots,V_{r}$ give a proper vertex coloring of $G$. This leads to the
achromatic and pseudoachromatic number of a graph which we define now. A
_complete $r$-coloring_ of a graph $G$ is a proper vertex coloring
$c:V(G)\rightarrow[r]$ such that between any two distinct color classes there
is an edge. The achromatic number of $G$, denoted $\chi_{a}(G)$, is the
maximum $r$ for which $G$ has a complete $r$-coloring. If there is no
restriction on the $V_{i}$’s, then we have a _pseudocomplete $r$-coloring_ of
$G$. Pseudocomplete colorings drop the restriction that the coloring must be
proper, and write $\psi(G)$ for the pseudoachromatic number of $G$. Complete
and pseudocomplete colorings of graphs and their associated parameters have a
fairly large body of work devoted to them. Researchers have studied them for
specific graph families [9, 12, 11, 35, 38], hypergraphs [13, 24], and the
surveys [10, 27] contain additional references.

Kostochka [29] and Thomason [39] used pseudochromatic coloring in their
influential work on the minimum degree forcing a complete minor, so there are
useful relationships between these two notions (see Section 3 of [39] or
Bollobás, Reed, Thomason [5] for brief discussions). The focus of this paper
is a function, considered by Barbanera and Ueckerdt [3] and studied further by
Axenovich and Martin [2], that falls into the branch of extremal partitioning
problems with (possibly) some condition on the parts. For an $m$-uniform
hypergraph $H$, define

$f_{m}(r,H)=\min\\{k:\mbox{exists an $H$-free $m$-uniform
$(r,k)$-hypergraph~{}$G$}\\}.$

In the case of $r=2$ we write $f(r,H)$ instead of $f_{2}(r,H)$.

Assuming that $H$ has minimum degree at least 3, Axenovich and Martin give a
simple construction that takes an $H$-free $(r,k)$-graph and produces an
$H$-free graph with a $K_{r}$ minor by adding vertices and edges to connect
the $V_{i}$’s. Regarding coloring, if $G$ is an $(r,k)$-graph, then
$r\leq\psi(G)$ and any complete or pseudocomplete $r$-coloring defines an
$(r,k)$-partition. Since we will consider only $H$-free graphs in this paper
and removing edges cannot create a copy of $H$, any graph with partition
$V_{1},\dots,V_{r}$ that we consider in this paper may be assumed to have each
$V_{i}$ an independent set. So bounds for $f(r,H)$ can imply bounds on
achromatic numbers and pseudoachromatic numbers and vice versa. However, in
this paper we want to minimize the maximum size of a color class in a
pseudocomplete $r$-coloring rather than maximizing the number of color
classes. Because of these differing objectives, we phrase all of our work in
the language of [2] instead of using the terminology from these graph coloring
or minor problems. It would be interesting to explore these connections in
more depth, but this is not the focus of the present paper.

A simple observation is that if $G$ is an $H$-free $(r,k)$-graph, then

$\binom{r}{2}\leq e(G)\leq\textup{ex}(rk,H).$

The first inequality is true since there is at least one edge between any two
of the $r$ parts. The second holds because $G$ is $H$-free with at most $rk$
vertices. For fixed $r$, this inequality gives a lower bound on $k$ which
implies a lower bound on $f(r,H)$. Any lower bound on $f(r,H)$ obtained using

$\binom{r}{2}\leq\textup{ex}(rk,H)$ (1)

will be called the “trivial (lower) bound”. Observe that the inequality
$\binom{r}{2}\leq e(G)$ also holds if $r$ is replaced by $\chi_{a}(G)$,
$\psi(G)$, and the Hadwiger number of $G$ which the largest $r$ such that
$K_{r}$ is a minor of $G$ (see Proposition 1 of [31] for example).

If $H$ is not bipartite, a simple argument given in [2] shows that $f(r,H)\leq
2$ for all $r\geq 1$. For this reason we will assume that $H$ is bipartite in
the graph case. Supposing for a moment that
$\textup{ex}(N,H)=\Theta(N^{\eta})$ for some $0<\eta<2$, the trivial lower
bound implies $f(r,H)=\Omega(r^{2/\eta-1})$. Axenovich and Martin proved an
upper bound that differs from this lower bound by a logarithmic factor under
an assumption on the Turán number of $H$.

######  Theorem 1.1 (Axenovich, Martin [2])

If $H$ is a bipartite graph that is not a forest with
$\textup{ex}(N,H)=\Theta(N^{\eta})$, then there are positive constants $c$ and
$C$ such that for all $r$,

$cr^{2/\eta-1}\leq f(r,H)\leq Cr^{2/\eta-1}\log^{1/\eta}r.$

They conjectured that the trivial lower bound (1) gives the correct order of
magnitude. If true, it shows that the logarithmic factor in Theorem 1.1 can be
removed.

######  Conjecture 1.2 (Axenovich, Martin [2])

Let $H$ be a bipartite graph that is not a forest. There is a positive
constant $c=c(H)$ such that for any positive integers $r$ and $k$ for which
$\textup{ex}(rk,H)>c\binom{r}{2}$, there is an $H$-free $(r,k)$-graph, i.e.,
$f(r,H)<k$.

Using the incidence graph of an affine plane, they proved that Conjecture 1.2
is true for $C_{4}$.

######  Theorem 1.3 (Axenovich, Martin [2])

The function $f(r,C_{4})$ satisfies

$r^{1/3}-o(r^{1/3})\leq f(r,C_{4})\leq 2r^{1/3}+o(r^{1/3}).$

For any $d\geq 1$, $C_{4}$ is a subgraph of $K_{2,d+1}$ so that
$f(r,K_{2,d+1})\leq f(r,C_{4})$. This means that the upper bound in Theorem
1.3 implies the same upper bound for $f(r,K_{2,d+1})$. The asymptotic formula
$\textup{ex}(N,K_{2,d+1})=\frac{\sqrt{d}}{2}N^{3/2}+o(N^{3/2})$, proved by
Füredi [18], together with the trivial bound (1) and Theorem 1.3, gives

$\frac{1}{d^{1/3}}r^{1/3}-o(r^{1/3})\leq f(r,K_{2,d+1})\leq
2r^{1/3}+o(r^{1/3}).$

For fixed $d\geq 2$, Theorem 1.3 proves Conjecture 1.2 for $H=K_{2,d+1}$.
However, this result does not capture the dependence of $f(r,K_{2,d+1})$ on
$d$. Using the projective norm graphs, we improve the constant in the upper
bound on $f(r,K_{2,d+1})$ for $d>1$ to one with the correct dependence on $d$,
and we confirm Conjecture 1.2 for $K_{t,(t-1)!+1}$.

###### Theorem 1.4

(a) For $t\geq 3$,

$\frac{1}{((t-1)!-t)^{1/(2t-1)}}r^{1/(2t-1)}-o(r^{1/(2t-1)})\leq
f(r,K_{t,(t-1)!+1})\leq 2r^{1/(2t-1)}+o(r^{1/(2t-1)}).$

(b) For $d\geq 12$,

$\frac{1}{d^{1/3}}r^{1/3}-o(r^{1/3})\leq
f(r,K_{2,d+1})\leq\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}r^{1/3}+o(r^{1/3}).$

It is important to remark that improvements for small $d$ are possible using
our proof technique. In particular, for $2\leq d\leq 5$

$f(r,K_{2,4})\leq f(r,K_{2,3})\lesssim 1.89r^{1/3}$ and $f(r,K_{2,6})\leq
f(r,K_{2,5})\lesssim 1.26r^{1/3}$.

Details for how to obtain these bounds can easily be read out of the proof of
Theorem 1.4 part (b). We have phrased the theorem without the cases
corresponding to smaller $d$ for simplicity and to emphasize the dependence on
$d$. Improvements for $7\leq d\leq 14$ are listed after the proof of Theorem
1.4 part (b).

Next, we turn our attention toward even cycles by confirming Conjecture 1.2
for $C_{6}$ and $C_{10}$.

###### Theorem 1.5

For the even cycles $C_{6}$ and $C_{10}$,

$f(r,C_{6})\leq 2r^{1/2}+o(r^{1/2})$ and $f(r,C_{10})\leq
2r^{2/3}+o(r^{2/3})$.

The graphs used to prove Theorem 1.5 were constructed by Wenger [41]. This
family of graphs is not $C_{2\ell}$-free when $\ell\neq 2,3,5$. One of the
more notable unsolved problems in extremal graph theory is to determine the
order of magnitude of $\textup{ex}(n,C_{2\ell})$ for $\ell\notin\\{2,3,5\\}$.
With the order of magnitude of $\textup{ex}(N,C_{2\ell})$ not known in these
cases, one cannot apply Theorem 1.1 directly. A version of Theorem 1.1 is
proved in [2] that relaxes the assumption $\textup{ex}(N,H)=\Theta(N^{\eta})$
to

$cN^{a}\leq\textup{ex}(N,H)\leq CN^{b}~{}~{}\mbox{for some $a<b$
with}~{}~{}b-a<\frac{(2-b)(b-1)}{5-b}.$ (2)

The densest constructions of $C_{2\ell}$-free graphs are due to Lazebnik,
Ustimenko, and Woldar [32] and they show that

$\textup{ex}(N,C_{2\ell})=\Omega(N^{1+\frac{2}{3\ell-3+\varepsilon}})$

where $\varepsilon=0$ if $k$ is odd and $\varepsilon=1$ if $k$ is even. In
this case, the exponent in the best known lower bound is too far from that of
the best known upper bound $\textup{ex}(N,C_{2\ell})=O(N^{1+\frac{1}{\ell}})$
to satisfy (2). Nevertheless, we are able to obtain upper bounds on
$f(r,C_{2\ell})$ using a different approach which gives an upper bound on
$f(r,H)$ whenever one has an $H$-free graph with certain pseudorandomness
properties quantified by the eigenvalues of the graph (see Theorem 3.4).
Ideally we would then apply this theorem to the Lazebnik-Ustimenko-Woldar
graphs. Unfortunately, with the exception of a few special cases, the
eigenvalues of these graphs are not well-understood. While not as dense, more
is known regarding the eigenvalues of the $C_{2\ell}$-free graphs constructed
by Lubotzky, Phillips, and Sarnak [34]. We discuss this more in Section 5,
including how proof of a conjecture of Ustimenko would improve Theorem 1.6.

###### Theorem 1.6

For $\ell\geq 2$, we have $f(r,C_{2\ell})\leq
Cr^{\frac{3\ell-2}{3\ell+2}}(\log r)^{\frac{3\ell}{3\ell+2}}$ for infinitely
many $r$.

The trivial lower bound (1) and the even cycle theorem
$\mathrm{ex}(N,C_{2\ell})=O\left(N^{1+1/k}\right)$ imply that
$f(r,C_{2\ell})=\Omega\left(r^{\frac{l-1}{l+1}}\right)$. We conclude that
Theorem 1.5 determines the order of magnitude for $f(r,C_{6})$ and
$f(r,C_{10})$, while Theorem 1.6 leaves a gap in the exponents for all
$\ell\not\in\\{2,3,5\\}$.

For $K,\ell\geq 2$, the _theta graph_ $\theta_{K,\ell}$ is the graph
consisting of $K\geq 2$ internally disjoint paths of length $\ell$ all having
the same two vertices as endpoints. Observe that $\theta_{2,\ell}=C_{2\ell}$.
The magnitude of $\textup{ex}(n,C_{8})$ is unknown, yet Verstraëte and
Williford [40] discovered an algebraic construction that gives the lower bound
in the asymptotic formula $\textup{ex}(n,\theta_{3,4})=\Theta(n^{5/4})$. Using
this we graph, we confirm Conjecture 1.2 for $\theta_{3,4}$.

###### Theorem 1.7

There are positive constants $c$ and $C$ such that for all $r$,

$cr^{3/4}<f(r,\theta_{3,4})<Cr^{3/4}.$

Next we move on to trees. For a tree $T$ with $t$ edges, Axenovich and Martin
[2] proved

$\frac{r-1}{2(t-1)}\leq f(r,T)\leq\frac{2(r-1)}{t-1}.$ (3)

In the special case that $T$ is a star with $t$ edges, they showed that
$\frac{r-1}{t-1}\leq f(r,T)\leq\frac{r}{t-1}$. The following result improves
(3) by a factor of $2+o(1)$.

###### Theorem 1.8

Suppose $t$ is a positive integer and $H$ is any connected graph with more
than $t$ vertices. Then

$f(r,H)\leq(1+o_{r}(1))\frac{r-1}{t-1}.$

Note in particular that for $T$ a tree on $t+1$ vertices, if the Erdős-Sós
conjecture is true then by (1) we have $f(r,T)\geq\frac{r-1}{t-1}$ and so
Theorem 1.8 gives an asymptotically sharp estimate for $f(r,T)$ in this case.
The proof uses the incidence structure of designs in a way that easily
generalizes to hypergraphs.

###### Theorem 1.9

Suppose that $t$ and $m\geq 2$ are integers and $\mathcal{H}$ is a family of
connected $m$-uniform hypergraphs each with more than $t$ vertices. Then

$f_{m}(r,\mathcal{H})\leq(1+o_{r}(1))\dfrac{\binom{r-1}{m-1}}{\binom{t-1}{m-1}}.$

An example showing that Theorem 1.9 is asymptotically best possible is Berge
paths. If $F$ is a graph and $H$ is a hypergraph, then $H$ is a _Berge-_ $F$
if there is a bijection $f:E(F)\to E(H)$ such that for every $e\in E(F)$ we
have $e\subseteq f(e)$. This notion was introduced in [20] and generalizes
Berge paths and Berge cycles. For integers $\ell>m+1>3$, Györi, Katona, and
Lemons [22] proved that
$\textup{ex}(n,\mathcal{H})\leq\frac{n}{\ell}\binom{\ell}{m}$ where
$\mathcal{H}$ is the family of $m$-uniform Berge paths of length $\ell$. If
$G$ is an $m$-uniform $(r,k)$-hypergraph with no Berge path of length $t$,
then $\binom{r}{m}\leq e(G)\leq\frac{rk}{t}\binom{t}{m}$. This can rewritten
as $\frac{\binom{r}{m}\frac{m}{r}}{\binom{t}{m}\frac{m}{t}}\leq k$ which then
simplifies to $\frac{\binom{r-1}{m-1}}{\binom{t-1}{m-1}}\leq k$.

In the case of graphs, we are unaware of a bipartite $H$, that is not a tree,
for which an asymptotic formula for $f(r,H)$ has been determined. However,
there is a family of 3-uniform hypergraphs $\mathcal{H}$ where the asymptotics
of $f_{m}(r,\mathcal{H})$ can be found. Write $\mathcal{C}_{\ell}^{(m)}$ for
the family of $m$-uniform Berge cycles of length $\ell$.

###### Theorem 1.10

If $\mathcal{C}_{2}^{(3)}$, $\mathcal{C}_{3}^{(3)}$, and
$\mathcal{C}_{4}^{(3)}$ are Berge cycles of length 2, 3, and 4 respectively,
then

$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\})=r+o(r)$

The lower bound follows first from the results of [33] who proved
$\textup{ex}_{3}(n,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\})\approx\frac{1}{6}n^{3/2}$.
It was shown in [16] that the same asymptotic formula holds even when
$\mathcal{C}_{3}^{(3)}$ is not in the forbidden family. Since,
$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{4}^{(3)}\\})\leq
f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\})$
we have

$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{4}^{(3)}\\})=r+o(r)$

as well.

In Section 2 we give some general upper and lower bounds. Section 3 concerns
bipartite graphs with a cycle, while Section 4 is on trees and hypergraphs.
Section 5 contains some concluding remarks and open problems.

##  2 General Bounds

For a set $\mathcal{H}$ of $m$-uniform hypergraphs, write
$\textup{ex}_{m}(n,\mathcal{H})$ for the Turán number of $\mathcal{H}$. This
is the maximum number of edges in an $m$-uniform $n$-vertex hypergraph that
does not contain any graph in $\mathcal{H}$ as a subgraph. When $\mathcal{H}$
consists of one graph, say $H$, we write $\textup{ex}_{m}(n,H)$ for the Turán
number of $H$. The first result of this section is a generalization of (1) to
hypergraphs.

###### Proposition 2.1

Let $H$ be an $m$-uniform hypergraph with $\textup{ex}_{m}(N,H)\leq CN^{e}$
for some positive constant $C$. If there is an $H$-free $m$-uniform
$(r,k)$-hypergraph, then

$\frac{(r-m)^{m}}{m!}\leq C(rk)^{e}.$

Proof. Suppose that there exists an $H$-free $m$-uniform $(r,k)$-hypergraph
$G$. The number of edges of $G$ is at least $\binom{r}{m}$ and is at most
$\textup{ex}_{m}(rk,H)$. Therefore, $\binom{r}{m}\leq
e(G)\leq\textup{ex}_{m}(rk,H)$ which implies $\frac{(r-m)^{m}}{m!}\leq
C(rk)^{e}$.

As $r$ tends to infinity, Proposition 2.1 gives the asymptotic lower bound

$f_{m}(r,H)\geq(1-o_{r}(1))\frac{r^{m/e-1}}{(Cm!)^{1/e}}.$ (4)

Next we prove a generalization to hypergraphs of the proposition

$f(r,H)\leq 2~{}\mbox{for all non-bipartite $H$ and $r\geq 2$}.$ (5)

Let $k\geq 2$ and $c_{1}+\cdots+c_{k}=m$ be a partition of $m$. Say that a
hypergraph $G$ has _Property $B_{\\{c_{1},\dots,c_{k}\\}}$_ if there is a
$k$-coloring of $V(G)$ such that each edge has exactly $c_{i}$ vertices of
color $i$. So for example, a graph having Property $B_{\\{1,1\\}}$ means that
the graph is bipartite.

###### Proposition 2.2

Let $k\geq 2$ and $c_{1}+\cdots+c_{k}$ be a partition of $m$. If $H$ is any
hypergraph that does not have Property $B_{\\{c_{1},\dots,c_{k}\\}}$, then

$f_{m}(r,H)\leq k$ for all $r\geq m$.

Proof. Let $V_{1},\dots,V_{r}$ be $r$ pairwise disjoint sets with $|V_{i}|=k$
for $1\leq i\leq r$. In each $V_{i}$, color the vertices with $1,2,\dots,k$
using each color exactly once. For each
$\\{i_{1},\dots,i_{m}\\}\in\binom{[r]}{m}$, let $e_{i_{1},\dots,i_{m}}$ be an
edge that contains one vertex from each $V_{i_{j}}$ and chosen so that there
are exactly $c_{i}$ vertices of color $i$. Let $G$ be the hypergraph with
vertex set $\cup_{j=1}^{r}V_{j}$ whose edges are the
$e_{i_{1},\dots,i_{m}}$’s. It is clear that $G$ is an $m$-uniform
$(r,k)$-hypergraph. Now let $H$ be any $m$-uniform hypergraph which does not
have Property $B_{\\{c_{1},\dots,c_{k}\\}}$. By definition, $G$ cannot contain
$H$ giving us an upper bound on $f_{m}(r,H)$.

Since an $m$-uniform hypergraph is $m$-partite if and only if it has Property
$B_{\\{1,\dots,1\\}}$, Proposition 2.2 gives the following generalization of
(5).

###### Corollary 2.3

Let $m\geq 2$ and let $H$ be an $m$-uniform hypergraph. If $H$ is not
$m$-partite, then $f_{m}(r,H)\leq m$ for all $r\geq m$.

##  3 Bipartite graphs with a cycle

###  3.1 Complete bipartite graphs

In this subsection we begin by proving the following result which will be used
to prove Theorem 1.4.

###### Theorem 3.1

Suppose that $q$ is an even power of an odd prime and that $d$ is a positive
integer for which $d|q-1$. For any $t\geq 2$ and positive integers $a\leq h$
for which $ha=\frac{q-1}{d}$,

$f(q^{t-1}a,K_{t,(t-1)!d^{t-1}+1})\leq a+h+O(h^{2/5}).$ (6)

Proof. Let $q$ be an even power of an odd prime and assume that $d$ is a
positive integer that divides $q-1$. Let $t\geq 2$ be an integer and
$N:\mathbb{F}_{q^{t-1}}\rightarrow\mathbb{F}_{q}$ be the $\mathbb{F}_{q}$-norm
on $\mathbb{F}_{q^{t-1}}$ defined by $N(x)=x^{1+q+q^{2}+\dots+q^{t-2}}$. Let
$K_{d}$ be the subgroup of $\mathbb{F}_{q}^{*}$ with $d$ elements. Let
$\theta$ be an element such that $\langle\theta\rangle=\mathbb{F}_{q}^{*}$ so
$K_{d}=\langle\theta^{(q-1)/d}\rangle$. Let $\mathcal{B}_{d}(q,t)$ be the
bipartite graph with parts
$\mathcal{P}=\mathbb{F}_{q^{t-1}}\times(\mathbb{F}_{q}^{*}/K_{d})$ and
$\mathcal{L}=\mathbb{F}_{q^{t-1}}\times(\mathbb{F}_{q}^{*}/K_{d})$ where
$(x,aK_{d})_{\mathcal{P}}$ in $\mathcal{P}$ is adjacent to
$(y,bK_{d})_{\mathcal{L}}$ in $\mathcal{L}$ if and only if

$N(x+y)\in abK_{d}.$

Here $\mathbb{F}_{q}^{*}/K_{d}$ is the quotient ring of $\mathbb{F}_{q}^{*}$
modulo $K_{d}$. This graph comes from the projective norm graph by taking
quotients, in a similar spirit to Füredi’s construction of $K_{2,t+1}$ free
graphs [18].

Let $a$ and $h$ be positive integers with $a\leq h$ for which
$ha=\frac{q-1}{d}$. Since $\mathbb{F}_{q}^{*}/K_{d}$ is a cyclic group with
$ha$ elements, we can choose a subgroup $H$ with $|H|=h$. Let $A$ be a set of
coset representatives of $H$ in $\mathbb{F}_{q}^{*}/K_{d}$. Thus, $|H|=h$,
$|A|=a$, and

$\mathbb{F}_{q}^{*}/K_{d}=\bigcup_{a\in A}aH.$ (7)

Partition $\mathcal{P}$ into the sets

$\mathcal{P}_{x,h_{1}}=\\{(x,a_{1}h_{1}K_{d})_{\mathcal{P}}:a_{1}K_{d}\in
A\\}~{}~{}\mbox{where}~{}~{}x\in\mathbb{F}_{q^{t-1}}~{}\mbox{and}~{}h_{1}K_{d}\in
H.$

Similarly, partition $\mathcal{L}$ into the sets

$\mathcal{L}_{y,a_{2}}=\\{(y,a_{2}h_{2}K_{d})_{\mathcal{L}}:h_{2}K_{d}\in
H\\}~{}~{}\mbox{where}~{}~{}y\in\mathbb{F}_{q^{t-1}}~{}\mbox{and}~{}a_{2}K_{d}\in
A.$

For convenience of notation we write $h_{1}$ instead of $h_{1}K_{d}$ in the
subscripts of $\mathcal{P}_{x,h_{1}}$ and likewise, $a_{2}$ for $a_{2}K_{d}$
in $\mathcal{L}_{y,a_{2}}$. Fix $x,y\in\mathbb{F}_{q^{t-1}}$ and
$h_{1}K_{d}\in H$, $a_{2}K_{d}\in A$. There is an edge between
$\mathcal{P}_{x,h_{1}}$ and $\mathcal{L}_{y,a_{2}}$ if and only if

$N(x+y)\in a_{1}h_{1}a_{2}h_{2}K_{d}$

for some $a_{1}K_{d}\in A$ and $h_{2}K_{d}\in H$.

First suppose $N(x+y)\neq 0$. Then $N(x+y)$ is some element of
$\mathbb{F}_{q}^{*}$, say $\alpha$. By (7) there is an $a\in A$ and $h\in H$
such that $\alpha K_{d}=ahK_{d}$. Choosing $a_{1}K_{d}=aa_{2}^{-1}K_{d}$ and
$h_{2}K_{d}=h_{1}^{-1}hK_{d}$ gives

$\alpha K_{d}=ahK_{d}=a_{1}a_{2}h_{1}h_{2}K_{d}=a_{1}h_{1}a_{2}h_{2}K_{d}.$

Therefore, $N(x+y)\in a_{1}h_{1}a_{2}h_{2}K_{d}$ and in this case, there is an
edge with one endpoint in $\mathcal{P}_{x,h_{1}}$ and the other in
$\mathcal{L}_{y,a_{2}}$.

Now suppose that $N(x+y)=0$ which holds if and only if $y=-x$. In this case,
$\mathcal{B}_{d}(q,t)$ does not have an edge between the parts
$\mathcal{P}_{x,h_{1}}$ and $\mathcal{L}_{y,a_{2}}$. For
$x\in\mathbb{F}_{q^{t-1}}$, let $\mathcal{D}_{x}$ be the subgraph induced by

$\left(\bigcup_{h_{1}K_{d}\in
H}\mathcal{P}_{x,h_{1}}\right)\cup\left(\bigcup_{a_{2}K_{d}\in
A}\mathcal{L}_{-x,a_{2}}\right).$

The sets in this union are pairwise disjoint and $\mathcal{D}_{x}$ is an
$R$-partite graph (inducing no edges) with $R=|H|+|A|$. We will add a small
number of new vertices and edges to $\mathcal{D}_{x}$. Add at most
$f(R,K_{t,(t-1)!d^{t-1}+1})$ vertices to each of the $R$ parts such that the
subgraph induced by these new vertices is $K_{t,(t-1)!d^{t-1}+1}$-free, and
there is an edge between any two of the $R$ parts. Write
$\mathcal{P}_{x,h_{1}}^{\prime}$ and $\mathcal{L}_{-x,a_{2}}^{\prime}$ for
these new sets. Observe that
$|\mathcal{P}_{x,h_{1}}^{\prime}|\leq|\mathcal{P}_{x,h_{1}}|+f(R,K_{t,(t-1)!d^{t-1}+1})$
and similarly for $\mathcal{L}_{-x,a_{2}}^{\prime}$.

Let
$\psi:\left\\{\mathcal{L}_{y,a}^{\prime}:y\in\mathbb{F}_{q^{t-1}},aK_{d}\in
A\right\\}\rightarrow\left\\{\mathcal{P}_{x,h}^{\prime}:x\in\mathbb{F}_{q^{t-1}},hK_{d}\in
H\right\\}$ be an arbitrary injection. Because $|A|\leq|H|$, such an injection
exists. For each $y$ and $a$, let

$V_{y,a}=\psi\left(\mathcal{L}_{y,a}^{\prime}\right)\cup\mathcal{L}_{y,a}^{\prime}.$

Let $G=G(q,t,d,H)$ be the graph whose vertex set is the union of the
$V_{y,a}$’s and all the edges among them. Then $G$ is a
$K_{t,(t-1)!d^{t-1}+1}$-free $(r,k)$-graph with

$r=q^{t-1}|A|=\frac{q^{t-1}(q-1)}{d|H|}$ and
$k\leq|A|+|H|+2f(|A|+|H|,K_{t,(t-1)!d^{t-1}+1})$.

We then have

$f(q^{t-1}|A|,K_{t,(t-1)!d^{t-1}+1})\leq|A|+|H|+2f(|A|+|H|,K_{t,(t-1)!d^{t-1}+1}).$
(8)

Using the results of [2],

$2f(R,K_{t,(t-1)!d^{t-1}+1})\leq
2CR^{\frac{1}{2t-1}}\log^{\frac{t}{2t-1}}R\leq C^{\prime}|H|^{2/5}$

which gives an upper bound on the last term in (8). Here we have used
$|A|\leq|H|$ and the inequality $\frac{1}{2t-1}\leq\frac{1}{3}<\frac{2}{5}$.
With this estimate, we have completed the proof since $a=|A|$ and $h=|H|$.

Proof of Theorem 1.4 part (a). Let $d=1$. The condition $d|q-1$ is satisfied
for any $q$. Taking $a=\sqrt{q}-1$ and $h=\sqrt{q}+1$ gives

$f(q^{t-1}(\sqrt{q}-1),K_{t,(t-1)!+1})\leq 2\sqrt{q}+O_{t}(q^{1/5})$

for all $t\geq 2$. As in [2], this upper bound and a density of primes
argument proves $f(r,K_{t,(t-1)!+1})\leq 2r^{1/(2t-1)}+o(r^{1/(2t-1)})$.

The lower bound follows from Proposition 2.1 and the best-known upper bound on
$\textup{ex}(N,K_{s,t})$ [19, 37].

Proof of Theorem 1.4 part (b). The upper bound will be proved by applying
Theorem 3.1 with $q=p^{2}$ where $p$ is a prime with the property that either

$p+1\equiv 0(\textup{mod}~{}D_{1})~{}~{}\mbox{and}~{}~{}p-1\equiv
0(\textup{mod}~{}D_{2}),$ (9)

or

$p-1\equiv 0(\textup{mod}~{}D_{1})~{}~{}\mbox{and}~{}~{}p+1\equiv
0(\textup{mod}~{}D_{2}),$ (10)

for some positive integers $D_{1}$ and $D_{2}$. If (9) holds and
$a:=\min\\{\frac{p+1}{D_{1}},\frac{p-1}{D_{2}}\\}$,
$h:=\max\\{\frac{p+1}{D_{1}},\frac{p-1}{D_{2}}\\}$, then by Theorem 3.1

$f(p^{2}a,K_{2,D_{1}D_{2}+1})\leq\left(\frac{1}{D_{1}}+\frac{1}{D_{2}}\right)p+O_{D_{1},D_{2}}(p^{2/5}).$

Because of the error term, we may also say that the same bound holds if (10)
is true instead of (9). We will want the prime $p$ to grow while $D_{1}$ and
$D_{2}$ are fixed. This leads to the following definition. Let $1\leq
D_{1}\leq D_{2}$ and consider the pair of integers $(D_{1},D_{2})$. This
ordered pair is _admissible_ if there are infinitely many primes $p$ such that
either (9) or (10) hold. Given an admissible pair, we may assume that
$a=\frac{p\pm 1}{D_{2}}\sim\frac{p}{D_{2}}$ and $h=\frac{p\mp
1}{D_{1}}\sim\frac{p}{D_{1}}$ as $p$ tends to infinity. If $\mathcal{S}$ is an
infinite set of primes for which (9) or (10) holds for $(D_{1},D_{2})$, then
we say $\mathcal{S}$ is a _supporting set_ for $(D_{1},D_{2})$.

The pairs $(1,1)$, $(1,2)$, $(2,2)$, $(2,3)$, and $(2,4)$ are all admissible
where the odd primes greater than 3 are a supporting set in all five cases.
Thus, for any prime $p>3$, we have $f(p^{2}(p-1),K_{2,2})\leq 2p+O(p^{2/5})$,
as well as

$f\left(p^{2}\cdot\frac{p-1}{2},K_{2,3}\right)\leq\left(\frac{1}{1}+\frac{1}{2}\right)p+O(p^{2/5})$,
$f\left(p^{2}\cdot\frac{p-1}{2},K_{2,5}\right)\leq\left(\frac{1}{2}+\frac{1}{2}\right)p+O(p^{2/5})$,

$f\left(p^{2}\cdot\frac{p-1}{3},K_{2,7}\right)\leq\left(\frac{1}{2}+\frac{1}{3}\right)p+O(p^{2/5})$,
$f\left(p^{2}\cdot\frac{p-1}{4},K_{2,9}\right)\leq\left(\frac{1}{2}+\frac{1}{4}\right)p+O(p^{2/5})$.

Notice that the case of $K_{2,4}$ is missing even though the pair $(1,3)$ is
admissible. The reason is that after our density of primes argument, we get a
better result using monotonicty $f(r,K_{2,4})\leq f(r,K_{2,3})$ and our upper
bound for $f(r,K_{2,3})$, as opposed to the bound obtained from
$f\left(p^{2}\cdot\frac{p-1}{3},K_{2,4}\right)\leq\left(\frac{1}{1}+\frac{1}{3}\right)p+O(p^{2/5})$.
A similar statement applies to $K_{2,6}$ where instead of using the admissible
pair $(1,5)$, it is better to use monotonicity and the bound
$f\left(p^{2}\cdot\frac{p-1}{2},K_{2,5}\right)\leq\left(\frac{1}{2}+\frac{1}{2}\right)p+O(p^{2/5})$.
Roughly speaking, given $d$, we look for the admissible pair $(D_{1},D_{2})$
such that

$f(r,K_{2,d+1})\leq f(r,K_{2,d})\leq\cdots\leq
f(r,K_{2,D_{1}D_{2}+1})\leq\left(\frac{1}{D_{1}}+\frac{1}{D_{2}}\right)D_{2}^{1/3}r^{1/3}+o(r^{1/3})$

gives the best result. In some instances, such as when $d=2^{2}$ (the
$K_{2,5}$ case) or $d=2\cdot 3$ (the $K_{2,7}$ case), there will be no
applications of monotonicty.

Keeping in mind the larger goal of determining the dependence on $d$, let us
now assume that $d\geq 12$ as it will simplify certain estimates. The ideas
below, together with the discussion from the previous paragraph, is enough so
that any small cases stated in this paper can be checked.

Let $D$ be the unique positive integer for which $D(D+1)<d\leq(D+1)(D+2)$.
First observe that

$(D+1/2)^{2}=D(D+1)+\frac{1}{4}<d\leq(D+1)(D+2)<(D+3/2)^{2}$

where the first inequality holds because $D(D+1)<d$ and $d,D$ are integers.
Thus,

$\sqrt{d}-\frac{3}{2}<D<\sqrt{d}-\frac{1}{2}.$ (11)

Next, since $D$ and $D+1$ are relatively prime, the system $x+1\equiv
0(\textup{mod}~{}D)$ and $x-1\equiv 0(\textup{mod}~{}D+1)$ has a unique
solution, say $x_{0}(\textup{mod}~{}D(D+1))$. Since $x_{0}\equiv
D-1(\textup{mod}~{}D)$ and $x_{0}\equiv 1(\textup{mod}~{}D+1)$, the least
residue $x_{0}$ is relatively prime with both $D$ and $D+1$. By Dirichlet’s
Theorem on Arithmetic Progressions, there are infinitely many primes $p$ with
$p\equiv x_{0}\,(\textup{mod}~{}D(D+1)$). Each of these primes satisfies
$p+1\equiv 0\,(\textup{mod}~{}D)$ and $p-1\equiv 0\,(\textup{mod}~{}D+1)$.
Therefore, $(D,D+1)$ is admissible and we may let $\mathcal{S}$ be a maximal
supporting set. For any $p\in\mathcal{S}$,

$f\left(p^{2}\cdot\frac{p-1}{D+1},K_{2,D(D+1)+1}\right)\leq\left(\dfrac{1}{D}+\dfrac{1}{D+1}\right)p+O(p^{2/5})=\frac{2D+1}{D(D+1)}p+O(p^{2/5}).$

If $R_{p}:=\dfrac{p^{2}(p-1)}{D+1}$, then using monotonicty and (11),

$\displaystyle f(R_{p},K_{2,d+1})\leq f(R_{p},K_{2,D(D+1)+1})$
$\displaystyle\leq\frac{2D+1}{D(D+1)}((D+1)R_{p})^{1/3}+O(R_{p}^{2/15})$
$\displaystyle=\frac{2D+1}{D(D+1)^{2/3}}R_{p}^{1/3}+O(R_{p}^{2/15})$
$\displaystyle<\frac{2D+1}{D^{5/3}}R_{p}^{1/3}+O(R_{p}^{2/15})$
$\displaystyle<\frac{2\sqrt{d}}{(\sqrt{d}-3/2)^{5/3}}R_{p}^{1/3}+O(R_{p}^{2/15})$
$\displaystyle=\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}R_{p}^{1/3}+O(R_{p}^{2/15}).$

The last step will be to use The Prime Number Theorem in Arithmetic
Progressions to go from
$f(R_{p},K_{2,d+1})<\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}R_{p}^{1/3}+O(R_{p}^{2/15})$
for $p\in\mathcal{S}$ to

$f(r,K_{2,d+1})<\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}r^{1/3}+o(r^{1/3}).$

For $x>0$, let $\pi_{D(D+1),x_{0}}(x)$ be the number of primes $p$ such that
$p\equiv x_{0}(\textup{mod}~{}D(D+1))$ and $p\leq x$. Let
$\textup{Li}(x)=\int_{2}^{x}\frac{dt}{\log t}$ and $\phi$ denote the Euler phi
function. By Theorem 1.3 in [4], there are positive constants $x_{D}$ and
$c_{D}$ depending only on $D$ such that

$\left|\pi_{D(D+1),x_{0}}(x)-\dfrac{\textup{Li}(x)}{\phi(D(D+1))}\right|<\frac{c_{D}x}{(\log
x)^{2}}$

for all $x>x_{D}$.

Let $0<\epsilon<1$. Let $r$ be a positive integer that we will taken
sufficiently large in terms of $\epsilon$ and $D$. Define
$f_{r,D}(z)=z^{3}-z^{2}-r(D+1)$. The function $f_{r,D}$ is strictly increasing
on $(1,\infty)$, continuous, and has one real root
$x_{1}=(1+o_{r}(1))(r(D+1))^{1/3}$ which tends to infinity with $r$. Let $r$
be any integer chosen large enough so that $x_{D}<x_{1}<2(r(D+1))^{1/3}$ and
$\frac{(\log x_{1})^{2}}{\log(\epsilon x_{1})}>\frac{3c_{D}D^{2}}{\epsilon}$.
Then, using the PNT and this last inequality,

$\displaystyle\pi_{D(D+1),x_{0}}((1+\epsilon)x_{1})-\pi_{D(D+1),x_{0}}(x_{1})$
$\displaystyle\geq$
$\displaystyle\dfrac{1}{\phi(D(D+1))}\left(\int_{x_{1}}^{(1+\epsilon)x_{1}}\frac{dt}{\log
t}\right)-\frac{3c_{D}x_{1}}{(\log(x_{1}))^{2}}$ $\displaystyle>$
$\displaystyle\frac{\epsilon x_{1}}{D^{2}\log(\epsilon
x_{1})}-\frac{3c_{D}x_{1}}{(\log x_{1})^{2}}>0.$

Let $p$ be a prime with $x_{1}\leq p\leq(1+\epsilon)x_{1}$ and $p\equiv
x_{0}(\textup{mod}~{}D(D+1))$. Write $R_{p}=\frac{p^{2}(p-1)}{D+1}$ as before.
Since $x_{1}$ is a root of $f_{r,D}(z)$, we have $0=f_{r,D}(x_{1})\leq
f_{r,D}(p)\leq f_{r,D}(x_{1}+\epsilon x_{1})$ which implies

$0\leq
p^{3}-p^{2}-r(D+1)\leq(3\epsilon+3\epsilon^{2}+\epsilon^{3})x_{1}^{3}-(2\epsilon+\epsilon^{2})x_{1}^{2}.$

Thus,

$r\leq\frac{p^{2}(p-1)}{D+1}\leq
r+\frac{(3\epsilon+3\epsilon^{2}+\epsilon^{3})x_{1}^{3}-(2\epsilon+\epsilon^{2})x_{1}^{2}}{D+1}<r+\frac{7\epsilon
x_{1}^{3}}{D+1}<r(1+56\epsilon)$

where we have used $x_{1}<2(r(D+1))^{1/3}$ for the last inequality. We now
have that $p$ is a prime in $\mathcal{S}$ with $r\leq R_{p}<r(1+56\epsilon)$.
Hence,

$\displaystyle f(r,K_{2,d+1})$ $\displaystyle\leq$ $\displaystyle
f(R_{p},K_{2,d+1})<\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}R_{p}^{1/3}+O(R_{p}^{2/15})$
$\displaystyle<$
$\displaystyle\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}r^{1/3}(1+56\epsilon)^{1/3}+O(r^{2/15}).$

As $\epsilon$ can be made arbitrarily small by taking $r$ large, we have

$f(r,K_{2,d+1})<\frac{2}{d^{1/3}}\cdot\frac{1}{(1-1.5d^{-1/2})^{5/3}}r^{1/3}+o(r^{1/3}).$

Remark: Theorem 3.1 applies for all $t$ once we have $d|q-1$. Thus, the same
argument used to prove Theorem 1.4 (b) shows that for all $d\geq 1$, $t\geq
2$, and large enough $r$,

$f(r,K_{t,(t-1)!d^{t-1}+1})=O_{d}(r^{1/(2t-1)}).$

This upper bound is the correct order of magnitude by (4).

###  3.2 Cycles

Let $q$ be a power of a prime, $M\geq 1$ be an integer,
$\mathcal{P}=\\{(p_{1},p_{2},\dots,p_{M+1})_{\mathcal{P}}:p_{i}\in\mathbb{F}_{q}\\}$,
and
$\mathcal{L}=\\{(\ell_{1},\ell_{2},\dots,\ell_{M+1})_{\mathcal{L}}:\ell_{i}\in\mathbb{F}_{q}\\}$.
Let $W_{M}(q)$ be the bipartite graph with parts $\mathcal{P}$ and
$\mathcal{L}$ where $(p_{1},p_{2},\dots,p_{M+1})_{\mathcal{P}}$ is adjacent to
$(\ell_{1},\ell_{2},\dots,\ell_{M+1})_{\mathcal{L}}$ if and only if
$\ell_{j+1}+p_{j+1}=l_{j}p_{1}$ for $1\leq j\leq M$. The graph $W_{M}(q)$ has
$2q^{M+1}$ vertices and is $q$-regular. For $M\in\\{1,2,4\\}$, $W_{M}(q)$ is
$C_{2M+2}$-free. These graphs were constructed by Wenger [41] and have been
studied extensively.

Proof of Theorem 1.5. Let $M=2$ and consider the bipartite graph $W_{2}(q)$
which is $C_{6}$-free. Partition $\mathcal{P}$ and $\mathcal{L}$ into $q^{2}$
sets by letting

$\mathcal{P}_{p_{1},p_{3}}=\\{(p_{1},p_{2},p_{3})_{\mathcal{P}}:p_{2}\in\mathbb{F}_{q}\\},~{}~{}p_{1},p_{3}\in\mathbb{F}_{q},$

and

$\mathcal{L}_{\ell_{1},\ell_{2}}=\\{(\ell_{1},\ell_{2},\ell_{3})_{\mathcal{L}}:\ell_{3}\in\mathbb{F}_{q}\\}~{}~{}\ell_{1},\ell_{2}\in\mathbb{F}_{q}.$

Fix $p_{1},p_{3},\ell_{1},\ell_{2}\in\mathbb{F}_{q}$. There is exactly one
edge between $\mathcal{P}_{p_{1},p_{3}}$ and $\mathcal{L}_{\ell_{1},\ell_{2}}$
because the two equations $\ell_{2}+p_{2}=\ell_{1}p_{1}$ and
$\ell_{3}+p_{3}=\ell_{2}p_{1}$ uniquely determine $p_{2}$ and $\ell_{3}$.
Arbitrarily pair up the $\mathcal{P}_{p_{1},p_{3}}$’s with the
$\mathcal{L}_{\ell_{1},\ell_{2}}$’s in a 1-to-1 fashion giving $q^{2}$ parts,
each containing $2q$ vertices. This partition shows that $W_{2}(q)$ is a
$(q^{2},2q)$-graph. Using a density of primes argument as in the proof of
Theorem 1.4 gives $f(r,C_{6})\leq 2r^{1/2}+o(r^{1/2})$.

Next we prove the upper bound on $f(r,C_{10})$. Let $M=4$ and consider
$W_{4}(q)$. Partition $\mathcal{P}$ and $\mathcal{L}$ into $q^{3}$ sets by
letting

$\mathcal{P}_{p_{1},p_{3},p_{5}}=\\{(p_{1},p_{2},p_{3},p_{4},p_{5})_{\mathcal{P}}:p_{2},p_{4}\in\mathbb{F}_{q}\\},~{}~{}p_{1},p_{3},p_{5}\in\mathbb{F}_{q},$

and

$\mathcal{L}_{\ell_{1},\ell_{2},\ell_{4}}=\\{(\ell_{1},\ell_{2},\ell_{3},\ell_{4},\ell_{5})_{\mathcal{L}}:\ell_{3},\ell_{5}\in\mathbb{F}_{q}\\},~{}~{}\ell_{1},\ell_{2},\ell_{4}\in\mathbb{F}_{q}.$

Fix $p_{1},p_{3},p_{5},\ell_{1},\ell_{2},\ell_{4}$. The system of equations

$\displaystyle\ell_{2}+p_{2}$ $\displaystyle=$ $\displaystyle\ell_{1}p_{1}$
$\displaystyle\ell_{3}+p_{3}$ $\displaystyle=$ $\displaystyle\ell_{2}p_{1}$
$\displaystyle\ell_{4}+p_{4}$ $\displaystyle=$ $\displaystyle\ell_{3}p_{1}$
$\displaystyle\ell_{5}+p_{5}$ $\displaystyle=$ $\displaystyle\ell_{4}p_{1}.$

has a unique solution for $p_{2}$, $\ell_{3}$, $p_{4}$, and $\ell_{5}$. This
implies that there is exactly one edge between
$\mathcal{P}_{p_{1},p_{3},p_{5}}$ and
$\mathcal{L}_{\ell_{1},\ell_{2},\ell_{4}}$. The last part of the argument is
almost the same as the $C_{6}$ case and leads to the upper bound
$f(r,C_{10})\leq 2r^{2/3}+o(r^{2/3})$.

Proof of Theorem 1.7. Let $q$ be an even power of an odd prime and $\mu$ be a
root of an irreducible quadratic over $\mathbb{F}_{\sqrt{q}}$. An element
$x_{j}\in\mathbb{F}_{q}$ can be written uniquely as $x_{j}=x_{1,j}+x_{2,j}\mu$
where and $x_{1,j},x_{2,j}\in\mathbb{F}_{\sqrt{q}}$. Let $G$ be the bipartite
graph with parts

$\mathcal{P}=\\{(v_{1},v_{2},v_{3},v_{4})_{\mathcal{P}}:v_{j}\in\mathbb{F}_{q}\\}$
and
$\mathcal{L}=\\{(w_{1},w_{2},w_{3},w_{4})_{\mathcal{L}}:w_{j}\in\mathbb{F}_{q}\\}$.

Vertices $(v_{1},v_{2},v_{3},v_{4})_{\mathcal{P}}$ and
$(w_{1},w_{2},w_{3},w_{4})_{\mathcal{L}}$ are adjacent if and only if

$\displaystyle v_{2}+w_{2}$ $\displaystyle=$ $\displaystyle v_{1}w_{1}$
$\displaystyle v_{4}+w_{3}$ $\displaystyle=$ $\displaystyle v_{1}^{2}w_{1}$
$\displaystyle v_{3}+w_{4}$ $\displaystyle=$ $\displaystyle v_{1}w_{1}^{2}.$

This graph is $\theta_{3,4}$-free [33]. Write each coordinate $v_{j}$ as
$v_{j}=v_{1,j}+v_{2,j}\mu$ and $w_{j}=w_{1,j}+w_{2,j}\mu$ where
$v_{1,j},v_{2,j},w_{1,j},w_{2,j}\in\mathbb{F}_{\sqrt{q}}$. Partition
$\mathcal{P}$ into the $q^{5/2}$ sets

$\mathcal{P}_{v_{1},v_{3,2},v_{4}}=\\{(v_{1},v_{2,1}+v_{2,2}\mu,v_{3,1}+v_{3,2}\mu,v_{4,1}+v_{4,2}\mu)_{\mathcal{P}}:v_{2,1},v_{2,2},v_{3,1}\in\mathbb{F}_{\sqrt{q}}\\}$

where $v_{1},v_{4}\in\mathbb{F}_{q}$, and $v_{3,2}\in\mathbb{F}_{\sqrt{q}}$.
Each of these parts contains $q^{3/2}$ vertices. Likewise, partition
$\mathcal{L}$ into the sets

$\mathcal{L}_{w_{1},w_{2},w_{4,1}}=\\{(w_{1},w_{2},w_{3,1}+w_{3,2}\mu,w_{4,1}+w_{4,2}\mu)_{\mathcal{L}}:w_{3,1},w_{3,2},w_{4,2}\in\mathbb{F}_{\sqrt{q}}\\}$

where $w_{1},w_{2}\in\mathbb{F}_{q}$ and $w_{4,1}\in\mathbb{F}_{\sqrt{q}}$.

Fix two parts $\mathcal{P}_{v_{1},v_{3,2},v_{4}}$ and
$\mathcal{L}_{w_{1},w_{2},w_{4,1}}$. There will be an edge between these two
parts provided that there exists
$v_{2,1},v_{2,2},v_{3,1},w_{3,1},w_{3,2},w_{4,2}\in\mathbb{F}_{\sqrt{q}}$ such
that

$\displaystyle v_{2,1}+v_{2,2}\mu+w_{2,1}+w_{2,2}\mu$ $\displaystyle=$
$\displaystyle v_{1}w_{1}$ $\displaystyle
v_{4,1}+v_{4,2}\mu+w_{3,1}+w_{3,2}\mu$ $\displaystyle=$ $\displaystyle
v_{1}^{2}w_{1}$ $\displaystyle v_{3,1}+v_{3,2}\mu+w_{4,1}+w_{4,2}\mu$
$\displaystyle=$ $\displaystyle v_{1}w_{1}^{2}.$

The first two equations are solved by choosing $v_{2,1}+v_{2,2}\mu$ to equal
$v_{1}w_{1}-w_{2,1}-w_{2,2}\mu$, and $w_{3,1}+w_{3,2}\mu$ to equal
$v_{1}^{2}w_{1}-v_{4,1}-v_{4,2}\mu$. The last equation can be solved by
choosing $v_{3,1}$ and $w_{4,2}$ so that
$v_{3,1}+w_{4,2}\mu=v_{1}w_{1}^{2}-v_{3,2}\mu-w_{4,1}$. This gives a unique
solution to this system of equations and so we have an edge between these
parts. Take an arbitrary pairing of the $\mathcal{P}_{v_{1},v_{3,2},v_{4}}$’s
and $\mathcal{L}_{w_{1},w_{2},w_{4,1}}$’s to obtain a $(p^{5},2p^{3})$-graph.
Hence, $f(q^{5/2},\theta_{3,4})\leq 2q^{3/2}$ for $q$ an even power of an odd
prime. By a density of primes argument,

$f(r,\theta_{3,4})\leq 2r^{3/5}+o(r^{3/5}).$

The trivial bound together with $\textup{ex}(N,\theta_{3,4})=O(N^{5/4})$
proved by Faudree and Simonovits [17] implies that
$f(r,\theta_{3,4})=\Omega(r^{3/5})$.

###  3.3 Longer even cycles

In this section we prove Theorem 1.6. We first prove a general result that
allows one to find an upper bound on $f(r,H)$ provided a sufficiently
pseudorandom $H$-free graph exists.

Let $G$ be a graph on $n$ vertices with adjacency matrix $A$. Then $A$ has $n$
real eigenvalues $\rho_{1}\geq\cdots\geq\rho_{n}$. We will make use of the
expander-mixing lemma which relates the second largest eigenvalue to the
distribution of the edges. This result can be traced back to at least as early
as a theorem about designs in Haemers’ Ph.D Thesis [23]. For the non-bipartite
and bipartite versions stated below in graph-theoretic terms, we refer to [1]
and [8] respectively. If $U,W\subseteq V(G)$ then we define
$e(U,W)=|\\{(u,w):u\in U,w\in W,u\sim w\\}|$.

######  Theorem 3.2 (Expander-Mixing Lemma)

Suppose that $G$ is a $d$-regular graph with
$\rho=\max\\{\rho_{2},-\rho_{n}\\}$. Then for any $U,W\subseteq V(G)$, we have

$\left|e(U,W)-\frac{d}{n}|U||W|\right|\leq\rho\sqrt{|U||W|}.$

######  Theorem 3.3 (Bipartite Expander-Mixing Lemma)

If $G$ is a $d$-regular bipartite graph with parts $X$ and $Y$ where
$\rho_{2}=\rho$, then for any $U\subseteq X,W\subseteq Y$, we have

$\left|e(U,W)-\frac{2d}{n}|U||W|\right|\leq\rho\sqrt{|U||W|}.$

###### Theorem 3.4

Let $H$ be a bipartite graph with no vertices of degree 1. Suppose there
exists an $H$-free $d$-regular graph $G$ on $n$ vertices, where $d=n^{a}$ and
$a<\frac{1}{3}$. Let $\rho=\max\\{\rho_{2},-\rho_{n}\\}$ if $G$ is not
bipartite and $\rho=\rho_{2}$ if $G$ is bipartite and assume that
$\rho=O(d^{\frac{1}{2}})$. Then there exists an absolute constant $C$ such
that if $n$ is large enough, we have $f(m,H)\leq Cm^{\frac{2}{1+a}-1}(\log
m)^{\frac{1}{1+a}}$, where $m=\frac{1}{4}n^{\frac{1+a}{2}}/(\log
n)^{\frac{1}{2}}.$

Proof. We fix some notation. Let $V=V(G)$, and if $G$ is bipartite let $(X,Y)$
be a balanced bipartition. For convenience let $A,B$ both denote $V$ if $G$ is
not bipartite, and let $A=X$, $B=Y$ if $G$ is bipartite. For $U,W\subseteq V$,
let $N(U)$ be the set of vertices not in $U$ which are adjacent to a vertex in
$U$. Unless otherwise indicated, all vertices and adjacency relations are
within the graph $G$. We show that the following algorithm successfully
terminates and outputs an $H$-free $(m,k)$-graph with parts
$V_{1},\ldots,V_{m}$.

  1. 1.

Initialize $V_{1}=\cdots=V_{m}=\emptyset$.

  2. 2.

For each $i$, add $n^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$ vertices in $G$ to
$V_{i}$ such that each vertex added is not already contained in any other
$V_{j}$ and is also at distance at least $3$ from every other vertex in
$V_{i}$. If $G$ is bipartite then all added vertices should also belong to
$X$.

  3. 3.

For $1\leq i\leq m$, define $\mathcal{S}_{i}=\\{j:j\neq i,e(V_{i},V_{j})=0\\}$
and $s_{i}=|\mathcal{S}_{i}|$. If for every $i$ we have
$s_{i}<n^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$, proceed to step 4. Otherwise,
for each $1\leq i\leq m$, choose the vertex in $B-(N(V_{i})\cup
N(N(V_{i})))-(V_{1}\cup\cdots\cup V_{m})$ which is adjacent to the maximum
number of vertices in $\bigcup_{j\in\mathcal{S}_{i}}V_{j}$, and add it to
$V_{i}$. Return to the beginning of step 3.

  4. 4.

For each $i$, for each $j\in\mathcal{S}_{i}$, create a new vertex in $V_{i}$
and make it adjacent to some vertex in $V_{j}$ which was added to $V_{j}$ in
one of the previous steps.

Is it possible to perform step 2, because at any point during step 2 when we
want to add a vertex to $V_{i}$, we have

$\displaystyle|A-(N(V_{i})\cup N(N(V_{i})))-(V_{1}\cup\cdots\cup V_{m})|$
$\displaystyle\geq\frac{n}{2}-d^{2}|V_{i}|-m\cdot|V_{1}|$
$\displaystyle\geq\frac{n}{2}-n^{2a+\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}-\frac{1}{4}n^{\frac{1+a}{2}+\frac{1-a}{2}}.$

The choice of $a$ ensures that both exponents in the right-hand side are at
most 1 and the right-hand side is positive for $n$ sufficiently large.

To show it is possible to perform step 3, we track how the number $s_{i}$
changes each time a vertex is added. Let $s_{i}(t)$ be the value of $s_{i}$
after $t$ iterations of step 3 have been performed. Now during any of the
first $2an^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$ iterations of step 3 we have

$\displaystyle|B-(N(V_{i})\cup N(N(V_{i})))-(V_{1}\cup\cdots\cup$
$\displaystyle V_{m})|\geq\frac{n}{2}-n^{2a}(n^{\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}+2an^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}})$
$\displaystyle-\frac{1}{4}\frac{n^{\frac{1+a}{2}}}{(\log
n)^{\frac{1}{2}}}(n^{\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}+2an^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}).$

The choice of $a$ ensures that the right-hand side is $\Theta(n)$. Set
$W=B-(N(V_{i})\cup N(N(V_{i})))-(V_{1}\cup\cdots\cup V_{m})$. To apply the
expander mixing lemma we would like

$\frac{d\left|\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right||W|}{n}\gg\rho\sqrt{\left|\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right||W|},$

in other words
$\Theta(n)=|W|\gg\frac{\rho^{2}n^{2}}{d^{2}\left|\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right|}$.
Noting that $\rho=\Theta(d^{\frac{1}{2}})$ and
$\left|\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right|\geq
s_{i}(t)n^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}\geq n^{1-a}(\log n)$ we see
that this condition is met. Therefore,

$e\left(W,\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right)\geq\frac{1}{2}\frac{ds_{i}(t)n^{\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}|W|}{n}=\frac{1}{2n^{\frac{1-a}{2}}}|W|s_{i}(t)(\log
n)^{\frac{1}{2}}.$

Thus, there exists a vertex in $W$ with at least
$\frac{1}{2n^{\frac{1-a}{2}}}s_{i}(t)(\log n)^{\frac{1}{2}}$ neighbors in
$\left|\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right|$, and so in iteration $t$
of step 3, a vertex is added to $V_{i}$ which has at least
$\frac{1}{2n^{\frac{1-a}{2}}}s_{i}(t)(\log n)^{\frac{1}{2}}$ neighbors in
$\left|\bigcup_{j\in\mathcal{S}_{i}(t)}V_{j}\right|$. Now since each of the
sets $V_{j}$ has all of its vertices at distance at least 3 from each other,
each neighbor of the vertex added belongs to a different set $V_{j}$ (where
$j\in\mathcal{S}_{i}(t)$). It follows that

$s_{i}(t+1)\leq s_{i}(t)-\frac{1}{2n^{\frac{1-a}{2}}}(\log
n)^{\frac{1}{2}}s_{i}(t).$

Using $s_{i}(0)\leq m\leq n^{\frac{1+a}{2}}/(\log n)^{\frac{1}{2}}$, we then
have that as long as $|W|$ is large enough as above,

$s_{i}(t)\leq\frac{n^{\frac{1+a}{2}}}{(\log
n)^{\frac{1}{2}}}\left(1-\frac{1}{2n^{\frac{1-a}{2}}}(\log
n)^{\frac{1}{2}}\right)^{t}.$

Using the estimate $\log(1-x)\leq-x$, we therefore have

$\log s_{i}(t)\leq\left(\frac{1+a}{2}\log n-\frac{1}{2}\log\log
n\right)-t\frac{(\log n)^{\frac{1}{2}}}{2n^{\frac{1-a}{2}}}.$

Step 3 terminates when for all $i$, $s_{i}(t)\leq n^{\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}$. Solving for $t$ in the inequality

$\left(\frac{1+a}{2}\log n-\frac{1}{2}\log\log n\right)-t\frac{(\log
n)^{\frac{1}{2}}}{2n^{\frac{1-a}{2}}}\leq\log\left(n^{\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}\right)$

we see that this is guaranteed to happen by iteration $t=2a(\log
n)^{\frac{1}{2}}n^{\frac{1-a}{2}}.$

In step 4, none of the vertices created creates a copy of $H$, since $H$ has
no vertex of degree 1.

We calculate the maximum size of a part in the resulting $(m,k)$-graph. For
each $V_{i}$, $n^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$ vertices were added in
step 2, at most $2an^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$ were added in step
3, and at most $n^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$ were added in step 4.
Therefore we have $f(m,H)\leq 4n^{\frac{1-a}{2}}(\log n)^{\frac{1}{2}}$.
Choose $C$ such that
$C\left(\frac{1}{4}\right)^{\frac{2}{1+a}-1}\left(\frac{1}{2}\right)^{\frac{1}{1+a}}\geq
4$. Using the fact that

$\log m=\frac{1+a}{2}\log n-\log 4-\frac{1}{2}\log\log n\geq\frac{1}{2}\log n$

for $n$ large enough, we find that

$Cm^{\frac{2}{1+a}-1}(\log m)^{\frac{1}{1+a}}\geq 4n^{\frac{1-a}{2}}(\log
n)^{\frac{1}{2}}\geq f(m,H).$

We remark that if $G$ is optimal in the sense that
$\textup{ex}(N,H)=\Theta(N^{1+a})$ then this result matches the upper bound in
Theorem 1.1. An advantage of this theorem is that it applies (if one has a
suitably pseudorandom graph) even in cases where the known upper and lower
bounds on the Turán number are too far apart to apply Theorem 1.1, illustrated
as follows with even cycles.

Proof of Theorem 1.6. We use the bipartite Lubotzky-Phillips-Sarnak graphs
[34]. If $p,q$ are primes such that $p$ is a nonresidue$\pmod{q}$, then
$X^{p,q}$ is a $(p+1)-$regular graph on $q(q^{2}-1)$ vertices with girth at
least $4\log_{p}q-\log_{p}4$ and its second eigenvalue is $\rho_{2}\leq
2\sqrt{p}$. To satisfy the assumptions of Theorem 3.4 we require a sequence of
such pairs $(p,q)$ where $q>p^{\frac{\ell}{2}}$ for the girth and
$q\in(p^{\frac{\ell}{2}},Cp^{\frac{\ell}{2}})$ for some constant $C>1$ to
ensure $d=\Theta(n^{\frac{2}{3\ell}})$. A construction of a similar sequence
occurs in Section 4 of [25] and we refer to that paper for the details (the
only difference is that in our case $p$ must be a nonresidue rather than a
residue).

##  4 Trees and Hypergraphs

###  4.1 Trees

Let $H$ be a graph and $k\geq 2$ be an integer. The _multicolor Ramsey number
for $H$_, denoted $R(H;k)$, is the smallest $n$ such that in every $k$
coloring of $E(K_{n})$, there is a copy of $H$ whose edges are all the same
color. It is proved in [2] that there is an $H$-free $(r,k)$-graph where
$r=R(H;k)-1$. Thus, a lower bound on $R(H;k)$ implies an upper bound on
$f(r,H)$. For a tree $T$ with $t$ edges, Axenovich and Martin use the bound
$R(T;k)>(t-1)\lfloor(k+1)/2\rfloor$ to prove that

$\frac{n-1}{2(t-1)}\leq f(n,T)\leq\frac{2(n-1)}{t-1}.$

They noted that for large $k$ congruent to $1$ modulo $n$, there is a better
lower bound $R(T;k)>(n-1)k+1$ due to Erdős and Graham [15]. Erdős and Graham
defined an edge-coloring of the complete graph using resolvable balanced
incomplete block designs. Recall that an $m$-$(r,t,\lambda)$ design is an
incidence structure consisting of $r$ points in which every block contains $t$
points, and any set of $m$ points is contained in exactly $\lambda$ blocks. A
BIBD is a design with $t=2$ and applying this Ramsey bound to the argument in
[2] gives

$f(n,T)\leq\frac{n}{t-1}$

for infinitely many $n$. Here we present another construction using designs
which gives asymptotically equivalent upper bounds on $f(n,T)$ and also
generalizes to hypergraphs.

###### Proposition 4.1

Let $\mathcal{H}$ be a set of connected hypergraphs each with more than $t$
vertices. If there exists an $m$-$(r,t,1)$ design then
$f_{m}(r,\mathcal{H})\leq\binom{r-1}{m-1}/\binom{t-1}{m-1}$.

Proof. Suppose there is a $m$-$(r,t,1)$-design and let $p_{1},\dots,p_{r}$ be
the points and $B_{1}\dots,B_{b}$ be the blocks where $b$ is the number of
blocks in the design. Let $G$ be the $m$-uniform hypergraph consisting of $b$
disjoint copies of $K_{t}^{(m)}$, the $m$-uniform complete hypergraph on $t$
vertices. Observe that $G$ is $\mathcal{H}$-free since each $H\in\mathcal{H}$
is connected with more than $t$ vertices, and no component of $G$ has more
than $t$ vertices. We now prove that $G$ is an $(r,k)$-hypergraph where $k$ is
the replication number $k=\binom{r-1}{m-1}/\binom{t-1}{m-1}$ of the design.

Label the vertices in the $j$-th copy of $K_{t}^{(m)}$ with
$(p_{i_{1}},j),\dots,(p_{i_{t}},j)$ where $p_{i_{1}},\dots,p_{i_{t}}$ are the
points contained in the block $B_{j}$. Consider the partition
$V_{1},V_{2},\dots,V_{r}$ of $V(G)$ where

$V_{i}=\\{(p_{i},j):p_{i}\in B_{j}\\}.$

For any $m$ parts, say $V_{i_{1}},\dots,V_{i_{m}}$, the corresponding points
$p_{i_{1}},\dots,p_{i_{m}}$ form an $m$-set and so there is some block $B_{j}$
that contains it. The vertices
$\\{(p_{i_{1}},j),(p_{i_{2}},j),\dots,(p_{i_{m}},j)\\}$ form an edge in $G$
with one vertex in each of the $m$ parts $V_{i_{1}},\dots,V_{i_{m}}$.

We can apply Proposition 4.1 to any value of $m$ by taking $r=\alpha
t(t-1)\cdots(t-m+1)+m-1$ for $\alpha\in\mathbb{N}$. By Keevash’s result [28]
on the existence of designs, when $\alpha$ is large enough an $m$-$(r,t,1)$
design exists and the upper bound of Proposition 4.1 holds. Taking $\alpha$ to
infinity proves Theorems 1.8 and 1.9.

###  4.2 Hypergraphs

Using polarity graphs of Desarguesian planes, Lazebnik and Verstraëte [33]
proved the asymptotic formula

$\textup{ex}_{3}(n,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\})=\frac{1}{6}(1+o(1))n^{3/2}.$
(12)

Two constructions were given in [33] that prove the lower bound. We use one of
these constructions to prove an upper bound on
$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{4}^{(3)}\\})$ and
$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\})$.

We use similar methods to prove Theorem 1.10.

Proof of Theorem 1.10. Let $q$ be an even power of an odd prime, and
$C_{q}=\\{(x_{1},2^{-1}x_{1}^{2}):x_{1}\in\mathbb{F}_{q}\\}$. Let $G_{q}$ be
the 3-uniform hypergraph with vertex set
$\mathcal{P}=\mathbb{F}_{q}^{2}\backslash C_{q}$ where
$\\{(a_{1},a_{2}),(b_{1},b_{2}),(c_{1},c_{2})\\}$ is an edge if and only if

$\displaystyle a_{2}+b_{2}$ $\displaystyle=$ $\displaystyle a_{1}b_{1}$
$\displaystyle b_{2}+c_{2}$ $\displaystyle=$ $\displaystyle b_{1}c_{1}$
$\displaystyle c_{2}+a_{2}$ $\displaystyle=$ $\displaystyle c_{1}a_{1}.$

This 3-uniform hypergraph is
$\mathcal{F}:=\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\}$-free
and has $q^{2}-q$ vertices.

Partition $\mathcal{P}$ into the $q$ parts

$\mathcal{P}_{x_{1}}=\\{(x,y)\in\mathcal{P}:x=x_{1}\\},~{}x_{1}\in\mathbb{F}_{q}.$

A part $\mathcal{P}_{x_{1}}$ intersects $C_{q}$ in exactly
$(x_{1},2^{-1}x_{1}^{2})$ so that each part has $q-1$ vertices. Let $\mu$ be a
root of an irreducible quadratic over $\mathbb{F}_{\sqrt{q}}$. We can then
write each $x_{j}\in\mathbb{F}_{q}$ as $x_{j}=x_{1,j}+x_{2,j}\mu$ where
$x_{1,j},x_{2,j}\in\mathbb{F}_{\sqrt{q}}$.

Fix three distinct parts $\mathcal{P}_{a_{1}}$, $\mathcal{P}_{b_{1}}$, and
$\mathcal{P}_{c_{1}}$. There will be an edge with one vertex in each of these
parts if and only if there exists an $a_{2},b_{2},c_{2}\in\mathbb{F}_{q}$ such
that $a_{2}\neq 2^{-1}a_{1}^{2}$, $b_{2}\neq 2^{-1}b_{2}^{2}$, $c_{2}\neq
2^{-1}c_{2}^{2}$, and $a_{2},b_{2},c_{2}$ solve the above system of equations.
Row reduction gives that the solution is

$a_{2}=2^{-1}(a_{1}b_{1}-b_{1}c_{1}+c_{1}a_{1})$,
$b_{2}=2^{-1}(b_{1}c_{1}-c_{1}a_{1}+a_{1}b_{1})$,
$c_{2}=2^{-1}(c_{1}a_{1}-a_{1}b_{1}+b_{1}c_{1})$.

For contradiction, suppose that the first equation implies
$a_{2}=2^{-1}a_{1}^{2}$. Then $a_{1}^{2}=a_{1}b_{1}-b_{1}c_{1}+c_{1}a_{1}$ and
after factoring by grouping, $0=(a_{1}-c_{1})(b_{1}-a_{1})$. This is a
contradiction, because the three chosen parts are all distinct. The same
argument shows $b_{2}\neq 2^{-1}b_{1}$ and $c_{2}\neq 2^{-1}c_{1}$ so that the
needed $a_{2},b_{2},c_{2}$ exist. As there is a triple between any three
parts, $G_{q}$ is a 3-uniform $(q,q-1)$-hypergraph that is $\mathcal{F}$-free.
Hence, for any $q$ that is an even power of an odd prime,
$f_{3}(q,\mathcal{F})\leq q-1$. A density of primes argument and the
observation that
$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{4}^{(3)}\\})\leq
f_{3}(r,\mathcal{F})$ completes the upper bound. In [16], the formula
$\textup{ex}_{3}(n,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{4}^{(3)}\\})=\frac{1}{6}n^{3/2}+o(n^{3/2})$
is proved. Using this formula gives

$f_{3}(r,\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{4}^{(3)}\\})\geq r+o(r).$

Remark: For
$\mathcal{F}=\\{\mathcal{C}_{2}^{(3)},\mathcal{C}_{3}^{(3)},\mathcal{C}_{4}^{(3)}\\}$,
in this proof we showed that for any even power of an odd prime $q$, one has
$f_{3}(q,\mathcal{F})\leq q-1$. If we set $k=f_{3}(q,\mathcal{F})$, in this
special case the best possible bound is $q-1$ or $q-2$. Indeed, if $k\leq
q-3$, then by Theorem 2.1 from [33], we have

$\displaystyle\frac{1}{6}(qk)\sqrt{qk-3/4}+\frac{1}{12}qk$ $\displaystyle\leq$
$\displaystyle\frac{1}{6}(qk)(q^{2}-3q+3/4-3/2)+\frac{1}{12}q(q-3)$
$\displaystyle<$
$\displaystyle\frac{1}{6}(qk)(q-3/2)+\frac{1}{12}q(q-3)<\binom{q}{3}$

for all $q\geq 3$. Thus, $k\in\\{q-1,q-2\\}$.

##  5 Concluding Remarks

In the introduction it was mentioned that this upper bound can be improved for
small $d$. For $d\geq 2$, write $c_{d}$ for a value such that
$f(r,K_{2,d+1})<c_{d}r^{1/3}+o(r^{1/3})$. One can use the proof of Theorem 1.4
to show that $c_{3}\leq c_{2}\leq 1.89$, $c_{5}\leq c_{4}\leq 1.26$,
$c_{7}\leq c_{6}\leq 1.21$, $c_{11}\leq c_{10}\leq c_{9}\leq c_{8}\leq 1.20$,
and $c_{14}\leq c_{13}\leq c_{12}\leq 0.93$. These bounds are much better than
that of Theorem 1.4 for small $d$. In light of Theorems 1.3 and 1.10, it would
be interesting to determine an asymptotic formula for $f(r,K_{2,d+1})$. It
seems possible that $f(r,K_{2,d+1})=(r/d)^{1/3}+o(r^{1/3})$ for all $d\geq 1$.
A first step could be to narrow the bounds on $f(r,C_{4})$.

We proved that $f(r,\theta_{3,4})=\Theta(r^{3/5})$. It was proved by Conlon
[7] that for every $\ell\geq 2$, there is a $K$ such that
$\textup{ex}(N,\theta_{K,\ell})=\Omega_{\ell}(N^{1+1/\ell})$, and an upper
bound that matches in order of magnitude is in [17]. It would be interesting
to determine the order of magnitude for $f(r,\theta_{t,\ell})$ for $t\geq K$
and in such cases where it can be done it would further be interesting to
determine the dependence on $t$.

Theorem 1.8 is asymptotically tight if the Erdős-Sós conjecture is true, and
hence is best possible for many trees $T$. It would be interesting to
determine if there is another natural family for which Theorem 1.9 is tight
besides Berge paths. Considering other families of forbidden hypergraphs where
there are constructions known for the corresponding Turán problem is also a
natural next step. For example, one might consider the family of
Berge-$K_{2,t}$ and use results from [21].

As noted in the discussion before Theorem 1.6, the densest known construction
of $C_{2\ell}$-free graphs are the $CD(k,q)$ graphs of Lazebnik, Ustimenko,
and Woldar. This is a $q$-regular bipartite graph on
$2q^{k-\lfloor\frac{k+2}{4}\rfloor+1}$ vertices with girth at least $k+5$, if
$k$ is odd (for details, see [32]). We cannot apply Theorem 3.4 to $CD(k,q)$
because the eigenvalues of these graphs are not fully understood. For the
background to the following conjecture, see [36].

######  Conjecture 5.1 (Ustimenko)

For all $(k,q)$, the nontrivial eigenvalues of $D(k,q)$ (and therefore
$CD(k,q)$) are at most $2\sqrt{q}$.

If the conjecture were true, then Theorem 3.4 would apply to $CD(k,q)$. If
$\ell$ is odd, we take $2\ell=k+3$ so that $n=q^{2\ell-3-\frac{2\ell-2}{4}+1}$
and $d=q=n^{\frac{2}{3\ell-3}}$. This would give the upper bound

$f(m,C_{2\ell})\leq Cm^{\frac{3\ell-5}{3\ell-1}}(\log
m)^{\frac{3\ell-3}{3\ell-1}}.$

If $\ell$ is even, then again with $2\ell=k+3$ we have
$n=q^{2\ell-3+\frac{2\ell-4}{4}+1}$ and $d=q=n^{\frac{2}{3\ell-6}}$, giving
the upper bound

$f(m,C_{2\ell})\leq Cm^{\frac{3\ell-8}{3\ell-4}}(\log
m)^{\frac{3\ell-6}{3\ell-4}}.$

The condition $\rho=O(d^{\frac{1}{2}})$ in Theorem 3.4 means that our $H$-free
graph is asymptotically a best possible pseudorandom graph. In this case we
match the upper bound of Theorem 1.1. If one weakened this assumption to
$\rho=O(d^{b})$ for some $b>\frac{1}{2}$ one could obtain weaker (but still
nontrivial) upper bounds on $f(m,H)$.

## References

  * [1] N. Alon and F.R.K. Chung.  Explicit construction of linear sized tolerant networks.  Discrete Mathematics, 72(1):15–19, 1988.
  * [2] M. Axenovich and R. Martin.  Splits with forbidden subgraphs.  Discrete Mathematics, 345(2), 2022.
  * [3] F. Barbanera.  Covering numbers in Ramsey problems.  Master’s thesis, Karlsruhe Institute of Technology, 2019.
  * [4] M. Bennett, G. Martin, K. O’Bryant, and A. Rechnitzer.  Explicit bounds for primes in arithmetic progressions.  Illinois J. Math., 62(1–4):427–532, 2018.
  * [5] B. Bollobás, B. Reed, and A. Thomason.  An extremal function for the achromatic number.  Graph structure theory _in Contemp. Math._ , 147(1–4):161–165, 1993.
  * [6] M. Bucić, J. Fox, and B. Sudakov.  Clique minors in graphs with a forbidden subgraph.  Random Structures Algorithms., 60(3):327–338, 2022.
  * [7] D. Conlon.  Graphs with few paths of prescribed length between any two vertices.  Bull. Lond. Math. Soc., 51(6):1015–1021, 2019.
  * [8] S. De Winter, J. Schillewaert, and J. Verstraete.  Large incidence-free sets in geometries.  The Electronic Journal of Combinatorics, 19(4), 2012.
  * [9] Michał Dȩbski, Zbigniew Lonc, and Paweł Rza̧żewski.  Achromatic and harmonious colorings of circulant graphs.  Journal of Graph Theory, 87(1):18–34, 2018.
  * [10] K. Edwards.  The harmonious chromatic number and the achromatic number.  In Surveys in combinatorics, 1997, pages 13–48. Cambridge University Press, 1997.
  * [11] K. Edwards.  Achromatic number of fragmentable graphs.  Journal of Graph Theory, 65(2):94–114, 2010.
  * [12] K. Edwards.  Achromatic number of collections of paths and cycles.  Discrete Mathematics, 313(19):1856–1860, 2013.
  * [13] K. Edwards and P. Rza̧żewski.  Complete colourings of hypergraphs.  Discrete Mathematics, 343(2):111673, 2020.
  * [14] David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, and Stephen Wismath.  On the planar split thickness of graphs.  Algorithmica, 80:977–994, 2018.
  * [15] P. Erdős and R. Graham.  On partition theorems for finite graphs.  Colloq. Math. Soc. János Bolyai, 10:515–527, 1975.
  * [16] B. Ergemlidze, E. Györi, and A. Methuku.  Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs.  J. Combin. Theory Ser. A, 163:163–181, 2019.
  * [17] R. Faudree and M. Simonovits.  On a class of degenerate extremal graph problems.  Combinatorica, 3:83–93, 1983.
  * [18] Z. Füredi.  New asymptotics for bipartite Turán numbers.  J. Combin. Theory Ser. A, 75:141–144, 1996.
  * [19] Z. Füredi.  An upper bound on Zarankiewicz problem.  Combin. Prob. Comput., 5(1):29–33, 1996.
  * [20] D. Gerbner and C. Palmer.  Extremal results for Berge hypergraphs.  SIAM Journal on Discrete Mathematics, 31(4):2314–2327, 2017.
  * [21] Dániel Gerbner, Abhishek Methuku, and Máté Vizer.  Asymptotics for the Turán number of Berge-${K}_{2,t}$.  Journal of Combinatorial Theory, Series B, 137:264–290, 2019.
  * [22] E. Györi, G. Katona, and N. Lemons.  Hypergraph extensions of the erdös-gallai theorem.  European J. Combin, 58:238–246, 2016.
  * [23] W.H. Haemers.  Eigenvalue techniques in design and graph theory.  PhD thesis, Mathematics and Computer Science, 1979.
  * [24] N. Haghparast, M. Hasanvand, and Y. Ohno.  The existence of uniform hypergraphs for which the interpolation property of complete coloring fails.  Discrete Mathematics, 345(3):112722, 2022.
  * [25] G. Harcos and D. Soltész.  New bounds on even cycle creating Hamiltonian paths using expander graphs.  Combinatorica, 40:435–434, 2020.
  * [26] Percy John Heawood.  Map-colour theorem.  Proceedings of the London Mathematical Society, 2(1):161–175, 1949\.
  * [27] F Hughes and Gary MacGillivray.  The achromatic number of graphs: a survey and some new results.  Bull. Inst. Combin. Appl, 19:27–56, 1997.
  * [28] P. Keevash.  The existence of designs.  arXiv preprint arXiv:1401.3665, 2014.
  * [29] A. V. Kostochka.  The minimum hadwiger number for graphs with a given mean degree. (russian).  Metody Diskret. Analiz., 38:37–58, 1982.
  * [30] M. Krivelevich and R. Nenadov.  Complete minors in graphs without sparse cuts.  Int. Math. Res. Not. IMRN, 12:8996–9015, 2021.
  * [31] M. Krivelevich and B. Sudakov.  Minors in expanding graphs.  Geom. Fun. Anal., 19:294–331, 2009.
  * [32] F. Lazebnik, V. A. Ustimenko, and A. J. Woldar.  A new series of dense graphs of high girth.  Bull. Amer. Math. Soc., 32:73–79, 1995.
  * [33] F. Lazebnik and J. Verstraëte.  On hypergraphs of girth five.  Electron. J. of Combin., 10, 2003.  Article #R25.
  * [34] A. Lubotzky, R. Phillips, and P. Sarnak.  Ramanujan graphs.  Combinatorica, 8:261–277, 1988.
  * [35] G. MacGillivray and A. Rodriguez.  The achromatic number of the union of paths.  Discrete Mathematics, 231(1-3):331–335, 2001.
  * [36] G. E. Moorhouse, S. Sun, and J. Williford.  The eigenvalues of the graphs ${D}(4,q)$.  Journal of Combinatorial Theory, Series B, 125:1–20, 2017.
  * [37] V. Nikiforov.  A contribution to the Zarankiewicz problem.  Linear Algebra Appl., 432(6):1405–1411, 2010.
  * [38] Y. Roichman.  On the achromatic number of hypercubes.  Journal of Combinatorial Theory, Series B, 79(2):177–182, 2000\.
  * [39] Andrew Thomason.  Extremal Functions for Graph Minors, pages 359–380.  Springer Berlin Heidelberg, 2006.
  * [40] J. Verstraëte and J. Williford.  Graphs without theta subgraphs.  J. Combin. Theory Ser. B, 134:76–87, 2019.
  * [41] R. Wenger.  Extremal graphs with no ${C}^{4}$’s, ${C}^{6}$’s, or ${C}^{10}$’s.  J. Combin. Theory Ser. B, 52:113–116, 1991.