% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.34}{24(4)}{2017} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf On $r$-uniform linear hypergraphs with no Berge-$K_{2,t}$} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Craig Timmons\thanks{This work was supported by a grant from the Simons Foundation (\#359419).}\\ \small Department of Mathematics and Statistics\\[-0.8ex] \small California State University Sacramento\\[-0.8ex] \small Sacramento, CA, U.S.A.\\ \small\tt craig.timmons@csus.edu\\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Sep 19, 2016}{Nov 12, 2017}{Nov 24, 2017}\\ \small Mathematics Subject Classifications: 05C35, 05D99} \begin{document} \maketitle \begin{abstract} Let $\mathcal{F}$ be an $r$-uniform hypergraph and $G$ be a multigraph. The hypergraph $\mathcal{F}$ is a \emph{Berge}-$G$ if there is a bijection $f: E(G) \rightarrow E( \mathcal{F} )$ such that $e \subseteq f(e)$ for each $e \in E(G)$. Given a family of multigraphs $\mathcal{G}$, a hypergraph $\mathcal{H}$ is said to be $\mathcal{G}$-\emph{free} if for each $G \in \mathcal{G}$, $\mathcal{H}$ does not contain a subhypergraph that is isomorphic to a Berge-$G$. We prove bounds on the maximum number of edges in an $r$-uniform linear hypergraph that is $K_{2,t}$-free. We also determine an asymptotic formula for the maximum number of edges in a linear 3-uniform 3-partite hypergraph that is $\{C_3, K_{2,3} \}$-free. % keywords are optional \bigskip\noindent \textbf{Keywords:} hypergraph Tur\'{a}n problem; Sidon sets; Berge-$K_{2,t}$ \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Let $G$ be a multigraph and $\mathcal{F}$ be a hypergraph. Following Gerbner and Palmer \cite{gp}, we say that $\mathcal{F}$ is a \emph{Berge}-$G$ if there is a bijection $f : E(G) \rightarrow E( \mathcal{F} )$ with the property that $e \subseteq f(e)$ for all $e \in E(G)$. This definition generalizes both Berge-cycles and Berge-paths in hypergraphs. Recall that for an integer $k \geq 2$, a Berge $k$-cycle is an alternating sequence $v_1 e_1 v_2 e_2 \cdots v_k e_k v_1$ of distinct vertices and edges such that $\{v_i, v_{i+1} \} \subseteq e_i $ for $1 \leq i \leq k - 1 $, and $\{v_k, v_1 \} \subseteq e_k$. A Berge $k$-path is defined in a similar way (omit $e_k$ and $v_1$ from the sequence). Given a family of multigraphs $\mathcal{G}$, the hypergraph $\mathcal{H}$ is \emph{$\mathcal{G}$-free} if for every $G \in \mathcal{G}$, the hypergraph $\mathcal{H}$ does not contain a subhypergraph that is isomorphic to a Berge-$G$. Observe that Berge-$G$ is a family of hypergraphs. For example, $\{ \{ a,b,c \}, \{c,d,e \} \}$ and $\{ \{ a, b, c \}, \{ b, c, d \} \}$ are non-isomorphic hypergraphs, but both are Berge-$G$'s where $G$ is the path whose edges are $\{b, c \}$ and $\{ c, d \}$. Write $\textup{ex}_r ( n, \mathcal{G} )$ for the maximum number of edges in an $n$-vertex $r$-uniform hypergraph that is $\mathcal{G}$-free. The function $\textup{ex}_r (n, \mathcal{G} )$ is the \emph{Tur\'{a}n number} or \emph{extremal number} of $\mathcal{G}$. When $r = 2$ and $\mathcal{G}$ consists of simple graphs, $\textup{ex}_2 ( n, \mathcal{G} )$ coincides with the usual definition of Tur\'{a}n numbers. When $\mathcal{G} = \{G \}$, we write $\textup{ex}_r ( n, G)$ instead of $\textup{ex}_r ( n, \{ G \} )$. One of the most important results in graph theory is the so-called Erd\H{o}s-Stone-Simonovits Theorem which is a statement about Tur\'{a}n numbers of graphs. \begin{theorem}[Erd\H{o}s, Stone, Simonovits]\label{ess} If $G$ is a graph with chromatic number $k \geq 2$, then \[ \textup{ex}_2 ( n, G) = \left( 1 - \frac{1}{k - 1} \right) \binom{n}{2} + o(n^2). \] \end{theorem} Theorem \ref{ess} provides an asymptotic formula for the Tur\'{a}n number of any non-bipartite graph. No such result is known for $r \geq 3$ and in general, hypergraph Tur\'{a}n problems are considerably harder than graph Tur\'{a}n problems. Despite this, there has been some success in estimating $\textup{ex}_r ( n, \mathcal{G} )$ when $\mathcal{G}$ contains short cycles. For instance, Bollob\'{a}s and Gy\H{o}ri \cite{bg} proved that \[ \frac{1}{ 3 \sqrt{3} } n^{3/2} - o( n^{3/2} ) \leq \textup{ex}_3 ( n, C_5 ) \leq \sqrt{2} n^{3/2} + 4.5 n. \] In other words, the maximum number of triples in an $n$-vertex 3-uniform hypergraph with no Berge 5-cycle is $\Theta (n^{3 / 2} )$. One of the motivations behind estimating $\textup{ex}_3 ( n, C_5 )$ is the problem of finding the maximum number of triangles in a graph with no 5-cycle. We refer the reader to \cite{bg} and the papers of Gy\H{o}ri, Li \cite{gli}, and Alon and Shikhelman \cite{as} for more on the intriguing problem of finding the maximum number of copies of a graph $F$ in an $H$-free graph $G$. Lazebnik and Verstra\"{e}te \cite{lv} proved several results concerning $r$-uniform hypergraphs that are $\{C_2, C_3, C_4 \}$-free. Here $C_2$ is the multigraph consisting of two parallel edges. Recall that a hypergraph $\mathcal{F}$ is \emph{linear} if any two distinct edges of $\mathcal{F}$ intersect in at most one vertex. It is easy to check that \begin{center} a hypergraph is linear if and only if it is $C_2$-free. \end{center} Lazebnik and Verstra\"{e}te showed that \begin{equation}\label{lv bound} \textup{ex}_3 ( n, \{C_2, C_3, C_4 \} ) = \frac{1}{6} n^{3/2} + o(n^{3/2}). \end{equation} A consequence of this result is the asymptotic formula $T_3 (n, 8, 4) = \frac{1}{6} n^{3/2} + o(n^{3/2})$ for the generalized Tur\'{a}n number $T_r (n, k, l )$. This is defined to be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph with the property that no $k$ vertices span $l$ or more edges. Provided cycles are defined in the Berge sense as above, one may say that a $\{C_2, C_3, C_4 \}$-free hypergraph is a hypergraph of girth 5, and this is the terminology that is used in \cite{lv}. The interest in $\textup{ex}_3( n, \{C_2, C_3, C_4 \})$ has its origins in determining the maximum number of edges in a graph with girth 5 which is a well-known, unsolved problem of Erd\H{o}s (see (\ref{girth 5 bound}) below). For related results, including results for paths, cycles, and some general bounds, see \cite{gl}, \cite{fo}, and \cite {gp}, respectively. The case of cycles has received considerable attention. Collier-Cartaino, Graber, and Jiang \cite{cgj} investigated so-called linear cycles in linear hypergraphs. Their paper has a particularly nice introduction that discusses several results in this area. Lastly, the papers of Gy\H{o}ri and Lemons \cite{gl2, gl1, gl}, in which bounds on the number of edges in a hypergraph with no Berge $k$-cycle are obtained, are also important contributions. In this paper we consider what happens in (\ref{lv bound}) when $C_4$ is replaced by $K_{2,3}$. Our main result is given in the following theorem. \begin{theorem}\label{main thm} For any integer $r \geq 3$, \[ \frac{1}{r^{3/2} } n^{3/2} - o( n^{3/2} ) \leq \textup{ex}_r ( n, \{C_2, C_3, K_{2, 2r - 3 } \} ) \leq \frac{ \sqrt{ 2r - 4} }{ r ( r - 1) } n^{3/2} + \frac{n}{r}. \] \end{theorem} Since $\frac{1}{3^{3/2} } > \frac{1}{6}$, Theorem \ref{main thm} implies that there are 3-uniform hypergraphs that are $\{C_2, C_3, K_{2,3} \}$-free and have more edges than any $\{C_2, C_3, C_4 \}$-free 3-uniform hypergraph. For graphs, the best known bounds on the Tur\'{a}n number of $\{C_3, C_4 \}$ are \begin{equation}\label{girth 5 bound} \frac{1}{ 2 \sqrt{2} } n^{3/2} - o(n^{3/2} ) \leq \textup{ex}_2( n, \{C_3, C_4 \} ) \leq \frac{1}{2} n^{3/2} + o(n^{3/2} ). \end{equation} In \cite{aksv} it is shown that $\textup{ex}_2(n, \{C_3, K_{2,3} \} ) \geq \frac{1}{ \sqrt{3} } n^{3/2} - o(n^{3/2} )$. Putting all of these results together, we see that in both the graph case and the 3-uniform hypergraph case, forbidding $K_{2,3}$ instead of $C_4$ allows one to have significantly more edges. It is not known if this is also true for $r \geq 4$. On an interesting related note, Erd\H{o}s has conjectured that the lower bound in (\ref{girth 5 bound}) is correct while in \cite{aksv} it is conjectured that the lower bound in (\ref{girth 5 bound}) can be improved. Our construction that establishes the lower bound in Theorem \ref{main thm} is $r$-partite. In this case, the upper bound of Theorem \ref{main thm} can be improved by adapting the counting argument of \cite{lv} to the $K_{2,3}$-free case. \begin{theorem}\label{main thm2} If $\mathcal{F}$ is a $\{C_2, C_3, K_{2,3} \}$-free 3-uniform 3-partite hypergraph with $n$ vertices in each part, then \[ | E( \mathcal{F} ) | \leq \sqrt{ \frac{2}{r - 1} } n^{3/2} + n. \] Furthermore, for any $q$ that is a power of an odd prime, there is a 3-uniform 3-partite $\{C_2, C_3, K_{2,3} \}$-free hypergraph with $q^2$ vertices in each part and $q^2 ( q - 1)$ edges. \end{theorem} A similar result for 3-uniform 3-partite $\{C_2, C_3, C_4 \}$-free graphs was proved in \cite{lv}. Let us write $z_r (n, \mathcal{G})$ for the maximum number of edges in a $\mathcal{G}$-free $r$-uniform $r$-partite hypergraph with $n$ vertices in each part. Using this notation, we can state Theorem 2.6 of \cite{lv} as $z_3(n, \{C_2, C_3, C_4 \} ) \leq \frac{1}{ \sqrt{2} }n^{3/2} + n$ for all $n \geq 3$, and $z_3(n, \{ C_2, C_3, C_4 \} ) \geq \frac{1}{2}n^{3/2} - 3n$ for infinitely many $n$. Theorem \ref{main thm2} gives the asymptotic formula \[ z_3(n, \{C_2, C_3, K_{2,3} \} ) = n^{3/2} + o(n^{3/2}). \] One drawback to Theorem \ref{main thm} is that the size of the forbidden graph $K_{2,2r-3}$ depends on $r$. There are two natural directions to pursue. On one hand, we can fix $r$ and attempt to construct $K_{2,t}$-free hypergraphs where $t$ tends to infinity and at the same time, the number of edges increases with $t$. Our next theorem shows that this can be done at the cost of allowing $C_3$. \begin{theorem}\label{thm3} Let $r \geq 3$ be an integer and $l$ be any integer with $2l + 1 \geq r$. If $q \geq 2lr^3$ is a power of an odd prime and $n = rq^2$, then \[ \textup{ex}_r ( n, \{ C_2, K_{2, t + 1} \} ) \geq \frac{l }{r^{3/2}} n^{3/2} - \frac{l}{r} n \] where $t = (r - 1)(2l^2 - l)$. \end{theorem} The other direction is to fix $t$ and let $r$ become large. This is a much more difficult problem as suggested by the results and discussion in \cite{lv}. We were unable to answer the following slight variation of a question posed to us by Verstra\"{e}te \cite{jv}. \begin{question} Is there a bipartite graph $F$ that contains a cycle for which the following holds: there is a positive integer $r(F)$ such that for all $r \geq r(F)$, we have \begin{equation}\label{q} \textup{ex}_r ( n, \{ C_2,F \} ) = o ( \textup{ex}_2 ( n, F) ). \end{equation} \end{question} Using the graph removal lemma, one can show that (\ref{q}) holds whenever $F$ is a non-bipartite graph provided $r \geq |V (F)|$. When $F= C_4$, the formula (\ref{lv bound}) implies that $\textup{ex}_3 ( n, \{C_2, C_4 \} ) = \Omega ( \textup{ex}_2 ( n, C_4 ))$, but it is not known if the same lower bound holds for larger $r$. Using blow ups of extremal graphs, Gerbner and Palmer \cite{gp} (see also \cite{gl2, gl} for cycles) proved that $\textup{ex}_r ( n, K_{s, t} ) = \Omega ( \textup{ex}_2 ( n, K_{s,t} ) )$ whenever $2 \leq r \leq s + t$, but the hypergraphs constructed using this method are not $C_2$-free. Improving the lower bound on $\textup{ex}_3 ( n, \{C_2, C_{2k} \} )$ that comes from random constructions is a problem that was mentioned explicitly by F\"{u}redi and \"{O}zkahya in \cite{fo}. In the next section we prove the upper bounds stated in Theorems \ref{main thm} and \ref{main thm2}. Both of these upper bounds use the counting arguments of \cite{lv}. We include their proofs for completeness, but we do want to make it clear that proving our upper bounds using the methods of \cite{lv} is straightforward. The lower bounds of Theorems \ref{main thm}, \ref{main thm2}, and \ref{thm3} are our main contribution. Section \ref{algebra} contains algebraic lemmas which are required for our construction. Section \ref{the H} gives the construction which is a generalization of the one found in \cite{tv} and is based on a construction Allen, Keevash, Sudakov, and Verstra\"{e}te (see Theorem 1.6 \cite{aksv}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Upper bounds} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The upper bound of Theorem \ref{main thm}} Using the counting argument of \cite{lv} we can prove an upper bound on the number of edges in a $\{ C_2, C_3, K_{2,t+1} \}$-free $r$-uniform hypergraph. Given a set $S$, write $S^{(2)}$ for the set of pairs of elements of $S$. In this section we prove the following which implies the upper bound given in Theorem \ref{main thm}. \begin{theorem}\label{ub} If $r \geq 3$ and $t \geq 1$ are integers, then \[ \textup{ex}_r ( n, \{ C_2, C_3, K_{2,t+1} \} ) \leq \frac{ \sqrt{t} }{r(r-1) } n^{3/2} + \frac{n}{r}. \] \end{theorem} \begin{proof} Let $\mathcal{F}$ be a $\{ C_2, C_3, K_{2,t+1} \}$-free $r$-uniform hypergraph with $n$ vertices. Let $V$ be the vertex set of $\mathcal{F}$. For $v \in V$, let $e_1^v, \dots, e_{d(v)}^{v}$ be the edges in $\mathcal{F}$ that contain $v$ where $d(v)$ is the degree of $v$ in $\mathcal{F}$. For $1 \leq i < j \leq d(v)$, let \[ P( e_i^v, e_j^v ) = \left\{ \{ x,y \} \in V^{(2)} : x \in e_i^v \backslash \{v\} ~\mbox{and}~ y \in e_j^v \backslash \{v \} \right\}. \] Since $\mathcal{F}$ is linear, the sets $e_1^v \backslash \{ v \}, e_2^v \backslash \{v\}, \dots, e_{d(v)}^v \backslash \{v \}$ are pairwise disjoint so we have $| P ( e_i^v, e_j^v ) | = (r-1)^2$. For any fixed vertex $v$, \begin{equation}\label{ub eq1} \sum_{1 \leq i < j \leq d(v) } | P ( e_i^v, e_j^v ) | = (r-1)^2 \binom{ d(v) }{2} \end{equation} and the sum in (\ref{ub eq1}) never counts a pair $\{x,y \} \in V^{(2)}$ more than once. Now consider the sum \begin{equation}\label{ub eq2} \sum_{v \in V} \sum_{1 \leq i < j \leq d(v) } | P( e_i^v, e_j^v ) |. \end{equation} Suppose a pair $\{x,y \} \in V^{(2)}$ is counted more than $t$ times in this sum. Let $v_1, \dots, v_{t+1}$ be distinct vertices such that there are edges $e_i \neq f_i \in E ( \mathcal{F})$, both of which contain $v_i$, and $\{x, y \} \in P ( e_i, f_i )$ for $1 \leq i \leq t+1$. Assume $x \in e_i$ and $y \in f_i$. By definition of $P(e,f)$, $\{x,y \} \cap \{v_1, \dots, v_{t+1} \} = \emptyset$ so $x,y, v_1, \dots, v_{t+1}$ are all distinct. If $e_1, \dots, e_{t+1}$, $f_1, \dots, f_{t+1}$ are all distinct, then $\mathcal{F}$ contains a $K_{2,t+1}$ so these $2t+2$ edges cannot all be distinct. We will show that this leads to a contradiction. If $e_i = e_j$ for some $1 \leq i < j \leq t+1$, then $v_j \in e_i$ and $\{ f_i, f_j, e_i \}$ is a $C_3$ since $v_i \in e_i \cap f_i$, $y \in f_i \cap f_j$, and $v_j \in f_j \cap e_i$. Note that $f_i \neq f_j$ otherwise $\{v_i, v_j \} \subseteq f_i \cap e_i$ contradicting the linearity of $\mathcal{F}$. We conclude that $e_i \neq e_j$ for $1 \leq i < j \leq t + 1$. A similar argument shows that $f_i \neq f_j$ for $1 < i < j \leq t+1$. The only remaining possibility is that $e_i = f_j$ for some $1 \leq i \neq j \leq t+1$. If this is the case, then $y \in e_i$ so $\{v_i, y \} \subseteq e_i \cap f_i$ which, by linearity, implies $e_i = f_i$ which is a contradiction. We conclude that the sum (\ref{ub eq2}) counts any pair $\{x,y \} \in V^{(2)}$ at most $t$ times. Let $m$ be the number of edges of $\mathcal{F}$. By (\ref{ub eq1}) and Jensen's Inequality applied to the convex function \[ f(x) = \left\{ \begin{array}{ll} \binom{x}{2} & \mbox{if $x \geq 2$} \\ 0 & \mbox{otherwise}, \end{array} \right. \] we have \[ t \binom{n}{2} \geq \sum_{v \in V} \sum_{1 \leq i < j \leq d(v) } | P ( e_i^v, e_j^v ) | = (r-1)^2 \sum_{v \in V} \binom{d(v)}{2} \geq n (r-1)^2 \binom{rm/n}{2}. \] This is a quadratic inequality in $m$ and implies that \[ m \leq \left( \frac{t n^3}{r^2 ( r - 1)^2 } + \frac{n^2}{4r^2} \right)^{1/2} + \frac{n}{2r} \leq \frac{ \sqrt{t} }{r(r-1)} n^{3/2}+ \frac{n}{r}.\qedhere \] \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The upper bound of Theorem \ref{main thm2}} The upper bound of Theorem \ref{main thm2} essentially follows from Theorem 2.3 in \cite{lv} with some modifications to the proof. We include the proof for completeness. \begin{theorem} Let $r \geq 3$. If $\mathcal{F}$ is a $\{C_2, C_3, K_{2,3} \}$-free $r$-uniform $r$-partite hypergraph with $n$ vertices in each part, then \[ | E( \mathcal{F} ) | \leq \sqrt{ \frac{2}{r - 1} } n^{3/2} + n. \] \end{theorem} \begin{proof} Let $\mathcal{F}$ be an $r$-partite $r$-uniform hypergraph with $n$ vertices in each part. Let $V_1, \dots, V_r$ be the parts of $\mathcal{F}$ and assume that $\mathcal{F}$ is $\{ C_2, C_3, K_{2,3} \}$-free. Let $S$ be the set of all pairs of the form $(v, \{x,y \})$ where $v \in V( \mathcal{F} )$, $\{x,y \}$ is a pair of vertices in the same part with $x \neq v$, $y \neq v$, and there are distinct edges $e$ and $f$ with $\{v, x \} \subset e$ and $\{v, y \} \subset f$. We will count the cardinality of $S$ in two ways. Given a vertex $v \in \mathcal{F}$, we again write $d(v)$ for the number of edges that contain $v$. If we first choose the vertex $v$, there are $\binom{d(v)}{2} (r - 1)$ ways to choose a pair $\{x, y \}$ for which $(v, \{x,y \} )$ belongs to $S$. Here we are using the fact that $\mathcal{F}$ is linear and so every edge of $\mathcal{F}$ contains exactly one vertex in each part. Therefore, \begin{equation}\label{main thm2 eq1} |S| = \sum_{v \in V( \mathcal{F} ) } \binom{ d(v) }{2} (r -1) = (r - 1) \sum_{i = 1}^{r} \sum_{ v \in V_i} \binom{ d(v) }{2}. \end{equation} Next we show that \begin{equation}\label{main thm2 eq2} |S| \leq 2 \sum_{i = 1}^{r} \binom{ |V_i | }{2}. \end{equation} We first pick a pair $\{x, y \}$ that are in the same part, say $\{ x, y \} \subset V_i$. We now claim that there are at most two distinct $v$'s for which $(v, \{ x, y \} )$ belongs to $S$. Aiming for a contradiction, suppose that $(v, \{x, y \} )$, $(v', \{x, y \} )$, and $(v '', \{x, y \} )$ all belong to $S$, where $v$, $v'$, and $v''$ are all distinct. Let $e$, $e'$, and $e''$ be the edges through $x$ that contain $v$, $v'$, and $v''$, respectively. Let $f$, $f'$, and $f''$ be the edges through $y$ that contain $v$, $v'$, and $v''$, respectively. We will show that since $\mathcal{F}$ is $\{ C_2, C_3 \}$-free, all of the edges $e$, $e'$, $e''$, $f$, $f'$, and $f''$ are distinct and so form a $K_{2,3}$, which provides the needed contradiction. If $e \in \{ f, f', f'' \}$, then $e$ contains both $x$ and $y$ which is impossible since $x$ and $y$ are in the same part. The same argument shows $e' \notin \{ f, f', f'' \}$ and $e'' \notin \{f, f', f'' \}$, so that $\{e, e', e'' \} \cap \{ f, f', f'' \} = \emptyset$. Now suppose $e = e'$. Then $\{ v, v' \} \subset e$, and now $v \in e \cap f $, $y \in f \cap f' $, and $v' \in f' \cap e $. The edges $e$, $f$, and $f'$ cannot form a $C_3$ since $\mathcal{F}$ is $C_3$-free. Therefore, $f = f'$ so $v' \in f$. Since $\{ v, v' \} \subset f$, $\{ v, v' \} \subset e$, and $\mathcal{F}$ is $C_2$-free, the edges $e$ and $f$ must be the same, but we have shown already that this cannot occur. By symmetry, $e \neq e''$ and $e' \neq e''$. We conclude that the edges $e$, $e'$, and $e''$ are all distinct. A similar argument shows that $f$, $f'$, and $f''$ are all distinct. This gives a $K_{2,3}$ in $\mathcal{F}$ which is a contradiction. Therefore, there are at most two distinct vertices $v$ and $v'$ for which the pairs $(v, \{x, y \} )$ and $(v', \{x, y \} )$ belong to $S$. %$Also note, that $f \neq f'$ % %If $v$, $v'$, and $v''$ are all in the same part, then $e,e',e'',f,f'$, and $f''$ are all distinct and we have %a $K_{2,3}$. %Therefore, we can assume at least two of $v$, $v'$, and $v''$ are in different parts. % %Suppose that $v \in V_j$ and $v ' \in V_k$ where $i$, $j$, and $k$ are all distinct. %If $v' \in e$, then $e$, $f'$, and $f$ form a $C_3$ in $\mathcal{F}$ %since %$v' \in e \cap f'$, $y \in f' \cap f$, and $v \in f \cap e$. %Also note that the edges $e$, $f$, and $f'$ are all distinct since by definition, $e$ and $f$ are distinct edges, and $f'$ cannot %be $e$ since $f' \cap V_i = \{y \}$ but $e \cap V_i = \{ x \}$. Lastly, $f$ cannot be $f'$ otherwise %$\{ v, v' \} \subset e \cap f$ which, by linearity, would imply $e = f$, a contradiction. Combining (\ref{main thm2 eq1}) and (\ref{main thm2 eq2}) and using the fact that $|V_i| = n$ for every $i$, we have \begin{equation*} 2 r \binom{n}{2} = 2 \sum_{i = 1}^{r} \binom{ |V_i | } {2} \geq |S| = (r - 1) \sum_{i = 1}^{r} \sum_{v \in V_i} \binom{ d(v) }{2}. \end{equation*} By Jensen's Inequality, $\sum_{v \in V_i} \binom{ d(v) }{2} \geq n \binom{ m / n }{2}$ where $m$ is the number of edges of $\mathcal{F}$. Together, these two estimates give $2r \binom{n}{2} \geq (r - 1 ) rn \binom{ m / n }{2}$ so \begin{equation*} r n ( n - 1) \geq (r - 1)r n \frac{ (m/n) (m/n - 1) }{2}. \end{equation*} It follows that \[ m \leq \sqrt{ \frac{2}{r - 1} } n^{3/2} + n.\qedhere \] \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Lower bounds} In this section we prove the lower bounds of Theorems \ref{main thm}, \ref{main thm2}, and \ref{thm3}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Algebraic Lemmas}\label{algebra} In this subsection we prove some lemmas that are needed to prove our lower bounds. We write $\mathbb{F}_q$ for the finite field with $q$ elements and $\mathbb{F}_q^*$ for the group $\mathbb{F}_q \backslash \{ 0 \}$ under multiplication. The first lemma is due to Ruzsa \cite{ruzsa} and was key to the construction in \cite{tv}. A proof can be found in \cite{tv}. \begin{lemma}\label{ruzsa} Suppose $\alpha, \beta, \gamma$, and $\delta$ are nonzero elements of $\mathbb{F}_q$ with $\alpha + \beta = \gamma + \delta$. If $a_1, a_2, a_3, a_4 \in \mathbb{F}_q^*$, $\alpha a_1 + \beta a_2 = \gamma a_3 + \delta a_4$, and $\alpha a_1^2 + \beta a_2^2 = \gamma a_3^2 + \delta a_4^2$, then \[ \alpha \beta ( a_1 - a_2 )^2 = \gamma \delta (a_3 - a_4)^2. \] \end{lemma} \bigskip The next lemma is known. It is merely asserting the well-known fact that $\{ (a,a^2) : a \in \mathbb{F}_q^* \}$ is a Sidon set in the group $\mathbb{F}_q \times \mathbb{F}_q$ where the group operation is componentwise addition. \begin{lemma}\label{arithmetic l2} If $a_1, a_2, a_3, a_4 \in \mathbb{F}_q^*$, $a_1 + a_2 = a_3 + a_4$, and $a_1^2 + a_2^2 = a_3^2 + a_4^2$, then $\{a_1, a_2 \} = \{ a_3,a_4 \}$. \end{lemma} The next two lemmas will be used to control the appearance of small graphs in our construction. The idea is that a copy of some small graph in our construction corresponds to a nontrivial solution to some system of equations over $\mathbb{F}_q$. Variations of these lemmas have appeared in \cite{tv}. \begin{lemma}\label{arithmetic l1} Let $\alpha, \beta$, and $\gamma$ be distinct elements of $\mathbb{F}_q$. If $a_1, a_2, a_3 \in \mathbb{F}_q^*$, \begin{equation}\label{arithmetic l1 eq1} 0 = \alpha ( a_2 - a_1) + \beta ( a_3- a_2) + \gamma ( a_1 - a_3), \end{equation} and \begin{equation*} 0 = \alpha ( a_2^2 - a_1^2 ) + \beta (a_3^2 - a_2^2 ) + \gamma (a_1^2 - a_3^2 ), \end{equation*} then $a_1 =a_2 = a_3$. \end{lemma} \begin{proof} Adding $\beta a_1$ to both sides of (\ref{arithmetic l1 eq1}) and rearranging gives \begin{equation}\label{arithmetic l1 eq3} ( \gamma - \beta )(a_3 - a_1) = ( \alpha - \beta )(a_2 - a_1). \end{equation} A similar manipulation yields $( \gamma - \beta )(a_3^2 - a_1^2 ) = ( \alpha - \beta )(a_2^2 - a_1^2 )$ which is equivalent to \begin{equation}\label{arithmetic l1 eq4} ( \gamma - \beta )(a_3 - a_1) (a_3 + a_1) = ( \alpha - \beta )( a_2 - a_1)(a_2 + a_1). \end{equation} Note that $\gamma - \beta \neq 0$ and $\alpha - \beta \neq 0$ since $\alpha, \beta$, and $\gamma$ are all different. If $a _ 3 = a_1$, then (\ref{arithmetic l1 eq3}) implies that $a_2 = a_1$ and we are done. Otherwise, we divide (\ref{arithmetic l1 eq4}) by (\ref{arithmetic l1 eq3}) to get $a_3 + a_1 = a_2 + a_1$ which gives $a_3 = a_2$. This equality, together with (\ref{arithmetic l1 eq1}), implies $0 = \alpha ( a_2 - a_1 ) + \gamma ( a_1 - a_2)$ so \[ \gamma (a_2 - a_1) = \alpha (a_2 - a_1). \] If $a_2 - a_1 = 0$, then with $a_3 = a_2$ we get $a_1 = a_2 = a_3$ and we are done. Otherwise, we may cancel $a_2 - a_1$ to get $\gamma = \alpha$ which contradicts the fact that $ \gamma \neq \alpha$. \end{proof} \begin{lemma}\label{arithmetic l3} Let $\alpha, \beta \in \mathbb{F}_q^*$ with $\alpha + \beta \neq 0$. If $a_1, a_2,a_3, b_1, b_2, b_3 \in \mathbb{F}_q^*$, \begin{equation}\label{arithmetic l3 eq1} \alpha a_1 + \beta b_1 = \alpha a_2 + \beta b_2 = \alpha a_3 + \beta b_3, \end{equation} and \begin{equation*}\label{arithmetic l3 eq2} \alpha a_1^2 + \beta b_1^2 = \alpha a_2^2 + \beta b_2^2 = \alpha a_3^2 + \beta b_3^2, \end{equation*} then there is a pair $\{i,j \} \subset \{1,2,3 \}$ with $a_i = b_i$ and $a_j = b_j$. \end{lemma} \begin{proof} By Lemma \ref{ruzsa}, \begin{equation}\label{arithmetic l3 eq3} \alpha \beta ( a_1 -b_1)^2 = \alpha \beta (a_2 - b_2)^2. \end{equation} Since $\alpha \beta \neq 0$, (\ref{arithmetic l3 eq3}) implies that $(a_1 - b_1)^2 = (a_2 - b_2)^2$ so either $a_1 - b_1 = a_2 - b_2$, or $a_1 - b_1 = b_2 - a_2$. Suppose $a_1 - b_1 = a_2 - b_2$. We multiply this equation through by $\alpha $ and subtract the resulting equation from the first equation in (\ref{arithmetic l3 eq1}) to get \[ ( \alpha + \beta ) b_1 = ( \alpha + \beta )b_2. \] As $\alpha + \beta \neq 0$, it must be the case that $b_1 = b_2$ which, with (\ref{arithmetic l3 eq1}), gives $a_1 = a_2$ and we are done. Now suppose that $a_1 -b_1 = b_2 - a_2$. By symmetry, we may then assume that $a_1 - b_1 = b_3 - a_3$. We then have $a_2 - b_2 = a_3 - b_3$ and the argument from the previous paragraph gives $a_2 = a_3$ and $b_2 = b_3$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The Construction}\label{the H} Let $r \geq 2$ and $l \geq 1$ be integers. Let $q$ be a power of an odd prime. Let $\alpha_1, \dots, \alpha_r$ be distinct elements of $\mathbb{F}_q$. We choose $q$ large enough so that there are distinct elements $m_1, \dots, m_l \in \mathbb{F}_q^*$ that satisfy the condition \begin{equation}\label{condition} m_s ( \alpha_k - \alpha_i ) \neq m_t ( \alpha_k - \alpha_j) \end{equation} whenever $1 \leq s, t \leq l$ and $i,j$, and $k$ are distinct integers with $1 \leq i, j, k \leq r$. For $1 \leq i \leq r$, let $V_i = \mathbb{F}_q \times \mathbb{F}_q \times \{ i \}$. The union $V_1 \cup V_2 \cup \dots \cup V_r$ will be the vertex set of our hypergraph. We now define the edges. Each edge will contain exactly one element from each $V_i$. Given $x,y \in \mathbb{F}_q$, $a \in \mathbb{F}_q^*$, and an integer $s \in \{1,2, \dots, l \}$, let \begin{eqnarray*} e( x, y, a, m_s ) & = & \{ ( x + \alpha_1 (m_s a), y + \alpha_1 (m_s a^2 ), 1 ), (x + \alpha_2 (m_s a ), y + \alpha_2 (m_s a^2 ), 2), \\ & ~ & \dots, (x + \alpha_r (m_s a ), y + \alpha_r ( m_s a^2 ), r) \}. \end{eqnarray*} We define $\mathcal{H}$ to be the $r$-uniform hypergraph with vertex set \[ V( \mathcal{H} ) = \{ ( x, y, i ) : x, y \in \mathbb{F}_q, 1 \leq i \leq r \} \] and edge set \[ E( \mathcal{H} ) = \{ e( x, y, a, m_s ) : x, y \in \mathbb{F}_q, a \in \mathbb{F}_q^*, s \in \{1, \dots l \} \}. \] The vertex set of $\mathcal{H}$ can be written as $V( \mathcal{H} ) = V_1 \cup \dots \cup V_r$ so $\mathcal{H}$ is $r$-partite. \begin{lemma}\label{super linear} The hypergraph $\mathcal{H}$ is linear. \end{lemma} \begin{proof} Suppose $e(x_1, y_1, a_1, m_s)$ and $e(x_2, y_2, a_2, m_t )$ are edges of $\mathcal{H}$ that share at least two vertices, say $(u_i, v_i, i)$ in $V_i$ and $(u_j, v_j, j)$ in $V_j$, where $1 \leq i < j \leq r$. We have \begin{center} $u_i = x_1 + \alpha_i ( m_s a_1 ) = x_2 + \alpha_i ( m_t a_2 )$, ~~$v_i = y_1 + \alpha_i ( m_s a_1^2 ) = y_2 + \alpha_i ( m_t a_2^2)$, \medskip $u_j = x_1 + \alpha_j (m_s a_1 ) = x_2 + \alpha_j (m_t a_2 )$, ~~$v_j = y_1 + \alpha_j (m_s a_1^2 ) = y_2 + \alpha_j (m_t a_2^2)$. \end{center} Taking differences yields \begin{equation*}\label{super linear eq1} u_i - u_j = m_s a_1 ( \alpha_i - \alpha_j ) = m_t a_2 ( \alpha_i - \alpha_j) \end{equation*} and \begin{equation*}\label{super linear eq2} v_i - v_j = m_s a_1^2 ( \alpha_i - \alpha_j ) = m_t a_2^2 ( \alpha_i - \alpha_j). \end{equation*} Since $\alpha_i$ and $\alpha_j$ are distinct, we may cancel $\alpha_i - \alpha_j$ to obtain $m_s a_1 = m_t a_2$ and $m_s a_1^2 = m_t a_2^2$. All of the elements $m_s, m_t, a_1$, and $a_2$ are not zero so that this pair of equations implies that $a_1 = a_2$ and $m_s = m_t$. It then follows from $x_1 + \alpha_i (m_s a_1 ) = x_2 + \alpha_i (m_t a_2 )$ that $x_1 = x_2$ and similarly, $y_1 = y_2$. We conclude that $e( x_1, y_1, a_1, m_s) = e( x_2, y_2, a_2, m_t)$ and so $\mathcal{H}$ is linear. \end{proof} \bigskip From Lemma \ref{super linear} we see that $\mathcal{H}$ has $l q^2 (q - 1)$ edges and it is clear that $\mathcal{H}$ has $r q^2$ vertices. When $r = 2$, $\mathcal{H}$ is a graph. \bigskip \noindent \textbf{Example}~ Let $r = 2$, $l = 1$, $q \geq 3$ be any power of an odd prime, $\alpha_1 = 0$, $\alpha_2 = 1$, and $m_1 = 1$. In this case, $\mathcal{H}$ is a $(q - 1)$-regular bipartite graph with $q^2$ vertices in each part. It can be shown that $\mathcal{H}$ is isomorphic to a subgraph of the incidence graph of the projective plane $PG(2,q)$. In particular, $\mathcal{H}$ is $C_4$-free. \bigskip In the terminology of forbidden subgraphs, Lemma \ref{super linear} tells us that $\mathcal{H}$ is $C_2$-free. \begin{lemma}\label{super c3} If $l = 1$, then the hypergraph $\mathcal{H}$ is $C_3$-free. \end{lemma} \begin{proof} This is certainly true if $r = 2$ as in this case $\mathcal{H}$ is a bipartite graph. Assume that $r \geq 3$ and suppose $\mathcal{H}$ contains a $C_3$. By Lemma \ref{super linear}, there are three distinct edges $e(x_1, y_1, a_1, m_1)$, $e(x_2, y_2, a_2,m_1)$, and $e(x_3, y_3, a_3, m_1)$ and integers $1 \leq i < j < k \leq r$ such that \begin{center} $(x_1 + \alpha_i ( m_1 a_1 ), y_1 + \alpha_i ( m_1 a_1^2), i) = ( x_2 + \alpha_i (m_1 a_2 ), y_2 + \alpha_i (m_1 a_2^2 ), i )$, \medskip $(x_2 + \alpha_j (m_1 a_2 ), y_2 + \alpha_j (m_1 a_2^2 ), j) = ( x_3 + \alpha_j (m_1 a_3 ), y_3 + \alpha_j (m_1 a_3^2 ), j )$, \medskip $(x_3 + \alpha_k (m_1 a_3 ), y_3 + \alpha_k (m_1 a_3^2 ), k) = ( x_1 + \alpha_k (m_1 a_1 ), y_1 + \alpha_k (m_1 a_1^2 ), k )$. \end{center} The first equation represents the vertex in $V_i$ that is the unique vertex in the intersection of the edges $e( x_1, y_1, a_1, m_1)$ and $e(x_2, y_2, a_2, m_1)$. By considering the equations coming from the first components, we get \begin{eqnarray*} 0 & = & (x_1 - x_2) + (x_2 - x_3) + (x_3 - x_1) \\ & = & m_1 \alpha_i ( a_2 - a_1) + m_1 \alpha_j (a_3 - a_2) + m_1 \alpha_k ( a_1 - a_3). \end{eqnarray*} Similarly, the equations from the second components give \begin{equation*} 0 = m_1 \alpha_i ( a_2^2 - a_1^2 ) + m_1 \alpha_j ( a_3^2 - a_2^2) + m_1 \alpha_k (a_1^2 - a_3^2 ). \end{equation*} By Lemma \ref{arithmetic l1} with $\alpha= m_1 \alpha_i$, $\beta = m_1 \alpha_j$, and $\gamma = m_1 \alpha_k$, we have $a_1 = a_2 = a_3$. Since \[ (x_1 + \alpha_i (m_1 a_1 ), y_1 + \alpha_i (m_1 a_1^2 ), i) = ( x_2 + \alpha_i (m_1 a_2 ), y_2 + \alpha_i (m_1 a_2^2 ), i ), \] we obtain $x_1 = x_2$ and $y_1 = y_2$ which gives $e(x_1, y_1, a_1, m_1) = e(x_2, y_2, a_2, m_1)$, a contradiction. \end{proof} \bigskip For the next sequence of lemmas we will require some additional notation and terminology. For $1 \leq i \neq j \leq r$, let $\mathcal{H} (V_i, V_j )$ be the bipartite graph with parts $V_i$ and $V_j$ where $(u, v, i ) \in V_i$ is adjacent to $(u', v', j ) \in V_j$ if and only if there is an edge $e \in E( \mathcal{H} )$ such that \begin{equation}\label{adjacencies} \{ (u, v, i ), (u', v ', j) \} \subseteq e. \end{equation} An equivalent way of defining adjacencies in $\mathcal{H} (V_i, V_j )$ is to say that $(u, v, i )$ is adjacent to $(u', v ', j)$ if and only if there are elements $x,y \in \mathbb{F}_q$, $a \in \mathbb{F}_q^*$, and an $s \in \{1,2, \dots, l \}$ such that \begin{equation}\label{adj 2} u' = u + m_s ( \alpha_j - \alpha_i ) a \mbox{~~and~~} v' = v + m_s ( \alpha_j - \alpha_i ) a^2. \end{equation} This is because if (\ref{adjacencies}) holds with $e = e( x, y, a, m_s)$, then \begin{center} $u = x + \alpha_i (m_s a )$, $v = y + \alpha_i (m_s a^2 )$, $u' = x + \alpha_j (m_s a)$, and $v' = y + \alpha_j (m_s a^2 )$. \end{center} For three distinct integers $i, j$, and $k$ with $1 \leq i, j, k \leq r$, let $\mathcal{H} (V_i, V_j, V_k)$ be the union of the graphs $\mathcal{H} ( V_i, V_j)$, $\mathcal{H} (V_j, V_k)$, and $\mathcal{H} (V_k, V_i )$. For any $x,y \in \mathbb{F}_q$ and $a \in \mathbb{F}_q^*$, the edge $e(x,y, a, m_s)$ in $\mathcal{H}$ is said to have \emph{color} $m_s$. An edge $f$ in the graph $\mathcal{H} (V_i,V_j)$ or $\mathcal{H} (V_i,V_j, V_k)$ is said to have \emph{color} $m_s$ if the unique edge $e$ in $\mathcal{H}$ with $f \subseteq e$ has color $m_s$. The edge $e$ is unique by Lemma \ref{super linear}. \begin{lemma}\label{c4 free in one color} For any $1 \leq i \neq j \leq r$ and $1 \leq s \leq l$, the edges of color $m_s$ in the graph $\mathcal{H} (V_i, V_j)$ induce a $K_{2,2}$-free graph. \end{lemma} \begin{proof} Suppose $\{ (u_1, v_1, i), (u_2, v_2, j), (u_3, v_3, i), (u_4, v_4,j) \}$ forms a $K_{2,2}$ in $\mathcal{H} (V_i, V_j)$ where each of the edges of this $K_{2,2}$ have color $m_s$. Using (\ref{adj 2}) as our condition for adjacency in $\mathcal{H} (V_i, V_j)$, we have \begin{center} $u_2 = u_1 + m_s ( \alpha_j - \alpha_i) a_1 = u_3 + m_s ( \alpha_j - \alpha_i )a_2$, \medskip $v_2= v_1 + m_s ( \alpha_j - \alpha_i ) a_1^2 = v_3 + m_s ( \alpha_j - \alpha_i )a_2^2$, \medskip $u_4 = u_1 + m_s ( \alpha_j - \alpha_i ) a_3 = u_3 + m_s ( \alpha_j - \alpha_i ) a_4$, \medskip $v_4 = v_1 + m_s ( \alpha_j - \alpha_i ) a_3^2 = v_3 + m_s ( \alpha_j - \alpha_i ) a_4^2$ \end{center} for some $a_1, a_2, a_3, a_4 \in \mathbb{F}_q^*$. By the first and third set of equations, \[ m_s^{-1} (\alpha_j - \alpha_i)^{-1} (u_1 - u_3) = a_2 - a_1 = a_4 - a_3. \] Similarly, by the second and fourth set of equations, $a_2^2 - a_1^2 = a_4^2 - a_3^2$. By Lemma \ref{arithmetic l2}, either $(a_1, a_4) = ( a_2, a_3)$ or $(a_1, a_4) = (a_3, a_2)$. If $a_1 = a_2$, then $u_1 = u_3$ by the first set of equations and $v_1 = v_3$ by the second set of equations. This implies $(u_1, v_1, i)$ and $(u_3, v_3, i)$ are the same vertex which is a contradiction. If $a_1 = a_3$, then by taking differences of the first and third set of equations we get $u_2 = u_4$. By taking differences of the second and fourth set of equations we get $v_2 = v_4$. This implies that the vertices $(u_2, v_2, j)$ and $(u_4, v_4, j)$ are the same which is another contradiction. \end{proof} \begin{lemma}\label{two part case} If $1 \leq i \neq j \leq r$, then for any $l \geq 1$, the graph $\mathcal{H}(V_i, V_j)$ is $K_{2,2l^2 - l + 1}$-free. \end{lemma} \begin{proof} If $l = 1$, then we are done by Lemma \ref{c4 free in one color} as all of the edges in $\mathcal{H} (V_i, V_j)$ will have the same color, namely $m_1$. Assume that $l \geq 2$ and suppose $u,v, w_1, \dots, w_{2l^2 - l + 1}$ are the vertices of of $K_{2,2l^2 - l + 1}$ in $\mathcal{H} (V_i, V_j)$ with $u, v \in V_i$ and $w_1, \dots, w_{2l^2 - l + 1} \in V_j$. Since $\frac{2l^2 - l + 1}{l} > 2l - 1$, there are at least $2l$ edges of the form $\{u, w_z \}$ that have the same color. Without loss of generality, assume that for $1 \leq z \leq 2l$, the edges $\{ u, w_z \}$ have color $m_1$. Let $W = \{w_1, \dots, w_{2l } \}$. By Lemma \ref{c4 free in one color}, there cannot be two distinct edges, both with color $m_1$, that are incident with $v$ and a vertex in $W$. Thus, at least $2l - 1$ of the edges between $W$ and $v$ have a color other than $m_1$. As $\frac{2l-1}{l-1} > 2$, there must be three edges between $W$ and $v$ that all have the same color. Without loss of generality, assume that $\{v, w_1 \}$, $\{v, w_2 \}$, and $\{v, w_3 \}$ all have color $m_2$. Let $v = (x_v, y_v, i )$, $u = (x_u, y_u, i)$, and $w_z = ( x_{ w_z}, y_{w_z}, j)$ for $z \in \{1,2, 3 \}$. For each $z \in \{1,2,3 \}$, there are elements $a_z, b_z \in \mathbb{F}_q^*$ with \[ x_{w_z} = x_u + m_1 ( \alpha_j - \alpha_i ) a_z = x_v + m_2 ( \alpha_j - \alpha_i ) b_z \] and \[ y_{w_z} = y_u + m_1 ( \alpha_j - \alpha_i ) a_z^2 = y_v + m_2 ( \alpha_j - \alpha_i ) b_z^2. \] From these equations we obtain \begin{eqnarray*} x_v - x_u = m_1 ( \alpha_j - \alpha_i )a_1 + m_2 ( \alpha_i - \alpha_j)b_1 & = & m_1 ( \alpha_j - \alpha_i )a_2 + m_2 ( \alpha_i - \alpha_j)b_2 \\ & = & m_1 ( \alpha_j - \alpha_i )a_3 + m_2 ( \alpha_i - \alpha_j)b_3 \end{eqnarray*} and \begin{eqnarray*} y_v - y_u = m_1 ( \alpha_j - \alpha_i )a_1^2 + m_2 ( \alpha_i - \alpha_j)b_1^2 & = & m_1 ( \alpha_j - \alpha_i )a_2^2 + m_2 ( \alpha_i - \alpha_j)b_2^2 \\ & = & m_1 ( \alpha_j - \alpha_i )a_3^2 + m_2 ( \alpha_i - \alpha_j)b_3^2. \end{eqnarray*} We want to apply Lemma \ref{arithmetic l3} with $\alpha = m_1 ( \alpha_j - \alpha_i)$ and $\beta = m_2 ( \alpha_i - \alpha_j)$ but before doing so, we verify that we have satisfied the hypothesis of Lemma \ref{arithmetic l3}. Since $m_i \neq 0$, and $\alpha_i - \alpha_j \neq 0$, both $\alpha$ and $\beta$ are not zero. If $\alpha + \beta = 0$, then \[ 0 = m_1 ( \alpha_j - \alpha_i ) + m_2 ( \alpha_i - \alpha_j ) = \alpha_i ( m_2 - m_1) - \alpha_j (m_2 - m_1) \] so $\alpha_i (m_2 - m_1) = \alpha_j ( m_2 - m_1)$. As $m_1$ and $m_2$ are distinct, $m_2 - m_1 \neq 0$ so $\alpha_i = \alpha_j$ which contradicts the fact that $\alpha_i$ and $\alpha_j$ are distinct. We conclude that $\alpha + \beta \neq 0$ and Lemma \ref{arithmetic l3} applies so we may assume that $a_1 = b_1$ and $a_2 = b_2$. These two equalities together with \[ m_1 ( \alpha_j - \alpha_i )a_1 + m_2 ( \alpha_i - \alpha_j)b_1 = m_1 ( \alpha_j - \alpha_i )a_2 + m_2 ( \alpha_i - \alpha_j)b_2 \] give \[ (m_1 - m_2) ( \alpha_j - \alpha_i ) a_1 = ( m_1 - m_2)( \alpha_j - \alpha_i ) a_2. \] Therefore, $a_1 = a_2$. From the equations \begin{center} $x_{w_1} = x_u + m_1 ( \alpha_j - \alpha_i) a_1$ ~ and ~ $x_{w_2} = x_u + m_1 (\alpha_j - \alpha_i ) a_2$ \end{center} we get $x_{w_1} = x_{w_2}$. A similar argument gives $y_{w_1} = y_{w_2}$, thus \[ w_1 = ( x_{w_1}, y_{w_1}, j) = (x_{w_2}, y_{w_2}, j ) = w_2 \] which provides the needed contradiction. We conclude that $\mathcal{H} ( V_i, V_j )$ is $K_{2, 2l^2 - l + 1}$-free. \end{proof} \begin{lemma}\label{three part case} Let $i, j$, and $k $ be distinct integers with $1 \leq i,j, k \leq r$. For any $l \geq 1$, the graph $\mathcal{H}(V_i, V_j, V_k)$ does not contain a $K_{2, 2l^2 + 1}$ with one vertex in $V_i$, one vertex in $V_j$, and $2l^2 + 1$ vertices in $V_k$. \end{lemma} \begin{proof} We proceed as in the proof of Lemma \ref{two part case}. Suppose $\{u, v \}$ and $\{w_1, \dots, w_{2l^2 + 1} \}$ are the parts of the $K_{2, 2l^2 + 1}$ with $u \in V_i$, $v \in V_j$, and $w_1, \dots, w_{2l^2 + 1} \in V_k$. As $\frac{2l^2 + 1}{l} > 2l$, we can assume that the edges $\{ u, w_1 \}, \dots, \{ u, w_{2l + 1 } \}$ all have the same color, say $m_1$. Since $\frac{2l+1}{l} > 2$, we can assume that at least three of the edges $\{ v, w_1 \}, \dots, \{ v, w_{2l + 1} \}$ have the same color. Let $\{v, w_1 \}, \{ v, w_2 \}$, and $\{v, w_3 \}$ have color $m_s$. As in the proof of Lemma \ref{two part case}, we have elements $a_1, a_2, a_3, b_1, b_2, b_3 \in \mathbb{F}_q^*$ such that \begin{eqnarray*} m_1 ( \alpha_k - \alpha_i )a_1 + m_s ( \alpha_j - \alpha_k)b_1 & = & m_1 ( \alpha_k - \alpha_i )a_2 + m_s ( \alpha_j - \alpha_k)b_2 \\ & = & m_1 ( \alpha_k - \alpha_i )a_3 + m_s ( \alpha_j - \alpha_k)b_3, \end{eqnarray*} and \begin{eqnarray*} m_1 ( \alpha_k - \alpha_i )a_1^2 + m_s ( \alpha_j - \alpha_k)b_1^2 & = & m_1 ( \alpha_k - \alpha_i )a_2^2 + m_s ( \alpha_j - \alpha_k)b_2^2 \\ & = & m_1 ( \alpha_k - \alpha_i )a_3^2 + m_s ( \alpha_j - \alpha_k)b_3^2. \end{eqnarray*} If $s =1$ (so $m_s = m_1$), then we apply Lemma \ref{arithmetic l3} with $\alpha = m_1 ( \alpha_k - \alpha_i )$ and $\beta = m_1 ( \alpha_j - \alpha_k)$ noting that $\alpha + \beta = m_1 ( \alpha_j - \alpha_i ) \neq 0$. If $s \neq 1$, then without loss of generality, assume that $s = 2$. We apply Lemma \ref{arithmetic l3} with \[ \alpha = m_1 ( \alpha_k - \alpha_i) ~ \mbox{and} ~ \beta = m_2 ( \alpha_j - \alpha_k). \] Here we recall that by (\ref{condition}), the $m_t$'s have been chosen so that $m_1 ( \alpha_k - \alpha_i ) \neq m_2 ( \alpha_k - \alpha_j)$ so $\alpha + \beta \neq 0$. In both cases, we can apply Lemma \ref{arithmetic l3} to get $a_1 = b_1$ and $a_2 = b_2$. The remainder of the proof is then identical to that of Lemma \ref{two part case}. \end{proof} \bigskip \begin{proof}[Proof of the lower bound in Theorem \ref{main thm} and Theorem \ref{main thm2}] Let $r \geq 3$ be an integer and $l = 1$. Let $q \geq r$ be a power of an odd prime and $\alpha_1, \dots, \alpha_r$ be distinct elements of $\mathbb{F}_q$. Let $m_1 = 1 \in \mathbb{F}_q$ and note that (\ref{condition}) holds for $\alpha_1, \dots, \alpha _r$ and $m_1$ since in this case, (\ref{condition}) is equivalent to the statement that $\alpha_1, \dots, \alpha_r$ are all different. Let $\mathcal{H}$ be the corresponding hypergraph defined at the beginning of Section \ref{the H}. By Lemmas \ref{super linear} and \ref{super c3}, $\mathcal{H}$ is $\{C_2, C_3 \}$-free. Now we show that $\mathcal{H}$ is $K_{2, 2r - 3}$-free. Suppose $\{u, v \}$ and $W = \{w_1, \dots, w_{2r - 3 } \}$ are the parts of a $K_{2, 2r - 3}$ in $\mathcal{H}$. If $\{ u, v \} \subset V_i$ for some $i \in \{1,2, \dots, r \}$, then by Lemma \ref{c4 free in one color}, $| V_j \cap W | \leq 1$ for each $j \in \{1,2, \dots, r \} \backslash \{i \}$. This is impossible since $2r - 3 > r - 1$ as $r > 2$. Now suppose $u \in V_i$ and $v \in V_j$ where $1 \leq i < j \leq r$. By Lemma \ref{three part case}, $| V_k \cap W | \leq 2$ for each $k \in \{1,2, \dots,r \} \backslash \{ i, j \}$. Once again this is impossible since $2r - 3 > 2 (r - 2)$. This shows that $\mathcal{H}$ is $K_{2, 2r-3 }$-free. The proof is completed by observing that $\mathcal{H}$ has $q^2$ vertices in each part $V_1, \dots, V_r$ and $\mathcal{H}$ has $q^2 (q - 1)$ edges. \end{proof} \bigskip \begin{proof}[Proof of Theorem \ref{thm3}] Let $r \geq 3$ and let $l$ be any integer with $2l + 1 \geq r$. This assumption on $l$ implies that \begin{equation}\label{l eq} (r - 2)(2l^2) \leq (r - 1) ( 2l^2 - l). \end{equation} Let $q$ be a power of an odd prime chosen large enough so that there are $r$ distinct elements $\alpha_1, \dots, \alpha_r \in \mathbb{F}_q$ and $l$ distinct elements $m_1, \dots, m_l \in \mathbb{F}_q^*$ that satisfy condition (\ref{condition}). We claim that choosing $q \geq 2 l r^3$ is sufficient for such elements to exist. Indeed, we first choose $\alpha_1, \dots, \alpha_r$ so that these elements are all distinct. We then choose the $m_z$'s. If we have chosen $m_1, \dots, m_t$ so that (\ref{condition}) holds for $\alpha_1, \dots, \alpha_r$ and $m_1, \dots, m_t$, then as long as we choose $m_{t+1}$ so that $m_{t + 1} \neq m_z ( \alpha_k - \alpha_j) (\alpha_k - \alpha_i)^{-1}$, then (\ref{condition}) holds for $\alpha_1, \dots, \alpha_r$ and $m_1, \dots, m_t, m_{t + 1}$. There are at most $t r^3 $ products of the form $m_z ( \alpha_k - \alpha_j ) ( \alpha_k - \alpha_i )^{-1}$ with $z \in \{1, \dots, t \}$ and $1 \leq i, j, k \leq r$ so $q \geq 2 l r^3$ is enough to choose $m_{t+1}$. Having chosen $\alpha_1, \dots, \alpha_r$ and $m_1, \dots, m_l$, let $\mathcal{H}$ be the corresponding hypergraph. By Lemma \ref{super linear}, $\mathcal{H}$ is $C_2$-free. Now we show that $\mathcal{H}$ is $K_{2, ( r - 1)( 2l^2 - l ) + 1 }$-free. Suppose $\{u,v \}$ and $W = \{w_1, \dots, w_t \}$ are the parts of a $K_{2,t}$ in $\mathcal{H}$. If $\{u, v \} \subset V_i$ for some $i$, then by Lemma \ref{two part case}, $| V_j \cap W | \leq 2l^2 - l$ for each $j \in \{1,2, \dots, r \} \backslash \{ i \}$ so $t \leq (r - 1) ( 2l^2 - l )$. If $u \in V_i$ and $v \in V_j$ for some $1 \leq i < j \leq r$, then by Lemma \ref{three part case}, $| V_k \cap W | \leq 2l^2 $ for each $k \in \{1,2, \dots, r \} \backslash \{ i,j \}$ so $t \leq (r - 2) (2l^2)$ thus by (\ref{l eq}), $t \leq (r - 1)(2l^2 - l)$. We conclude that $\mathcal{H}$ is $K_{2, (r - 1) ( 2l^2 - l )+1}$-free. The proof of Theorem \ref{thm3} is completed by observing that $\mathcal{H}$ has $rq^2$ vertices and $l q^2 ( q - 1)$ edges. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding Remarks and Acknowledgments} It was pointed out to the author by Cory Palmer that the argument used to prove Theorem \ref{ub} can be used to show that \[ \textup{ex}_r ( n, \{ C_2, K_{2,t + 1} \} ) \leq \frac{ \sqrt{ 2 (t + 1) } }{r } n^{3/2} + \frac{n}{r} \] for all $r \geq 3$ and $t \geq 1$. This shows that the lower bound in Theorem \ref{thm3} gives the correct order of magnitude but determining the correct constant could be difficult. It is known that in the case of graphs, $\textup{ex}_2 ( n, K_{2, t + 1} ) = \frac{1}{2} \sqrt{ t} n^{3/2} + o( n^{3/2} )$ (see F\"{u}redi \cite{fur}). The author would like to thank Cory Palmer and Jacques Verstra\"{e}te for helpful discussions. \begin{thebibliography}{10} \bibitem{aksv} P.\ Allen, P.\ Keevash, B.\ Sudakov, J.\ Verstra\"{e}te, Tur\'{a}n numbers of bipartite graphs plus an odd cycle, {\em J.\ Combin.\ Theory Ser.\ B} 106 (2014), 134--162. \bibitem{as} N.\ Alon, C.\ Shikhelman, Many $T$ copies in $H$-free graphs, {\em J.\ Combin.\ Theory Ser.\ B} 121 (2016), 146--172. \bibitem{bg} B.\ Bollob\'{a}s, E.\ Gy\H{o}ri, Pentagons vs.\ triangles, {\em Discrete Math}.\ 308 (2008), no.\ 19, 4332--4336. \bibitem{cgj} C.\ Collier-Cartaino, N.\ Graber, T.\ Jiang, Linear Tur\'{a}n numbers of linear cycles and cycle-complete graph Ramsey numbers, to appear in {\em Combin.\ Probab.\ Comput}.\ \bibitem{gp} D.\ Gerbner, C.\ Palmer, Extremal Results for Berge Hypergraphs, {\em SIAM J.\ Discrete Math}.\ 31 (2017), no.\ 4, 2314--2327. \bibitem{fur} Z.\ F\"{u}redi, New asymptotics for bipartite Tur\'{a}n numbers, {\em J.\ Combin.\ Theory Ser.\ A} 75(1) (1996), 141--144. \bibitem{fo} Z.\ F\"{u}redi, L.\ \"{O}zkahya, On 3-uniform hypergraphs without a cycle of a given length, {\em Discrete Appl.\ Math}.\ 216 (2017), part 3, 582--588. \bibitem{gl2} E.\ Gy\H{o}ri, N.\ Lemons, 3-uniform hypergraphs avoiding a given odd cycle {\em Combinatorica} 32 (2012), no.\ 2, 187--203. \bibitem{gl1} E.\ Gy\H{o}ri, N.\ Lemons, Hypergraphs with no cycle of length 4, {\em Discrete Math}.\ 312 (2012), no.\ 9, 1518--1520. \bibitem{gl} E.\ Gy\H{o}ri, N.\ Lemons, Hypergraphs with no cycle of a given length, {\em Combin.\ Probab.\ Comput}.\ 21 (2012), no.\ 1-2, 193--201. \bibitem{gli} E.\ Gy\H{o}ri, H.\ Li, The maximum number of triangles in $C_{2k + 1}$-free graphs, {\em Combin.\ Probab.\ Comput}.\ 21 (2012), no.\ 1-2, 187--191. \bibitem{gkl} E.\ Gy\H{o}ri, G.\ Katona, N.\ Lemons, Hypergraph extensions of the Erd\H{o}s-Gallai Theorem {\em Electron.\ Notes Discrete Math}.\ 36 (2010) 655--662. \bibitem{lv} F.\ Lazebnik, J. Verstra\"{e}te, On hypergraphs of girth five, {\em Electron.\ J. of Combin}., {\bf 10}, (2003), \#R25. \bibitem{ruzsa} I.\ Ruzsa, Solving a linear equation in a set of integers.\ I.\ {\em Acta Arith}.\ 65 (1993), no.\ 3, 259--282. \bibitem{tv} C.\ Timmons, J.\ Verstra\"{e}te, A counterexample to sparse removal, {\em European J.\ Combin}.\ 44 (2015), part A, 77--86. \bibitem{jv} J.\ Verstra\"{e}te, personal communication. \end{thebibliography} \end{document}