%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Turan's Extremal Problem in Random Graphs: Forbidding Odd Cycles
% 
%   P.E. Haxell, Y. Kohayakawa, T. Luczak
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%                     Final Version
%
%               To appear in Combinatorica
%                 (Submitted 4 Nov 1994)
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstephalf
\input amstex
\documentstyle{amsppt}
\refstyle{C}
%
% refdef
%
\newcount\refno\refno=1
\def\referencelabel{\number\refno} 
\def\newrefno{\advance\refno by1}
%
\edef\refnoBSS
{\referencelabel}\newrefno
\def\refBSS{{\bf[\refnoBSS]}}
\edef\refnoEGT
{\referencelabel}\newrefno
\def\refEGT{{\bf[\refnoEGT]}}
\edef\refnoBBrgs
{\referencelabel}\newrefno
\def\refBBrgs{{\bf[\refnoBBrgs]}}
\edef\refnoErSt
{\referencelabel}\newrefno
\def\refErSt{{\bf[\refnoErSt]}}
\edef\refnoFR
{\referencelabel}\newrefno
\def\refFR{{\bf[\refnoFR]}}
\edef\refnoFu
{\referencelabel}\newrefno
\def\refFu{{\bf[\refnoFu]}}
\edef\refnoHKL
{\referencelabel}\newrefno
\def\refHKL{{\bf[\refnoHKL]}}
\edef\refnoHKLeven
{\referencelabel}\newrefno
\def\refHKLeven{{\bf[\refnoHKLeven]}}
\edef\refnoHoeff
{\referencelabel}\newrefno
\def\refHoeff{{\bf[\refnoHoeff]}}
%\edef\refnoKe
%{\referencelabel}\newrefno
%\def\refKe{{\bf[\refnoKe]}}
%\edef\refnoKW
%{\referencelabel}\newrefno
%\def\refKW{{\bf[\refnoKW]}}
\edef\refnoKo
{\referencelabel}\newrefno
\def\refKo{{\bf[\refnoKo]}}
\edef\refnoLRV
{\referencelabel}\newrefno
\def\refLRV{{\bf[\refnoLRV]}}
%\edef\refnoLu
%{\referencelabel}\newrefno
%\def\refLu{{\bf[\refnoLu]}}
\edef\refnoMcD
{\referencelabel}\newrefno
\def\refMcD{{\bf[\refnoMcD]}}
%\edef\refnoRo
%{\referencelabel}\newrefno
%\def\refRo{{\bf[\refnoRo]}}
\edef\refnoRoSzL
{\referencelabel}\newrefno
\def\refRoSzL{{\bf[\refnoRoSzL]}}
\edef\refnoRRa
{\referencelabel}\newrefno
\def\refRRa{{\bf[\refnoRRa]}}
\edef\refnoRRab
{\referencelabel}\newrefno
\def\refRRab{{\bf[\refnoRRab]}}
\edef\refnoRRb
{\referencelabel}\newrefno
\def\refRRb{{\bf[\refnoRRb]}}
\edef\refnoSz
{\referencelabel}\newrefno
\def\refSz{{\bf[\refnoSz]}}
%\edef\refnoTur
%{\referencelabel}\newrefno
%\def\refTur{{\bf[\refnoTur]}}
%
% Journals
%
\def\BLMS{Bull. London Math. Soc.}
\def\BAMS{Bull. Amer. Math. Soc.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\PLMS{Proc. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory~(A)}
\def\JCTB{J. Combinatorial Theory~(B)}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\CPC{Combinatorics, Probability and Computing}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\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.H.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
% macros
%
\hoffset=1.5truecm
\overfullrule=0pt
\def\({\left(}
\def\){\right)}  
\def\[{\left[}
\def\]{\right]}
\def\e{{\text{\rm e}}}
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\deffont{\it}
%\def\gammaarrow{\mathop\rightarrow\limits^{\text{ind}}_\gamma}
\def\gammaarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm ind}}
                                          _\gamma}}}
