%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% LaTeX2e file for
%
% ``AN EXTREMAL PROBLEM FOR RANDOM GRAPHS AND THE
%   NUMBER OF GRAPHS WITH LARGE EVEN-GIRTH''
%
% by Y. Kohayakawa, B. Kreuter, and A. Steger
% REVISED VERSION
%
% Last update: 7 Jan 1998
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{article}
\usepackage{latexsym}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%    A few style macros...
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\input mssymb
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\thebibliography#1{\section*{References\markboth
 {REFERENCES}{REFERENCES}}\list
 {[\arabic{enumi}]}{\settowidth\labelwidth{[#1]}\leftmargin\labelwidth
 \advance\leftmargin\labelsep\setlength{\parsep}{0pt}%
 \setlength{\itemsep}{3pt}%
 \usecounter{enumi}}
 \def\newblock{\hskip .11em plus .33em minus -.07em}
 \sloppy
 \sfcode`\.=1000\small\relax}
\let\endthebibliography=\endlist
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\outer\def\endproof{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil$\Box$
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\outer\def\endproofnosquare{\removelastskip\penalty-10\bigskip}
\outer\def\proof{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty1000\medskip\fi
   \noindent{\it Proof.\enspace}\ignorespaces}
\outer\def\proofof#1.{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of {#1}\/}.\enspace\ignorespaces}
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\assertion(#1){\smallbreak\noindent
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
%
% Macros for references
%
% Journals
\def\AA{Acta Arithmetica}
\def\ADM{Ann. Discrete Math.}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\ASMS{Acta Sci. Math. Szeged}
\def\BRCI{Bull. Research Council of Israel}
\def\BLMS{Bull. London Math. Soc.}
\def\CJM{Canad. J. Math.}
\def\Comb{Combinatorica}
\def\CM{Compositio Math.}
\def\DM{Discrete Mathematics}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\GMJ{Glasgow Math. J.}
\def\IJM{Israel J. Math.}
\def\JAM{J. Anal. Math.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory{\rm, Series~A}}
\def\JCTB{Journal of Combinatorial Theory{\rm, Series~B}}
\def\JGT{J. Graph Theory}
\def\JLMS{J. London Math. Soc.}
\def\JNT{J. Number Theory}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\MZ{Math. Zeit.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\PJM{Pacific J. Math.}
\def\PLMS{Proc. London Math. Soc.}
\def\PM{Publ. Math.}
\def\PMH{Periodica Math. Hungar.}
\def\RSA{Random Structures and Algorithms}
\def\SSMH{Studia Sci. Math. Hung.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\UM{Utilitas Math.}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{lem}       {Lemma}
\newtheorem{thm} [lem] {Theorem}
\newtheorem{cor} [lem] {Corollary}
\def\Forb{{\cal F}\kern-.202em\hbox{\it orb}}
\def\ex{\mathop{{\rm ex}}}
\def\({\left(}
\def\){\right)}
%\def\[{\left[}
%\def\]{\right]}
\def\e{{\hbox{\rm e}}}
\def\cL{{\cal L}}
\def\cH{{\cal H}}
\def\cO{{\cal O}}
\def\E{{\bf E}}

\let\epsilon=\varepsilon
\let\eps=\epsilon
\let\ln=\log


\begin{document}
\title{An extremal problem for random graphs and the
  number of graphs with large even-girth %(DRAFT)
}

\author{%\sc
    Y.~Kohayakawa\thanks{Partially
    supported by FAPESP (Proc.~93/0603--1 and~96/04505--2) and by CNPq
    (Proc.~300334/93--1). Part of this work was done while this
    author was visiting the other two authors at
    Universit\"at Bonn, supported by a
    DAAD--University of S\~ao Paulo exchange programme.
    Part of the revision was carried out with the support of
    PROBRAL project~026/95, a CAPES--DAAD exchange programme,
    and PRONEX project 107/97.}\\\small
    Instituto de Matem\'atica e Estat\'\i stica, %\\\small
    Universidade de S\~ao Paulo\\\small
    Rua do Mat\~ao 1010, 05508--900 S\~ao Paulo,
    Brazil \\\small
    {\it E-mail address\/}: {\tt yoshi@ime.usp.br}
\and
    %\sc
    B.~Kreuter \\\small
    %Forschungsinstitut f\"ur Diskrete Mathematik, %\\\small
    %Universit\"at Bonn\\\small
    %Nassestra\ss e 2, D--53113 Bonn,
    %Germany\thanks\it Current address\/}:
    Institut f\"ur Informatik,
    Humboldt Universit\"at zu Berlin \\\small
    Unter den Linden 6,
    10099 Berlin,
    Germany\\\small
    {\it E-mail address\/}: {\tt kreuter@informatik.hu-berlin.de}
\and
\setcounter{footnote}{3}
    A.~Steger\thanks{Partially supported by DFG grant
      Pr~296/2--1.}\\\small
    Institut f\"ur Informatik, Technische Universit\"at M\"unchen \\\small
    80290 M\"unchen, Germany\\\small
    {\it E-mail address\/}: {\tt steger@informatik.tu-muenchen.de}
    }
\date{}
\maketitle
\vspace{-.8cm}
\begin{abstract}We study the maximal number of edges a $C_{2k}$-free
  subgraph of a random graph~$G_{n,p}$ may have, obtaining best
  possible results for a range of~$p=p(n)$. Our estimates strengthen
  previous bounds of F\"uredi~\cite{Fu} and Haxell, Kohayakawa, and \L
  uczak~\cite{HKL}.  Two main tools are used here: the first one is an
  upper bound for the number of graphs with large even-girth, {\it
    i.e.\/}, graphs without short even cycles, with a given number of
  vertices and edges, and satisfying a certain additional pseudorandom
  condition; the second tool is the powerful result of Ajtai,
  Koml\'os, Pintz, Spencer, and Szemer\'edi~\cite{AKPSSz} on uncrowded
  hypergraphs as given by Duke, Lefmann, and R\"odl~\cite{DLRo}.
\end{abstract}

\vspace*{0.2cm}{\noindent
\small
{\it AMS subject classification code\/} (1991): 05A16, 05C35, 05C38,
05C80
\par\noindent
{\it Key words and phrases\/}: Tur\'an's extremal problem, forbidden
subgraphs, cycles, random graphs, asymptotic enumeration}

\section{Introduction}

A classical area of extremal graph theory concerns the asymptotic
structure of $n$-vertex graphs~$G=G^n$ that do not contain an
isomorphic copy of a given graph~$H$ as a subgraph. A basic problem is
to determine or estimate the maximal number of edges~$\ex(n,H)$ that
such a graph~$G$ may have. The answer to this problem is beautiful:
the celebrated Erd\H os--Stone Theorem implies that,
as~$n\to\infty$, we have
\begin{equation}
  \ex(n,H)=\(1-{1\over\chi(H)-1}+o(1)\){n\choose2}. \label{ESS}
\end{equation}
Furthermore, as proved independently by Erd\H os and Simonovits, every
$H$-free graph $G=G^n$ that has as many edges as~(\ref{ESS}) is in
fact `very close' (in a certain precise sense) to the densest
$n$-vertex $(\chi(H)-1)$-partite graph. For these and related results,
see~\cite{BBEGT,Simo,Steger}.

Thus the situation for graphs~$H$ with~$\chi(H)\geq3$ is quite well
understood. Unfortunately, the same cannot be said about the case in
which we forbid a bipartite graph~$H$ in our~$G=G^n$.  Indeed, in this
case, usually referred to as the {\it degenerate\/} case,
relation~(\ref{ESS}) only tells us that~$\ex(n,H)=o(n^2)$, and
obtaining any further information on~$\ex(n,H)$ is usually very hard.
To see the level of difficulty here, recall that an old and very well
known unresolved conjecture of Erd\H os and Simonovits~\cite{ES}
states that~$\ex(n,C_{2k})\asymp n^{1+1/k}$ for all~$k\geq2$. Here,
as usual, $C_{2k}$ denotes the cycle of length~$2k$, and
for two functions $f$ and $g$ we write $f\asymp g$ if
$f=\cO(g)$ and $g=\cO(f)$.  Bondy and
Simonovits~\cite{BoSi} have proved the upper bound of $\cO(n^{1+1/k})$.

In this note we are concerned with the following variant of the
problems above. For graphs~$G$ and~$H$, write~$\ex(G,H)$ for the
maximum number of edges an $H$-free subgraph of~$G$ may have. Thus,
writing~$K_n$ for the complete graph on~$n$ vertices, we
have~$\ex(n,H)=\ex(K_n,H)$.  We are interested in~$\ex(G,H)$ for a
`typical' graph~$G$ and a fixed graph~$H$, where by a `typical'~$G$ we
mean the random graph~$G_{n,p}$, the graph on $n$~labelled vertices
whose edges are independently present with probability~$p=p(n)$.
The  random variable  $\ex(G_{n,p},H)$ was
first considered by Babai, Simonovits, and Spencer \cite{BSiSp}
who treated the case in which~$H$ has chromatic number~3
and $p$ is a constant.
Here, however, we concentrate on very small values of $p$
and on the very specific degenerate
case focused on in the Erd\H os--Simonovits conjecture, {\it i.e.\/},
when~$H=C_{2k}$ ($k\geq2$).

The behaviour of~$\ex(G_{n,p},C_4)$ was investigated by
F\"uredi~\cite{Fu} in relation to a Ramsey type problem posed by Erd\H
os and Faudree~\cite{ErdosFaudree}.  For general~$k\geq2$, Haxell,
Kohayakawa, and \L uczak~\cite{HKL} showed that, for all~$p=p(n)=\omega
n^{-1+1/(2k-1)}$ with~$\omega=\omega(n)\to\infty$ as~$n\to\infty$, we
have
\begin{equation}
  \ex(G_{n,p},C_{2k})=o(|E(G_{n,p})|)
  \label{HKLbd}
\end{equation}
almost surely, {\it i.e.\/}, with probability tending to~$1$
as~$n\to\infty$. Thus, provided~$p=p(n)$ is sufficiently large, we are
again dealing with a degenerate extremal problem: even a fraction
approaching~$0$ of the edges of a typical~$G_{n,p}$ spans a~$C_{2k}$.

The condition on~$p=p(n)$ for~(\ref{HKLbd}) to hold, namely,
that~$pn^{1-1/(2k-1)}\to\infty$ as~$n\to\infty$, deserves a quick
remark.  A simple first moment calculation gives that,
for~$p=p(n)=o(n^{-1+1/(2k-1)})$, the number of $2k$-cycles in a
typical~$G_{n,p}$ is negligible compared with~$|E(G_{n,p})|$.  Thus,
as a simple deletion argument shows, we
have~$\ex(G_{n,p},C_{2k})=(1-o(1))|E(G_{n,p})|$ almost surely for such
a~$p=p(n)$ (a more precise result is described in
Section~\ref{se:concludingremarks}).  For these and related results concerning
random graphs that we tacitly assume throughout the rest of the paper, cf.\
Bollob\'as~\cite{Bo}.

The main result in this paper strengthens~(\ref{HKLbd}) by
determining~$\ex(G_{n,p},C_{2k})$ \textit{up to a constant factor} for
a polynomial range of~$p=p(n)$ starting at the
threshold~$n^{-1+1/(2k-1)}$ (see Theorem~\ref{thm:exc2k}).
Unfortunately, our technique breaks down for~$p$
too far above this threshold, although the situation is better
for~$k=2$ (see Theorem~\ref{thm:exc4}). As a consequence of our sharp
result for small enough~$p$, we may deduce an explicit bound
for~$\ex(G_{n,p},C_{2k})$ improving~(\ref{HKLbd}) for the whole range
of~$p$ (see Corollary~\ref{largep}).  We remark that our sharp
estimates for~$\ex(G_{n,p},C_{2k})$ also imply that, surprisingly,
this function contains a logarithmic factor.  In classical extremal
graph theory, a conjecture of Erd\H{o}s and Simonovits says that
logarithmic factors do not occur; cf.,{\it~e.g.\/},~\cite{Simo}. It
has already been shown that this conjecture does not hold for
hypergraphs: Frankl and F\"uredi~\cite{FrFu} have constructed a
$5$-uniform hypergraph~$\cH$ with no exponent, {\it i.e.\/},~for which
there exists no~$\beta$ such that $\ex(n,\cH) \asymp n^\beta$.

Our method for obtaining the upper bound for~$\ex(G_{n,p},C_{2k})$ is
based on a technical lemma concerning the number of certain graphs
with no short even cycles. Let the {\it even-girth\/} of a graph be
the length of its shortest {\it even\/} cycle. To estimate
$\ex(G_{n,p},C_{2k})$ from above, we estimate the number of certain
$n$-vertex graphs with even-girth larger than~$2k$ and with a given
number~$T=T(n)$ of edges; see Lemma~\ref{mainl} below. On the other
hand, we deduce our lower bound for~$\ex(G_{n,p},C_{2k})$ from a
powerful result of Ajtai, Koml\'os, Pintz, Spencer, and
Szemer\'edi~\cite{AKPSSz} on `uncrowded hypergraphs' as given in Duke,
Lefmann, and R\"odl~\cite{DLRo}.

The method used in the proof of Lemma~\ref{mainl}, coupled with another
idea, gives an estimate for the {\it total\/} number of $n$-vertex
graphs with even-girth larger than~$2k$.  Theorem~\ref{forbc2k} gives
this estimate.  We remark that this result was proved in
Kreuter~\cite{Kr}, but while writing this note we were kindly informed that
a weaker form of this theorem was independently proved by Kleitman and
Wilson~\cite{KWilson}. Kleitman and Wilson  achieve the same estimate
for the number
of graphs of even-girth larger than~$2k$ which, in addition, contain
no odd cycles of length smaller than~$k$.
Further enumeration results are
proved in~\cite{KWilson}; in particular, the long-standing problems of
estimating the number of $C_6$-free graphs and of $C_8$-free graphs
are resolved in~\cite{KWilson}.  Finally, we mention
that further results concerning~$\ex(G_{n,p},H)$ are obtained in
Haxell, Kohayakawa, and
\L uczak~\cite{HKLodd}, and Kohayakawa, \L uczak, and
R\"odl~\cite{KLRo}.

\section{Main results}

We state our main results in this section.  Recall that we may assume
that~$p$ is at least of order~$n^{-1+1/(2k-1)}$, for otherwise we
have~$\ex(G_{n,p},C_{2k})=(1-o(1))|E(G_{n,p})|$.  It turns out that
our results are best formulated in terms of the `multiplicative
excess' of~$p=p(n)$ over the threshold~$n^{-1+1/(2k-1)}$.  Thus, we
put
\begin{equation}
  \label{eq:alpha_def}
  \alpha=\alpha(n)=p/n^{-1+1/(2k-1)},
\end{equation}
so that~$p=\alpha n^{-1+1/(2k-1)}$.  Our first result is the
following.  As usual, for any graph~$G$, we write~$e(G)$ for the
number of edges in~$G$.

\begin{thm}\label{thm:exc2k}
Let $k\ge 2$ be an integer and let $p=p(n)=\alpha n^{-1+1/(2k-1)}$
be such that
\[
  2 \le \alpha \le n^{1/(2k-1)^2}.
\]
Then
\begin{equation}
  \label{eq:main_asymp}
  \ex(G_{n,p},C_{2k}) \asymp
    \frac{ (\log \alpha)^{1/(2k-1)}}{\alpha} e(G_{n,p}).
\end{equation}
\end{thm}

For $C_4$ we can show the following slightly stronger theorem,
holding for a wider range of $p$.

\begin{thm} \label{thm:exc4}
Let $\delta>0$ be given and $p=p(n)= \alpha
n^{-2/3}$ such that $2\le \alpha \le  n^{1/3-\delta}$. Then
\[
  \ex(G_{n,p},C_{4}) \asymp
   \frac{ (\log \alpha)^{1/3}}{\alpha} e(G_{n,p}).
\]
\end{thm}

Unfortunately, the techniques used in the proofs of
Theorems~\ref{thm:exc2k} and~\ref{thm:exc4} break down for large~$p$.
Nevertheless, for larger~$p$, Theorem~\ref{thm:exc2k} implies the
following result, which strengthens~(\ref{HKLbd}) above.

\begin{cor}
\label{largep}
There exists a constant~$c_k$ that depends only on~$k$ such that,
for $p=p(n)\ge n^{-1+1/(2k-1)+1/(2k-1)^2}$, we almost surely have
%$$
%  \ex(G_{n,p},C_{2k})
%   \le c_k(\log n)^{1/(2k-1)}n^{-1/(2k-1)^2}e(G_{n,p}).
%$$
$$
  \ex(G_{n,p},C_{2k})
   \le \frac{c_k(\log n)^{1/(2k-1)}}{n^{1/(2k-1)^2}}e(G_{n,p}).
$$
\end{cor}

The heart of the proof of the upper bounds in these theorems
is a somewhat technical upper bound on the number
of $n$-vertex graphs with even-girth larger than~$2k$, a given
number~$T=T(n)$ of edges and satisfying some additional constraints.
The precise
statement of this lemma is deferred to the next section (Lemma~\ref{mainl}).
An idea used in the
proof of this lemma first appears in Kreuter~\cite{Kr}, where the
following generalization of a theorem of Kleitman and
Winston~\cite{KW} is proved.  For an integer~$n$ and a family of
graphs~$\cL$, denote by~$\Forb_n({\cL})$ the set of all $n$-vertex
graphs containing no graph from~$\cL$ as a subgraph.

\begin{thm}{\rm \cite{Kr}}
\label{forbc2k}
Let~$k\geq2$ be a fixed integer and put~$c_k=0.54k+1.5$. Then,
as~$n\to\infty$, we have
\[
  |\Forb_n(C_4,\ldots,C_{2k})|\le2^{c_kn^{1+1/k}(1+o(1))}.
\]
\end{thm}
In Section~\ref{sec:forbc2k} we include a
sketch of the proof of Theorem~\ref{forbc2k}. Note that
for~$k=2$, $3$ and~$5$, Theorem~\ref{forbc2k} is, apart from the
factor~$c_k$ in the exponent, best possible because, for these values
of~$k$, there are~$\{C_4,\ldots,C_{2k}\}$-free graphs
with~$\Theta(n^{1+1/k})$ edges (see Benson~\cite{Benson} and
Wenger~\cite{Wenger}) and~$2^{\ex(n,\{C_4,\ldots,C_{2k}\})}$ is an
obvious lower bound for~$|\Forb_n(C_4,\ldots,C_{2k})|$. For
general~$k$ we remark that a conjecture of Erd\H{o}s and
Simonovits~\cite{ES} states that $\ex(n,\{C_4,\ldots,C_{2k}\})=\Omega(
n^{1+1/k})$.

It is crucial for the proof of Theorem~\ref{forbc2k} that the graphs
under consideration contain no small even cycles.
A special case of a more general conjecture
of Erd\H os (cf.,~{\it e.g.},~\cite{Erdoes}) states that in fact
\begin{equation}
  \label{conj}
  |\Forb_n(C_{2k})|=2^{\cO(n^{1+1/k})}
\end{equation}
should hold.  In the forthcoming paper of Kleitman and
Wilson~\cite{KWilson}, inequality~(\ref{conj}) is proved for~$k=3$
and~$k=4$.

\section{Proofs}

\subsection{Proof of the upper bounds}
%In this section we shall prove the following two theorems, which
%together easily imply the upper bounds in Theorems~\ref{thm:exc2k}
%and~\ref{thm:exc4}.
%
%\begin{thm}
%  \label{strl}
%  For any given integer~$k\ge2$, there exists a constant $C_0=C_0(k)$
%  such that the following holds.  Suppose~$\alpha=\alpha(n)\geq 2$ is
%  such that~$\alpha<n^{1/13}$ if~$k=2$ and~$\alpha<n^{1/(2k-1)^2}$ if
%  $k\ge 3$. Let $p=p(n,\alpha)=\alpha n^{-1+1/(2k-1)}$. Then with
%  probability $1-o(n^{-1/(2k-1)})$ we have
%\begin{equation}
%  \label{strlbd}
%  \ex(G_{n,p},C_{2k})\le C_0n^{1+1/(2k-1)}(\ln\alpha)^{1/(2k-1)}.
%\end{equation}
%\end{thm}
%
%\begin{thm}
%  \label{tc4}
%  For any~$\delta>0$, there exists a constant~$C=C(\delta)$ such that,
%  for all~$p<n^{-1/3-\delta}$, almost surely
%\begin{equation}
%  \label{tc4bd}
%  \ex(G_{n,p},C_4)\le Cn^{4/3}(\ln n)^{1/3}.
%\end{equation}
%\end{thm}
The proofs of the upper bounds in Theorems~\ref{thm:exc2k}
and~\ref{thm:exc4}
are based on a technical lemma, which we shall now state.
It gives an upper bound for the number of $n$-vertex graphs with a given
number~$T=T(n)$ of edges, even-girth larger than~$2k$, and
satisfying a certain pseudorandom condition, {\it i.e.\/}, a
condition satisfied by certain random graphs.  The pseudorandom
condition is introduced to allow us to obtain a bound that takes into
account the number of edges~$T$.

For given integers~$n$ and~$T$ and a
set of graphs~$\cL$, define~$f({\cL},n,T)$ to be the number of graphs
on~$n$ labelled vertices with~$T$ edges and not containing any graph
from~$\cL$ as a subgraph.
We want to bound
$f(\{C_4,C_6,\ldots,C_{2k}\}\cup\cL_k,n,T)$, where~$\cL_k$ is a
certain finite family of `dense' graphs.

The families~$\cL_k$ ($k\geq2$) are defined as follows.  We first
put~${\cL}_2=\emptyset$.  For~$k\ge3$, we let~${\cL}_k$ be the set of
all graphs~$H$ on at most~$(4k)^4$ vertices satisfying
$$
  e(H)>\(1-\frac{1}{2k-1}-\frac{1}{(2k-1)^2}\)^{-1}v(H),
$$
where~$v(H)=|V(H)|$ and~$e(H)=|E(H)|$.

For any fixed~$k\geq2$, if~$p\leq n^{-1+1/(2k-1)+1/(2k-1)^2}$, the
expected number of graphs from~${\cL}_k$ in~$G_{n,p}$ is~$o(1)$.  The
following lemma will therefore enable us to prove an upper bound on
the number of~$\{C_4,\ldots,C_{2k}\}$-free graphs that are subgraphs
of a typical~$G_{n,p}$ for such a~$p=p(n)$.

\begin{lem}
  \label{mainl}
  Let an integer~$k\ge 2$ be fixed. Define the
  constants~$c_1=2(8k)^6$, $c_2=\(2(k-1)(8k)^{8k}/(2k-1)\)^{1/(2k-1)}$
  and~$\eps=24/(13(8k)^{8k+1})$, and let~$T=\beta n^{1+1/(2k-1)}$ be
  an integer. Then, if~$c_1<\beta<c_2(\ln n)^{1/(2k-1)}$, we have
$$
  f(\{C_4,\ldots,C_{2k}\}\cup{\cL}_k,n,T)
    <\left(\frac{n^2}{T}\exp\left\{-\eps\beta^{2k-1}\right\}\right)^T,
$$
  and, if~$\beta\geq c_2(\ln n)^{1/(2k-1)}$, we have
$$
  f(\{C_4,\ldots,C_{2k}\}\cup{\cL}_k,n,T)
    <\left(\frac{4\e n^{k+1}}{T^k}\right)^T
      \exp\left\{\epsilon^{-1}(n\ln n)^{1+1/(2k-1)}\right\}.
$$
\end{lem}

The proof of Lemma~\ref{mainl} is postponed until
Section~\ref{secmainl}.  From the first part of Lemma~\ref{mainl} we
may easily deduce the following theorem, which
proves the upper bound of
Theorem~\ref{thm:exc2k}.

\begin{thm}
  \label{strl}
  For any given integer~$k\ge2$, there exists a constant $C_0=C_0(k)$
  such that the following holds.  Suppose~$\alpha=\alpha(n)\geq 2$ is
  such that~$\alpha<n^{1/13}$ if~$k=2$ and~$\alpha<n^{1/(2k-1)^2}$ if
  $k\ge 3$. Let $p=p(n,\alpha)=\alpha n^{-1+1/(2k-1)}$. Then with
  probability $1-o(n^{-1/(2k-1)})$ we have
\begin{equation}
  \label{strlbd}
  \ex(G_{n,p},C_{2k})\le C_0n^{1+1/(2k-1)}(\ln\alpha)^{1/(2k-1)}.
\end{equation}
\end{thm}

\proof Observe first that it is enough to prove
the theorem for $\alpha \geq \alpha_0$ for some constant $\alpha_0$. When
this case is settled, the theorem follows from the fact that
$\ex(G_{n,p},C_{2k})$ is increasing in probability with respect to $p$
and by suitably altering the constant $C_0$.

Choose $C_0$ such that $\frac{1}{2}\eps
C_0^{2k-1}=1$ and $\alpha_0$ such that
$C_0(\frac{1}{2}\ln\alpha_0)^{1/(2k-1)}>c_1$, where $\eps=\eps(k)$ and
$c_1=c_1(k)$ are the constants from Lemma \ref{mainl}.
Let~$\alpha=\alpha(n)$ and~$p=p(n,\alpha)$ be as in the statement of
our theorem. Before applying Lemma~\ref{mainl} we first show that with
high probability  $G_{n,p}$ does not contain too many even cycles of length at
most $2k-2$. The expected number of these cycles in   $G_{n,p}$ is bounded from
above by
$$
\sum_{l=2}^{k-1}\frac{n^{2l}}{4l} p^{2l}\;
  \le\;\(n^{1/(2k-1)+1/(2k-1)^2}\)^{2(k-1)}\;
  = o(n).
$$
Now let~$\beta=C_0({1\over2}\log\alpha)^{1/(2k-1)}$ and~$T=\beta
n^{1+1/(2k-1)}$. Then, by Markov's inequality, with probability
$1-o(n^{-1/(2k-1)})$ our~$G_{n,p}$ contains~$o(T)$ even cycles of
length at most~$2k-2$.

Now, one may check that
$\beta=C_0(\frac{1}{2}\ln\alpha)^{1/(2k-1)}<c_2(\ln n)^{1/(2k-1)}$,
where $c_2$ is as defined in Lemma~\ref{mainl}.  Hence, by the first
case of that lemma, the expected number of
$\{C_4,\ldots,C_{2k}\}\cup\cL_k$-free subgraphs of~$G_{n,p}$ with~$T$
edges is
\begin{eqnarray*}
  &&f(\{C_4,\ldots,C_{2k}\}\cup{\cL}_k,n,T)p^T\\
  &&\qquad\qquad
    \leq\(\frac{n^2}{T}
     \exp\left\{-\frac{1}{2}\eps C_0^{2k-1}\ln\alpha\right\}
        \alpha n^{-1+1/(2k-1)}\)^T\\
  &&\qquad\qquad\qquad\qquad
    \le\(\frac{1}{C_0(\frac{1}{2}\ln\alpha)^{1/(2k-1)}}\)^T
    =o(n^{-1/(2k-1)}).
\end{eqnarray*}
Thus with probability $1-o(n^{-1/(2k-1)})$ every~$G_{n,p}$ ({\it i\/})
contains~$o(T)$ copies of graphs from~$\cL_k$ (this follows
again from Markov's inequality and the remarks of the beginning of
this section), ({\it
  ii\/})~contains~$o(T)$ even cycles of length smaller than~$2k$,
and ({\it iii\/})~contains no $\{C_4,\ldots,C_{2k}\}\cup\cL_k$-free
subgraph with~$T$ edges. To finish the proof, we simply observe that a
graph satisfying~({\it i\/}), ({\it ii\/}), and~({\it iii\/}) above
cannot contain a $C_{2k}$-free subgraph with~$T+\Omega(T)$ edges:
if~$H$ is such a subgraph, by~({\it i\/}) and~({\it ii\/}) we are able
delete some edges from~$H$ to obtain a
$\{C_4,\ldots,C_{2k}\}\cup\cL_k$-free subgraph of~$G_{n,p}$ with~$T$
edges, contradicting~({\it iii\/}).
\endproof

\proofof Corollary~\ref{largep}.  We can assume that
$p=\cO(n^{-1+1/k+1/(2k)^2})$ for otherwise the statement follows
because of the deterministic bound~$\ex(n,C_{2k})=\cO(n^{1+1/k})$.

In order to be able to apply Theorem~\ref{strl} we write $G_{n,p}$ as
a union of random graphs with smaller edge probability.  So let
$p_1=n^{-1+1/(2k-1)+1/(2k-1)^2}$ and define $l$ to be an integer
such that $(1-p_1)^l=1-p$ holds (approximately).  Then
$l=\cO(n^{1/(2k-1)})$.  If we let $p_i=p_1$ for $i=2,\ldots,l$, we can
write our random graph as $G_{n,p}=\bigcup_{i=1}^l G_{n,p_i}$. Let $H$
be an edge-maximal $C_{2k}$-free subgraph of $G_{n,p}$ and define $H_i
= H \cap G_{n,p_i}$. Then the following inequalities hold almost
surely:
\begin{eqnarray*}
  \frac{e(H)}{e(G_{n,p})} &\leq& \frac{\sum_{i=1}^l e(H_i)}{\sum_{i=1}^l
    (e(G_{n,p_i})- \sum_{j=i+1}^l e(G_{n,p_i} \cap G_{n,p_j}))}\\
  &\leq& \frac{2\sum_{i=1}^l e(H_i)}{\sum_{i=1}^l e(G_{n,p_i})} \\
  &\leq& \max_i \frac{2 e(H_i)}{e(G_{n,p_i})} \\
  &=&\cO\left\{(\log n)^{1/(2k-1)}n^{-1/(2k-1)^2}\right\}.
\end{eqnarray*}
The second inequality follows from properties of the binomial
distribution taking into account that $l p_1=o(1)$. The last
inequality follows from Theorem~\ref{strl} because~$l= {\cal
  O}(n^{1/(2k-1)})$.
\endproof

Using the second part of Lemma~\ref{mainl} we
may easily deduce the following theorem, which proves
the upper bound of Theorem~\ref{thm:exc4}.

\begin{thm}
  \label{tc4}
  For any~$\delta>0$, there exists a constant~$C=C(\delta)$ such that,
  for all~$p<n^{-1/3-\delta}$, almost surely
\begin{equation}
  \label{tc4bd}
  \ex(G_{n,p},C_4)\le Cn^{4/3}(\ln n)^{1/3}.
\end{equation}
\end{thm}

\proof  For given~$\delta$, choose
$C=\max\{1/\epsilon\delta,c_2\}$, where~$\epsilon$ and~$c_2$ are as in
Lemma~\ref{mainl}.  With $T=Cn^{4/3}(\ln n)^{1/3}$ it follows from
Lemma~\ref{mainl} that the expected number of spanning, $C_4$-free subgraphs
of~$G_{n,p}$ with~$T$ edges is
$$
f(\{C_4\},n,T)p^T
  \le\(\frac{4\e n^3}{T^2}\e^{\delta\ln n}n^{-1/3-\delta}\)^T
  =\(\frac{4\e}{(C(\ln n)^{1/3})^2}\)^T=o(1),
$$
and the result follows.
\endproof

\subsection{Proof of the lower bounds}
The following theorem implies the lower bounds in
Theorems~\ref{thm:exc2k} and~\ref{thm:exc4}.

\begin{thm}
  \label{notstrl}
  For any given integer~$k\geq2$, there exists a
  constant~$C_1=C_1(k)>0$ such that if~$\alpha=\alpha(n)\geq1$
  and~$p=p(n,\alpha)=\alpha n^{-1+1/(2k-1)}\leq 1$, then almost surely
\begin{equation}
  \label{notstrlbd}
  \ex(G_{n,p},C_{2k})\geq C_1n^{1+1/(2k-1)}(\ln\alpha)^{1/(2k-1)}.
\end{equation}
\end{thm}

We start by quoting a version of the result of Ajtai, Koml\'os, Pintz,
Spencer, and Szemer\'edi~\cite{AKPSSz} given by Duke, Lefmann, and
R\"odl~\cite{DLRo}. %Following~\cite{AKPSSz}, let us say that a
A hypergraph is called
{\it linear\/} if two hyperedges share at most one vertex.
%it contains no cycle of length~$2$,
%$3$ or~$4$.
As usual, the maximum degree of a hypergraph~$\cH$ is
denoted by~$\Delta(\cH)$.

\begin{thm}
  \label{UnHy}
  %For any integer~$r\geq1$ there is a constant~$t_0=t_0(r)$ such that
  %the following holds.
  Let~$r\geq1$ be an integer and
  let~$\cH$ be an $(r+1)$-uniform hypergraph
  on~$N$ vertices. Assume that {\rm({\it i\/})}~$\cH$ is linear,
  and {\rm({\it ii\/})}~$\Delta(\cH)\leq t^r$ for some~$t\geq 1$.
  Then~$\cH$ contains an independent set of size at least
  $$
  %{1\over3}10^{-5/r}
  c_r{N\over t}(\log t)^{1/r},
  %\label{UnHylb}
  $$
 where $c_r$ is a constant only depending on $r$.
\end{thm}

Theorem~\ref{notstrl} follows easily from Theorem~\ref{UnHy}.

\proofof Theorem~\ref{notstrl}. Note that the lower bound stated in the
theorem only
changes by a multiplicative constant as we change the power of~$n$
in~$\alpha$. Hence it is enough to prove the theorem for all~$\alpha$
satisfying~$1\leq\alpha
\leq n^{\delta}$ for some $\delta >0$. For larger~$\alpha$, the theorem then
follows again by monotonicity.

So consider~$G_{n,p}$
where~$p=p(n)=\alpha n^{-1+1/(2k-1)}$
and~$\alpha=\alpha(n)\geq 1$.
Since~$e(G_{n,p})=(1/2+o(1))\alpha n^{1+1/(2k-1)}$ almost surely and~$G_{n,p}$ almost surely contains at most~$n^{2k}p^{2k}/(2k)$ cycles of length
$2k$, in
the sequel we condition on these two events.  Define a $2k$-uniform
hypergraph~$\cH$ on the edge set of~$G_{n,p}$ putting $2k$~edges
of~$G_{n,p}$ in a hyperedge if they form the edge set of
a~$C_{2k}\subset G_{n,p}$. The number of hypervertices~$e\in
E(G_{n,p})$ in~$\cH$ with degree~$d_{\cH}(e)$ larger than
$4\times2k\times|E(\cH)|/|V(\cH)| \leq 8 n^{2k-2}p^{2k-1}=
8 \alpha^{2k-1}$ is  smaller than~$e(G_{n,p})/4$.
It is easy to verify that, \textit{e.g.},~for~$\delta<1/(8k^2)$,
if~$\alpha\leq n^\delta$ then almost surely

\assertion(*) the number of pairs of hyperedges intersecting in more
than one vertex is smaller than~$e(G_{n,p})/4$.
\endassertion

Assume that~(*) does hold for
our~$G_{n,p}$.  Then clearly there is a spanning subgraph~$G'\subset
G_{n,p}$ such that the corresponding subhypergraph~$\cH'$ of~$\cH$
on~$E(G')$ is linear, has maximum degree at most~$8\alpha^{2k-1}$,
and has at least~$(1+o(1))e(G_{n,p})/2$ hypervertices ({\it i.e.\/}, there
are at least~$(1+o(1))e(G_{n,p})/2$ edges in~$G'$).  By
Theorem~\ref{UnHy}, we have that~$\cH'$ has an independent set of
size at least
$$
\Omega\left\{{e(G')\over 2\alpha}(\log(2\alpha))^{1/(2k-1)}
      \right\}
=\Omega\(n^{1+1/(2k-1)}(\ln\alpha)^{1/(2k-1)}\),
$$
concluding the proof of~(\ref{notstrlbd}).
\endproof


\subsection{Proof of Lemma~\ref{mainl}}
\label{secmainl}

This fairly long section is entirely devoted to the proof of
Lemma~\ref{mainl}. We start with a simple lemma that is used later to
show that graphs with large even-girth have a certain expansion
property.

\begin{lem}
\label{2path}
Let~$H$ be a graph containing no even cycle of length at most~$2k$ and
let~$v$, $x$,  and~$y$ be distinct vertices such that~$x$ and~$y$ are
both at distance~$l<k$ from~$v$. Then there cannot exist a $2$-path
in~$H$ of the form~$xzy$ with~$z$ having distance at least~$l$
from~$v$.
\end{lem}
\proof
Suppose to the contrary that there exists a vertex~$z$ as
specified in the statement of the lemma.  Let~$x\,x_1\ldots
x_{l-1}x_l=v$ and $y\,y_1\ldots y_{l-1}y_l=v$ be shortest paths in~$H$
from~$x$ and respectively~$y$ to $v$.  Because~$z$ is at distance at
least~$l$ from~$v$, it has to be different from the vertices on these
two paths.  If $x_j$ is the first vertex from the first path also
contained in the second path then the fact that both paths are
shortest paths implies that $x_j=y_j$. Hence, $x\,x_1\ldots
x_j(=y_j)y_{j-1}\ldots y_1y zx$ is an even cycle of
length~$2j+2\leq2k$, which is impossible.
\endproof

We may now prove an expansion property of graphs with large
even-girth.  Given a graph~$H$, a vertex~$v$ in~$H$, and an
integer~$l\geq1$, write~$\Gamma'_l(v)$ for the set of vertices of~$H$
at distance~$l$ from~$v$. Denote by $d(v)$ the degree of the
vertex~$v$.

\begin{lem}
\label{expans}
Let~$H$ be a~$\{C_4,\ldots,C_{2k}\}$-free graph with minimal
degree~$d$ and suppose~$v$ is a vertex in~$H$ with degree~$d(v)$. Then
for all integers~$l\leq k$ we have
\[
|\Gamma'_l(v)|\ge d(v)(d-2)^{l-1}.
\]
\end{lem}
\proof
The case~$l=1$ is trivially true. Let~$l<k$ and suppose that the lemma
is true for~$l$. First observe that for a vertex $w\in\Gamma'_l(v)$ at
least~$d(w)-2$ of the vertices adjacent to~$w$ are at distance~$l+1$
from~$v$: by Lemma~\ref{2path} (with~$z=w$) there can be at most one
neighbour of~$w$ at distance~$l-1$ from~$v$ and at most one neighbour
at distance~$l$ from $v$. The remaining, at least~$d(w)-2$ many,
neighbours of~$w$ are at distance~$l+1$ from~$v$.

On the other hand, again by Lemma~\ref{2path}, two such vertices $u$,
$w\in\Gamma'_l(v)$ cannot have a common neighbour
in~$\Gamma'_{l+1}(v)$.  Therefore,
$|\Gamma'_{l+1}(v)|\ge|\Gamma'_l(v)|(d-2)$ and the lemma follows by
induction.
\endproof

Next we prove an upper bound for the number of $(2k-2)$-walks that may
join two vertices in an $\cL_k$-free graph~$G$ ($k\geq3$). Here we do
not attempt to give a best possible result, as any bound that is
independent of the number of vertices in our graph~$G$ will suffice
for our purposes.

\begin{lem}
\label{doublec}
Let~$k\ge3$ and the set~$\cL_k$ be as defined before
Lemma~\ref{mainl}.  If~$G$ is an~$\cL_k$-free graph then for any two
vertices~$x$ and~$y$ in~$G$ there are less than~$(4k)^{8k}$ different
walks of length~$2k-2$ from~$x$ to~$y$.
\end{lem}
\proof
Suppose to the contrary that there are two vertices~$x$ and~$y$
in~$G$ such that there are at least~$(4k)^{8k}$ different
$(2k-2)$-walks from~$x$ to~$y$. Let~$L$ be the subgraph of~$G$ spanned
by some~$(4k)^{8k}$ of these walks. If~$L$ contains~$e(L)$ edges then
they can form at most~$e(L)^{2k-2}$ different $(2k-2)$-walks and
therefore
\[
e(L)\ge(4k)^{8k/(2k-2)}>(4k)^4.
\]
Now write the edge set of~$L$ as a union of the edge sets of
$(2k-2)$-walks such that no walk is completely contained in the union
of the others:
\begin{equation}
\label{ykunion}
     E(L)=\bigcup_{i=1}^l E_i,
\end{equation}
where~$E_i$ is the edge set of the $i$th walk,
and~$E(L)\neq\bigcup_{j\neq i}E_j$ for any~$i$.
Obviously~$l\ge e(L)/(2k-2)\ge(4k)^3$, because
every walk can contribute at most~$2k-2$ new edges
to the union in~(\ref{ykunion}).

Let~$H$ be the union of some~$(4k)^3$ walks
from~$x$ to~$y$. Then~$H$ has at most~$(4k)^4$
vertices. Now, suppose we `build'~$H$ by adding one walk at
a time.  Suppose~$i\ge2$ and the $i$th walk
adds~$y_i$ new edges to $H$. Then it can add at
most $y_i-1$ new vertices. Observing that~$y_i\le
2k-2$, it follows that
\begin{eqnarray*}
  \frac{v(H)}{e(H)}&\le&\frac{2+\sum_{i=1}^{(4k)^3}(y_i-1)}
                                 {\sum_{i=1}^{(4k)^3} y_i}  \\
    &\le&\frac{2 + (4k)^3(2k-3)}{(4k)^3(2k-2)} \\
    &<& 1 - \frac{1}{2k-1} - \frac{1}{(2k-1)^2},
\end{eqnarray*}
implying that $H$ is a graph from $\cL_k$, which is impossible.
\endproof

The next crucial lemma singles out the key combinatorial idea in the
proof of Lemma~\ref{mainl}.

\begin{lem}
  \label{mainhl}
  Let integers~$n\geq2$, $k\geq2$, $T\geq1$, and~$4\leq d\leq2T/n$ be
  fixed.  For an integer~$4\leq t\leq d$, let
  \begin{equation}
    \label{nundkt}
    \nu(t)=\nu(n,d,k,t)
      =\(1-\frac{(d-3)^{2k-2}}{(4k)^{8k}n}\)^t+\frac{1}{(d-3)^{k-1}}.
  \end{equation}
  Suppose~$G'$ is a $\{C_4,\ldots,C_{2k}\}\cup\cL_k$-free graph
  on~$n-1$ vertices with~$T-d$ edges and minimal degree at
  least~$d-1$.  Then, under the restriction that no even cycle of
  length at most~$2k$ should arise, there are at most
  \begin{equation}
    \label{eq:extns_bd}
    \min_{4\le t\le d}{n\choose t}{n\nu(t)\choose d-t}
  \end{equation}
  ways of adding a new vertex~$v$ of degree~$d$ to~$G'$.
\end{lem}
\proof Let~$G'$, $d$, and~$v$ be as in the statement of the lemma.
Assume for the moment that the neighbourhood~$\Gamma(v)$ of size~$d$
of the new vertex~$v$ is fixed, and that an integer~$0\leq t\leq d$ is
given.  Following the ideas of Kleitman and Winston~\cite{KW} we shall
show that

\assertion($\dag$) for any choice of~$\Gamma(v)$, there exist
vertices~$v_1,\ldots,v_t$ in~$\Gamma(v)$ such that the remaining~$d-t$
neighbours of~$v$ have to be in a set of size at most~$n\nu(t)$.
\endassertion

Roughly speaking, every time a vertex~$v_\ell$ from the neighbourhood
of~$v$ is chosen, certain other vertices become ``forbidden'' as
neighbours of~$v$, since joining~$v$ to both~$v_\ell$ and a
``forbidden'' vertex creates an even cycle of length at most~$2k$.  It
is clear that assertion~($\dag$) proves Lemma~\ref{mainhl}.

We now prove~($\dag$). Thus let~$\Gamma(v)$ be fixed, and assume that
the neighbours~$v_1,\ldots,v_\ell$ ($0\leq\ell<t$) have already been
found.  Denote by~$Z_\ell$ the set of {\it eligible\/} vertices
for~$v_{\ell+1}$, namely, the ones that have not been forbidden
by~$v_1,\ldots,v_\ell$.  Note that~$Z_0$ is by definition the whole
vertex set of~$G'$.  Set
\[
\zeta_\ell=|Z_\ell|.
\]
Call a $(2k-2)$-walk $x_0x_1\ldots x_{2k-2}$ a {\it composed walk\/}
if $x_0\neq x_{2k-2}$ and~$x_0\ldots x_{k-1}$ and~$x_{k-1}\ldots
x_{2k-2}$ are shortest paths in $G$.

Now we order~$Z_\ell$ and then select~$v_{\ell+1}$ from among the
elements of~$Z_\ell$ in such a way that many vertices will then be
forbidden: let~$z_1^{(\ell)}$ be a vertex from~$Z_\ell$ joined to the
greatest number of vertices of~$Z_\ell$ by a composed walk, and
inductively define~$z_j^{(\ell)}$ for~$2\leq j\leq|Z_\ell|$ to be a
vertex from~$Z_\ell\setminus\{z_1^{(\ell)},\ldots,z_{j-1}^{(\ell)}\}$
joined to the greatest number of vertices of this set by a composed
walk.  If~$i$ is the smallest index such that~$z_i^{(\ell)}$ is in the
neighbourhood~$\Gamma(v)$ of~$v$, then define~$v_{\ell+1}$ to
be~$z_i^{(\ell)}$.  Furthermore, set
\[
  X=Z_\ell\backslash\{z_1^{(\ell)},\ldots,z_i^{(\ell)}\},
   \quad \xi=|X|,
    \quad\mbox{and}\quad
     Z_{\ell+1}=X\,\backslash\bigcup_{j=1}^{k-1}
                          \tilde{\Gamma}_{2j}(v_{\ell+1}),
\]
where~$\tilde{\Gamma}_{2j}(v_{\ell+1})$ is the set of vertices that
can be reached from~$v_{\ell+1}$ by a path of length~$2j$.

In order to obtain an upper bound for~$\zeta_{\ell+1}=|Z_{\ell+1}|$,
we first estimate the number of composed walks whose starting and end
points are in~$X$. For a vertex~$u\in V(G')$, let~$q_u$ denote the
number of vertices in~$X$ at distance~$k-1$ from~$u$. By
Lemma~\ref{expans},
\[
\sum_{u\in V(G')}q_u
   =\sum_{x\in X}|\Gamma'_{k-1}(x)|\ge\xi(d-3)^{k-1}.
\]

Putting together two shortest paths of length~$k-1$ starting at the
same vertex~$u\in V(G')$ and ending at some pair of distinct vertices
of~$X$ yields a composed walk.  Therefore the number of such walks is
at least
\begin{eqnarray*}
\sum_{u\in V(G')}{q_u\choose2}
    &\ge&(n-1){\xi(d-3)^{k-1}/(n-1)\choose2} \\
    &=&\frac{\xi(d-3)^{k-1}}{2}\(\frac{\xi(d-3)^{k-1}}{n-1}-1\).
\end{eqnarray*}
By the definition of~$v_{\ell+1}$, there are at least
\[
\frac{2}{\xi}\sum_{u\in V(G')}{q_u\choose2}
  \ge(d-3)^{k-1} \(\frac{\xi(d-3)^{k-1}}{n-1}-1\)
\]
composed walks starting from $v_{\ell+1}$.

If~$v_{\ell+1}y_1\ldots y_{k-1}(=y'_{k-1})y'_{k-2}\ldots y'_1x$ is a
composed walk, then~$x$ cannot be a neighbour of~$v$: this is because
such a walk is composed of two shortest paths and if~$y_j$ is the
first vertex from the first path occurring also in the second path
then~$y_j=y'_j$. Hence there is a path of length~$2j$
between~$v_{\ell+1}$ and~$x$ and an edge between~$x$ and $v$ would
complete a cycle of length~$2j+2\leq 2k$, which is not allowed.

For~$k\ge3$, by Lemma~\ref{doublec}, at most~$(4k)^{8k}$ composed
walks can start at~$v_{\ell+1}$ and end at~$x$, for any vertex~$x$.
For~$k=2$, no two composed walks starting at~$v_{\ell+1}$ can have the
same endvertex, for otherwise a~$C_4$ would arise. Therefore, there are
at least
\begin{equation}
\label{compw}
    \frac{(d-3)^{k-1}}{(4k)^{8k}}\(\frac{\xi(d-3)^{k-1}}{n-1}-1\)
\end{equation}
vertices in~$X$ which can be reached from~$v_{\ell+1}$ by a composed
walk. These vertices cannot share an edge with~$v$ and hence
\begin{eqnarray*}
\zeta_{\ell+1}&\le&\xi-\frac{(d-3)^{k-1}}{(4k)^{8k}}
                        \(\frac{\xi(d-3)^{k-1}}{n-1}-1\)  \\
  &\le&\xi\(1-\frac{(d-3)^{2k-2}}{(4k)^{8k}(n-1)}\)
                        +\frac{(d-3)^{k-1}}{(4k)^{8k}}  \\
  &\le&\zeta_\ell\(1-\frac{(d-3)^{2k-2}}{(4k)^{8k}n}\)
                        +\frac{(d-3)^{k-1}}{(4k)^{8k}}.
\end{eqnarray*}
Using that~$\zeta_0=n-1$, it follows by induction that
\[
\zeta_\ell\le n\left(1-\frac{(d-3)^{2k-2}}{(4k)^{8k}n}\)^\ell
                                          +\frac{n}{(d-3)^{k-1}}
      =n\nu(\ell).
\]
Thus~($\dag$) follows.  As observed above, Lemma~\ref{mainhl} follows
from~($\dag$).
\endproof

We are now in position to prove Lemma~\ref{mainl}.

\proofof Lemma \ref{mainl}.  We shall prove Lemma~\ref{mainl} by
applying Lemma~\ref{mainhl} recursively. Given a
$\{C_4,\ldots,C_{2k}\}\cup\cL_k$-free graph~$G$ on~$n$ vertices,
let~$v_n$ be a vertex of minimal degree. Remove it and let~$v_{n-1}$
be a vertex of minimal degree in the remaining graph, and so on. For
simplicity, let~$d_i$ denote the degree of~$v_i$ in the graph
$G\setminus\{v_{i+1},\dots,v_n\}$. Then by a recursive application of
Lemma~\ref{mainhl} we obtain
\begin{equation}
  \label{eq:f_bd}
  f(\{C_4,\ldots,C_{2k}\}\cup\cL_k,n,T)
   \le\sum_{(d_i)}
      \left\{n!n^{3n}\prod_{i=1}^n\left[\min_{4\le t\le d_i}
          {n\choose t}{n\nu(n,d_i,k,t)\choose d_i-t}\right]\right\}.
\end{equation}
Here,
$$
\nu(n,d_i,k,t)
  =\(1-\frac{(d_i-3)^{2k-2}}{(4k)^{8k}n}\)^t+\frac{1}{(d_i-3)^{k-1}}
$$
is as defined in Lemma~\ref{mainhl}, the sum is over all non-negative
integer vectors $(d_i)_{1\le i\le n}$ such that $d_1+\dots+d_n=T$, and
the minimum is defined to be~$1$ if~$d_i\le3$.  Note that the factor
of~$n!$ takes care of all the possible orderings $v_1,\dots,v_n$ of
the vertices of~$G$.  The factor~$n^{3n}$ takes care of all the
indices~$i$ such that~$d_i\leq3$.  Indeed, for any such~$i$, the
number of ways~$v_i$ can be added to~$G\setminus\{v_i,\dots,v_n\}$ is
trivially bounded by~${n\choose3}\leq n^3$.

Our task for the remainder of the proof is to massage~(\ref{eq:f_bd})
to deduce Lemma~\ref{mainl}.  Unfortunately, this will entail some
fussy and somewhat tedious calculations.

Before we start, observe that for ``small'' $d_i$, the first term
in~$\nu(n,d_i,k,t)$ is the larger one, whereas for ``large'' $d_i$ the
second term dominates.  To be able to distinguish between these two
cases, we introduce a value~$d_0$ for which both terms are roughly
equal at $t=d_0/2$.  More precisely, let $d_0\ge4$ be such
that
\begin{equation}
  \label{eq:d_0_def}
  \frac{d_0^{2k-1}}{2(8k)^{8k}n}=(k-1)\ln (d_0-3).
\end{equation}
Note that the order of magnitude of $d_0$ is $(n\ln n)^{1/(2k-1)}$.
More precisely, for~$n$ sufficiently large we have
$$
c_2(n\ln n)^{1/(2k-1)}\le d_0\le(8k)^8(n\ln n)^{1/(2k-1)},
$$
where~$c_2$ is as in the statement of Lemma~\ref{mainl}.  Now define
(for each~$n$) the functions
$$
g_1(x)=\frac{2x^{2k}}{(8k)^{8k+1}n}
$$
and
$$
g_2(x)=(k-1)x\ln x-\frac{1}{2}kd_0\ln x
          -\frac{d_0}{2}\((k-2)\ln d_0-\(1-\frac{1}{k}\)\ln(d_0-3)\)\!,
$$
and let
$$
g(x)=\cases{g_1(x)   &if~$1\leq x<d_0$ \cr\noalign{\vskip1\jot}
            g_2(x)   &if~$d_0\leq x$.\cr
           }
%g(x)=\left\{\begin{array}{r@{\qquad}l}
%               g_1(x)&\mbox{if }4\le x<d_0 \\
%               g_2(x)&\mbox{if }d_0\le x.
%           \end{array}\right.
$$
We claim that for all $1\le d\le n$ we have
\begin{equation}
\label{mainl:e1}
\min_{4\le t\le d}  {n\choose t}{n\nu(n,d,k,t)\choose d-t}
                           \le\(\frac{4\e n}{d}\)^d\e^{-g(d)},
\end{equation}
where~$\nu(n,d,k,t)$ is as in~(\ref{nundkt}) and the minimum is defined
to be~1 for $d\le 3$.

>>From inequality~(\ref{mainl:e1}) the proof of Lemma~\ref{mainl} is
easily concluded: the only missing observation is that the
function~$g$ is convex.  This is obviously true for~$g_1$ and~$g_2$.
So the only interesting case is the point~$x=d_0$.  Here it suffices
to check that~$g_1(d_0)=g_2(d_0)$ and $g'_1(d_0)\le g'_2(d_0)$. This
is easily verified using~(\ref{eq:d_0_def}).

The convexity of~$g$ and Jensen's inequality imply that
\begin{eqnarray}
f(\{C_4,\ldots,C_{2k}\}\cup\cL_k,n,T)
  &\le&n^{4n}\sum\prod
          \(\frac{4\e n}{d_i}\)^{d_i}\e^{-g(d_i)} \nonumber\\
  &\le&n^{5n}\(\frac{4\e n^2}{T}\)^T\e^{-ng(T/n)} \label{convexity},
\end{eqnarray}
where the sum is over all vectors~$(d_i)_{i=1}^n$ of non-negative
integers~$d_i$ with~$d_1+\ldots+d_n=T$, and the product is over
all~$1\leq i\leq n$ with~$d_i\geq4$.  The statement of the lemma is
easily deduced from~(\ref{convexity}) by distinguishing two cases according
to the size of $T/n$.

Now we go back to the proof of inequality (\ref{mainl:e1}). The cases
$d=1$, $2$, and~$3$ are easily checked.  For~$d\ge4$ we first observe
that, from the definition~(\ref{nundkt}) of~$\nu$, we have
\begin{equation}\label{nnu}
  n\nu(n,d,k,t)
    \le2n\max\left\{\exp\(-\frac{d^{2k-2}t}{(8k)^{8k}n}\),
                                        (d-3)^{-(k-1)}\right\}.
\end{equation}
Consider first the case in which~$d<d_0$. Here we set
$t=\lfloor d/2\rfloor$.  By the choice of $d_0$, the maximum
in~(\ref{nnu}) is attained by the first term.  Therefore,
\begin{eqnarray*}
{n\choose t}{n\nu(n,d,k,t)\choose d-t}
   &\le&{n\choose\lfloor d/2\rfloor}
      {2n\exp\left\{-d^{2k-1}\left/\(4(8k)^{8k}n\)\right.\right\}
             \choose\lceil d/2\rceil}\\
   &\leq&\(\e n\over\lfloor d/2\rfloor\)^{\lfloor d/2\rfloor}
      \(2\e n\exp\left\{-d^{2k-1}\left/\(4(8k)^{8k}n\)\right.\right\}
        \over\lceil d/2\rceil
      \)^{\lceil d/2\rceil}\\
   &\leq&\(4\e n\over d\)^{\lfloor d/2\rfloor}
      \({4\e n\over d}
          \exp\left\{-d^{2k-1}\left/\(4(8k)^{8k}n\)\right.\right\}
      \)^{\lceil d/2\rceil}\\
   &\leq&\(4\e n\over d\)^d
      \exp\left\{-\frac{2d^{2k}}{(8k)^{8k+1}n}\right\}.
\end{eqnarray*}
We now turn to the case~$d\ge d_0$.  Here we use~$t=\lceil
d_0/2\rceil$.  Then the maximum in~(\ref{nnu}) is attained by the
second term (this follows from~(\ref{eq:d_0_def})).  Hence,
\begin{eqnarray*}
  &&{n\choose t}{n\nu(n,d,k,t)\choose d-t}
   \leq{n\choose\lceil d_0/2\rceil}
            {2n/(d-3)^{k-1}\choose d-\lceil d_0/2\rceil}\\
  &&\qquad\leq\(\e n\over\lceil d_0/2\rceil\)^{\lceil d_0/2\rceil}
            \(2\e n\over d^{k-1}(d-\lceil d_0/2\rceil)
            \)^{d-\lceil d_0/2\rceil}
            \(d\over d-3\)^{(k-1)(d-\lceil d_0/2\rceil)}\\
  &&\qquad\leq\(4\e n\over d\)^dd^d2^{-d}d_0^{-d_0/2}
            \(1\over d^{k-1}(d-\lceil d_0/2\rceil)
            \)^{d-\lceil d_0/2\rceil}\e^{3k}\\
  &&\qquad\leq\(4\e n\over d\)^d2^{-d}d_0^{-d_0/2}
            d^{d-(k-1)d+kd_0/2-\lceil d_0/2\rceil+k-1}
            \(2\over d\)^{d-\lceil d_0/2\rceil}\e^{2+3k}\\
  &&\qquad\leq\(4\e n\over d\)^dd^{-(k-1)d+kd_0/2},
\end{eqnarray*}
completing the proof of inequality~(\ref{mainl:e1}).
Lemma~\ref{mainl} is therefore proved.
\endproof

\section{Proof of Theorem~\ref{forbc2k}}\label{sec:forbc2k}

We start by stating Lemma~\ref{corml}, which will enable us to prove
Theorem~\ref{forbc2k}. To state our lemma, let~$h_k(n,d)$ be the
number of $n$-vertex graphs with minimal degree at least~$d$ and even-girth
greater than~$2k$.

\begin{lem}
  \label{corml}
  Let~$k\ge2$ be an integer.  Then there is a
  constant~$c_3=c_3(k)>0$ depending only on~$k$ such that, for
  all integers~$d\geq4$ and all sufficiently large~$n$, we have
$$
  h_k(n,d)\le n h_k(n-1,d-1)
           \min_{4\le t\le d}{n\choose t}{n\mu(t)\choose d-t},
$$
  where
\begin{equation}
  \label{mundkt}
  \mu(t)=\mu(n,d,k,t)
    =\(1-\frac{(d-3)^{k(k-1)}}{c_3n^{k-1}}\)^t+\frac{1}{(d-3)^{k-1}}.
\end{equation}
\end{lem}

We now prove Theorem~\ref{forbc2k} assuming Lemma~\ref{corml}.

\proofof Theorem~\ref{forbc2k}.
To prove the theorem, it is enough to show that there exists a
constant~$n_0$ such that, for all~$n\ge n_0$, we have
\begin{equation}
\label{rec}
  \ln\frac{|\Forb_n(C_4,\ldots,C_{2k})|}
           {|\Forb_{n-1}(C_4,\ldots,C_{2k})|}
   \le(\log2)c_kn^{1/k}.
\end{equation}
Any $\{C_4,\ldots,C_{2k}\}$-free graph on~$n$ vertices with minimal
degree~$d$ may be obtained from a~$\{C_4,\ldots,C_{2k}\}$-free graph
on~$n-1$ vertices and minimal degree at least~$d-1$ by the addition of
a vertex of degree~$d$. For $d\le c_kn^{1/k}/\ln n$,
inequality~(\ref{rec}) follows from the fact
that~$\ln\left\{n{n\choose d}\right\}\le c_kn^{1/k}$ for any
sufficiently large~$n$.

So let us from now on assume that~$d\ge c_kn^{1/k}/\ln n$. With
$$
t_0=\left\lceil\frac{c_3n^{k-1}\ln n}{(d-3)^{k(k-1)}}\right\rceil
   =\cO\left\{(\ln n)^{k(k-1)+1}\right\},
$$
Lemma~\ref{corml} yields that
\begin{eqnarray*}
\ln\frac{|\Forb_n(C_4,\ldots,C_{2k})|}
       {|\Forb_{n-1}(C_4,\ldots,C_{2k})|}
    &<&\ln\(n{n\choose t_0}{n\mu(n,d,k,t_0)\choose d-t_0}\) \\
    &\le&\ln\(n^{1+t_0}{{t_0+1+n/(d-3)^{k-1}}\choose d}\)\\
    &=&(1+t_0)\log n + (1+o(1))\ln{n/d^{k-1}\choose d}.
\end{eqnarray*}
As $(1+t_0)\log n= o(n^{1/k})$, we only need to estimate the second term.
With~$x=dn^{-1/k}$, using Stirling's formula one sees that
$$
\ln{n/d^{k-1}\choose d}
\le\(\frac{-1}{x^{k-1}}
       \big\{(1-x^k)\ln(1-x^k)+x^k\ln x^k\big\}\)n^{1/k}.
$$
The first factor is easily seen to be smaller than
$(\log2)(0.531k+1.45)$ ({\it e.g.\/}, by considering the Taylor series
of this function). Hence Theorem~\ref{forbc2k} is proven.
\endproof

It now remains to prove Lemma~\ref{corml}. One may prove this lemma
following the proof of Lemma~\ref{mainhl}, and suitably altering a
step in that proof.

\proofof Lemma~\ref{corml} {\rm({\it Sketch\/})}. Only once in the
proof of Lemma~\ref{mainhl} is it needed that the graphs under
consideration are~$\cL_k$-free, namely, in the derivation of
inequality~(\ref{compw}),
where Lemma~\ref{doublec} is applied to give an upper bound for the
number of composed walks of length~$2k-2$ between two vertices. To
show an analogue of Lemma~\ref{doublec}, fix two distinct vertices~$x$
and~$y$ in a $\{C_4,\ldots,C_{2k}\}$-free graph~$G$ with maximal
degree~$\Delta=\Delta(G)$.  We shall prove that

\assertion($\ddag$) there is a constant~$c_3=c_3(k)$ such that the
number of different $(2k-2)$-walks from~$x$ to~$y$ in~$G$ is at
most~$c_3\Delta^{k-2}$.
\endassertion

Denote by $d(x,y)$ the distance between the vertices $x$ and $y$ in
$G$.  We first consider the case in which~$d(x,y)\ge k$.  To construct
a $(2k-2)$-walk $(x=)x_0x_1\ldots x_{2k-2}(=y)$ in~$G$, choose
first~$k$ indices $0\le i_1<\ldots<i_k\le2k-3$ such that
\[
k\ge d(x_{i_\rho},y)=d(x_{i_\rho+1},y)+1\:
                          \mbox{ for }\rho=1,\ldots,k.
\]
Observe that by Lemma~\ref{2path} (with~$z=x_{i_\rho}$), the
vertex~$x_{i_\rho+1}$ is uniquely determined once~$x_{i_\rho}$ is chosen.
For an index~$j$ not among these~$k$ indices, there are at
most~$\Delta$ choices for~$x_{j+1}$ for a given vertex $x_j$. Hence,
in total, there are at most
\[
{2k-2\choose k}\Delta^{k-2}
\]
$(2k-2)$-walks from~$x$ to~$y$.

For the case when~$d(x,y)<k$ one has to use in addition that, again
by Lemma~\ref{2path}, for a given~$x_j$, there is only one choice
for~$x_{j+1}$ if~$d(x_j,y)=d(x_{j+1},y)<k$. The number of walks
containing a vertex~$x_j$ with~$d(x_j,y)\geq k$ is estimated as in the
first case. For the other walks, partition the index
set~$\{0,1,\ldots,2k-3\}$ into three sets~$A$, $B$, and~$C$ such that
\[
\begin{array}{lll}
 d(x_{i_\rho},y)=d(x_{i_\rho+1},y) -1  & \mbox{ for }
& \rho \in A, \\
 d(x_{j_\rho},y)=d(x_{j_\rho+1},y)     & \mbox{ for }
& \rho \in B, \\
 d(x_{m_\rho},y)=d(x_{m_\rho+1},y) +1  & \mbox{ for }
& \rho \in C.
\end{array}
\]
Then, $|C|-|A|=d(x,y)\ge1$ and, consequently, $|A|\leq|C|-1\le k-2$.
Hence, the number of all $(2k-2)$-walks from~$x$ to~$y$ in the second
case is bounded from above by
\[
{2k-2\choose k}\Delta^{k-2}
+\sum{2k-2\choose{a,b,c}}\Delta^a\le c_3\Delta^{k-2},
\]
where the sum is over all triples~$(a,b,c)$ of non-negative integers
with~$a+b+c=2k-2$ and~$a\leq k-2$, and~$c_3=c_3(k)$ is a suitably
chosen constant. Thus~($\ddag$) follows. Actually, it would have been
enough to bound from above the number of composed walks between two
vertices, but this is not much easier than bounding the number of
$(2k-2)$-walks.

To apply~($\ddag$), we use that~$\Delta\le n/(d-3)^{k-1}$, which
follows immediately from Lemma~\ref{expans}.  Following the notation
of Lemma~\ref{mainhl}, we have shown (instead of~(\ref{compw})) that
there are at least
$$
\frac{(d-3)^{k-1}}{c_3\Delta^{k-2}}
         \(\frac{\xi(d-3)^{k-1}}{n-1}-1\)
\ge\frac{(d-3)^{(k-1)^2}}{c_3  n^{k-2}}
    \(\frac{\xi(d-3)^{k-1}}{n-1}-1\)
$$
vertices in~$X$ that can be reached from~$v_{\ell+1}$ by a composed
walk.  With this modification, Lemma~\ref{corml} may now be proven in
the same way as Lemma~\ref{mainhl}.
\endproof

In order to prove~(\ref{conj}), \textit{i.e.}, to get rid of the
smaller cycles, one could make use of an analogue to
Lemma~\ref{expans} as proven in~\cite{BoSi}, where only $C_{2k}$ is
forbidden.  However composed walks that are not self-avoiding are
useless now and substantially new ideas would be needed in order to
prove that sufficiently many composed walks are not self-avoiding.

\section{Concluding remarks}\label{se:concludingremarks}

In the case in which $p=p(n)$ is such that $pn^{-1+{1/(2k-1)}}=O(1)$
and $pn\to \infty$,
 we may
actually determine $\ex(G_{n,p},C_{2k})$ more precisely as follows.
Clearly,
\begin{equation}
  \label{eq:gap}
  \nu_{2k}(G_{n,p})
    \leq e(G_{n,p})-\ex(G_{n,p},C_{2k})
      \leq 2k \nu_{2k}(G_{n,p}),
\end{equation}
where~$\nu_{2k}(G_{n,p})$ denotes the maximal size of a pairwise edge-disjoint
family of copies of~$C_{2k}$ in~$G_{n,p}$.  For this range of~$p$ by  Theorem~4
from \cite{KrT} (or more precisely, by the remarks to this theorem), we
almost surely have
\begin{equation}
  \label{eq:nu}
  \nu_{2k}(G_{n,p})\asymp n^{2k}p^{2k}.
\end{equation}
Inequalities~(\ref{eq:gap}) and~(\ref{eq:nu})
determine~$e(G_{n,p})-\ex(G_{n,p},C_{2k})$ up to a multiplicative constant.

It would not be hard to weaken the upper bound on~$\alpha=\alpha(n)$
in Theorem~\ref{thm:exc2k} very slightly.  Here is how: one could
allow a larger constant in the statement of Lemma~\ref{doublec} and
then ${\cal L}_k$ could be defined slightly differently. However, with
these small changes our arguments give~(\ref{eq:main_asymp})
for~$\alpha=\alpha(n)$ up to~$n^{1/(2k-1)(2k-2)-o(1)}$ only.

It would be very interesting to determine~$\ex(G_{n,p},C_{2k})$ up to
a constant factor for a much wider range of~$p=p(n)$ than the one
given in Theorem~\ref{thm:exc2k}.  We have no guess as to the
behaviour of~$\ex(G_{n,p},C_{2k})$ for reasonably large~$p=p(n)$.  For
this case we only know Corollary~\ref{largep} and the trivial
inequalities
$$
  (1+o(1))p\ex(n,C_{2k})\leq\ex(G_{n,p},C_{2k})\leq\ex(n,C_{2k}) .
$$
The case $p$ constant and $k=2$ is already mentioned as an open problem in
Babai, Simonovits, and Spencer~\cite{BSiSp}.

\section*{Acknowledgement}
We are grateful to Z.~F\"uredi for informing us about the results of
D.J.~Kleitman and D.B.~Wilson, and to these authors for letting us
have a preliminary copy of~\cite{KWilson}.

This paper went through a
detailed revision owing to the insightful comments of two anonymous
referees.  We are glad to thank them for their fine job.

\bibliographystyle{plain}
\bibliography{bibl}
\end{document}
