% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P43}{19(4)}{2012} % 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} \allowdisplaybreaks % 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}}} \newcommand{\prob}{\mathbb{P}} \newcommand{\expect}{\mathbb{E}} \newcommand{\variance}{\textrm{var}} \newcommand{\rn}{\mathbb{R}} \newcommand{\integers}{\mathbb{Z}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\eps}{\epsilon} \newcommand{\points}{\mathcal{P}} \newcommand{\lines}{\mathcal{L}} \newcommand{\incidence}{\mathcal{I}} \newcommand{\nn}{\mathbb{N}} % 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 An ordered Tur\'{a}n problem\\ for bipartite graphs} % 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\\ \small Department of Mathematics\\[-0.8ex] \small University of California San Diego\\[-0.8ex] \small La Jolla, CA 92093\\ \small\tt ctimmons@ucsd.edu %\and %Forgotten Second Author \qquad Forgotten Third Author\\ %\small School of Hard Knocks\\[-0.8ex] %\small University of Western Nowhere\\[-0.8ex] %\small Nowhere, Australasiaopia\\ %\small\tt \{fsa,fta\}@uwn.edu.ao } % \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{June 22, 2012}{Dec 2, 2012}{Dec 13, 2012}\\ \small Mathematics Subject Classification: 05C35} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Let $F$ be a graph. A graph $G$ is \emph{$F$-free} if it does not contain $F$ as a subgraph. The \emph{Tur\'{a}n number of $F$}, written $\textrm{ex}(n,F)$, is the maximum number of edges in an $F$-free graph with $n$ vertices. The determination of Tur\'{a}n numbers of bipartite graphs is a challenging and widely investigated problem. In this paper we introduce an ordered version of the Tur\'{a}n problem for bipartite graphs. Let $G$ be a graph with $V(G) = \{1, 2, \dots , n \}$ and view the vertices of $G$ as being ordered in the natural way. A \emph{zig-zag $K_{s,t}$}, denoted $Z_{s,t}$, is a complete bipartite graph $K_{s,t}$ whose parts $A = \{n_1 < n_2 < \dots < n_s \}$ and $B = \{m_1 < m_2 < \dots < m_t \}$ satisfy the condition $n_s < m_1$. A \emph{zig-zag $C_{2k}$} is an even cycle $C_{2k}$ whose vertices in one part precede all of those in the other part. Write $\mathcal{Z}_{2k}$ for the family of zig-zag $2k$-cycles. We investigate the Tur\'{a}n numbers $\textrm{ex}(n,Z_{s,t})$ and $\textrm{ex}(n,\mathcal{Z}_{2k})$. In particular we show $\textrm{ex}(n, Z_{2,2}) \leq \frac{2}{3}n^{3/2} + O(n^{5/4})$. For infinitely many $n$ we construct a $Z_{2,2}$-free $n$-vertex graph with more than $(n - \sqrt{n} - 1) + \textrm{ex} (n,K_{2,2})$ edges. % keywords are optional \bigskip\noindent \textbf{Keywords:} Tur\'{a}n problem; bipartite graphs; \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\mathcal{F}$ be a family of graphs. A graph $G$ is \emph{$\mathcal{F}$-free} if $G$ contains no subgraph isomorphic to a graph in $\mathcal{F}$. The \emph{Tur\'{a}n number} of $\mathcal{F}$ is the maximum number of edges in an $n$-vertex graph that is $\mathcal{F}$-free. Write $\textrm{ex}(n, \mathcal{F})$ for this maximum and when $\mathcal{F}$ consists of a single graph $F$, write $\textrm{ex}(n,F)$ instead of $\textrm{ex}(n, \{F \})$. Tur\'{a}n problems have a rich history in extremal graph theory. While many Tur\'{a}n problems have been solved, there are still many open problems such as determining the Tur\'{a}n number of $C_8$, the Tur\'{a}n number of $K_{4,4}$, and the Tur\'{a}n number of the family $\{C_3,C_4 \}$. The earliest result in this field is Mantel's Theorem proved in 1907. Mantel proved $\textrm{ex}(n,K_3) = \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil$ and the $n$-vertex $K_3$-free graphs with $\textrm{ex}(n,K_3)$ edges are complete bipartite graphs with part sizes as equal as possible. In 1940 Tur\'{a}n extended Mantel's Theorem and determined the Tur\'{a}n number of $K_t$, $t \geq 3$. Tur\'{a}n's Theorem is considered to be the first theorem of extremal graph theory. When $\mathcal{F}$ consists of non-bipartite graphs the Erd\H{o}s-Stone-Simonovits Theorem determines $\textrm{ex}(n, \mathcal{F} )$ asymptotically. \begin{theorem}[Erd\H{o}s, Stone, Simonovits]\label{ess} Let $\mathcal{F}$ be a family of graphs and let $r = \min_{F \in \mathcal{F}} \chi (F)$. If $r \geq 2$ then \begin{equation*} \emph{ex}(n, \mathcal{F}) = \left( 1 - \frac{1}{r-1} \right) \binom{n}{2} + o(n^2). \end{equation*} \end{theorem} When $\mathcal{F}$ contains bipartite graphs, the Erd\H{o}s-Stone-Simonovits Theorem gives \noindent $\textrm{ex}(n , \mathcal{F} ) = o(n^2)$. More precise results can be obtained by using different counting arguments and algebraic constructions. In this paper we introduce an ordered Tur\'{a}n problem for bipartite graphs. Given an $n$-vertex graph $G$, label its vertices with the numbers $[n]:= \{1, 2, \dots , n \}$ using each number exactly once. This induces a natural ordering of the vertices of $G$ and we use this ordering to distinguish between different types of a fixed subgraph. This idea is not new to Tur\'{a}n theory. Czipszer, Erd\H{o}s, and Hajnal \cite{CEH} and Dudek and R\"{o}dl \cite{DR} investigated Tur\'{a}n problems for increasing paths of length $k$. An increasing path of length $k$ is a sequence of $k$ edges $n_1 n_2 , n_2 n_3, \dots , n_{k}n_{k+1}$ such that $n_i < n_{i+1}$ for $1 \leq i \leq k$. Let $H$ be a bipartite graph with parts $A$ and $B$. Let $f: \{1,2 \} \rightarrow \{A,B \}$ be a bijection and call $f$ an \emph{ordering} of the parts. A \emph{zig-zag} $H$ relative to $f$ and bipartition $\{A,B\}$ is a copy of $H$ in $G$ such that all of the vertices in $f(1)$ precede all of the vertices in $f(2)$ in the ordering of $V(G) = [n]$. %The notation may be a bit awkward but it does indicate how one could generalize the definition of a zig-zag $r$-partite graph for $r \geq 3$. One of the reason we consider zig-zag complete bipartite graphs as opposed to complete bipartite graphs that do not zig-zag is because there exist graphs with $\frac{1}{8}n^2 + o(n^2)$ edges that do not contain increasing paths of length 2. One such graph is obtained by joining each even vertex to all of the odd vertices that come after it in the ordering. If a complete bipartite graph does not zig-zag then it will contain an increasing path of length 2. In contrast, if a zig-zag bipartite graph is forbidden then the number of edges will not be quadratic in $n$. %The increasing paths of length $k$ fit nicely into this framework. Our focus will be on zig-zag complete bipartite graphs and zig-zag even cycles so we specialize the notation. As before let $G$ be an $n$-vertex graph with $V(G) = [n]$ and consider the vertices of $G$ as being ordered. A \emph{zig-zag $K_{s,t}$}, which will be denoted by $Z_{s,t}$, is a $K_{s,t}$ whose parts $A = \{n_1 < n_2 < \dots < n_s \}$ and $B = \{ m_1 < m_2 < \dots < m_t \}$ satisfy the condition $n_s < m_1$. A \emph{zig-zag $2k$-cycle}, denoted $Z_{2k}$, is a $2k$-cycle whose vertices are $\{ n_1 < n_2 < \dots < n_{2k} \}$ and $A = \{n_1, \dots , n_k \}$, $B = \{n_{k + 1}, \dots , n_{2k} \}$ is the bipartition. Let $\mathcal{Z}_{2k}$ be the family of all zig-zag $2k$-cycles. Observe that for $k=2$, $\mathcal{Z}_{2k}$ consists of a single graph and we simply write $Z_4$ for this family. \pagebreak \begin{center} \begin{picture}(400,40) \put(0,20){\circle*{3}} \put(25,20){\circle*{3}} \put(50,20){\circle*{3}} \put(75,20){\circle*{3}} \put(-4,10){\footnotesize{$n_1$}} \put(21,10){\footnotesize{$n_2$}} \put(46,10){\footnotesize{$n_3$}} \put(71,10){\footnotesize{$n_4$}} \qbezier(0,20)(25,40)(50,20) \qbezier(0,20)(37,50)(75,20) \qbezier(25,20)(37,30)(50,20) \qbezier(25,20)(50,40)(75,20) \put(16,-4){$Z_4=Z_{2,2}$} \put(125,20){\circle*{3}} \put(150,20){\circle*{3}} \put(175,20){\circle*{3}} \put(200,20){\circle*{3}} \put(225,20){\circle*{3}} \put(250,20){\circle*{3}} \put(121,10){\footnotesize{$n_1$}} \put(146,10){\footnotesize{$n_2$}} \put(171,10){\footnotesize{$n_3$}} \put(196,10){\footnotesize{$n_4$}} \put(221,10){\footnotesize{$n_5$}} \put(246,10){\footnotesize{$n_6$}} \qbezier(125,20)(187,70)(250,20) \qbezier(125,20)(167,50)(200,20) \qbezier(150,20)(175,40)(200,20) \qbezier(150,20)(187,50)(225,20) \qbezier(175,20)(200,40)(225,20) \qbezier(175,20)(212,50)(250,20) \put(155,-4){A member of $\mathcal{Z}_6$} \put(300,20){\circle*{3}} \put(325,20){\circle*{3}} \put(350,20){\circle*{3}} \put(375,20){\circle*{3}} \put(400,20){\circle*{3}} \put(296,10){\footnotesize{$n_1$}} \put(321,10){\footnotesize{$n_2$}} \put(346,10){\footnotesize{$n_3$}} \put(371,10){\footnotesize{$n_4$}} \put(396,10){\footnotesize{$n_5$}} \qbezier(300,20)(325,40)(350,20) \qbezier(300,20)(337,50)(375,20) \qbezier(300,20)(350,70)(400,20) \qbezier(325,20)(337,30)(350,20) \qbezier(325,20)(350,40)(375,20) \qbezier(325,20)(360,55)(400,20) \put(340,-4){$Z_{2,3}$} \end{picture} \vspace{1em} Figure 1: $Z_4=Z_{2,2}$, a member of $\mathcal{Z}_6$, and $Z_{2,3}$. \end{center} Any $n$-vertex $K_{s,t}$-free graph $G$ can be used to define a $Z_{s,t}$-free graph so $\textrm{ex}(n,K_{s,t} ) \leq \textrm{ex}(n, Z_{s,t} )$. A non-trivial relation between $\textrm{ex}(n,K_{s,t})$ and $\textrm{ex}(n , Z_{s,t})$ can be viewed as a compactness result (see \cite{ES}) since one is forbidding a special type of $K_{s,t}$ rather than forbidding all $K_{s,t}$'s. The same remark applies to zig-zag even cycles as well. Our original motivation for investigating zig-zag bipartite graphs comes from a problem in additive number theory. A set $A \subset \mathbb{Z}$ is a \emph{$B_2$-set} if $a_1 + a_2 = b_1 + b_2$ with $a_i , b_j \in A$ implies $\{a_1, a_2 \} = \{b_1 , b_2 \}$. $B_2$-sets, also called \emph{Sidon} sets, were introduced in the early 1930's and since then they have attracted the attention of many researchers. Let $F_2 (n)$ be the maximum size of a $B_2$-set contained in $[n]$. Erd\H{o}s and Tur\'{a}n \cite{ET} proved $F_2 (n) < n^{1/2} + O(n^{1/4})$. In 1968 Lindstr\"{o}m \cite{Li}, refining the argument of Erd\H{o}s and Tur\'{a}n, proved $F_2 (n) < n^{1/2} + n^{1/4} +1$. Recently Cilleruelo \cite{Ci} obtained $F_2 (n) < n^{1/2} + n^{1/4} + 1/2$ as a consequence of a more general result. Erd\H{o}s conjectured $F_2 (n) < n^{1/2} + O(1)$ and offered \$500 for a proof or disproof of this conjecture \cite{Erd}. The error term of $n^{1/4}$ has not been improved since the original argument of Erd\H{o}s and Tur\'{a}n. The connection between $B_2$-sets and ordered Tur\'{a}n theory is given by the following construction. Let $A \subset [n]$ be a $B_2$-set and define the graph $G_{A}$ by $V(G_A) = [n]$ and \begin{equation*} E(G_A) = \{ ij : i = j +a, a \in A \}. \end{equation*} It is easily checked that $G_A$ is $Z_4$-free and so bounds on $\textrm{ex}(n,Z_4)$ translate to bounds on $F_{2}(n)$. Our results are presented in the next section. Proofs are given in Sections 3, 4, and 5. In Section 6 we discuss the interaction between ordered Tur\'{a}n theory and $B_2$-sets. In the final section we make some concluding remarks. \section{Results} We begin our discussion with zig-zag even cycles. Before stating our result we recall some of the known bounds for $\textrm{ex}(n,C_{2k})$. The first general upper bound on $\textrm{ex}(n,C_{2k})$ is due to Bondy and Simonovits \cite{BS} who proved $\textrm{ex}(n, C_{2k} ) \leq c_k n^{1 + 1/k}$ where $c_k$ is a constant depending only on $k$. The best known upper bound on $\textrm{ex}(n,C_{2k})$ for general $k$ is due to Pikhurko \cite{P} who, using ideas of Verstra\"{e}te \cite{V}, showed \begin{equation*}\label{P upper bound} \textrm{ex}(n, C_{2k} ) \leq (k-1) n^{1 +1/k} + 16(k-1)n. \end{equation*} For $k \in \{2,3 \}$ more precise results are known. By counting pairs of vertices in a common neighborhood, it is not hard to show $\textrm{ex}(n,C_4) \leq \frac{1}{2} n^{3/2} + O(n)$ (see \cite{L}, Ch.\ 10, Problem 36). Graphs constructed independently by Erd\H{o}s, R\'{e}nyi \cite{ER} and Brown \cite{B} show this upper bound is essentially best possible. F\"{u}redi, Naor, and Verstra\"{e}te \cite{FNV} proved for sufficiently large $n$, $\textrm{ex}(n, C_6) \leq 0.6272 n^{4/3}$. They also gave a construction which shows $\textrm{ex}(n,C_6) > 0.5338 n^{4/3}$ for infinitely many $n$. Lazebnik, Ustimenko, and Woldar \cite{LUW}, using a construction of Wenger \cite{W}, proved $\textrm{ex}(n,C_{10}) > 4 / 5^{6/5} n^{6/5} + o(n^{6/5})$. To summarize, $\textrm{ex}(n,C_4)$ is known asymptotically. For $k \in \{3 , 5 \}$, the order of $\textrm{ex}(n,C_{2k})$ is $n^{1 + 1/k}$. For $k \notin \{2,3,5 \}$, $\textrm{ex}(n,C_{2k})$ is $O(n^{1 + 1/k} )$ but there is no matching lower bound. Our first theorem gives an upper bound on $\textrm{ex}(n, \mathcal{Z}_{2k})$. \begin{theorem}\label{theorem 1} Let $k \geq 2$ be an integer. For any $n$, \begin{equation*} \emph{ex}(n , \mathcal{Z}_{2k} ) \leq \frac{ k - 3/2 }{ 2^{1/k} - 1 } n^{1 + 1/k} + (2k - 3)n \log_2 n. \end{equation*} \end{theorem} For $k=2$ the upper bound given by Theorem~\ref{theorem 1} will be improved by Theorem~\ref{theorem 2}. Using the bound $\textrm{ex}(n,C_{2k}) \leq \textrm{ex}(n,\mathcal{Z}_{2k})$, Theorem~\ref{theorem 1} shows the order of magnitude of $\textrm{ex}(n,\mathcal{Z}_{2k})$ is $n^{1 + 1/k}$ for $k \in \{2,3,5 \}$, but it is very unlikely that it is asymptotically optimal for any $k$. The constant $\frac{ k - 3/2 }{ 2^{1/k} - 1 }$ is asymptotic to $\frac{k^2}{ \log 2}$ whereas the leading coefficient in the upper bound on $\textrm{ex}(n,C_{2k})$ is linear in $k$. Next we discuss zig-zag complete bipartite graphs. Given integers $n,m,t,s$ with $2 \leq t \leq n$ and $2 \leq s \leq m$, let $z(n,m;t,s)$ be the maximum number of 1's in an $n$ by $m$ 0,1-matrix that contains no $t$ by $s$ submatrix of all 1's. The problem of determining $z(n,m;t,s)$ is known as the problem of Zarankiewicz. Improving an upper bound of K\"{o}v\'{a}ri, S\'{o}s, and Tur\'{a}n \cite{KST}, F\"{u}redi \cite{F} proved \begin{equation}\label{F upper bound} z(n,m;t,s) \leq (t - s + 1)^{1/s}mn^{1-1/s} + sm + sn^{2 - 2/s} \end{equation} for all $n \geq t$, $m \geq s$, and $t \geq s \geq 1$. The connection between the Zarankiewicz problem and Tur\'{a}n theory is given by the inequality $\textrm{ex}(n, K_{s,t}) \leq \frac{1}{2} z(n,n;t,s)$ (see \cite{Bo}) so that (\ref{F upper bound}) implies \begin{equation}\label{general upper bound of Furedi} \textrm{ex}(n, K_{s,t} ) \leq \frac{1}{2}(t-s+1)^{1/s} n^{2 - 1/s} + O ( n^{2 - 2/s} ) \end{equation} for $t \geq s$. For lower bounds, a construction of F\"{u}redi \cite{F3} and (\ref{general upper bound of Furedi}) give $\textrm{ex}(n,K_{2,t}) = \frac{1}{2} \sqrt{t-1}n^{3/2} + o(n^{3/2})$. A construction of Brown \cite{B} and (\ref{general upper bound of Furedi}) give $\textrm{ex}(n,K_{3,3}) = \frac{1}{2}n^{5/3} + o(n^{5/3})$. For other values of $s$ and $t$ the results are not as precise. When $t \geq (s-1)! + 1$, graphs constructed by Koll\'{a}r, R\'{o}nyai, and Szab\'{o} \cite{KRS} (see also the paper of Alon, R\'{o}nyai, Szab\'{o} \cite{ARS}) show $\textrm{ex}(n,K_{s,t}) \geq c_{s,t}n^{2-1/s}$. For other values of $s$ and $t$, there are no lower bounds that match (\ref{general upper bound of Furedi}) in order of magnitude. Theorem~\ref{theorem 2} gives an upper bound on $\textrm{ex}(n,Z_{s,t})$ corresponding to (\ref{general upper bound of Furedi}). \begin{theorem}\label{theorem 2} Let $t \geq s \geq 2$ be integers. For any $n$, \begin{equation*} \emph{ex}(n,Z_{s,t}) \leq \frac{ (t - 1)^{1/s} }{ 2 - 1/s} n^{2 - 1/s} + \left( (t-1)^{1/s} + \frac{1}{2}(s-1) \right) n^{3/2 - 1/2s} + (s-1)n. \end{equation*} \end{theorem} It is worth noting that for $s \leq t$, \begin{equation*} \lim_{s \rightarrow \infty} \lim_{t \rightarrow \infty} \frac{ \frac{1}{2} ( t - s + 1)^{1/s} }{ (t-1)^{1/s} / (2 - 1/s) } =1. \end{equation*} For small values of $s$ and $t$ there is certainly a gap between the upper bounds on $\textrm{ex}(n,K_{s,t})$ and $\textrm{ex}(n,Z_{s,t})$. When $s = t = 2$ the upper bound of Theorem~\ref{theorem 2} gives $\textrm{ex}(n,Z_{2,2}) \leq \frac{2}{3} n^{3/2} + O(n^{5/4})$ whereas (\ref{general upper bound of Furedi}) gives $\textrm{ex}(n,K_{2,2,}) \leq \frac{1}{2}n^{3/2} + O (n)$. We are able to give a construction using projective planes which shows \begin{equation*} \limsup_{n \rightarrow \infty} \left( \textrm{ex}(n,Z_{4}) - \textrm{ex}(n, C_{4} ) \right) = \infty. \end{equation*} Unfortunately we were unable to determine whether or not $\textrm{ex}(n,Z_{4}) \sim \textrm{ex}(n,C_{4})$ but we do have the following theorem. \begin{theorem}\label{theorem 3} For any prime $p$, \begin{equation*} \emph{ex}(p^2 + p + 1, Z_{4} ) \geq p^2 + \emph{ex}(p^2 + p + 1 , C_{4}). \end{equation*} \end{theorem} The upper bound $\textrm{ex}(n, Z_{4}) \leq \frac{2}{3}n^{3/2} + o(n^{3/2})$ given by Theorem~\ref{theorem 2} can probably be improved. We believe the constructions are best possible. \begin{conjecture} The zig-zag Tur\'{a}n number $\textrm{ex}(n,Z_4)$ satisfies \begin{equation*} \textrm{ex}(n,Z_4) \leq \frac{1}{2} n^{3/2} + o(n^{3/2}). \end{equation*} \end{conjecture} The notion of compactness \cite{ES} has produced several interesting problems concerning Tur\'{a}n numbers for bipartite graphs. Similar questions can be asked for our ordered version of the problem. \begin{problem}\label{problem 1} Is it true that for any bipartite graph $H$ and any zig-zag $ZH$ we have \begin{equation*} \textrm{ex}(n, ZH) = O ( \textrm{ex}(n , H) )? \end{equation*} \end{problem} A positive answer to Problem~\ref{problem 1} is supported by Theorem~\ref{theorem 2}. Another interesting problem related to compactness is the following. Let $\mathcal{Z}_{2k}^{\times}$ be the sub-family of $\mathcal{Z}_{2k}$ that consists of all $Z_{2k}$'s with a longest or shortest edge. \begin{problem}\label{problem 2} Is $\textrm{ex}(n, \mathcal{Z}_{2k}^{\times} ) = O(n^{1+1/k})$ for $k \geq 3$? \end{problem} We will discuss Problem~\ref{problem 2} in more detail in Section 7. For now we remark that it is not difficult to show $\textrm{ex}(n , \mathcal{Z}_{2k}^{\times} ) > cn^{1 + 1/k}$ for all $k \geq 3$ which may come as a surprise considering the difficulty in finding good lower bounds on $\textrm{ex}(n,C_{2k})$ for $k \notin \{2,3,5 \}$. In the next three sections we will prove Theorems~\ref{theorem 1} - \ref{theorem 3}. Throughout the paper all floor and ceiling symbols are omitted whenever they do not affect the asymptotics of the results. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{theorem 1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $k \geq 2$ be an integer. Let $G$ be a $\mathcal{Z}_{2k}$-free graph with $V(G) = [n]$. Given two subsets $A, B \subset V(G)$, write $A < B$ if all of the elements of $A$ are less than the smallest element of $B$. For disjoint subsets $A, B \subset V(G)$, let $G(A,B)$ be the subgraph of $G$ with $V(G(A,B)) = A \cup B$ and \begin{equation*} E(G(A,B)) = \{ ij \in E(G) : i \in A, j \in B \}. \end{equation*} For any pair of subsets $A, B \subset V(G)$ with $A < B$, the graph $G(A,B)$ is $C_{2k}$-free since $G$ is $\mathcal{Z}_{2k}$-free. Given integers $m_1$ and $m_2$, let $\textrm{ex}(m_1 , m_2 , C_{2k})$ be the maximum number of edges in a $C_{2k}$-free bipartite graph with $m_1$ vertices in one part and $m_2$ vertices in the other. Naor and Verstra\"{e}te \cite{NV} proved an upper bound on $\textrm{ex}(m_1,m_2,C_{2k})$ that implies a $C_{2k}$-free bipartite graph with $m$ vertices in each part has at most $(2k-3)( m^{1+1/k} + 2m)$ edges. Applying this bound to $G(A_1,B_1)$ where $A_1 = \{1, 2, \dots , n/2 \}$ and $B_1 = \{ n/2 + 1, n/2 + 2, \dots , n \}$ gives \begin{equation*} e( G(A_1 ,B_1 )) \leq (2k-3) ( (n/2)^{1 + 1/k} + n ). \end{equation*} We repeat the argument on the sets $A_{2,1} = \{1, 2, \dots , n/4 \}$, $B_{2,1} = \{n/4 +1 , n/4 +2, \dots , n/2 \}$ and on the sets $A_{2,2} = \{n/2+1, n/2+2, \dots , 3n/4 \}$, $B_{2,2} = \{ 3n/4 +1 , 3n/4 +2, \dots ,n \}$. Continuing in this fashion gives \begin{eqnarray*} e(G) & \leq & \sum_{l=1}^{ \log_2 n } 2^{l-1} \textrm{ex}( n2^{-l} , n2^{-l} , C_{2k} ) \\ & \leq & \sum_{l=1}^{ \log_2 n } 2^{l-1} (2k-3) \left( (n/2^l)^{1 + 1/k} + 2n/2^l \right) \\ & \leq & \frac{ (k-3/2) n^{1 + 1/k} }{2^{1/k} } \sum_{l=0}^{\infty} \left( \frac{1}{2^{1/k} } \right)^l + (2k-3)n \log_2 n \\ & = & \frac{ k - 3/2 }{ 2^{1/k} - 1 } n^{1 + 1/k} + (2k - 3)n \log_2 n. \end{eqnarray*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{theorem 2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%% The following lemma was used by F\"{u}redi \cite{F} to prove \begin{equation*} z(m,n;t,s) \leq (t-s+1)^{1/s}nm^{1-1/s} + sn + sm^{2 - 2/s} \end{equation*} for all $m \geq t$, $n \geq s$ and $t \geq s \geq 2$. The proof of the lemma is an easy application of Jensen's Inequality. For $k \geq 1$ and $x \geq k-1$ define $\binom{x}{k} = \frac{1}{k!} x(x-1)\cdots (x-k+1)$. If $k -1 > x \geq 0$ define $\binom{x}{k}=0$. For fixed $k$ each of these functions is convex. \begin{lemma}[F\"{u}redi, \cite{F}]\label{lemma 1} If $n, k \geq 1$ are integers and $c, y, x_1, \dots , x_k$ are non-negative real numbers and $\sum_{i=1}^{n} \binom{x_i}{k } \leq c \binom{y}{k}$ then \begin{equation}\label{ineq 1} \sum_{i=1}^{n} x_i \leq yc^{1/k}n^{1 - 1/k} + (k-1)n. \end{equation} \end{lemma} \begin{proof} Let $s = \sum_{i=1}^{n} x_i$. If $s \leq n(k-1)$ then the inequality holds so assume $\frac{s}{n} - k +1 >0$. Apply Jensen's Inequality to get $\sum_{i=1}^{n} \binom{x_i}{k} \geq n \binom{s/n}{k}$ which implies $c \binom{y}{k} \geq n \binom{s/n}{ k}$. Rearranging this inequality gives \begin{equation*} \frac{ y(y-1)(y-2) \cdots (y-k+1) }{ (s/n) (s/n -1) \cdots (s/n - k + 1 ) } \geq \frac{n}{c}. \end{equation*} The left hand side can be bounded above by $\left( \frac{y}{s/n-k+1} \right)^k$ to get $\left( \frac{y}{s/n-k+1} \right)^k \geq \frac{n}{c}$. Solving this inequality for $s$ gives (\ref{ineq 1}). \end{proof} \vspace{1em} Define the \emph{back neighborhood} of a vertex $i \in V(G)$ to be the set \begin{equation*} \Gamma^{-}(i) = \{ j < i : ji \in E(G) \}. \end{equation*} Let $G$ be a $Z_{s,t}$-free graph with $V(G) = \{1,2, \dots , n \}$. Define an $n$ by $n$ bipartite graph $H$ with parts $L = \{b_1, b_2, \dots , b_n \}$, $P = \{1, 2, \dots , n \}$, and edge set \begin{center} $E(H) = \{ \{ i , b_j \} : i \in \Gamma^{-}(j) \}$. \end{center} $H$ is the incidence graph of the back neighborhoods $\{ \Gamma^{-}(i) \}_{i=1}^{n}$ of $G$. It is easy to check that $e(H) = e(G)$ and $H$ has no complete bipartite subgraph with $t$ vertices in $L$ and $s$ vertices in $P$. Let $k = n^{1/2 - 1/2s}$. For $j=1,2, \dots , k$ let \begin{center} $P_j = \{ 1 + (j-1) \frac{n}{k} , 2 + (j-1) \frac{n}{k}, \dots , \frac{jn}{k} \}$. \end{center} Any back neighborhood $\Gamma^{-}(i)$ is a subset of $\{1, 2, \dots , i-1 \}$ and so the neighbors of $b_i$ in $H$ are contained in the set $\{1, 2, \dots , i - 1 \}$. If $i < (j-1) \frac{n}{k} +1$ then $d_{P_j}(b_i) = 0$ hence \begin{equation}\label{ineq 2} e(L,P_j) = \sum_{i=1}^{n} d_{P_j} (b_i) = \sum_{i= 1+(j-1)\frac{n}{k} }^{n} d_{P_j}(b_i). \end{equation} Recall $ \binom{x}{s} = 0$ if $0 \leq x < s$ and so \begin{equation*} \sum_{i=1}^{n} \binom{ d_{P_j}(b_i)}{s } = \sum_{ i = (j-1) \frac{n}{k} + 1 }^{n} \binom{ d_{ P_j}(b_i)}{ s}. \end{equation*} Each subset of size $s$ in $P_j$ can be counted at most $t-1$ times in the sum $\sum_{i=1}^{n} \binom{ d_{P_j}(b_i)}{ s}$ therefore \begin{equation*} (t-1) \binom{ n/k }{ s} \geq \sum_{i= 1}^{n} \binom{ d_{P_j}(b_i) }{ s} = \sum_{i=1 + (j-1)\frac{n}{k} }^{n} \binom{ d_{P_j}(b_i) }{ s}. \end{equation*} By Lemma~\ref{lemma 1}, \begin{equation}\label{ineq 3} \sum_{i =1 + (j-1) \frac{n}{k} }^{n} d_{P_j}(b_i) \leq \frac{n}{k} (t-1)^{1/s} \left( n \left( 1 - \frac{j-1}{k} \right) \right)^{1 - 1/s} + (s-1) \left(n \left(1 - \frac{j-1}{k} \right) \right). \end{equation} Using (\ref{ineq 2}) and (\ref{ineq 3}) we obtain \begin{eqnarray*} e(H) & = & \sum_{j=1}^{k} e(L,P_j) \\ \vspace{.25em} & \leq & \frac{ (t-1)^{1/s}n^{2-1/s} }{k} \sum_{j=1}^{k} \left( 1 - (j-1)/k \right)^{1-1/s} + (s-1)n \sum_{j=1}^{k} \left(1 - (j-1)/k \right) \\ \vspace{.25em} & \leq & \frac{ (t-1)^{1/s}n^{2-1/s} }{k} ( 1 + \int_{0}^{k} ( 1-x/k)^{1 - 1/s} dx ) + (s-1)n ( 1 + \int_{0}^{k} (1 - x/k) dx ) \\ \vspace{.25em} & = & \frac{ (t-1)^{1/s} }{ 2 - 1/s} n^{2 - 1/s} + \frac{ (t-1)^{1/s} n^{2 - 1/s} }{k} + \frac{ (s-1)nk}{2} + (s-1)n \\ \vspace{.25em} & = & \frac{ (t-1)^{1/s} }{ 2 - 1/s} n^{2 - 1/s} + \left( (t-1)^{1/s} + \frac{1}{2} (s-1) \right)n^{3/2-1/2s} + (s-1)n. \end{eqnarray*} Since $e(G) = e(H)$, this completes the proof. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A lower bound} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Graphs constructed by Erd\H{o}s, R\'{e}nyi \cite{ER} and Brown \cite{B} show $\textrm{ex}( q^2 + q + 1 , C_4 ) \geq \frac{1}{2}q(q+1)^2$ where $q$ is any odd prime power. Since $\textrm{ex}(n,Z_4) \geq \textrm{ex}(n,C_4)$, this implies \begin{equation*} \textrm{ex}(n,Z_4) \geq \frac{1}{2}n^{3/2} - o(n^{3/2}). \end{equation*} The construction we present improves this lower bound in the error term. F\"{u}redi \cite{F1} proved $\textrm{ex}(q^2 + q + 1 , C_4) \leq \frac{1}{2}q(q+1)^2 = \frac{1}{2}q^3 + q^2 + \frac{1}{2}q$ for $q \geq 15$. Using the constructions of Erd\H{o}s, R\'{e}nyi, and Brown we have the exact result $\textrm{ex}(q^2 + q + 1, C_4) = \frac{1}{2}q(q+1)^2$ for prime power $q$. For each prime $p$, we construct a $Z_4$-free graph with $p^2 + p + 2$ vertices, maximum degree $p+1$, and $\frac{1}{2}p^3 + 2p^2 + \frac{3}{2}p +1$ edges. It follows that there exists a $Z_4$-free graph on $p^2 + p +1$ vertices with at least $\frac{1}{2}p^3 + 2p^2 + \frac{1}{2}p$ edges and so for prime $p \geq 15$, \begin{equation*} \textrm{ex}(p^2 + p + 1,C_4) +p^2 \leq \textrm{ex}(p^2 + p + 1 , Z_4). \end{equation*} \vspace{1em} Before giving the construction we point out a connection between $Z_4$-free graphs on $n$-vertices and collections subsets of $[n]$. Let $G$ be a $Z_4$-free graph on $[n]$. The back neighborhoods $\{ \Gamma^{-}(i) \}_{i=2}^{n}$ form a collection of subsets of $[n]$ that satisfy \begin{enumerate} \item $\Gamma^{-}(i) \subseteq [i-1]$ for $2 \leq i \leq n$. \item For any $i \neq j$, $| \Gamma^{-}(i) \cap \Gamma^{-}(j) | \leq 1$. \end{enumerate} Conversely any collection of sets $\{ A_i \}_{i=1}^{n-1}$ that satisfy $A_i \subset [i]$ and $|A_i \cap A_j | \leq 1$ for $i \neq j$ can be used to define a $Z_4$-free graph $G$ by setting $\Gamma^{-}(i+1) = A_i$. We will construct a family of sets $A_1, \dots , A_{p^2 + p + 1}$ that satisfies these conditions by labeling the points of a projective plane using the numbers $1, 2 , \dots , p^2 + p +1$ and by labeling the lines of the plane using the numbers $1, 2, \dots , p^2 + p +1$. Suppose $l$ is a line that is assigned label $i$ and we denote this by $l_i$. Our goal is to make the sum \begin{equation*} \sum_{i=1}^{p^2+p+1} |l_i \cap [i] | \end{equation*} as large as possible for if $G$ is defined by setting $\Gamma^{-}(i+1) = l_i \cap [i]$ for $1 \leq i \leq p^2 + p +1$, then \begin{equation*} e(G) = \sum_{i=2}^{p^2 + p + 2} | \Gamma^{-}(i)| = \sum_{i=1}^{p^2 + p + 1} | l_i \cap [i] |. \end{equation*} Now we proceed with the construction. Fix a prime $p$. The number $p^2+p +1$ and the numbers in the array \[ \begin{array}{lllll} p^2 + p ~~~ & p^2 + p -1 ~~~ & p^2+p - 2 ~~~ & \dots & p^2 + 1 \\ p^2 & p^2-1 & p^2 -2 & \dots & p^2 - p + 1 \\ \vdots & \vdots & \vdots & \dots & \vdots \\ p & p-1 & p-2 & \dots ~ & 1 \\ \end{array} \] are the points of the projective plane. To define the lines of the plane it is convenient to let $a = p^2 + p + 1$ and let $a_{i-1,j}$ be the $(i,j)$-entry in the array above. The lines of the plane are $l(r) = \{ a , a_{r,1}, a_{r,2}, \dots , a_{r,p} \}$ where $0 \leq r \leq p$, and $l(r,c) = \{a_{0,r} , a_{1, r+c}, a_{2, r + 2c}, \dots , a_{p,r+pc} \}$ where $1 \leq r, c \leq p$. The second subscript $r+jc$ is reduced modulo $p$ so that its value is in $\{1, 2, \dots , p \}$. These names are used only to define the lines and at this point we are ready to assign the labels $1, 2 , \dots , p^2 + p +1$ to the lines. Each label will be used exactly once and there are $p^2 + p+1$ lines so to label the lines we just drop the name after the label has been assigned. Give $l(0)$ label $p^2 + p +1$ and for $1 \leq r \leq p$, give $l(r)$ label $p^2 - p(r-1)$. \begin{center} $l(0) \rightarrow l_{p^2 + p + 1}$ ~~~~~~ $l(r) \rightarrow l_{ p^2 - p (r-1) }$ for $1 \leq r \leq p$. \end{center} To determine the label assigned to $l(r,c)$, we look at which point $l(r,c)$ contains from the $(c+1)$-st row of the array. This point, or more precisely its label, will be the label assigned to $l(r,c)$ unless this element is a multiple of $p$. Specifically for $1 \leq r , c \leq p$, \[ l(r,c) \rightarrow \left \{ \begin{array}{ll} l_{a_{c,r+c^2}} & \mbox{if $a_{c,r+c^2} < p^2 - (c-1)p$}, \\ l_{p^2 + p - (c-1)} & \mbox{if $a_{c,r+c^2} = p^2 - (c-1)p$}. \end{array} \right. \] Before going further an example is needed. For $p =3$ form the array \[ \begin{array}{ccc} 12 & 11 & 10 \\ 9 & 8 & 7 \\ 6 & 5 & 4 \\ 3 & 2 & 1 \\ \end{array} \] In this case $a = 13$, $a_{0,1} = 12$, $a_{0,2} = 11$, $a_{0,3}=10, a_{1,1}=9, \dots , a_{3,3}=1$. Below we show the lines before the label assignments are given and the new labels. For lines of the form $l(r,c)$ we have underlined the point of the line used to determine its label. \[ \begin{array}{lll} l(0) = \{13, 12, 11, 10 \} \rightarrow l_{13} ~ & l(1) = \{13, 9 , 8, 7 \} \rightarrow l_{9} ~ & l(2) = \{ 13, 6, 5, 4 \} \rightarrow l_{6} \\ l(3) = \{ 13, 3, 2, 1 \} \rightarrow l_3 & ~ & ~ \\ l(1,1) = \{ 12, \underline{8} , 4, 3 \} \rightarrow l_8 ~& l(1,2) = \{ 11, 7 , \underline{5}, 3 \} \rightarrow l_5 ~& l(1,3) = \{ 10, 9 , 6, \underline{3} \} \rightarrow l_{10} \\ l(2,1) = \{12,\underline{7},6,2 \} \rightarrow l_7 ~ & l(2,2) = \{11,9,\underline{4},2 \} \rightarrow l_4 ~ & l(2,3) = \{10,8,5,\underline{2} \} \rightarrow l_2 \\ l(3,1) = \{12,\underline{9},5,1 \} \rightarrow l_{12} ~ & l(3,2) = \{11,8,\underline{6},1 \} \rightarrow l_{11} ~ & l(3,3) = \{10,7,4,\underline{1} \} \rightarrow l_1 \end{array} \] To compute $\sum_{i=1}^{p^2 + p + 1} |l_i \cap [i]|$, we divide it into three smaller sums. It is easy to check \begin{equation}\label{sum 1} \sum_{i=1}^{p} |l_{ip} \cap [ip] | = p \cdot p \end{equation} and \begin{equation}\label{sum 2} \sum_{i=p^2 + 1}^{p^2 + p+1} |l_i \cap [i] | = (p+1)(p+1). \end{equation} For fixed $j$ with $0 \leq j \leq p-1$, \begin{equation}\label{sum 3} \sum_{i=jp +1}^{(j+1)p-1} |l_i \cap [i] | = (p-1)(j+1). \end{equation} Putting (\ref{sum 1}), (\ref{sum 2}), and (\ref{sum 3}) together gives \begin{equation*} \sum_{i=1}^{p^2 + p + 1} |l_i \cap [i]| = p^2 + (p+1)^2 + (p-1) \sum_{j=1}^{p} j = \frac{1}{2}p^3 + 2p^2 + \frac{3}{2}p + 1. \end{equation*} We summarize this construction as a result on labeling points and lines of a projective plane. Define a \emph{labeling} of a projective plane $( \mathcal{P} , \mathcal{L} )$ of order $q$ to be a pair of bijections $L_{ \points} : \points \rightarrow \{1, 2, \dots , q^2 + q + 1 \}$ and $L_{ \lines} : \lines \rightarrow \{ l_1, l_2, \dots , l_{q^2 + q + 1} \}$. \begin{proposition}\label{label} Let $ ( \mathcal{P} , \mathcal{L} )$ be a projective plane of order $p$ where $p$ is prime. There is a labeling of the points $L_{ \mathcal{P}}: \mathcal{P} \rightarrow \{1, 2, \dots , p^2 + p + 1\}$ and the lines $L_{ \mathcal{L} }: \mathcal{L} \rightarrow \{ l_1, l_2, \dots , l_{p^2 + p + 1} \}$ such that \begin{equation*} \sum_{i=1}^{p^2 + p + 1} | l_i \cap [i] | = \frac{1}{2} p^3 + 2 p^2 + \frac{3}{2}p + 1. \end{equation*} \end{proposition} An easier way to obtain a labeling of a projective plane of order $q$ is to label the points and lines randomly. The sum $X = \sum_{i=1}^{q^2 + q + 1} | l_i \cap [i] |$ is a random variable whose expectation and variance can be computed exactly as $\mathbb{E}X = \frac{1}{2}q^3 + q^2 + \frac{3}{2}q + 1$ and $\mbox{Var}X = \frac{n}{12} \sqrt{n - 3/4} - \frac{n}{24} + \frac{1}{12} \sqrt{n - 3/4} - \frac{1}{24}$ where $n = q^2 + q + 1$. Furthermore $X$ has a nice symmetry property that allows one to prove that there are outcomes where $X \geq \mathbb{E}X + \frac{1}{2} \sqrt{ \mbox{Var}X }$. This method produces a labeling with $X \geq \frac{1}{2}q^3 + q^2 + O(q^{1.5})$. When $q$ is prime this matches our construction in the leading term but is not as good in second term. On the other hand, we do not know of any other method to label projective planes whose order is not a prime. One may suspect that with some clever labeling we can find a sequence of projective planes of order $q_1 < q_2 < \dots $ such that \begin{equation*} \sum_{i=1}^{q_{k}^{2} + q_k + 1} | l_i \cap [i] | > \left( \frac{1}{2} + \epsilon \right)q_{k}^{3} \end{equation*} for a fixed $\epsilon >0$. The next result shows that this cannot be done. \begin{proposition}\label{labeling 1} Let $( \points , \lines )$ be a projective plane of order $q$. If $L_{ \points}$, $L_{ \lines}$ is a labeling of $( \points , \lines )$ then \begin{equation*} \sum_{i=1}^{q^2 + q + 1} |l_i \cap [i] | = \frac{1}{2} q^3 + o (q^3). \end{equation*} \end{proposition} To prove Proposition~\ref{labeling 1} we need the following lemma (see \cite{KSV}). \begin{lemma}\label{spectral} Let $G$ be a $d$-regular, $n$-vertex bipartite graph with parts $X,Y$ and set $\lambda = \max_{i \neq 1 , n } | \lambda_i |$ where $\lambda_1 \geq \dots \geq \lambda_n$ are the eigenvalues of the adjacency matrix of $G$. For any $S \subset X$, $T \subset Y$, \begin{equation*} \left| e(S,T) - \frac{2d |S||T| }{n} \right| \leq \frac{ \lambda }{2} ( |S| + |T| ). \end{equation*} \end{lemma} \vspace{1em} \begin{proof}[Proof of Proposition~\ref{labeling 1}] Let $( \points , \lines )$ be a projective plane of order $q$ and let $L_{ \points}$, $L_{ \lines }$ be a labeling of $( \points , \lines )$. Let $t = q^{1/4}$ and for $1 \leq i \leq t$, let $S_i = \{ 1, 2, \dots , \frac{iq^2}{t} \}$ and \begin{equation*} T_i = \{ l_{1 + (i-1)\frac{q^2}{t}} , l_{2 + (i-1)\frac{q^2}{t}}, \dots , l_{ \frac{q^2}{t} + (i-1)\frac{q^2}{t}} \}. \end{equation*} Let $A$ be the adjacency matrix of the incidence graph of $( \points , \lines )$. The eigenvalues of $A$ are $q+1$, $-(q+1)$, each with multiplicity 1, and all other eigenvalues are $\pm \sqrt{q}$. This can be seen by considering the matrix $A^2$ which has the rather simple form $A^2 = \left( \begin{array}{cc} B & 0 \\ 0 & B \end{array} \right)$ where $B = I + qJ$ and $J$ is the all 1's matrix. Using Lemma~\ref{spectral}, \begin{eqnarray*} \sum_{i=1}^{q^2 + q + 1} |l_i \cap [i] | & \leq & (q+1)^2 + \sum_{i=1}^{q^2} |l_i \cap [i] | \leq (q+1)^2 + \sum_{i=1}^{t} e(S_i , T_i ) \\ & \leq & (q+1)^2 + \sum_{i=1}^{t} \left( \frac{ 2(q+1)q^4 i }{2(q^2+q+1)t^2} + \frac{ \sqrt{q} }{2} \left( \frac{iq^2}{t} + \frac{q^2}{t} \right) \right) \\ & \leq & (q+1)^2 + \frac{q^4 (t+1) }{2(q-1)t } + \frac{q^{5/2}}{2} + \frac{q^{5/2}(t+1)}{4} \\ & = & \frac{1}{2}q^3 + o (q^3). \end{eqnarray*} A similar argument gives the lower bound $\sum_{i=1}^{q^2 + q + 1} |l_i \cap [i] | \geq \frac{1}{2}q^3 + o (q^3)$. \end{proof} \vspace{1em} \begin{proof}[Proof of Theorem~\ref{theorem 3}] By Proposition~\ref{label}, there exists a $Z_4$-free graph $G_p$ with $p^2 + p + 2$ vertices and $\frac{1}{2} p^3 + 2 p^2 + \frac{3}{2} p + 1$ edges for prime $p$. Furthermore this graph has maximum degree $p+1$. Let $G_{p}'$ be a subgraph of $G_p$ with $p^2 + p +1$ vertices and at least $\frac{1}{2} p^3 + 2 p^2 + \frac{1}{2}p$ edges. Then \begin{eqnarray*} \textrm{ex}(p^2 + p +1 , Z_4 ) & \geq & e(G_{p}') \geq \frac{1}{2}p^3 + 2p^2 + \frac{1}{2}p \\ & = & \textrm{ex}(p^2 + p + 1 , C_4 ) + p^2. \end{eqnarray*} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{\texorpdfstring{$B_2$}--sets and \texorpdfstring{$Z_4$}--free graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section we show how $B_2$-sets can be used to construct $Z_{4}$-free graphs. Let $A \subset [n]$ be a $B_2$-set. Define the graph $G_A$ by $V(G_A) = [n]$ and \begin{equation*} E(G_A) = \{ij : i = j + a , a \in A \}. \end{equation*} Perhaps the most interesting feature of this construction is that, in general, $G_A$ will contain many $C_4$'s but will still be $Z_4$-free. For each vertex $i$ and pair $\{a , b \} \subset A$ with $i + a + b \leq n$, the vertices $\{i , i+a , i+b , i + a + b \}$ form a $C_4$ in $G$. \begin{lemma} If $A \subset [n]$ is a $B_2$-set, then $G_A$ is a $Z_{4}$-free graph with $\sum_{i=1}^{n-1} | A \cap [i] | $ edges. \end{lemma} \begin{proof} Suppose $n_1 < n_2 < n_3 < n_4$ are the vertices of a $Z_{4}$ in $G$. There exists $a,b,c,d \in A$ such that $n_3 = a + n_1$, $n_4 = b + n_1$, $n_3 = c + n_2$, and $n_4 = d + n_2$. This implies $a - c + d - b = 0$ so that $\{a,d \} = \{b,c \}$. If $a = b$ then $n_3 = n_4$ and if $a = c$ then $n_1 = n_2$. In either case we have a contradiction. The number of edges of $G_A$ is $\sum_{i=1}^{n} | \Gamma^{-}(i)|$ and $|\Gamma^{-}(i)| = |A \cap [i-1]|$. \end{proof} Observe that for any such $G_A$, \begin{equation*} \textrm{ex}(n, Z_{4}) \geq e (G_A). \end{equation*} If we can accurately estimate $\sum_{i=1}^{n-1} |A \cap [i] |$ then upper bounds on $\textrm{ex}(n, Z_{4})$ can imply upper bounds on $|A|$. We can use the following result of Cilleruelo to show $e(G_A) = \frac{1}{2}n^{3/2} - o(n^{3/2})$ provided $A$ is chosen appropriately. \begin{theorem}[Cilleruelo, \cite{Ci2}]\label{theorem C} If $A \subset [n]$ is a $B_2$-set with $n^{1/2} - L$ elements then any interval of length $cn$ contains $c|A| + e_I$ elements of $A$ where \begin{equation*} |e_I | \leq 52n^{1/4} ( 1 + c^{1/2} n^{1/8})(1 + L_{+}^{1/2}n^{-1/8} ) \end{equation*} and $L_{+} = \max \{ 0 , L \}$. \end{theorem} \begin{theorem}\label{prop 1} For each $B_2$-set $A$ with $|A| = n^{1/2}$ there exists an $n$-vertex $Z_{4}$-free graph $G_A$ with \begin{equation*} e(G_A) \geq \frac{1}{2}n^{3/2} - O(n^{5/4}). \end{equation*} Furthermore $G_A$ has at least $\frac{n^2}{18} - O(n^{15/8})$ 4-cycles. \end{theorem} \begin{proof} Suppose $A \subset [n]$ is a $B_2$-set with $|A| = n^{1/2}$. Let $k = n^{1/4}$ and for $1 \leq j \leq k$, let \begin{equation*} P_j = \{1 + \frac{ (j-1)n }{k},2 + \frac{ (j-1)n }{k}, \dots , \frac{jn}{k} \}. \end{equation*} Using Theorem~\ref{theorem C}, \begin{equation*} \sum_{i=1}^{n} |A \cap [i] | \geq \sum_{j=2}^{k} \sum_{i \in P_j} \left|A \cap [i] \right| \geq \sum_{j=2}^{k} \frac{n}{k} \left|A \cap \left[ \frac{(j-1)n}{k} \right] \right| = \frac{n}{k} \sum_{j=2}^{k} \left( \frac{j-1}{k} |A| + e_{I_j} \right) \end{equation*} where $e_{I_j}$ satisfies the inequality \begin{equation*} e_{I_j} \geq - 52 n^{1/4} \left(1 + \sqrt{ \frac{j-1}{k} } n^{1/8} \right). \end{equation*} Now $\frac{n}{k} \sum_{j=2}^{k} \frac{j-1}{k} |A| = \frac{1}{2}n^{3/2} - \frac{n^{3/2}}{2k} $ and so it remains to find a lower bound on the sum $- \frac{52n^{5/4}}{k} \sum_{j=1}^{k-1} ( 1 + \sqrt{j / k} n^{1/8})$. Estimating the sum with an integral gives \begin{equation*} - \frac{52n^{5/4}}{k} \sum_{j=1}^{k-1} \left( 1 + \sqrt{j / k} n^{1/8} \right) \geq - \frac{52n^{5/4}}{k} \left( k + \frac{2n^{1/8}k}{3} \right) = - 52n^{5/4} - \frac{104n^{11/8} }{3}. \end{equation*} Thus \begin{equation*} \sum_{i=1}^{n} |A \cap [i] | \geq \frac{1}{2} n^{3/2} - \frac{n^{3/2}}{2k} - 52n^{5/4} - \frac{104n^{11/8}}{3} \geq \frac{1}{2} n^{3/2} - O(n^{5/4}). \end{equation*} To prove the statement concerning 4-cycles, observe Theorem~\ref{theorem C} implies \begin{equation*} |A \cap [1 , n/3 ] | \geq \frac{1}{3}n^{1/2} - 104 n^{3/8}. \end{equation*} For any vertex $i \in [1, n/3]$ and pair $\{a,b \} \subset A \cap [1,n/3]$, the vertices $\{i , i + a , i +b , i + a+b \}$ form a 4-cycle. If $\alpha = \frac{1}{3} n^{1/3} - 104n^{3/8}$, then there are $\frac{n}{3} \binom{ \alpha }{ 2} = \frac{n^2}{18} - O(n^{15/8})$ such 4-cycles. \end{proof} For $q$ a prime power, there exists $B_2$-sets $A \subset [q^2]$ with $|A| = q$ (see \cite{BC}). Applying Theorem~\ref{prop 1} to such a $B_2$-set gives a $Z_{4}$-free graph with $\frac{1}{2}n^{3/2} + o(n^{3/2})$ edges where $n = q^2$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding Remarks} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% $\bullet$ One might hope that the idea of using $B_2$-sets to construct $Z_4$-free graphs extends to using $B_k$-sets to construct $\mathcal{Z}_{2k}$-free graphs. A set $A \subset \integers$ is a $B_k$-set if whenever \begin{equation*} a_1 + a_2 + \dots + a_k = b_1 + b_2 + \dots + b_k ~ \textrm{with} ~ a_i,b_j \in A, \end{equation*} the elements $a_1, a_2, \dots , a_k$ are a permutation of $b_1, b_2, \dots , b_k$. Unfortunately this does not work in general. If $A \subset [n]$ is a $B_k$-set with $k \geq 3$, then $G_A$, defined the same way as in Section 6, may not be $\mathcal{Z}_{2k}$-free. For example, if $a > b > c$ are elements of $A$ with $a-c 0$ is a constant independent of $k$. The difficulty now lies in proving good upper bounds which is the content of Problem~\ref{problem 2}. \vspace{.5em} $\bullet$ The argument used to prove Theorem~\ref{theorem 1} can be generalized. If $F$ is a bipartite graph with a unique bipartition and an automorphism interchanging the parts then we can obtain an upper bound on $\textrm{ex}(n, \mathcal{ZF} )$ in terms of $\textrm{ex}(n,F)$ where $\mathcal{ZF}$ is the family of zig-zag versions of $F$. More precisely, if $\textrm{ex}(n,F) \leq cn^{ \delta }$ for some constant $c > 0$ and real $\delta \in (1,2)$, then we can show $\textrm{ex}(n , \mathcal{ZF} ) \leq \frac{ 2^{ \delta -1}c }{2^{ \delta -1} - 1}n^{ \delta }$. For instance, using the bound $\textrm{ex}(n,C_{6}) < 0.6272n^{4/3}$ for large $n$ \cite{FNV}, we get $\textrm{ex}(n, \mathcal{Z}_6) < \frac{2^{1/3}}{2^{1/3} - 1} \cdot 0.6272n^{4/3} < 3.0403n^{4/3}$ for large $n$ which is an improvement of Theorem~\ref{theorem 1}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} The author would like to thank Jacques Verstra\"{e}te for his many helpful suggestions and Andr\'{e} K\"{u}ndgen for comments that improved the presentation of the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{ARS} N.\ Alon, L.\ R\'{o}nyai, T.\ Szab\'{o}, {\em Norm-graphs: variations and applications}, J. Combinatorial Theory B, {\bf 76} (2) (1999), p. 280-290. \bibitem{Bo} B.\ Bollob\'{a}s, {\em Extremal Graph Theory}, Academic Press, London - New York, 1978. \bibitem{BS} J.\ A.\ Bondy, M.\ Simonovits, {\em Cycles of even length in graphs}, J. Combinatorial Theory B, {\bf 16} (1974), p. 97-105. \bibitem{BC} R.\ C.\ Bose, S.\ Chowla, {\em Theorems in the additive theory of numbers}, Comment. Math. Helv. {\bf 37} (1962/1963), p. 141-147. \bibitem{B} W.\ G.\ Brown, {\em On graphs that do not contain a Thomsen graph}, Canad. Math. Bull. {\bf{9}} (1966), p. 281-289. \bibitem{Ci} J.\ Cilleruelo, {\em Sidon sets in $\mathbb{N}^d$}, J. of Combinatorial Theory Series A, {\bf 117} (2010), p. 857-871. \bibitem{Ci2} J.\ Cilleruelo, {\em Gaps in dense Sidon sets}, Integers {\bf 11} (2001) A11. \bibitem{CEH} J.\ Czipszer, P.\ Erd\H{o}s, A.\ Hajnal, {\em Some extremal problems on infinite graphs}, Publications of the Math.\ Inst.\ of the Hungarian Academy of Sci.\ Ser.\ A {\bf 7} (1962), p. 441- 456. \bibitem{DR} A.\ Dudek, V.\ R\"{o}dl, {\em On the Tur\'{a}n properties of infinite graphs}, Electronic J.\ of Combinatorics {\bf 15} (2008) \#R47. \bibitem{Erd} P.\ Erd\H{o}s, {\em A survey of problems in combinatorial number theory}, Annals of Discrete Mathematics 6 (1980), p. 89-115. \bibitem{ER} P.\ Erd\H{o}s, A.\ R\'{e}nyi, {\em On a problem in the theory of graphs}, Publ. Math. Inst. Hungar. Acad. Sci. 7A (1962), p. 623-641. \bibitem{ES} P.\ Erd\H{o}s, M.\ Simonovits, {\em Compactness results in extremal graph theory}, Combinatorica {\bf 2} (3) (1982), p. 275-288. \bibitem{ET} P.\ Erd\H{o}s, P. Tur\'{a}n, {\em On a problem of Sidon in additive number theory, and on some related problems}, J. London Math. Soc. {\bf 16} (1941), p. 212-215. \bibitem{F} Z.\ F\"{u}redi, {\em An upper bound on Zarankiewicz' Problem}, Combinatorics, Probability and Computing {\bf 5} (1996), p. 29-33. \bibitem{F3} Z.\ F\"{u}redi, {\em New asymptotics for bipartite Tur\'{a}n numbers}, J. of Combinatorial Theory Series A, {\bf 75} (1) (1996), p. 141-144. \bibitem{F1} Z.\ F\"{u}redi, {\em On the number of edges of quadrilateral-free graphs}, J.\ Combinatorial Theory B, {\bf 68} 1 (1974), p. 1-6. \bibitem{FNV} Z.\ F\"{u}redi, A.\ Naor, J.\ Verstra\"{e}te, {\em On the Tur\'{a}n number for the hexagon}, Adv.\ Math.\ 203 (2006), no. 2, p. 476-496. \bibitem{KSV} P.\ Keevash, B.\ Sudakov, J.\ Verstra\"{e}te, {\em On a conjecture of Erd\H{o}s and Simonovits: Even Cycles}, arXiv:1107.4715. \bibitem{KRS} J.\ Koll\'{a}r, L.\ R\'{o}nyai, T.\ Szab\'{o}, {\em Norm-graphs and bipartite Tur\'{a}n numbers}, Combinatorica, 16 (3) (1996), p. 399-406. \bibitem{KST} T.\ K\"{o}v\'{a}ri, V.\ T.\ S\'{o}s, P.\ Tur\'{a}n, {\em On a problem of Zarankiewicz}, Colloq. Math. {\bf 3} (1954), p. 50-57. \bibitem{LUW} F.\ Lazebnik, V.\ A.\ Ustimenko, A.\ J.\ Woldar, {\em Properties of certain families of $2k$-cycle-free graphs}, J. of Combinatorial Theory Series B, {\bf 60} 2 (1994), p. 293-298. \bibitem{Li} B.\ Lindstr\"{o}m, {\em An inequality for $B_2$-sequences}, J. Combinatorial Theory {\bf 6} (1969), p. 211-212. \bibitem{L} L.\ Lov\'{a}sz, {\em Combinatorial Problems and Exercises}, AMS Chelsea Publishing, 2nd ed., 1979. \bibitem{NV} A.\ Naor, J. Verstra\"{e}te, {\em A note on bipartite graphs without $2k$-cycles}, Combinatorics, Probability, and Computing {\bf 14} (2005), p. 845-849. \bibitem{P} O.\ Pikhurko, {\em A note on the Tur\'{a}n function of even cycles}, Proc. Amer. Math. Soc., to appear. \bibitem{V} J.\ Verstra\"{e}te, {\em Arithmetic progressions of cycle lengths in graphs}, Combinatorics, Probability, and Computing {\bf 9} (2000), 369-373. \bibitem{W} R.\ Wenger, {\em Extremal graphs with no $C^{4}$'s, $C^{6}$'s, or $C^{10}$'s}, J.\ of Combinatorial Theory Series B, {\bf 52} (1991), p. 113-116. \end{thebibliography} \end{document}