%\def\indarrow{\mathop\rightarrow\limits^{\text{ind}}\nolimits}
\def\indarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm ind}}}}}
\def\dHG{d_{H,G}}
\def\Vb{{\bar V}}
\def\GammaG{\Gamma_G}
\def\GammaJ{\Gamma_J}
\def\GammatJ{\Gamma_{\tJ}}
\def\GammaJdp{\Gamma_{J'}^+}
\def\GammaJdm{\Gamma_{J'}^-}
\def\bfx{{\bold x}}
\def\yip{y_i^+}
\def\yim{y_i^-}
\def\Ybp{Y_{\text b}^+}
\def\Ybm{Y_{\text b}^-}
\def\Ygp{Y_{\text g}^+}
\def\Ygm{Y_{\text g}^-}
\def\Xbp{X_{\text b}^+}
\def\Xbm{X_{\text b}^-}
\def\Xgp{X_{\text g}^+}
\def\Xgm{X_{\text g}^-}
\def\Xg{X_{\text g}}
\def\V#1#2{V_{#1}^{(#2)}}
\def\Jt{{\widetilde J}}
\let\tJ=\Jt
\def\Qb{{\bar Q}}
\def\tQ{{\widetilde Q}}
\def\tQo{\tQ^{(1)}}
\def\tQt{\tQ^{(2)}}
\def\Qo{Q^{(1)}}
\def\Qt{Q^{(2)}}
\def\Qjd{Q_{j'}}
\def\Qjdo{Q_{j'}^{(1)}}
\def\Qjdt{Q_{j'}^{(2)}}
\def\bmu{{\bar\mu}}
\def\bm{{\bar m}}
%
\newcount\eqnocounter
\eqnocounter=0
\def\slabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  \eqno({\number\eqnocounter})}
\def\alabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  ({\number\eqnocounter})}
%
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak\noindent  
  {\it Claim.\enspace}\ignorespaces\bgroup\sl}
  \def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
  \hskip2em\hbox{}\nobreak\hfil\square
    \parfillskip0pt\finalhyphendemerits=0\par}%
    \egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak\noindent 
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
  \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak\noindent 
  {\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak\noindent 
  {\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
  {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
%
%
\def\arrow{\to}
\def\indarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm ind}}}}}
\def\sizeR{r_{\text e}}
\def\indr{r^{\text{ind}}}
\def\rinde{r_{\text e}^{\text{ind}}}
\def\indsizeR{\sizeR^{\text{ind}}}
\def\indarrowd#1{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm
        ind}}_{#1}}}} 
%
% new macros
%
\def\:{{:}\;}
\def\cond{\,\big|\,}
%\def\cond{{\mathrel{\mathop|}}}
\def\G{{\Cal G}}
\def\F{{\Cal F}}
\def\B{{\Cal B}}
\def\cH{{\Cal H}}
\def\E{{\Bbb E}}
\def\P{{\Bbb P}}
\def\Z{{\Bbb Z}}
\def\bd{{\bold d}}
%\def\dHp{d_{H,p}}
%\def\dHrp{d_{H_r,p}}
%\def\dHr{d_{H_r}}
%\def\fAb{f_{A,b,\rho}}
%\def\FAb{\F_{A,b,\rho}}
%\def\FdAb{\F'_{A,b,\rho}}
%\def\X#1#2{X_{#1}^{(#2)}}
\def\x#1#2{x_{#1}^{(#2)}}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\ex{\mathop{\text{\rm ex}}\nolimits}
%\def\supp{\mathop{\text{\rm supp}}\nolimits}
\def\bS{{\bar S}}
\def\bV{{\bar V}}
\def\bH{{\bar H}}
\def\bG{{\bold G}}
\def\A{{\Cal A}}
\def\bgamma{\bar\gamma}
\def\dgamma{d^{\bgamma}}
\def\Ave{\mathop{\text{\rm Ave}}}
\def\Forb{\mathop{\text{\rm Forb}}}
\def\Gp#1#2{G_{p_{#1}}^{(#2)}}
%
% statems
%
\newcount\statemno\statemno=1
\def\newstatemno{\advance\statemno by1}
\def\statementlabel{\number\statemno} %new command
%
% intro
%
\edef\MainOddThm
{\statementlabel}\newstatemno

%
% sec1
%
\edef\SSz
{\statementlabel}\newstatemno
\edef\etaunif
{\statementlabel}\newstatemno
\edef\lemmapA
{\statementlabel}\newstatemno
\edef\lemmaLocpA
{\statementlabel}\newstatemno
%
% sec21
%
\edef\MainOddL
{\statementlabel}\newstatemno
\edef\OddCor
{\statementlabel}\newstatemno
%
% sec22
%
\edef\WeightL
{\statementlabel}\newstatemno
\edef\LocExp
{\statementlabel}\newstatemno
%
% sec3
%
\edef\MainDetThm
{\statementlabel}\newstatemno
\edef\DetCor
{\statementlabel}\newstatemno
%
% fstpg
%
\topmatter
\title
Tur\'an's Extremal Problem in Random Graphs: Forbidding Odd Cycles
\endtitle
\rightheadtext{AN EXTREMAL PROBLEM FOR RANDOM GRAPHS}
\author
P.E.~Haxell, Y.~Kohayakawa and T.~\L uczak
\endauthor
\address
\noindent
Department of Combinatorics and Optimisation, 
University of Waterloo, Waterloo, Ontario, 
Canada N2L 3G1
\endaddress
\email{\tt<pehaxell\@math.uwaterloo.ca>}
\endemail
\address
\noindent
Instituto de Matem\'atica e Estat\'\i stica, 
Universidade de S\~ao Paulo, 
Caixa Postal 20570, 01452--990 S\~ao Paulo~SP, 
Brazil
\endaddress
\email{\tt<yoshi\@ime.usp.br>}
\endemail
\address
\noindent
Mathematical Institute of the Polish Academy of Sciences, Pozna\'n,
Poland, {\it on leave from the\/} Department of Discrete Mathematics,
Adam Mickiewicz University, ul.~Matejki 48/49, 60--769~Pozna\'n,
Poland 
\endaddress
\email{\tt<tomasz\@plpuam11.bitnet>, <tomasz\@mathcs.emory.edu>} 
\endemail
\keywords Tur\'an's extremal problem, cycles, random graphs,
Szemer\'edi's lemma
\endkeywords
\subjclass Primary 05C80, 05C35, 05C38; Secondary 05C55
\endsubjclass
\thanks
The first author was partially supported by NSERC.  The second author
was partially supported by FAPESP (Proc.~93/0603--1) and by CNPq 
(Proc.~300334/93--1).  The third author was partially supported by~KBN
grant~2~1087~91~01. 
\endthanks
\abstract For~$0<\gamma\leq1$ and graphs~$G$ and~$H$, we
write~$G\to_\gamma H$ if any $\gamma$-proportion of the edges of~$G$
span at least one copy of~$H$ in~$G$. As customary, we write~$C^k$ for
a cycle of length~$k$.  We show that, for every fixed
integer~$\ell\geq1$ and real~$\eta>0$, there exists a real
constant~$C=C(\ell,\eta)$, such that almost every random graph
$G_{n,p}$ with $p=p(n)\geq Cn^{-1+1/2\ell}$
satisfies~$G_{n,p}\to_{1/2+\eta}C^{2\ell+1}$.  In particular, for any
fixed~$\ell\geq1$ and~$\eta>0$, this result implies the existence of
very sparse graphs~$G$ with~$G\to_{1/2+\eta}C^{2\ell+1}$.
\endabstract
\endtopmatter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\document 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% intro
%
\head\S0. Introduction
\endhead

In this note we are interested in a Tur\'an type problem concerning
extremal subgraphs of random graphs, which may be formulated as
follows.  Given a graph~$H$, we ask for the maximal size of an
$H$-free subgraph of~$G_p=G_{n,p}$, the usual binomial random graph
on~$n$ vertices with edge probability~$p$. Let us make this precise
by introducing some definitions and notation.

Let a graph~$G$ be given. As customary, write~$|G|$ for the {\deffont
  order\/}~$|V(G)|$ of~$G$ and~$e(G)$ for the {\deffont
  size\/}~$|E(G)|$ of~$G$. If~$H$ is a graph, we say that~$G$ is
{\deffont$H$-free\/} if~$G$ does not contain a subgraph isomorphic
to~$H$. Also, we let~$\ex(G,H$) be the maximal size of an $H$-free
subgraph of~$G$, that is~$\ex(G,H)=\max\{e(J)\:H\not\subset J\subset
G\}$. For instance, if~$G=K^n$, the complete graph on~$n$ vertices,
then~$\ex(K^n,H)=\ex(n,H)$, the usual Tur\'an number of~$H$.  Here we
are concerned with the case in which~$G=G_p=G_{n,p}$, the random graph
on~$V(G_p)=\{1,\dots,n\}$ where each edge~$ij$ ($1\leq i<j\leq n$)
belongs to~$G_p$ with probability~$p$, independently of all other
edges. (See Bollob\'as~{\refBBrgs} for details concerning random
graphs.)

With the notation as above, our Tur\'an type extremal problem for
random graphs asks for the investigation of
the random variable~$Z_H=Z_H(G_p)=\ex(G_p,H)$ for any
given~$0<p=p(n)\leq1$. 

A celebrated result of Erd\H os and Stone~{\refErSt} (see
also Bollob\'as~{\refEGT}) states that the asymptotic behaviour 
of $\ex(n,H)=\ex(K^n,H)$ is determined by the chromatic number of $H$, 
provided only that~$\chi(H)\geq3$. Indeed, for any~$H$ we have
$$
\lim_{n\to\infty}{\ex(K^n,H)\over e(K^n)}=1-{1\over\chi(H)-1}\;. 
$$
Now, clearly, for every family of graphs~$\{G^n\}_{n\geq1}$ with
each~$G^n$ of order~$n$ and with at least one edge, we have
$$
\liminf_{n\to\infty}{\ex(G^n,H)\over e(G^n)}\ge 1-{1\over\chi(H)-1}\;. 
   \slabel{TrivLB}
$$
However, if~$e(G^n)\to\infty$ as~$n\to\infty$ and, for all large~$n$,
the number of copies of~$H$ in~$G^n$ is much larger than~$e(G^n)$ and
these copies are distributed in~$G^n$ in a ``uniform'' way, then, in
fact, one may expect that equality holds in~{\eqnoTrivLB}
with~$\liminf$ replaced by~$\lim$. We conjecture that this is indeed
the case when the~$G^n$ are the random graphs~$G_{n,p}$ of
sufficiently large density to make the expected number of copies
of~$H$ in~$G_{n,p}$ larger than the expected size of~$G_{n,p}$ by a
factor that tends to~$\infty$ arbitrarily slowly.  Strong evidence in
support of this conjecture is provided by a recent, beautiful result
of R\"odl and Ruci\'nski~{\refRRb}, who proved that every
$r$-colouring of the edges of such a dense random graph~$G_{n,p}$
leads to a monochromatic copy of~$H$ almost surely, {\it i.e.\/}~with
probability tending to~$1$ as $n\to\infty$ (For earlier related
results see~{\bf[\refnoLRV, \refnoRRa, \refnoRRab]}.)

The case~$H=K^3$ of our conjecture is already well understood. One of
the results in Frankl and R\"odl~{\refFR} says
that~$\ex(G_p,K^3)=(1/2+o(1))e(G_p)$ almost surely if~$p=p(n)\geq
n^{-1/2+\epsilon}$ and~$\epsilon>0$ is any fixed constant. More
recently, Babai, Simonovits, and Spencer~{\refBSS} showed that
if~$p=1/2$, then~$\ex(G_p,K^3)$ is almost surely the maximal size of a
bipartite subgraph of~$G_p$. Moreover, it is shown in~{\refBSS} that
almost surely all the $K^3$-free subgraphs of~$G_p$ of maximal size
are in fact bipartite. In this note we
investigate~$\ex(G_p,C^{2\ell+1})$ for~$\ell\geq1$, where as usual we
write~$C^{2\ell+1}$ for a cycle of length~$2\ell+1$. Our main result
is as follows.

\proclaim {Theorem {\MainOddThm}} Let an integer~$\ell\geq1$ and a real
number~$0<\eta\leq1/2$ be fixed. Then there is a
constant~$C=C(\ell,\eta)>0$ such that, if~$p=p(n)\geq Cn^{-1+1/2\ell}$,
then almost every~$G_p\in\G(n,p)$
satisfies~$\ex(G_p,C^{2\ell+1})\leq(1/2+\eta)e(G_p)$.
\endproclaim

Clearly, by~{\eqnoTrivLB}, we always
have~$\ex(G_p,C^{2\ell+1})\geq1/2$.  Moreover, the condition
on~$p=p(n)$ in Theorem~{\MainOddThm} cannot be substantially weakened.
To see this, just note that, for~$p=p(n)=\delta n^{-1+1/2\ell}$,
almost every~$G_p$ has~$O\{(\delta^{2\ell}/2\ell)e(G_p)\}$ copies
of~$C^{2\ell+1}$.
Thus~$\ex(G_p,C^{2\ell+1})\geq\{1-O(\delta^{2\ell}/\ell)\}e(G_p)$
almost surely for such~$p$, and hence the lower bound for~$p$ in
Theorem~{\MainOddThm} is, as claimed, essentially best possible: given
any~$0<\epsilon\leq1$, there is a~$\delta=\delta(\epsilon)>0$ such
that for~$p=p(n)$ as above we
have~$\ex(G_p,C^{2\ell+1})\geq(1-\epsilon)e(G_p)$ almost surely.  We
mention that the general approach in the proof of
Theorem~{\MainOddThm} was inspired by R\"odl and Ruci\'nski~{\refRRb}
(cf.~Section~2.1).

The result of Frankl and R\"odl mentioned above has as a corollary a
purely deterministic result that in fact settled a problem of Erd\H os
and Ne\v set\v ril. For convenience, for any two graphs~$G$ and~$H$ and
any given~$0<\gamma\leq1$, let us write~$G\to_\gamma H$
if~$\ex(G,H)<\gamma e(G)$.  Then the deterministic result of Frankl and
R\"odl~{\refFR} says that, for any~$0<\eta\leq1/2$, there is a
$K^4$-free graph~$G=G_\eta$ such that~$G\to_{1/2+\eta}K^3$. Here, as a
corollary to Theorem~{\MainOddThm}, we show that, for
any~$0<\eta\leq1/2$ and~$\ell\geq1$, there are `very sparse'
graphs~$G=G_{\eta,\ell}$ satisfying~$G\to_{1/2+\eta}C^{2\ell+1}$. For
instance, $G$ may be required to have girth~$g(G)=2\ell+1$, and to
contain no two $(2\ell+1)$-cycles that share more than two vertices
(cf.~Corollary~{\DetCor}). 

Finally, we mention that our conjecture above for~$H=C^4$ follows from
F\"uredi~{\refFu} in a rather stronger form. The case in which~$H$ is
a general even cycle~$C^{2\ell}$ ($\ell\geq2$) will be dealt with
in~{\refHKLeven}, where a completely different approach from the one
here will be used.

This note is organised as follows. In~\S1 we give a few preliminary
definitions and lemmas. The proof of Theorem~{\MainOddThm}, which is
based on a somewhat surprising deterministic lemma on subgraphs of
pseudo-random graphs, Lemma~{\MainOddL}, is the subject of~\S2. The
statement of Lemma~{\MainOddL} and the proof of Theorem~{\MainOddThm}
are given in Section~2.1, and the proof of Lemma~{\MainOddL} is given
in Section~2.2. In~\S3 we give the deterministic consequences of
Theorem~{\MainOddThm}. 
%
% sec1
%
\head\S1. Preliminary Lemmas
\endhead
We start with a variant of the powerful lemma of Szemer\'edi~{\refSz} 
concerning regular partitions of graphs.  Let a graph~$G=G^n$ of
order~$|G|=n$ be fixed.  For~$U$, $W\subset V=V(G)$ with~$U\cap
W=\emptyset$, we write~$E(U,W)=E_G(U,W)$ for the set of edges of~$G$
that have one endvertex in~$U$ and the other in~$W$. We
set~$e(U,W)=e_G(U,W)=|E(U,W)|$. The following notion will
be needed in the sequel.  Suppose~$0<\eta\leq1$ and~$0<p\leq1$.
We say that~$G$ is {\deffont$\eta$-uniform\/} with {\deffont
  density\/}~$p$ if, for all~$U$, $W\subset V$ with~$U\cap
W=\emptyset$ and~$|U|$, $|W|\geq\eta n$, we have
$$
\big|e_G(U,W)-p|U||W|\big|\leq\eta p|U||W|.
$$

Now let~$H\subset G$ be a spanning subgraph of~$G$. For~$U$, $W\subset
V$ with~$U\cap W=\emptyset$, let 
$$
\dHG(U,W)=\cases e_H(U,W)/e_G(U,W)  &\text{if }e_G(U,W)>0 \\
                 0                  &\text{if }e_G(U,W)=0.
          \endcases
$$
Suppose~$\epsilon>0$, $U$, $W\subset V$, and~$U\cap W=\emptyset$. We
say that the pair~$(U,W)$ is {\deffont$(\epsilon,H,G)$-regular\/}
if for all~$U'\subset U$, $W'\subset W$ with~$|U'|\geq\epsilon|U|$
and~$|W'|\geq\epsilon|W|$, we have 
$$
|\dHG(U',W')-\dHG(U,W)|\leq\epsilon.
$$

We say that a partition~$P=(V_i)_0^k$ of~$V=V(G)$ is
{\deffont$(\epsilon,k)$-equitable\/} if~$|V_0|\leq\epsilon n$,
and~$|V_1|=\ldots=|V_k|$. Also, we say that~$V_0$ is the {\deffont
  exceptional\/} class of~$P$. When the value of~$\epsilon$ is not
relevant, we refer to an $(\epsilon,k)$-equitable partition as a
{\deffont$k$-equitable\/} partition. Similarly, $P$ is an {\deffont
  equitable\/} partition of~$V$ if it is a $k$-equitable partition for
some~$k$. Finally, we say that an $(\epsilon,k)$-equitable
partition~$P=(V_i)_0^k$ of~$V$ is
{\deffont$(\epsilon,H,G)$-regular\/} if at most~$\epsilon{k\choose2}$ 
pairs~$(V_i,V_j)$ with~$1\leq i<j\leq k$ are not
$(\epsilon,H,G)$-regular.  We can now state an extension of
Szemer\'edi's lemma to subgraphs of $\eta$-uniform graphs, observed
independently by R\"odl~{\refRoSzL} and Kohayakawa~{\refKo}. 

\proclaim {Lemma {\SSz}} For given~$\epsilon>0$ and~$k_0\geq1$, there
are constants~$\eta=\eta(\epsilon,k_0)>0$
and~$K_0=K_0(\epsilon,k_0)\geq k_0$ that depend only on~$\epsilon$
and~$k_0$ such that, if~$G$ is an $\eta$-uniform graph and~$H\subset
G$ is a spanning subgraph of~$G$, then there is an
$(\epsilon,H,G)$-regular $(\epsilon,k)$-equitable partition
of~$V=V(G)$ with~$k_0\leq k\leq K_0$.\qed
\endproclaim

We now state two lemmas concerning random graphs. Here and below,
if~$n\geq1$ and~$0\leq p=p(n)\leq1$, we let~$\G(n,p)$ be the
probability space of the random graphs~$G_p=G_{n,p}$.  The following
is immediate from standard estimates for tails of the binomial
distribution.

\proclaim{Lemma {\etaunif}} Let~$0<\eta\leq1$ be given, and consider
the random graph~$G_p=G_{n,p}\in\G(n,p)$ with~$0<p=p(n)<1$.
Put~$d=d(n)=np(n)$. Then, there is a constant~$d_0=d_0(\eta)$ such
that, if~$d\geq d_0$, almost every~$G_p$ is $\eta$-uniform with
density~$p$.\qed
\endproclaim

We now introduce another uniformity condition for graphs.  Let~$G=G^n$
be a graph of order~$n$, and suppose~$A>0$ and~$p>0$.  Let~$d=pn$. We
say that~$G$ is {\deffont$(p,A)$-uniform\/} if, for all sets~$U$,
$W\subset V(G)$ with~$U\cap W=\emptyset$ and~$1\leq|U|\leq|W|\leq
d|U|$, we have
$$
\big|e_G(U,W)-p|U||W|\big|\leq A\{d|U||W|\}^{1/2}. 
$$
The following lemma is proved in~{\refHKL}. 

\proclaim{Lemma {\lemmapA}} Let~$d=d(n)>0$ be given, and
put~$p=p(n)=d/n$. Then a.e.~$G_p=G_{n,p}\in\G(n,p)$ is
$(p,20)$-uniform.\qed
\endproclaim

Let us remark that when dealing with $(p,A)$-uniform graphs of
order~$n$, we shall always have~$d=pn$. Our last preliminary lemma
concerns the size of induced subgraphs of $(p,A)$-uniform graphs.  In
this lemma and in the sequel, we write~$O_1(x)$ for a term~$y$ that
satisfies~$|y|\leq x$. 

%Using the fact
%that every graph~$H$ on~$u$ vertices contains a bipartite
%subgraph~$B\subset H$ whose vertex classes have cardinalities~$\lfloor
%u/2\rfloor$ and~$\lceil u/2\rceil$ and such that~$e(B)\geq(\lfloor
%u^2/4\rfloor/{u\choose2})e(H)$, one may easily deduce the following result.

\proclaim{Lemma {\lemmaLocpA}} Suppose given~$A$ and~$p>0$,
let~$G=G^n$ be a $(p,A)$-uniform graph, and suppose~$U\subset V(G)$.
Then the size~$e(G[U])$ of the graph~$G[U]$ induced by~$U$ in~$G$
satisfies
$$
e(G[U])=p{|U|\choose2}+O_1(Ad^{1/2}|U|). %\eqno{\qed}
$$
\endproclaim
\demo{Sketch of proof}
It suffices to notice that
$$
e(G[U])={u\choose2}\left\{\left\lfloor{u\over2}\right\rfloor
          \left\lceil{u\over2}\right\rceil\right\}^{-1}
            \Ave_Se_G(S,U\setminus S), 
$$
where~$u=|U|$ and~$\Ave_Se_G(S,U\setminus S)$ denotes the average
of~$e_G(S,U\setminus S)$ when~$S$ runs over all~$S\subset U$
with~$|S|=\lfloor u/2\rfloor$.\qed
\enddemo
%
% sec21
%
\head\S2. The Main Result
\endhead

\subhead2.1. Proof of the main result
\endsubhead
Our aim in this section is to give the proof of Theorem~{\MainOddThm}.
However, to state the key lemma in our argument, Lemma~{\MainOddL}, we
need to introduce some definitions and notation.  Given a graph~$H$
and an integer~$\ell\geq1$, let us define the graph~$J=J(H)=J_\ell(H)$
on~$V=V(H)$ by joining two distinct vertices~$x$, $y\in V$ in~$J$ if
and only if there is an $x$--$y$~path of length~$2\ell$ in~$H$. Now
suppose real constants~$A$, $C>0$ and~$0<\gamma_0\leq1$ are fixed.
Moreover, suppose~$G=G^n$ is a $(p,A)$-uniform graph,
where~$p=p(n)\geq Cn^{-1+1/2\ell}$, and let~$H\subset G$ be a subgraph
of~$G$ of size~$e(H)\geq\gamma_0e(G)$.  The main lemma in the proof of
Theorem~{\MainOddThm}, Lemma~{\MainOddL}, states that~$e(J)$ is nearly
as large as~$(e(H)/e(G)){n\choose2}$ provided~$C$ and~$n$ are
sufficiently large with respect to~$\ell$, $A$, and~$\gamma_0$.

\proclaim {Lemma {\MainOddL}} Let an integer~$\ell\geq1$, and
reals~$0<\delta\leq1$, $0<\gamma_0\leq1$, and~$A>0$ be fixed. Then
there is a constant~$C_0=C_0(\ell,\delta,\gamma_0,A)>0$ for which the
following holds. Let~$G=G^n$ be a $(p,A)$-uniform graph
with~$p=p(n)\geq C_0n^{-1+1/2\ell}$, and let~$H\subset G$ be a
subgraph of~$G$ with~$e(H)\geq\gamma_0e(G)$. Then, provided~$n$ is
sufficiently large, we
have~$e(J_\ell(H))\geq(1-\delta)(e(H)/e(G)){n\choose2}$.
\endproclaim

The proof of Lemma~{\MainOddL} is given in Section~2.2. In that
section we also observe that this result is in fact best possible, and
make a few remarks on the structure of the extremal subgraphs~$H$ for
this lemma. 

Let us now turn to the proof of Theorem~{\MainOddThm}.  However, as
this proof is somewhat technical in parts, we first present its main
idea informally here to give the reader some feeling about the way we
shall follow. Thus let~$\ell\geq1$ and~$0<\eta\leq1/2$ be given, and
let~$p=p(n)\geq Cn^{-1+1/2\ell}$ where~$C$ is a suitably large
constant to be chosen later. Let us add the technical condition
that~$p=p(n)=o(1)$ as~$n\to\infty$.  We view the random
graph~$G_p=G_{n,p}$ as a union of two independent random
graphs~$\Gp11$ and~$\Gp12$, both with edge-probability~$p_1$. Thus, as
we are assuming that~$p=o(1)$, we have in particular that~$p_1\sim
p/2$. We decompose~$\Gp11$ even further, writing it as a union of~$k$
independent random graphs~$\Gp2i$ ($1\leq i\leq k$). Here~$k$ is a
fixed large constant to be chosen later, and hence, since~$p=o(1)$, we
have~$p_2\sim p_1/k\sim p/2k$.

Now suppose~$F$ is a subset of edges of~$G_p$ with
cardinality~$(1/2+\eta)e(G_p)$ but spanning no $(2\ell+1)$-cycle.
Assume that~$\Gp11$ and~$\Gp12$ contain~$\gamma_1e(\Gp11)$
and~$\gamma_2e(\Gp12)$ edges of~$F$ respectively. Note
that~$\gamma_1+\gamma_2\sim1+2\eta$. Moreover, amongst the~$\Gp2i$
($1\leq i\leq k$), assume that~$\Gp2j$ contains the maximum number of
edges from~$F$: we assume that it contains~$\gamma^*e(\Gp2j)$ of them,
where clearly~$\gamma^*\gtrsim\gamma_1$. Now, assuming that~$C$ is
large enough, we use Lemma~{\MainOddL} to deduce that the edges of~$F$ 
contained in~$\Gp2j$ create at least about~$\gamma^*{n\choose2}$ pairs
of vertices of~$\Gp12$ that may not form edges in~$F$, as~$G_p[F]$
contains no $(2\ell+1)$-cycle. Let us call such pairs of vertices
{\deffont prohibited\/}. Now, with very large probability, say~$\tilde
P$, not many fewer than~$\gamma^*e(\Gp12)$ edges of~$\Gp12$ join
prohibited pairs, and hence not many more than~$(1-\gamma^*)e(\Gp12)$
edges of~$\Gp12$ belong to~$F$. However, the number of such edges is  
$$
\gamma_2e(\Gp12)\sim(1+2\eta-\gamma_1)e(\Gp12)
  \gtrsim(1+2\eta-\gamma^*)e(\Gp12).
$$
This shows that actually considerably fewer than~$\gamma^*e(\Gp12)$
edges of~$\Gp12$ may join prohibited pairs of vertices. Thus the
probability that there is a set~$F\subset E(G_p)$ as above is at
most~$1-\tilde P$. It turns out that in fact~$\tilde P$ is so large
that~$1-\tilde P$ can kill the number of possibilities for the
set~$F\cap E(\Gp2j)\subset E(\Gp2j)$, provided we pick~$k$ large
enough. Thus we conclude that almost surely such a set~$F$ does not
exist, and the theorem follows in this case, namely, when~$p=p(n)\geq 
Cn^{-1+1/2\ell}$ for some suitably large constant~$C$ and~$p=o(1)$. 

We still have to deal with the case in which~$p=p(n)$ does not
tend to~$0$ as~$n\to\infty$. Here we only sketch an argument based on the
original regularity lemma of Szemer\'edi. Recall~$\ell\geq1$
and~$0<\eta\leq1/2$ are given. Suppose~$0<\rho\leq1$ and~$A>0$ are
fixed constants and let~$G=G^n$ be a $(\rho,A)$-uniform graph of
order~$n$. Then a standard application of Szemer\'edi's lemma gives
that~$\ex(G,C^{2\ell+1})\leq(1/2+\eta)e(G)$ as long as~$n\geq n_0$ for
some constant~$n_0=n_0(\ell,\eta,\rho,A)$.  This implies that there is
a function~$\rho_0=\rho_0(n)$ tending to~$0$ as~$n\to\infty$ such that
the above statement remains true even if~$\rho$ is allowed to vary
with~$n$: it suffices that~$\rho=\rho(n)\geq\rho_0(n)$. Since almost
every random graph~$G_p=G_{n,p}$ is $(p,20)$-uniform,
Theorem~{\MainOddThm} follows for~$p=p(n)\geq\rho_0(n)$.

Let us now give the proof with all the details.

\demo{Proof of Theorem~{\MainOddThm}} Let~$A=20$,
$k=\lceil54\eta^{-3}\rceil$, $\epsilon=\eta/12$, $\delta=\eta/4$,
$\gamma_0=\eta$, and let~$C=C(\ell,\eta)=2kC_0>0$, where
$C_0=C_0(\ell,\delta,\gamma_0,A)>0$ is as given in Lemma~{\MainOddL}.
We shall show that this choice of~$C$ will do in
Theorem~{\MainOddThm}. Thus we fix~$p=p(n)\geq Cn^{-1+1/2\ell}$ and
investigate $C^{2\ell+1}$-free subgraphs of~$G_p\in\G(n,p)$ of large
size. As always, we may assume throughout that~$n$ is as large as we
please. Also, owing to the remarks above, it suffices to consider the
case in which~$p=p(n)=o(1)$.

We shall `generate'~$G_p$ in~$k+1$ `rounds' as follows.
Let~$0<p_1=p_1(n)<1$, $0<p_2=p_2(n)<1$ be such that~$1-p=(1-p_1)^2$,
$1-p_1=(1-p_2)^k$, and consider~$k+1$ independent random
graphs~$\Gp2j\in\G(n,p_2)$ ($1\leq j\leq k$), $\Gp12\in\G(n,p_1)$. It
is clear that~$\Big\{\bigcup_{1\leq j\leq k}\Gp2j\Big\}\cup\Gp12$ is a
random element of the space~$\G(n,p)$. Below we work
with~$\bG=(\Gp21,\dots,\Gp2k;\Gp12)\in\Omega=\Big\{\prod_{1\leq j\leq
  k}\G(n,p_2)\Big\}\times\G(n,p_1)$, and always
let~$\Gp11=\bigcup_{1\leq j\leq k}\Gp2j$ and~$G_p=\Gp11\cup\Gp12$.
The `bad' event~$\B$ whose probability we need to show approaches~$0$
as~$n\to\infty$ is that there should be a set~$F\subset E(G_p)$
with~$|F|>(1/2+\eta)e(G_p)$ and~$G_p[F]\not\supset C^{2\ell+1}$. 

Recall that we write~$O_1(x)$ for a term~$y$ that satisfies~$|y|\leq
x$. Let~$\Omega'\subset\Omega$ be the set
of~$\bG=(\Gp21,\dots,\Gp2k;\Gp12)\in\Omega$ for which the~$\Gp2j$
($1\leq j\leq k$) are $(p_2,A)$-uniform,
$e(\Gp2j)=(1+O_1(\epsilon))(p/2k){n\choose2}$ ($1\leq j\leq k$),
$e(\Gp1i)=(1+O_1(\epsilon))(p/2){n\choose2}$ ($i\in\{1,2\}$), and
finally~$e(G_p)=(1+O_1(\epsilon))p{n\choose2}$.
Since~$\P(\Omega')=1-o(1)$ as~$n\to\infty$, below we always assume
that our~$\bG$ are in~$\Omega'$. In particular, we concentrate
on~$\B'=\B\cap\Omega'$.

Now, for each~$\bG\in\B'$, fix~$F=F(\bG)\subset E(G_p)$
with~$|F|>(1/2+\eta)e(G_p)$ and~$G_p[F]\not\supset C^{2\ell+1}$.
Moreover, let~$F_i=F_i(\bG)=F\cap E(\Gp1i)$, $f_i=f_i(\bG)=|F_i|$,
and~$\gamma_i=\gamma_i(\bG)=f_i/e(\Gp1i)$ for~$i\in\{1,2\}$,
and similarly~$F^{(j)}=F^{(j)}(\bG)=F\cap E(\Gp2j)$,
$f^{(j)}=f^{(j)}(\bG)=|F^{(j)}|$,
and~$\gamma^{(j)}=\gamma^{(j)}(\bG)=f^{(j)}/e(\Gp2j)$ for~$1\leq j\leq
k$. Let us now fix~$\bG\in\B'$. 

Note that clearly~$|F|=|F(\bG)|\leq f_1+f_2$, and
hence~$1/2+\eta<|F|/e(G_p)
\leq\{e(\Gp11)/e(G_p)\}\gamma_1+\{e(\Gp12)/e(G_p)\}\gamma_2
\leq(1+3\epsilon)(\gamma_1+\gamma_2)/2$.
Thus~$\gamma_1+\gamma_2\geq(1+2\eta)/(1+3\epsilon)$. Furthermore, we
have that~$f_1\leq f^{(1)}+\dots+f^{(k)}$, and
hence~$\gamma_1\leq((1+3\epsilon)/k)\sum_{1\leq j\leq k}\gamma^{(j)}$.
Hence, putting~$\gamma^*=\gamma^*(\bG)=\max_{1\leq j\leq
  k}\gamma^{(j)}$, we have~$(1+3\epsilon)(\gamma^*+\gamma_2)
\geq(1+3\epsilon)(\gamma_1+\gamma_2)\geq1+2\eta$, and
therefore~$\gamma^*+\gamma_2\geq(1+2\eta)/(1+3\epsilon)\geq1+\eta$. 
Note that in particular~$\gamma^*\geq\eta$. Now, for~$1\leq j\leq k$, 
let~$\B_j'=\{\bG\in\B'\:\gamma^{(j)}(\bG)=\gamma^*(\bG)\}$.
Clearly~$\B'=\bigcup_{1\leq j\leq k}\B_j'$, and hence it suffices to
show that~$\P(\B_j')=o(1)$ as~$n\to\infty$ for all fixed~$1\leq j\leq
k$. Thus let us now fix~$1\leq j\leq k$, and
consider~$\bG\in\B_j'$. We have
$$
\eqalignno{
\P(\B_j')&=\sum_{G_0}\P(\B_j'\cap\{\bG\:\Gp2j=G_0\})\cr
  &\qquad=\sum_{G_0}\P(\B_j'\cond\Gp2j=G_0)\P(\Gp2j=G_0)
     \leq\max_{G_0}\P(\B_j'\cond\Gp2j=G_0),\quad&\alabel{SumA}\cr 
}
$$
where~$G_0$ ranges over all $(p_2,A)$-uniform graphs on~$V(G_p)$ with
size~$e(G_0)=(1+O_1(\epsilon))(p/2k){n\choose2}$. We now {\it fix\/}
one such~$G_0$ and argue that~$\P(\B_j'\cond\Gp2j=G_0)$ is small. 
For~$F_0\subset E(G_0)$, let~$P(j,G_0,F_0)=\P\{\bG\in\B_j'\text{
  and }F^{(j)}(\bG)=F_0\cond\Gp2j=G_0\}$. Then
$$
\P(\B_j'\cond\Gp2j=G_0)=\sum_{F_0\subset E(G_0)}P(j,G_0,F_0) 
  \leq2^{(1+\epsilon)(p/2k){n\choose2}}
          \max_{F_0\subset E(G_0)}P(j,G_0,F_0).\slabel{SumB}
$$
Let us now {\it fix\/}~$F_0\subset E(G_0)$ with~${P(j,G_0,F_0)}>0$.
In particular, $\gamma^*=|F_0|/e(G_0)\geq\eta=\gamma_0$. It now
follows from Lemma~{\MainOddL}
that~$e(J_\ell(G_0[F_0]))\geq(1-\delta)\gamma^*{n\choose2}$.

Now, for each~$\bG\in\Omega$, let us put~$F'=F'(\bG)=E(\Gp12)\cap
E(J_\ell(G_0[F_0]))$, and let~$f'=f'(\bG)=|F'|$. Note that
then, clearly, $f'=f'(\bG)$ ($\bG\in\Omega$) has binomial
distribution~$\Bi(e(J_\ell(G_0[F_0])),p_1)$ with
parameters~$e(J_\ell(G_0[F_0]))$ and~$p_1$. Now suppose~$\bG\in\B'$,
$\Gp2j=G_0$, and~$F^{(j)}=F_0$. Then, since~$F=F(\bG)$ does not span a  
$(2\ell+1)$-cycle, we have~$F'(\bG)\cap F_2(\bG)=\emptyset$.
Since~$F'(\bG)\cup F_2(\bG)\subset E(\Gp12)$, we
have~$f'(\bG)+\gamma_2(\bG)e(\Gp12)=f'(\bG)+f_2(\bG)\leq e(\Gp12)$,
and hence~$f'(\bG)\leq(1-\gamma_2(\bG))e(\Gp12)$. Therefore
$$
\eqalignno{
P(j,G_0,F_0)
&\leq\P\{\bG\in\Omega'\text{ and }
  f'(\bG)\leq(1-\gamma_2(\bG))e(\Gp12)\}\cr
&\leq\P\left\{f'(\bG)
   \leq(1-\gamma_2(\bG))(1+\epsilon){p\over2}{n\choose2}\right\}.
  &\alabel{SumC}\cr
}
$$
We now bound this last probability using
that~$f'=f'(\bG)\sim\Bi(e(J_\ell(G_0[F_0])),p_1)$.  
Clearly, $\E(f')\leq p_1{n\choose2}\leq p{n\choose2}$. Moreover, 
recalling that~$\gamma^*+\gamma_2\geq1+\eta$, we have
$$
\eqalign{
\E(f')-(1-\gamma_2)(1+\epsilon){p\over2}{n\choose2}
 \geq\big\{(1-\delta)\gamma^*-(1+\epsilon)(1-\gamma_2)\big\}
       {p\over2}{n\choose2}\qquad\qquad&\cr
\geq(\eta-\delta-\epsilon){p\over2}{n\choose2}
\geq{\eta\over3}p{n\choose2}\geq{\eta\over3}\E(f'),&\cr
}
$$
and in particular~$\E(f')\geq(\eta p/3){n\choose2}$. 
Hence, by Hoeffding's inequality~{\refHoeff} (see also
inequality (5.6) in McDiarmid~{\refMcD}), 
$f'\leq(1-\gamma_2)(1+\epsilon){p\over2}{n\choose2}$ occurs with
probability no greater than 
$$
\P\left\{f'\leq\(1-{\eta\over3}\)\E(f')\right\}
    \leq\exp\left\{-{\eta^3\over54}p{n\choose2}\right\}. 
$$
Thus, by~{\eqnoSumB} and~{\eqnoSumC}, we have
$$
\P(\B_j'\cond\Gp2j=G_0)
 \leq2^{(1+\epsilon)(p/2k){n\choose2}}
        \exp\left\{-{\eta^3\over54}p{n\choose2}\right\}
 \leq\exp\left\{-{C\over352}\eta^3n^{1+1/2\ell}\right\}. 
$$
Thus, by~{\eqnoSumA}, we have~$\P(\B_j')=o(1)$ as~$n\to\infty$, as
required.\qed
\enddemo

\remark{Remark} The idea of looking at~$\G(n,p)$
as~$\Omega=\Big\{\prod_{1\leq j\leq k}\G(n,p_2)\Big\} 
\times\G(n,p_1)$ in the above proof was inspired by R\"odl and
Ruci\'nski~{\refRRb}, where a similar, slightly simpler, decomposition
is used. 
\endremark

An immediate corollary of Theorem~{\MainOddThm} is as follows. 

\proclaim {Corollary {\OddCor}} Let an integer~$\ell\geq1$ be fixed,
and suppose~$\omega=\omega(n)\to\infty$ as~$n\to\infty$. Then
if~$0<p=p(n)=\omega n^{-1+1/2\ell}\leq1$ we almost surely
have~$\ex(G_p,C^{2\ell+1})=(1/2+o(1))e(G_p)$.\qed
\endproclaim

\remark{Remark} A simple alteration to the above proof of
Theorem~{\MainOddThm} gives in fact that, for any fixed~$\ell\geq1$
and~$0<\eta\leq1/2$, there is a constant~$C'=C'(\ell,\eta)>0$ such
that, if~$p=p(n)\geq C'n^{-1+1/2\ell}$, then almost
every~$G_p\in\G(n,p)$ is such that any subgraph~$H\subset G_p$
with~$e(H)\geq(1/2+\eta)e(G_p)$ contains at least~$c\eta e(G_p)$
copies of~$C^{2\ell+1}$, where~$c>0$ is an absolute constant. This
result is, however, rather weak for large~$p$, as in this case one
would expect the number of such copies to be much greater
than~$e(G_p)$. This problem will be addressed elsewhere, as will the
problem of investigating the structure of the extremal subgraphs for
Theorem~{\MainOddThm}. 
\endremark
%
% sec22
%
\subhead2.2. Proof of the main lemma
\endsubhead
The main ingredients of the proof of Lemma~{\MainOddL} are a simple
deterministic extremal result on edge-weighted graphs,
Lemma~{\WeightL}, and the variant of Szemer\'edi's lemma,
Lemma~{\SSz}, given in~\S1.  Let a graph~$H=H^k$ of order~$k$ be
given, and suppose~$\bgamma=(\gamma_e)_{e\in E(H)}^{}$ is a family of
{\deffont weights\/}~$0\leq\gamma_e\leq1$ on the edges~$e\in E(H)$
of~$H$.  Given vertices~$x$, $y\in H$, not necessarily distinct,
let~$Z_{x,y}=\Gamma_H(x)\cap\Gamma_H(y)$, and put
$$
w(x,y)=w_{H,\bgamma}(x,y)
  =\cases0   &\text{if~$Z_{x,y}=\emptyset$}\\
         \max\{\gamma_{zy}\:z\in Z_{x,y}\}
             &\text{if~$Z_{x,y}\neq\emptyset$.}
   \endcases                          
$$
Also, for~$x\in H$, let~$\dgamma(x)=d^{H,\bgamma}(x)
=\sum_{y\in\Gamma_H(x)}\gamma_{xy}$ be the
{\deffont$\bgamma$-degree\/} of~$x$. For simplicity, put
also~$\bgamma(H)=\sum_{e\in E(H)}\gamma_e$. Assume now
that~$\bfx=(x_1,\dots,x_k)$ is an ordering of the vertices of~$H$.
Then we let~$w(H,\bgamma,\bfx)=\sum_{1\leq i\leq j\leq
  k}w(x_i,x_j)$. We shall in fact be interested in certain special
orderings of~$V(H)$. Let us say that an
ordering~$\bfx=(x_1,\dots,x_k)$ of the vertices of~$H$ {\deffont
  respects\/}~$\bgamma$ if, for any~$1\leq i\leq k$, the
vertex~$x_i$ is a vertex of minimal $\bgamma_i$-degree
in~$H_i=H[x_i,\dots,x_k]$, the subgraph of~$H$ induced
by~$\{x_i,\dots,x_k\}$, where~$\bgamma_i=(\gamma_e)_{e\in
  E(H_i)}^{}$. We may now give the first ingredient of the proof of
Lemma~{\MainOddL}. 

\proclaim {Lemma {\WeightL}} Let~$H=H^k$ be a graph of order~$k$, and
let~$\bgamma=(\gamma_e)^{}_{e\in E(H)}$ with~$0\leq\gamma_e\leq1$
$(e\in E(H))$ be given. Let~$\bfx=(x_1,\dots,x_k)$ be an ordering of
the vertices of~$H$ that respects~$\bgamma$.
Then~$w(H,\bgamma,\bfx)\geq\bgamma(H)$. 
\endproclaim
\demo{Proof}
We prove this lemma by induction on~$k$. If~$k=1$, there is nothing to
prove. Thus assume~$k\geq2$, and suppose the lemma holds for smaller
values of~$k$. Consider~$H_2=H[x_2,\dots,x_k]$
and~$\bgamma_2=(\gamma_e)_{e\in E(H_2)}^{}$. Clearly,
$\bfx_2=(x_2,\dots,x_k)$ is an ordering of the vertices of~$H_2$ that 
respects~$\bgamma_2$, and hence by induction we
have~$w(H_2,\bgamma_2,\bfx_2)\geq\bgamma_2(H_2)$.
If~$\Gamma_H(x_1)=\emptyset$, we
have~$w(H,\bgamma,\bfx)=w(H_2,\bgamma_2,\bfx_2)\geq\bgamma_2(H_2)=
\bgamma(H)$, as required. Thus assume~$\Gamma_H(x_1)\neq\emptyset$,
and pick~$z\in\Gamma_H(x_1)$. From our assumption on the
ordering~$\bfx$, we have~$d^{H,\bgamma}(z)\geq d^{H,\bgamma}(x_1)$.
Therefore 
$$
\eqalign{
w(H,\bgamma,\bfx)
&\geq w(H_2,\bgamma_2,\bfx_2)+\sum_{y\in\Gamma_H(z)}w(x_1,y)
  \geq\bgamma_2(H_2)+\sum_{y\in\Gamma_H(z)}\gamma_{zy}\cr
&\qquad\qquad\qquad=\bgamma_2(H_2)+d^{H,\bgamma}(z) 
    \geq\bgamma_2(H_2)+d^{H,\bgamma}(x_1)
       =\bgamma(H),\cr
}
$$
as required.\qed
\enddemo

Our next lemma, Lemma~{\LocExp}, is the key observation that enables
us to use Lemma~{\SSz} together with Lemma~{\WeightL} to prove
Lemma~{\MainOddL}. To describe the context in which Lemma~{\LocExp}
applies, let an integer~$\ell\geq1$, and reals~$A$, $C$, $\epsilon$,
$\mu>0$, and~$\gamma\geq\rho>0$ be fixed. Assume that~$G=G^n$ is a
$(p,A)$-uniform graph with~$p\geq Cn^{-1+1/2\ell}$, and let~$H\subset
G$ be a spanning subgraph of~$G$. Let three pairwise disjoint
sets~$V_1$, $V_2$, $V_3\subset V=V(G)$ with~$|V_i|=m\geq\mu n$
($i\in\{1,2,3\}$) be given.  Furthermore, assume~$(V_1,V_2)$
and~$(V_2,V_3)$ are $(\epsilon,H,G)$-regular pairs
with~$d_{1,2}=\dHG(V_1,V_2)\geq\rho$
and~$d_{2,3}=\dHG(V_2,V_3)\geq\gamma$.  Roughly speaking,
Lemma~{\LocExp} states that the graph~$J=J(H)=J_\ell(H)$ is such
that~$e_{J_\ell}(V_1,V_3)$ is nearly as large as~$\gamma m^2$,
provided only that~$C$ and~$n$ are sufficiently large and~$\epsilon$
is sufficiently small with respect to~$\ell$, $A$, $\mu$, $\gamma$, 
and~$\rho$.

In the proof of Lemma~{\LocExp}, we shall need the following simple
definitions. Let~$J$ be a bipartite graph with a fixed bipartition,
say~$V(J)=X\cup Y$.  Then we shall say that~$J$ is a
{\deffont$(b,f)$-expander\/}, and that it is
{\deffont$(b,f)$-expanding\/}, if for all~$U\subset V(J)$
with~$|U|\leq b$ and moreover~$U\subset X$ or~$U\subset Y$ we
have~$|\Gamma_J(U)|\geq f|U|$.  Also, if~$G$ is a graph and~$U$,
$W\subset V(G)$ are two disjoint sets of vertices, we shall
write~$G[U,W]$ for the bipartite subgraph of~$G$ with vertex
classes~$U$, $W$ and with edge set~$E(U,W)=E_G(U,W)$.

\proclaim {Lemma {\LocExp}} Let an integer~$\ell\geq1$, and reals~$A$,
$C>0$, $0<\delta\leq1$, $0<\mu\leq1$, and~$0<\rho\leq\gamma\leq1$ be
fixed. Let the graphs~$H\subset G$, and~$J_\ell=J_\ell(H)$ be as
above. Then, if~$C\geq C_0=32(A/\delta\rho\mu)^2$
and~$0<\epsilon\leq\epsilon_0=\delta\rho/24$, we
have~$e(J_\ell[V_1,V_3])\geq(1-\delta)\gamma m^2$ provided~$n$ is
sufficiently large.
\endproclaim
\demo{Proof}
We assume throughout that~$n$ is large, and in particular that~$G$ is
$\eta$-uniform for~$\eta=\epsilon\mu$. We prove Lemma~{\LocExp} by
establishing three claims. 

\assertion(1) There are sets~$\bV_i\subset V_i$
with~$|\bV_i|\geq(1-2\epsilon)m$ $(i\in\{1,2,3\})$ such
that~$H_{1,2}=H[\bV_1,\bV_2]$ and~$H_{2,3}=H[\bV_2,\bV_3]$ have minimal
degree~$\delta(H_{1,2})\geq(1-\delta/4)d_{1,2}pm$
and~$\delta(H_{2,3})\geq(1-\delta/4)d_{2,3}pm$.
\endassertion
\proofofassertion
To prove~(1), one may use the argument in the proof of Lemma~2
of~{\refHKL}. Here we only sketch an argument. To find the~$\bV_i$
($i\in\{1,2,3\}$), we successively delete the vertices~$v\in V_1\cup 
V_2\cup V_3$ that violate the condition we seek. Then one may easily
show that, owing to the $(\epsilon,H,G)$-regularity
of~$(V_1,V_2)$ and~$(V_2,V_3)$, this process finishes with the
required sets~$\bV_i$ ($i\in\{1,2,3\}$). 
\endproofofassertion

Our next claim follows from~(1) above and the $(p,A)$-uniformity
of~$G$.

\assertion(2) For~$(i,j)=(1,2)$ and~$(i,j)=(2,3)$, the bipartite
graph~$H_{i,j}=H[\bV_i,\bV_j]$ is
$((1-\delta/2)d_{i,j}m/f,f)$-expanding for
any~$0<f\leq(\delta\rho\mu/4A)^2d$.
\endassertion
\proofofassertion
To prove~(2), fix~$(i,j)\in\{(1,2),(2,3)\}$, 
let~$\sigma\in\{i,j\}$, and suppose~$0<f\leq(\delta\rho\mu/4A)^2d$. 
Pick~$U\subset\bV_\sigma$ with~$u=|U|\leq(1-\delta/2)d_{i,j}m/f$, and 
put~$W=\Gamma_{H_{i,j}}(U)$. Assume for a contradiction
that~$w=|W|<fu$. Then, by~(1) and the $(p,A)$-uniformity of~$G$,  
we have 
$$
\eqalign{
&\(1-{\delta\over4}\)d_{i,j}pmu
      \leq e_{H_{i,j}}(U,W)\leq e_G(U,W)\cr
&\qquad\qquad\qquad\leq puw+A(duw)^{1/2}
    \leq\(1-{\delta\over2}\)d_{i,j}pmu+A(duw)^{1/2}.\cr
}
$$
Thus~$(\delta/4)d_{i,j}pmu\leq A(duw)^{1/2}$, and
hence~$w\geq(\delta\rho\mu/4A)^2du\geq fu$, which is a contradiction.
Thus~$|\Gamma_{H_{i,j}}(U)|\geq f|U|$, as required. 
\endproofofassertion

Our third and last claim is as follows. 

\assertion(3) For all~$x\in\bV_1$, we
have~$|\Gamma_{J_\ell}(x)\cap\bV_3|\geq(1-3\delta/4)\gamma m$. 
\endassertion
\proofofassertion
To check~(3), note that~$d=pn=Cn^{1/2\ell}$, and hence that~$H_{1,2}$
and~$H_{2,3}$ are $((1-\delta/2)d_{i,j}m/f,f)$-expanding
for~$0<f\leq2n^{1/2\ell}$.  Now fix~$x\in\bV_1$, and let~$X_0=\{x\}$.
Let $X_1$, $X_2, \ldots, X_{2\ell-1}$ be such that $n^{i/2\ell}\leq
|X_i|\leq 2n^{i/2\ell}$ for $1\leq i\leq 2\ell-1$, and
$X_1\subset\Gamma_{H_{1,2}}(X_0)$, $X_2\subset\Gamma_{H_{1,2}}(X_1)\setminus
X_0,\dots$,
$X_{2\ell-1}\subset\Gamma_{H_{1,2}}(X_{2\ell-2})\setminus(X_1\cup\cdots\cup
X_{2\ell-3})$. Finally, let~$X_{2\ell}=\Gamma_{H_{2,3}}(X_{2\ell-1})$. 
From the expansion property~(2) of the~$H_{i,j}$, the result follows.  
\endproofofassertion

Lemma~{\LocExp} follows from~(1) and~(3) above, 
as~$e(J_\ell[V_1,V_3])\geq(1-3\delta/4)\gamma
m|\bV_1|\geq(1-\delta)\gamma m^2$.\qed
\enddemo

We are now ready to prove Lemma~{\MainOddL}, the main lemma in the
proof of Theorem~{\MainOddThm}.

\demo{Proof of Lemma~{\MainOddL}} Let an integer~$\ell\geq1$, and
reals~$0<\delta\leq1$, $0<\gamma_0\leq1$, and~$A>0$ be fixed.  We may
clearly assume that~$\delta\leq15\gamma_0$.
Let~$\epsilon=\gamma_0\delta^2/2200$ and~$k_0=\lceil1/\epsilon\rceil$,
and let~$0<\eta=\eta(\epsilon,k_0)\leq1$
and~$K_0=K_0(\epsilon,k_0)\geq k_0$ be as given in Lemma~{\SSz}. We
may and shall assume that~$\eta\leq\epsilon/2K_0$.
Let~$\rho=\gamma_0\delta/15\leq1$ and~$C_0=C_0(\ell,\delta,\gamma_0,A)
=10^7(AK_0/\delta^2\gamma_0)^2_{}$.  We shall show that this~$C_0$
will do in our lemma. Thus, let~$H\subset G$ be a subgraph of a
$(p,A)$-uniform graph~$G=G^n$ with~$e(H)\geq\gamma_0e(G)$,
where~$p=p(n)\geq C_0n^{-1+1/2\ell}$. Let~$\gamma=e(H)/e(G)$. We now 
investigate~$J_\ell=J_\ell(H)$. We may clearly assume that~$H$ is a
spanning subgraph of~$G$. Furthermore, we may assume throughout
that~$n$ is larger than some suitably chosen large constant, and in
particular that~$G=G^n$ is $\eta$-uniform with density~$p$
(cf.~Lemma~{\lemmaLocpA}). We now apply Lemma~{\SSz} to~$H\subset G$
to obtain an $\epsilon$-equitable $(\epsilon,H,G)$-regular
partition~$P=(V_i)_0^k$ of~$V=V(G)$ with~$k_0\leq k\leq K_0$. For
convenience, let~$m=|V_i|$ ($1\leq i\leq k$).

We now define a graph~$H^*$ on~$[k]$ by letting~$ij\in E(H^*)$ ($1\leq
i<j\leq k$) if and only if~$(V_i,V_j)$ is an $(\epsilon,H,G)$-regular
pair with~$\dHG(V_i,V_j)\geq\rho$. Moreover, for~$e=ij\in E(H^*)$,
let~$\gamma_e=\dHG(V_i,V_j)$, and
let~$\bgamma=(\gamma_e)^{}_{e\in E(H^*)}$.  We may and shall assume
that the natural ordering~$\bfx=(1,\dots,k)$ of the vertices of~$H^*$
respects~$\bgamma$. Finally, let us define a spanning
subgraph~$H'\subset H$ of~$H$ by letting~$xy\in E(H)$ be an edge
of~$H'$ if and only if~$x\in V_i$ and~$y\in V_j$ for some~$1\leq
i<j\leq k$ with~$ij\in E(H^*)$. 

\assertion(1) We have~$e(H')\geq(1-\delta/6)\gamma p{n\choose2}$. 
\endassertion
\proofofassertion
We first estimate~$|E(H)\setminus E(H')|$. 
From the $(p,A)$-uniformity of~$G$ it follows that, for
any~$W\subset V(G)$ with~$|W|\geq\eta n$, we
have~$e(G[W])\leq(1+\eta)p{|W|\choose2}$ if~$n$ is large enough.  
Hence~$e(H[V_0])\leq\epsilon^2pn^2$. Moreover, writing~$d=pn$ as
usual, we have that~$e_G(V_0,V\setminus V_0)$ is at most  
$$
p|V_0||V\setminus V_0|+A\{d|V_0||V\setminus V_0|\}^{1/2}\leq\epsilon 
pn^2+And^{1/2}\leq2\epsilon pn^2
$$
for large enough~$n$. Now note that~$\sum e_G(V_i,V_j)$ with the
sum over all~$1\leq i<j\leq k$ such that~$(V_i,V_j)$ is {\it not\/} 
$(\epsilon,H,G)$-regular is at
most~$\epsilon{k\choose2}(1+\eta)pm^2\leq\epsilon pn^2$. Also, $\sum 
e_H(V_i,V_j)$ with the sum extended over all~$1\leq i<j \leq k$ such
that~$\dHG(V_i,V_j)\leq\rho$ is at
most~$\rho{k\choose2}(1+\eta)pm^2\leq\rho pn^2$. Finally, for large
enough~$n$, we have that $\sum_{1\leq i\leq k}e(G[V_i])\leq
k(1+\eta)p{m\choose2}\leq pn^2/k$. Therefore~$|E(H)\setminus 
E(H')|\leq(4\epsilon+\rho+1/k)pn^2\leq(5\epsilon+\rho)pn^2$ if~$n$ is
sufficiently large. On the other hand, we have~$e(H)=\gamma
e(G)\geq\gamma(1-\eta)p{n\choose2}$. Thus
$$
\eqalign{
e(H')&\geq\gamma(1-\eta)p{n\choose2}-2(6\epsilon+\rho)p{n\choose2}\cr 
     &\qquad\qquad\qquad
        =\(1-\eta-12{\epsilon\over\gamma}-2{\rho\over\gamma}\)
           \gamma p{n\choose2}
           \geq\(1-{\delta\over6}\)\gamma p{n\choose2}.\cr
}
$$
\endproofofassertion

We now look at~$(H^*,\bgamma)$. As in Lemma~{\WeightL},
let~$\bgamma(H^*)=\sum_{e\in E(H^*)}\gamma_e$.

\assertion(2) We have~$\bgamma(H^*)\geq(1-\delta/2)\gamma k^2/2$. 
\endassertion
\proofofassertion
To prove~(2), note that
$$
\eqalign{
\(1-{\delta\over6}\)\gamma p{n\choose2}
 \leq e(H')&=\sum_{e=ij\in E(H^*)}\gamma_ee_G(V_i,V_j)\cr
 &\qquad\leq(1+\eta)pm^2\bgamma(H^*)
    \leq(1+\eta)p{n^2\over k^2}\bgamma(H^*).\cr
}
$$
Therefore~$\bgamma(H^*)\geq\{(1-\delta/6)/(1+\eta)\}(1-1/n)\gamma
k^2/2\geq(1-\delta/2)\gamma k^2/2$. 
\endproofofassertion

We may now complete the proof of our lemma. 

\assertion(3) We have~$e(J_\ell(H))\geq(1-\delta)\gamma{n\choose2}$. 
\endassertion
\proofofassertion
Let~$1\leq i<j\leq k$. By Lemma~{\LocExp}, applied with $\delta/6$, we have
that~$e(J_\ell[V_i,V_j])\geq(1-\delta/6)w(i,j)m^2$,
where~$w(i,j)=w_{H^*,\bgamma}(i,j)$ is as defined before Lemma~{\WeightL}.
Thus, by~(2) and Lemma~{\WeightL}, we have
$$
\eqalign{
e(J_\ell(H))&\geq\sum_{1\leq i<j\leq k}e(J_\ell[V_i,V_j])
 \geq\(1-{\delta\over6}\)m^2
    \Big\{w(H^*,\bgamma,\bfx)-\sum_{1\leq i\leq k}w(i,i)\Big\}\cr  
&\qquad\geq\(1-{\delta\over6}\)m^2\bgamma(H^*)-km^2
  \geq{1\over2}\(1-{2\delta\over3}\)\gamma k^2m^2-{n^2\over k}\cr
&\qquad\qquad
 \geq{1\over2}(1-\epsilon)^2\(1-{2\delta\over3}\)\gamma n^2 
      -\epsilon n^2\geq(1-\delta)\gamma{n\choose2},\cr
}
$$
as required.\qed
\endproofofassertion
\enddemo

\remark{Remark} Lemma~{\MainOddL} is essentially best possible in the
sense that the lower bound for~$e(J_\ell(H))$ cannot be substantially
improved. In fact, any graph~$G$ on~$n$ vertices contains many
subgraphs~$H$ for which~$e(J_{\ell}(H))$ is not greater
than~$(e(H)/e(G)){n\choose2}$. To mention just two examples of quite
different nature, first fix any~$1\leq k\leq n$ and let~$H=H^k$ be a
$k$-vertex subgraph of~$G$ of maximum size, and note that
then~$e(H)\geq e(G){k\choose2}{n\choose2}^{-1}$ whereas
trivially~$e(J_\ell(H))\leq{k\choose2}$. Now suppose~$1\leq k\leq n/2$
and let~$H=H^{2k}$ be a balanced bipartite subgraph of~$G$ of
order~$2k$ and maximum size. Then~$e(H)\geq 2e(G)k^2/n^2$
whilst~$e(J_\ell(H))\leq k^2$. From these two examples, we also see
that the `extremal' or `near-extremal' subgraphs~$H$ for
Lemma~{\MainOddL} may have quite a varied structure.
\endremark
%
% sec3
%
\head\S3. Deterministic Consequences
\endhead

In this section we give a few results concerning the existence, for
any given~$0<\epsilon\leq1/2$ and~$\ell\geq1$, of very sparse
graphs~$G$ that satisfy~$G\to_{1/2+\epsilon}C^{2\ell+1}$.

If~$H$ is a graph of order~$|H|\geq3$ and size~$e(H)\geq1$, 
its {\deffont$2$-density\/} is~$d_2(H)=(e(H)-1)/(|H|-2)$. In
particular, the $2$-density of the
$(2\ell+1)$-cycle~$C^{2\ell+1}$ ($\ell\geq1$)
is~$d_2(C^{2\ell+1})=2\ell/(2\ell-1)$. For integers~$k\geq3$ 
and~$\ell\geq1$, let~$\cH_{k,\ell}$ be the family of all graphs~$H$
with~$3\leq|H|\leq k$, $e(H)\geq1$, and~$d_2(H)>d_2(C^{2\ell+1})$.
Also, let~$\Forb(\cH_{k,\ell})$ be the collection of all graphs~$G$
that are $H$-free for all~$H\in\cH_{k,\ell}$. 

\proclaim {Theorem {\MainDetThm}} Let~$0<\epsilon\leq1/2$
and integers~$k\geq3$ and~$\ell\geq1$ be fixed. Then there exists a 
graph~$G=G_{\epsilon,k,\ell}\in\Forb(\cH_{k,\ell})$ such
that~$G\to_{1/2+\epsilon}C^{2\ell+1}$. 
\endproclaim
\demo{Proof}
Put~$\eta=\epsilon/2$ and let~$C=C(\ell,\eta/2)$ be as given in
Theorem~{\MainOddThm}. Let~$p=p(n)=Cn^{-1+1/2\ell}$, and
consider~$G_p\in\G(n,p)$. Theorem~{\MainOddThm} then tells us
that~$G_p\to_{1/2+\eta}C^{2\ell+1}$ almost surely, and it is a 
standard matter to check that a.e.~$G_p$ contains, very generously, at 
most~$(\epsilon/2)e(G_p)$ copies of elements of~$\cH_{k,\ell}$ as
subgraphs. Fix a~$G_p$ satisfying both conditions above, and
let~$G\subset G_p$ be a spanning subgraph of~$G_p$ obtained from~$G_p$
by the removal of at least one edge from each subgraph of~$G_p$ that
is a copy of an element of~$\cH_{k,\ell}$, and such
that~$e(G)\geq(1-\epsilon/2)e(G_p)$. Then
clearly~$G\in\Forb(\cH_{k,\ell})$. Moreover, we have
that~$G\to_{1/2+\epsilon}C^{2\ell+1}$. To see this, suppose~$J\subset
G$ is a subgraph of~$G$ with~$e(J)\geq(1/2+\epsilon)e(G)$.
Then~$e(J)\geq(1/2)(1+2\epsilon)(1-\epsilon/2)e(G_p)
\geq(1/2)(1+\epsilon)e(G_p)$. As~$G_p\to_{(1+\epsilon)/2}C^{2\ell+1}$,
the graph~$J$ must contain a $(2\ell+1)$-cycle and we are done.\qed
\enddemo

We now single out a corollary to Theorem~{\MainDetThm}.  In
Corollary~{\DetCor} below, the property that~$G$ belongs
to~$\Forb(\cH_{k,\ell})$ in Theorem~{\MainDetThm} is replaced by a
collection of simpler and more concrete conditions. For instance, one
of these conditions is that the girth~$g(G)$ of~$G$ should be at
least~$2\ell+1$. To state another condition that appears in
Corollary~{\DetCor}, we need to introduce a definition.

Let~$G$ be a graph and~$\ell\geq1$ a positive integer.
Suppose~$C_1,\dots,C_h$ ($h\geq2$) are distinct $(2\ell+1)$-cycles
of~$G$, and~$e_1\in E(C_1),\dots,e_{h-1}\in E(C_{h-1})$ are~$h-1$
edges of~$G$ such that~$E(C_i)\cap\bigcup_{1\leq
  j<i}E(C_j)=\{e_{i-1}\}$ ($2\leq i\leq h$). Then we say
that~$(C_1,\dots,C_h)$ is a {\deffont$(h,C^{2\ell+1})$-path\/} in~$G$.
Now assume that~$(C_1,\dots,C_h)$ is a $(h,C^{2\ell+1})$-path in~$G$
and that the edge~$e\in E(G)$ joins a vertex
in~$V(C_1)\setminus\bigcup_{1<j\leq h}V(C_j)$ to a vertex
in~$V(C_h)\setminus\bigcup_{1\leq i<h}V(C_i)$.  We then say
that~$(C_1,\dots,C_h;e)$ is a {\deffont$(h,C^{2\ell+1})$-cycle\/}
in~$G$.

It is immediate to check that if~$(C_1,\dots,C_h)$ is a
$(h,C^{2\ell+1})$-path, then~$H=\bigcup_{1\leq j\leq h}C_j$ has
$2$-density~$d_2(H)\geq d_2(C^{2\ell+1})$. Also, if~$(C_1,\dots,C_h;e)$ is
a $(h,C^{2\ell+1})$-cycle, then~$H'=H+e$ has
$2$-density~$d_2(H')>d_2(C^{2\ell+1})$. 

\proclaim {Corollary {\DetCor}} For any~$0<\epsilon\leq1/2$ and
integers~$k\geq2$ and~$\ell\geq1$, there is a
graph~$G=G_{\epsilon,k,\ell}$ such that \rom({\it
  i\/}\rom)~$g(G)=2\ell+1$, \rom({\it ii\/}\rom)~no two
$(2\ell+1)$-cycles in~$G$ share more than two vertices, and if two
such cycles do share two vertices then they also share an edge,
\rom({\it iii\/}\rom)~$G$ contains no $(h,C^{2\ell+1})$-cycles for
any~$2\leq h\leq k$, and \rom({\it
  iv\/}\rom)~$G\to_{1/2+\epsilon}C^{2\ell+1}$.\qed
\endproclaim

\remark{ Acknowledgements}
The authors are indebted to an anonymous referee for a very meticulous reading.
\endremark
%  
% refs
%
\Refs
\ref\key\refnoBSS
\by Babai, L., \Si, \Sp
\paper Extremal subgraphs of random graphs
\jour\JGT
\vol14
\yr1990
\pages 599--622
\endref

\ref\key\refnoEGT
\by\BB
\book Extremal Graph Theory
\publ Academic Press 
\publaddr London 
\yr1978 
%${\it xx}+488$pp
\endref

\ref\key\refnoBBrgs
\bysame
\book Random Graphs
\publ Academic Press 
\publaddr London 
%${\it xvi}+447$pp
\yr1985
\endref

\ref\key\refnoErSt 
\by\Er, Stone, A.H.
\paper On the structure of linear graphs
\jour\BAMS
\vol52
\yr1946
\pages1089--1091
\endref

\ref\key\refnoFR
\by \Fr, \Ro
\paper Large triangle-free subgraphs in graphs without $K_4$
\jour Graphs and Combinatorics
\vol2
\yr 1986
\pages 135--244
\endref

\ref\key\refnoFu
\by\Fu
\paper Random Ramsey graphs for the four-cycle
\jour Discrete Mathematics
\vol126
\yr1994
\pages407--410
\endref

\ref\key\refnoHKL
\by Haxell, P.E., Kohayakawa, Y., \L uczak, T.
\paper The induced size-Ramsey number of cycles
\jour\CPC
\toappear
\endref

\ref\key\refnoHKLeven
\bysame %Haxell, P.E., Kohayakawa, Y., \L uczak, T.
\paper Tur\'an's extremal problem in random graphs: forbidding even
cycles 
\miscnote submitted
\endref

\ref\key\refnoHoeff
\by Hoeffding, W.
\paper Probability inequalities for sums of bounded random variables
\jour Jour. Amer. Statistical Assoc.
\vol58
\yr1963
\pages13--30
\endref

\ref\key\refnoKo
\by Kohayakawa, Y. 
\paper The regularity lemma of Szemer\'edi for sparse graphs
\finalinfo manuscript, 1993
\endref

\ref\key\refnoLRV
\by\L uczak, T., Ruci\'nski, A., Voigt, B.
\paper Ramsey properties of random graphs 
\jour\JCTB
\vol56
\yr1992
\pages 55--68
\endref

\ref\key\refnoMcD
\by McDiarmid, C.J.H.
\paper On the method of bounded differences
\inbook Surveys in Combinatorics~1989, London %
        Mathematical Society Lecture Notes Series~141
\ed Siemons, J. 
\publ Cambridge University Press
\publaddr Cambridge
\yr1989
\pages148--188
\endref

\ref\key\refnoRoSzL
\by \Ro
\finalinfo Personal communication, July~1993
\endref

\ref\key\refnoRRa 
\by \Ro, Ruci\'nski, A.
\paper Lower bounds on probability thresholds for Ramsey properties   
\inbook Comb\-in\-ator\-ics---Paul Erd\H os is Eighty (Volume~1) 
\eds Mikl\'os, D., S\'os, V.T., Sz\H onyi, T. 
\publaddr Budapest
\publ Bolyai Soc.\ Math.\ Studies 
\yr1993 
\pages317--346
\endref

\ref\key\refnoRRab 
\bysame
\paper Random graphs with monochromatic triangles in every
edge colouring
\jour\RSA
\vol5
\yr1994
\pages253--270
\endref

\ref\key\refnoRRb
\bysame
\paper Threshold functions for Ramsey properties
\jour\JAMS 
\miscnote to appear
\endref

\ref\key\refnoSz
\by\Sz
\paper Regular partitions of graphs 
\inbook Probl\`emes en Combinatoire et Th\'eorie des Gra\-phes, %
        Proc. Colloque Inter. CNRS 
\eds Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., Sotteau, D.
\publ CNRS
\publaddr Paris
\yr1978
\pages399--401
\endref

\endRefs
\enddocument

