%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% LaTeX2e file for 
%
% ``THRESHOLD FUNCTIONS FOR ASYMMETRIC RAMSEY 
%   PROPERTIES INVOLVING CYCLES''
%
% by Y. Kohayakawa and B. Kreuter
%
% Last update: 26 January 1996
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{latexsym}
\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}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\def\casebody{\noindent\ignorespaces}
\def\Nset{\hbox{I\hskip-0.20em I\hskip-0.35em N}}        
\def\Qset{\hbox{\hbox{Q\hskip-0.525em\lower-0.097ex
          \hbox{\vrule height1.47ex width0.07em}}\hskip0.50em}}
\def\Rset{\hbox{I\hskip-0.23em R}}
\def\Zset{\hbox{Z\hskip-0.38em Z}}
%
% 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{J. 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.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\pagestyle{empty}
\oddsidemargin 4mm
\evensidemargin 4mm  
\textwidth15cm
\newtheorem{lem}       {Lemma}
\newtheorem{thm} [lem] {Theorem}
\newtheorem{cor} [lem] {Corollary}
\newtheorem{cl}        {Claim}
\newtheorem{ecl} [cl]  {Claim}
\newtheorem{con} [lem] {Conjecture}
\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\E{{\bf E}}
\def\textit#1{{\it #1\/}}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% New macros
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ycite#1{}
\def\cA{{\cal A}}
\def\cB{{\cal B}}
\def\cF{{\cal F}}
\def\cG{{\cal G}}
\def\cP{{\cal P}}
\def\cV{{\cal V}}
\def\P{{\bf P}}
\def\bfV{{\bf V}}
\def\bfW{{\bf W}}
\def\bV{{\bar V}}
\def\bU{{\bar U}}
\def\bgamma{{\bar\gamma}}
\def\bm{{\bar m}}
\def\bp{{\bar p}}
\def\bepsilon{{\bar\epsilon}}
\def\bd{{\bar d}}
\def\bB{{\bar B}}
\def\bC{{\bar C}}
\def\bD{{\bar D}}
\def\bT{{\bar T}}
\def\brho{{\bar\rho}}
\def\bbfV{{\bar\bfV}}
\def\cU{{\cal U}}
\def\cH{{\cal H}}
\def\tH{{\widetilde H}}
\def\tp{{\widetilde p}}
\def\pH{{p_H}}
\def\pO{{p_0}}
\def\d0{{d_0}}
\def\td{{\widetilde d}}
\def\dJp{d_{J,p}}
\def\dJpD{d_{J,p,D}}
\def\dJpO{d_{J,\pO}}
\def\dFpO{d_{F,\pO}}
%\def\dJtp{d_{J,\tp}}
%\def\dJtpD{d_{J,\tp,D}}
\def\dFp{d_{F,p}}
\def\dFbp{d_{F,\bp}}
\def\dFbpbD{d_{F,\bp,\bD}}
%\newcommand{\Aut}{\protect\operatorname{Aut}}
\def\Aut{\mathop{\!\hbox{\rm Aut}}}
\def\im{\mathop{{\rm im}}}
\let\:=\colon
\def\ykcomm{{\it yk\/}: }
\def\dGamma{{\dot\Gamma}}
\def\dF{{\dot F}}
\def\irr{^{({\rm irr})}}
\def\dmin{{d_{\rm min}}}
%\def\dmax{{d_{\rm max}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Macros from 0state
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\bfG{{\bf G}}
\def\tbfG{{\widetilde{\bf G}}}
\def\cG{{\cal G}}
\def\cH{{\cal H}}
\def\cE{{\cal E}}
\def\cF{{\cal F}}
\def\Hypertree{\textsc{Hypertree}}
\def\lan{$\langle$}
\def\ran{$\rangle$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{Threshold functions for asymmetric Ramsey properties 
       involving cycles}

\author{%\sc 
    Y.~Kohayakawa\thanks{Partially
    supported by CNPq (Proc.~300334/93--1 and ProTeM-CC-II Project
    ProComb).  Part of this work was done while this
    author was visiting Humboldt-Universit\"at zu Berlin through
    PROBRAL project number~026/95, a CAPES--DAAD exchange
    programme.}\\\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~SP,
    Brazil \\\small
    {\it E-mail address\/}: {\tt<yoshi@ime.usp.br>}
\and 
    %\sc 
    B.~Kreuter \\\small 
    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>} 
    }
\date{}
\maketitle
\vspace{-.8cm}
\begin{abstract}\noindent
We consider the binomial random graph~$G_{n,p}$ and determine a sharp
threshold function for the edge-Ramsey property
$$
  G_{n,p}\to(C^{\ell_1},\ldots,C^{\ell_r})  %\eqno{\hbox{(*)}}
$$
for all~$\ell_1,\ldots,\ell_r$, where~$C^\ell$ denotes the cycle of
length~$\ell$.  As deterministic consequences of our results, we prove 
the existence of sparse graphs having the above Ramsey property as
well as the existence of infinitely many critical graphs with respect
to the property above. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%and of infinitely many critical
%graphs with respect to the above Ramsey property.
%that there are very sparse graphs that satisfy~(\ref{eq:abstract}),
%and that there are infinitely many critical graphs
%with respesct to property~(\ref{eq:abstract}). 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{abstract}
\vspace*{0.2cm}{\noindent
\small
{\it AMS subject classification code\/} (1991): 05C55, 05C80, 05C38
%(Generalised Ramsey theory, random graphs, paths and cycles)
\par\noindent 
{\it Key words and phrases\/}: Ramsey theory, random graphs, threshold
functions, Szemer\'edi's lemma, cycles}
\section{Introduction and Results}

Ramsey properties of random graphs have been investigated only
recently.  The aim of these investigations has been to find sharp
thresholds for various Ramsey properties that a random graph may
satisfy.  Let us concentrate here on the binomial model of random
graphs, the so-called $G_{n,p}$-~or $G_p$-model.  Thus, our random
graph~$G_p=G_{n,p}$ has~$n$ vertices and its edges are present
independently with probability~$p$.  See~Bollob\'as~\cite{BBrgs} for
details concerning random graphs and Graham, Rothschild, and
Spencer~\cite{GRS} for Ramsey theory.

The thresholds for vertex-Ramsey properties, \textit{i.e.}, the case
in which the vertices of the random graph are coloured, were
established by {\L}uczak, Ruci\'nski, and Voigt~\cite{LRV}.  The case
in which edges are coloured turned out to be rather more involved, but
R\"odl and Ruci\'nski~\cite{RR1,RRtrigs,RR2} succeeded in settling
this case quite recently as well.  Now, the results
in~\cite{LRV,RR1,RRtrigs,RR2} cover the case of \textit{symmetric}
Ramsey properties, that is, the case in which we seek a monochromatic
copy of one given graph.  Here we shall consider the
\textit{asymmetric} case, namely, when we have one target graph for
each colour.  The threshold functions for asymmetric Ramsey properties
with respect to vertex colourings are determined in~\cite{Kr}.  In
this note we consider edge-Ramsey properties of~$G_p$ when the target
graphs are cycles.
  
We need some definitions before we may proceed. For an integer~$n$, 
we write~$[n]$ for~$\{1,\ldots,n\}$. All logarithms in this note are 
with respect to base e. For a graph~$G$, we
denote by~$V(G)$ and~$E(G)$ the sets of vertices and edges of~$G$.
The sizes of these sets will be abbreviated by~$|G|=|V(G)|$
and~$e(G)=|E(G)|$.  The \textit{maximum $2$-density} of a graph~$G$ is 
\[
m_2(G)
  \quad =\quad\max
          \left\{
             \frac{e(J)-1}{|J|-2}\:\;J\subseteq G\mbox{ with }
                                  |J|\ge3
          \right\}.
\] 

We now recall the arrow notation for Ramsey properties.  For two
graphs~$F$ and~$H$ and an integer~$r\ge2$, we write~$F\to(H)_r$ to
mean that in any colouring of the edges of~$F$ with~$r$ colours there
is a subgraph of~$F$ isomorphic to~$H$ whose edges are all coloured by
the same colour.  Given~$r$ graphs $H_1,\ldots,H_r$, we may generalize 
this definition by letting~$F\to(H_1,\ldots,H_r)$ stand for the fact
that, for any colouring of the edges of~$F$ with colours~$1,\ldots,r$,
there is a colour~$i$ for which there is a copy of~$H_i$ in~$F$ whose
edges are all coloured with colour~$i$.

Using this notation, the results of R\"odl and Ruci\'nski read as
follows, where~$P^4$ denotes the path on four vertices.

\begin{thm} 
\label{thm:RR}
%  {\rm\cite{RR2,RR1}} 
  Let~$H$ be a graph containing a cycle or
  a~$P^4$.  Let~$\beta=1/m_2(H)$ and let~$r\ge2$ be an integer.  Then 
  there exist constants~$b$ and~$B>0$ such that
  \begin{enumerate}
  \item[{\rm({\it a\/})}] for~$p=p(n)\le bn^{-\beta}$ we have
       \[\P\left[G_p\to(H)_r\right]\quad=\quad o(1),\]
  \item[{\rm({\it b\/})}] for~$p=p(n)\ge Bn^{-\beta}$ we have
       \[\P\left[G_p\to(H)_r\right]\quad=\quad1-o(1).\]
  \end{enumerate}
\end{thm}

Now consider the problem of determining the threshold for the
property~$G_p\to(H_1,H_2)$. For graphs~$H_1$ and~$H_2$
with~$m_2(H_1)\le m_2(H_2)$, put 
\begin{equation}
\beta=\beta(H_1,H_2)
     =\min\left\{{|J|-2+1/m_2(H_1)\over e(J)}
             \:\;J\subseteq H_2\hbox{ with }e(J)\geq1
      \right\}.
  \label{def-beta}
\end{equation}
Observe that $\beta$ is not symmetric in~$H_1$ and~$H_2$ but depends
to a larger extent on the denser of the two graphs.
The following theorem contains the so-called 1-statement corresponding
to the case in which~$H_1$ is the cycle~$C^\ell$ and~$H_2$ is an
arbitrary $2$-balanced graph~$H$
with~$m_2(H)>m_2(C^\ell)=(\ell-1)/(\ell-2)$.

\begin{thm}
  \label{MainThm-1}
  Let~$\ell\geq3$ be a fixed integer, and let~$H$ be a $2$-balanced
  graph with
  $m_2(H)={(e(H)-1)/(|H|-2)}>m_2(C^\ell)=(\ell-1)/(\ell-2)$. 
  Then there is a constant~$B$ such that, setting~$p=p(n)=Bn^{-\beta}$
  where 
 \begin{equation}
 \beta=\beta(C^\ell,H) 
      ={|H|-2+1/m_2(C^\ell)\over e(H)} 
      ={|H|-1-1/(\ell-1)\over e(H)},
 \label{beta-C-H}
 \end{equation}
  we have
  \begin{equation}
    \P\left[G_p\to(C^\ell,H)\right]=1-o(1).
    \label{final-aim}
  \end{equation}
\end{thm}

In the result above, the condition that~$H$ should be $2$-balanced and 
that~$m_2(H)>m_2(C^{\ell})$ may be replaced by the condition that~$H$
should be \textit{strictly} $2$-balanced (\textit{i.e.}, the maximum
in the definition of~$m_2(H)$ should be attained by~$H$ only) and
that~$m_2(H)\geq m_2(C^\ell)$.  The main lemma in the proof of
Theorem~\ref{MainThm-1}, Lemma~\ref{count-lemma}, concerns the number 
of $C^\ell$-free graphs on~$n$ vertices fulfilling some additional
properties.  This lemma is a generalization of Lemma~11
from~\cite{KLR1}, which deals with the case~$\ell=3$.  Furthermore,
Lemma~\ref{count-lemma} may be used to unify the proofs of the 
results in~\cite{HKLb} and~\cite{HKL}.  However, the main result
from~\cite{KKS}, which is similar in spirit, does not follow from
Lemma~\ref{count-lemma}.

The next theorem says that the exponent~$\beta$ in
Theorem~\ref{MainThm-1} is involved in the corresponding 0-statement,
thus establishing a sharp threshold for the
property~$G_p\to(C^\ell,C^k)$.

\begin{thm}
  \label{thm:0-statement}
  Let~$3\leq k\leq\ell$ be integers, and let
  \[ 
     \beta=\beta(C^\ell,C^k)
          =\frac{(k-1)(\ell-1)-1}{k(\ell-1)}
          =1-{\ell\over k(\ell-1)}. 
  \]
  Then there exists a constant $b>0$ such that, for
  $p=p(n)=bn^{-\beta}$, we have
  \[ 
     \P\left[G_p\to(C^\ell,C^k)\right]=o(1).
  \]
\end{thm}

We shall also sketch the proof of the following generalized version of
Theorem~\ref{MainThm-1}.

\begin{thm}
  \label{Gen1State}
  Let~$3\leq\ell_2\leq\cdots\leq\ell_r$ $(r\ge2)$ be integers, and
  suppose~$H$ 
  is a $2$-balanced graph with~$m_2(H)>m_2(C^{\ell_2})$.
  Let~$\beta=\beta(C^{\ell_2},H)$.  Then there are constants~$B$
  and~$\kappa>0$ such that, for~$p=p(n)=Bn^{-\beta}$, almost
  every~$G_p$ satisfies the property that any 
  subgraph~$G'\subseteq G_p$ of~$G_p$ with~$e(G')\geq e(G_p)-\kappa
  n^{1+1/(\ell_2-1)}/(\log n)^{|H|}$ is such that
  $$
     G'\to(H,C^{\ell_2},\ldots,C^{\ell_r}).
  $$
\end{thm}

Similarly to the case of Theorem~\ref{MainThm-1}, the result above
also holds if~$H$ is strictly $2$-balanced
and~$m_2(H)=m_2(C^{\ell_2})$.  We further remark that the
$\log$-factor in the number of edges that one is allowed to delete
from~$G_p$ can be got rid of.

The following result is an immediate corollary to
Theorems~\ref{thm:0-statement} and~\ref{Gen1State}.

\begin{cor}
  \label{cor:many-cycles}
  Let~$3\leq\ell_1\le\cdots\le\ell_r$ $(r\ge2)$ be
  integers, and let~$\beta=\beta(C^{\ell_2},C^{\ell_1})$.  
  Then there exist constants~$b$ and~$B>0$ such that
  \begin{enumerate}
  \item[{\rm({\it a\/})}] for~$p=p(n)\le bn^{-\beta}$ we have
       \[\P\left[G_p\to(C^{\ell_1},\ldots,C^{\ell_r})\right]
                                       \quad=\quad o(1),\]
  \item[{\rm({\it b\/})}] for~$p=p(n)\ge Bn^{-\beta}$ we have
       \[\P\left[G_p\to(C^{\ell_1},\ldots,C^{\ell_r})\right]
                                       \quad=\quad1-o(1).\]
  \end{enumerate}
\end{cor}

It would be interesting to determine the threshold functions for the
properties~$G_p\to(H_1,H_2)$ for arbitrary graphs~$H_1$ and~$H_2$, or
more generally for the analogous problem when more than two graphs are
involved.  We formulate the following conjecture.

\begin{con}
  Let~$H_1$, $H_2$ be graphs with~$m_2(H_1)\leq m_2(H_2)$ and  
  let~$\beta=\beta(H_1,H_2)$ be as defined
  in~{\rm(\ref{def-beta})}. Then~$p=p(n)=n^{-\beta}$ is a sharp
  threshold for the property $G_p\to(H_1,H_2)$. 
\end{con}

\noindent
Unfortunately, the techniques used in this note are by far not
sufficient to yield a proof of this more general case.

We now single out two deterministic consequences of our methods.  Let
integers~$t$, $\ell_2\geq3$ and a graph~$H$ be given.
Let~$\cV_{\ell_2,H,t}$ be the class of graphs~$F$ with at most~$t$
vertices satisfying~$|F|-\beta(C^{\ell_2},H)e(F)<1+1/(\ell_2-1)$.

\begin{cor}
  \label{cor:large-girth}
  For any fixed integers~$3\leq\ell_2\le\cdots\le\ell_r$ $(r\geq2)$  
  and~$t\geq1$ 
  and any $2$-balanced graph~$H$ with~$m_2(H)>m_2(C^{\ell_2})$, 
  there is a graph~$G$ that satisfies~$G\to(H,C^{\ell_2},\ldots,C^{\ell_r})$
  and  contains no member of~$\cV_{\ell_2,H,t}$.
\end{cor}

An immediate consequence of the corollary above is that, for
any~$3\leq\ell_1\leq\cdots\leq\ell_r$, there are graphs~$G$ of
girth~$\ell_1$ satisfying~$G\to(C^{\ell_1},\ldots,C^{\ell_r})$.

Our second deterministic result states that the
$r$-tuple~$(C^{\ell_1},\ldots,C^{\ell_r})$ is Ramsey-infinite for
any~$\ell_1,\ldots,\ell_r\geq3$.  A graph~$G$ is called~{\it
Ramsey-critical\/}, or simply 
\textit{critical}, for an $r$-tuple of graphs~$(H_i)_{1\leq i\leq r}$
($r\geq2$) if~$G\to(H_i)_{1\leq i\leq r}$ but, for any proper
subgraph~$G'\subset G$ of~$G$, the relation~$G'\to(H_i)_{1\leq i\leq
r}$ fails.  The $r$-tuple~$(H_i)_{1\leq i\leq r}$ is called {\it
Ramsey-finite\/} if the class of all graphs that are critical
for~$(H_i)_{1\leq i\leq r}$ is finite and {\it Ramsey-infinite\/}
otherwise. If~$(H_i)_{1\leq i\leq r}$ is Ramsey-finite then there
clearly is a polynomial time algorithm that, given a graph~$G$,
decides whether or not~$G\to(H_i)_{1\leq i\leq r}$ holds.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%The fact that an
%$r$-tuple~$(H_i)_{1\leq i\leq r}$ is Ramsey-infinite might indicate
%that it may be hard to come up with such an algorithm.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Corollary~2 of~\cite{RR2} implies that the pair~$(H,H)$ is
Ramsey-infinite for any graph~$H$ containing a cycle, and
{\L}uczak~\cite{Lu} showed that the pair~$(F,H)$ is Ramsey-infinite
if~$F$ is a forest and~$H$ contains a cycle.  Our result is as
follows. 

\begin{thm}
  \label{rainf}
  For any~$3\leq\ell_1\le\cdots\le\ell_r$ $(r\ge2)$, 
  the $r$-tuple~$(C^{\ell_i})_{1\leq i\leq r}$ is Ramsey-infinite.
\end{thm}

The organisation of this note is as follows.  In
Section~\ref{sec:1-state} we give the proof of Theorem~\ref{MainThm-1}
and sketch the proof of Theorem~\ref{Gen1State}.
Theorem~\ref{thm:0-statement} is proved in Section~\ref{sec:proofof0}.
The deterministic consequences are proved in
Section~\ref{sec:det-conseq}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The proofs of Theorems~\ref{MainThm-1} and~\ref{Gen1State}} 
\label{sec:1-state}

We shall need a fair amount of preparation to prove
Theorems~\ref{MainThm-1} and~\ref{Gen1State}.  In
Sections~\ref{sec:basic} and~\ref{sec:prelim-lemmas}, we set out some
well known lemmas and some preliminary results that we shall need.  In
Section~\ref{sec:count-lemma}, we prove our crucial lemma,
Lemma~\ref{count-lemma}.

\subsection{Basic tools}
\label{sec:basic}

\subsubsection{Janson's inequality}
\label{sec:Janson-ineq}

Let~$E$ be a finite set.  Let~$(J_e)_{e\in E}$ be a family of
independent random indicator variables indexed by~$E$ 
such that~$\E(J_e)=p$ for
all~$e\in E$. Suppose~$(E_\alpha)_{\alpha\in \cA}$ 
is a family of subsets of~$E$.
Let~$I_\alpha=\prod_{e\in E_\alpha}J_e$, and~$S=\sum_{\alpha\in
  \cA}I_\alpha$. Thus, the random variable~$S$ counts how many of the
sets~$E_\alpha$ ($\alpha\in \cA$) have all its elements~$e\in E_\alpha$
such that~$J_e=1$. 
%Suppose for simplicity that~$\E(J_e)=p$ for all~$e\in E$.
Let
\begin{equation}
  \Delta=\sum_{\alpha,\beta}\E(I_\alpha I_\beta), 
 \label{def-Delta}
\end{equation}
where the sum extends over all ordered pairs~$(\alpha,\beta)$
with~$\alpha\neq\beta$ but~$E_\alpha\cap E_\beta\neq\emptyset$.
Janson's inequality~\cite{Ja} is then the following.

\begin{lem}\label{lem:Janson-ineq}
  For all~$0\leq\epsilon\leq1$, writing~$\mu=\E(S)$, we have
  \begin{equation}
   \P[S\leq(1-\epsilon)\mu]
      \leq\exp\left\{-{1\over2(1+\Delta/\mu)}\epsilon^2\mu\right\}.
    \label{Janson-ineq}
  \end{equation}
\end{lem}

%\noindent[\ykcomm at the moment the formalisms in
%Sections~\ref{sec:BK-ineq} and~\ref{sec:Janson-ineq} are too
%different. I think this has to be fixed; sorry.]

\subsubsection{Szemer\'edi's lemma}

The following notions will be needed in what follows. Let a graph~$J$
be fixed. In the sequel we let~$V=V(J)$.  Suppose~$0<\eta\leq1$,
$D>1$, and~$0<p\leq1$.  We say that~$J$ is
{\it$(\eta,D,p)$-upper-uniform\/} if for all~$U$, $W\subseteq V$
with~$U\cap W=\emptyset$ and~$|U|$, $|W|\geq\eta n$, we have
$e_J(U,W)\leq Dp|U||W|$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Clearly, if~$J$ is $(\eta,D,p)$-upper-uniform,
% then it is also $(\eta',D',p')$-upper-uniform if~$\eta\leq\eta'\leq1$, $D\leq
% D'$, and~$0<p\leq p'\leq1$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In the sequel, for any two disjoint non-empty sets~$U$, $W\subseteq V$,
let the {\it$p$-density\/} of~$J$ between~$U$ and~$W$ be
\[  
  \dJp(U,W)=e_J(U,W)/p|U||W|.
\]

Now suppose~$0<\epsilon\leq1$ is a real number, and~$U$, $W\subseteq V$
are two non-empty disjoint sets of vertices of~$J$.  We say that the
pair~$(U,W)$ is {\it$(\epsilon,J,p)$-regular\/} if for all~$U'\subseteq
U$, $W'\subseteq W$ with~$|U'|\geq\epsilon|U|$ and~$|W'|\geq\epsilon|W|$
we have
\[  
   |\dJp(U',W')-\dJp(U,W)|\leq\epsilon.
\]
We say that a partition~$P=(V_i)_{i=0}^k$ of~$V=V(J)$ is
{\it$(\epsilon,k)$-equitable\/} if~$|V_0|\leq\epsilon n$,
and~$|V_1|=\ldots=|V_k|$.  Also, we say that~$V_0$ is the {\it
exceptional\/} class of~$P$.  When the value of~$\epsilon$ is not
relevant, we refer to an $(\epsilon,k)$-equitable partition as a
{\it$k$-equitable\/} partition. Similarly, $P$ is an {\it 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)_{i=0}^k$ of~$V$ is {\it$(\epsilon,J,p)$-regular\/}
if at most~$\epsilon{k\choose2}$ pairs~$(V_i,V_j)$ with~$1\leq i<j\leq
k$ are not $(\epsilon,J,p)$-regular.  We may now state an extension of
Szemer\'edi's lemma~\cite{Szem} to subgraphs of
$(\eta,D,p)$-upper-uniform graphs, observed independently by R\"odl
and Kohayakawa~\cite{Ko}. 

\begin{lem}\label{SSz}
  For any given~$\epsilon>0$, $k_0\geq1$, and~$D>1$, there are
  constants~$\eta=\eta(\epsilon,k_0,D)>0$
  and~$K_0=K_0(\epsilon,k_0,D)\geq k_0$ that depend only
  on~$\epsilon$, $k_0$, and~$D$ such that any
  $(\eta,D,p)$-upper-uniform graph~$J$ admits an
  $(\epsilon,J,p)$-regular $(\epsilon,k)$-equitable partition of its
  vertex set with~$k_0\leq k\leq K_0$.
\end{lem}

\subsubsection{Nearly regular subgraphs}

Let us introduce a piece of notation. Let a positive integer~$t$ be given.
If~$U_1,\dots,U_t\subseteq
V(J)$ are pairwise disjoint sets of vertices of a given graph~$J$, we
write~$J[U_1,\dots,U_t]$ for the $t$-partite subgraph of~$J$
naturally defined by the~$U_i$ ($1\leq i\leq t$).  Thus,
$J[U_1,\dots,U_t]$~has vertex set~$\bigcup_{i=1}^t U_i$ and two
of its vertices are adjacent in~$J[U_1,\dots,U_t]$ if and only if
they are adjacent in~$J$ and, moreover, they belong to distinct~$U_i$.

Now suppose we have real numbers~$0<p\leq1$, $0<\epsilon\leq1$,
and~$0<\gamma_0\leq1$. Let also~$m_i=|U_i|$ ($1\leq i\leq t$), and
write~$\gamma_{ij}$ for the $p$-density~$\dJp(U_i,U_j)$ for all
distinct~$i$ and~$j$.  Suppose~the pair~$(U_i,U_{i+1})$ is
$(\epsilon,J,p)$-regular and~$\gamma_{i,i+1}\geq\gamma_0$ for
any~$1\leq i<t$.

We may now state our next lemma. In what follows, we write~$O_1(x)$
for any term~$y$ satisfying~$|y|\leq x$.  We write~$\Gamma_J(x)$ for
the $J$-neighbourhood of a vertex~$x\in V(J)$.

\begin{lem}\label{MinDegree}
  Let~$J$ and the sets~$U_i$ $(1\leq i\leq t)$ be as above.
  Suppose~$0<\epsilon\leq1/5$ and put~$A=4+1/\gamma_0$.  Then there are
  sets~$\bU_i\subseteq U_i$ with~$|\bU_i|\geq(1-4\eps)m_i$ for all~$1\leq i\leq
  t$ such that, for all~$i$, $j\in[t]$ with~$|i-j|=1$ and any~$x\in\bU_i$, we
  have
  \[    
     d_{ij}(x)=|\Gamma_J(x)\cap\bU_j|=(1+O_1(A\eps))
    \gamma_{ij}pm_j.  
  \]
\end{lem}

\noindent
Lemma~\ref{MinDegree} above is very similar to Lemma~2
from~\cite{KLR1} and Lemma~5 from~\cite{KLR2}, and hence its proof is
omitted.

\subsubsection{Ramsey's theorem}

Here we give the following easy consequence of Ramsey's theorem. 

\begin{lem}\label{QRamsey}
  Let graphs~$H_1,\dots,H_r$ $(r\geq1)$ be given. Then there exist positive
  constants~$c=c(H_1,\dots,H_r)>0$ and~$k_0=k_0(H_1,\dots,H_r)$ for which the
  following holds.  If~$k\geq k_0$ and~$K^k$ is given an arbitrary
  $r$-edge-colouring, then we necessarily have, for some~$1\leq i\leq r$, at
  least~$ck^{|H_i|}$ monochromatic copies of~$H_i$ of colour~$i$.
\end{lem}
\proof Let~$k_0=q$ and~$c=(1/r)q^{-\max_i|H_i|}$,
where
$$ 
q=R(H_1,\dots,H_r)=\min\{n\:K^n\to(H_1,\dots,H_r)\}, 
$$ 
the Ramsey number for~$(H_1,\dots,H_r)$. Now let~$K^k$ with~$k\geq k_0$ 
be given an arbitrary $r$-edge-colouring. Then, each $q$-subset of the vertex
set of~$K^k$ gives, for some~$i$, a monochromatic copy of~$H_i$ of colour~$i$.
For some~$i$, at least~$(1/r){k\choose q}$ of these $q$-subsets gives a
monochromatic~$H_i$ of colour~$i$. Each such copy is counted at
most~${k-|H_i|\choose q-|H_i|}$ times. The number of such copies is,
therefore, at least
$$
{1\over r}{k\choose q}\left/{k-|H_i|\choose q-|H_i|}\right.  
  ={1\over r}{(k)_{|H_i|}\over(q)_{|H_i|}}
  \geq{1\over r}\(k\over q\)^{|H_i|}
  \geq ck^{|H_i|}, 
$$
as required.
\endproof

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof of Theorem~\ref{MainThm-1}}% Will it work?
%\section{Proof of the 1-statement} % Will it work?
%\label{sec:proof-of-thm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Preliminary lemmas}
\label{sec:prelim-lemmas}

Throughout this section we fix an integer~$\ell\geq3$ and a graph~$H$ as in
the statement of Theorem~\ref{MainThm-1}. Moreover, here we shall always
suppose that~$p=p(n)=Bn^{-\beta}$, where~$\beta$ is as defined
in~(\ref{beta-C-H}) and~$B>0$ is some constant. We also sometimes write~$h$
for the order of our graph~$H$. For the sake of definiteness, 
we shall assume that $V(G_p)=[n]$.

If~$H_1$ is a copy of~$H$ in~$G_p$ we say that~$H_1$ is {\it
isolated\/} if it does not intersect any other copy of~$H$ present
in~$G_p$ on an edge.  In other words, if we have~$E(H_1)\cap
E(H_2)=\emptyset$ for any other copy~$H_2$ of~$H$ in~$G_p$.

\subsubsection{Isolated copies of~$H$ in $G_p$}
\label{ssec:isolated-copies}

Let us write~$T=T(G_p)$ for the number of isolated copies of~$H$
in~$G_p$.  Let~$h=|H|$. Using the fact that~$H$ is $2$-balanced and
that~$m_2(C^\ell)<m_2(H)$, it is easy to see that almost all copies
of~$H$ in~$G_p$ are isolated but we shall not need this here. Let us
write~$\pO $ for the expected number of (not necessarily isolated)
copies of~$H$ in~$G_p$ that contain some fixed
edge~$e\in{[n]\choose2}$.  Clearly, the expected number~$\mu_H$ of
copies of~$H$ in~$G_p$ is~$|\Aut(H)|^{-1}(n)_hp^{e(H)}$,
where~$\Aut(H)$ denotes the automorphism group of~$H$.  A moment's
thought then shows that
\begin{equation}
\pO ={(n)_he(H)\over|\Aut(H)|{n\choose 2}}p^{e(H)}
   =(2+o(1)){e(H)B^{e(H)}\over|\Aut(H)|}n^{-1+1/(\ell-1)}. 
  \label{tilde-p-asymp}
\end{equation}

We now consider the following construction we shall use later.
Let~$\cH=\{H_1,\dots,H_T\}$ be the set of isolated copies of~$H$
in~$G_p$. We shall always write~$\tH=\tH(G_p)$ for the spanning
subgraph of~$G_p$ whose edge set is the union of the edge sets of
the~$H_i$ ($1\leq i\leq T$).  Clearly, we have~$e(\tH)=Te(H)$.

If we denote by~$\tp$ the probability that a given
edge~$e\in{[n]\choose2}$ is contained in~$\tH$ then~$\tp=(1+o(1))\pO$
as almost all copies of~$H$ are isolated.  In the sequel we shall only
use~$\pO$, which may be considered to be the edge probability
of~$\tH$.

Next we show that the edges of~$\tH$ satisfy some negative correlation
properties. For~$E\subseteq{[n]\choose 2}$, write~$E\sqsubset
E(\tH)$ if~$E\subseteq E(\tH)$ and all edges from~$E$ belong to {\it
different\/} isolated copies of~$H$ in~$G_p$.

\begin{lem}
\label{neg-cor}
For any set~$E\subseteq {[n]\choose 2}$,
\[ 
  \P[ E\sqsubset E(\tH)] \le \pO^{|E|}.
\]
\end{lem}
\proof Suppose~$E=\{e_1,\ldots, e_a\}$ where~$a=|E|$. Let~$I$ be the
set of all $a$-tuples~$(H_1,\dots,H_a)$ of $H$-subgraphs of~$K^n$
with~$e_i\in E(H_i)$ for all~$1\leq i\leq a$. Also, let~$J$ be the set
of such $a$-tuples~$(H_1,\dots,H_a)\in I$ with the~$H_i$ ($1\leq i\leq
a$) pairwise edge-disjoint. Finally, let~$\cH_i$ be set of
$H$-subgraphs of~$K^n$ that contain the edge~$e_i$ ($1\leq i\leq
a$). Thus, in particular, $I=\cH_1\times\cdots\times\cH_a$. Then
\begin{eqnarray*}
  \P[E\sqsubset E(\tH)]
     &\leq&\sum_{(H_1,\dots,H_a)\in J}
            \P[H_1\subseteq G_p,\dots,H_a\subseteq G_p]    \\
     &=&   \sum_{(H_1,\dots,H_a)\in J}
            \P[H_1\subseteq G_p]\cdots\P[H_a\subseteq G_p] \\
     &\leq&\sum_{(H_1,\dots,H_a)\in I}
            \P[H_1\subseteq G_p]\cdots\P[H_a\subseteq G_p] \\
     &=&   \sum_{H_1\in\cH_1}\P[H_1\subseteq G_p]
            \cdots\sum_{H_a\in\cH_a}\P[H_a\subseteq G_p] \\
     &=&   \pO^a, 
\end{eqnarray*}
as required.
\endproof

\subsubsection{Upper-uniformity results for~$\tH$}

In this section we show that the edges of~$\tH$ are fairly well distributed in
the sense that~$\tH$ is, almost surely, locally sparse. Our first lemma
implies that almost every~$\tH$ is $(\eta,3e(H),\pO)$-upper-uniform for any
fixed~$0<\eta\leq1$. 

\begin{lem}\label{upper-unif-1}
  Let~$\omega=\omega(n)\to\infty$ as~$n\to\infty$. Then, for
  almost every~$G_p$, the graph~$\tH=\tH(G_p)$ is such that the following
  holds. Suppose~$U$, $W\subseteq V(\tH)$ with~$U\cap W=\emptyset$ are
  such that~$|U||W|\geq\omega n^{2-1/(\ell-1)}$. Then we have
  \begin{equation}
    e_{\tH}(U,W)\leq3e(H)\pO|U||W|.
    \label{upper-unif-1-ineq}
  \end{equation}
\end{lem}
\proof If a fixed pair~$(U,W)$ with~$u=|U|$ and~$w=|W|$ does not
satisfy~(\ref{upper-unif-1-ineq}) then there is a set~$E\subseteq U\times W$
with $E\subseteq E(\tH)$ and~$|E|=\lceil3e(H)\pO uw\rceil$.  This implies the
existence of a set~$E'\subseteq U\times W$ of
size~$|E'|=\lceil3\pO uw\rceil$ such that all edges from~$E'$
belong to different isolated copies of~$H$ in~$G_p$.  The probability of this
event is by Lemma~\ref{neg-cor} at most
\[ 
{uw\choose\lceil3\pO uw\rceil}\pO^{\lceil3\pO uw\rceil}
    \le\(\frac{\e}{3}\)^{3\pO uw}. 
\]
As there are at most~$2^{2n}$ choices for the sets~$U$ and~$W$, 
the lemma follows from the fact that~$3\pO uw/n\to\infty$ as~$n\to\infty$  
(cf.~(\ref{tilde-p-asymp})).
\endproof

Our next lemma concerns the number of $\tH$-edges between sets~$U$ and~$W$
smaller than the ones considered in Lemma~\ref{upper-unif-1}, and hence may be
thought of as a more local condition on the sparseness of~$\tH$. To state our
lemma concisely, we introduce a definition. Let~$J$ be a graph on~$n$ vertices
and suppose $C\geq1$ and~$\ell\geq1$ are given.  We say that~$J$
is {\it locally $(\pO,C,\ell)$-upper-uniform\/} if for all pairs~$(U,W)$ of
disjoint sets of vertices~$U$, $W\subseteq V(J)$ satisfying
\begin{equation}
  |U|\leq|W|\leq \d0|U|\leq \d0^{\ell-2}, 
  \label{cond-UW}
\end{equation}
where~$\d0=\pO n$, we have
\begin{equation}
  e_J(U,W)\leq C|W|.
  \label{ineq-UW}
\end{equation}

\begin{lem}\label{upper-unif-2}
  Almost every~$G_p$ is such that~$\tH=\tH(G_p)$ is locally 
  $(\pO,2\ell e(H),\ell)$-upper uniform.
\end{lem}
\proof The probability that a fixed pair~$(U,W)$ of disjoint sets of
vertices with~$u=|U|$ and~$w=|W|$ does not satisfy~(\ref{ineq-UW}) can
be bounded similarly as in the proof of Lemma~\ref{upper-unif-1} by
\[ 
{uw\choose\lceil2\ell w\rceil}\pO^{\lceil2\ell w\rceil}  
  \le\(\frac{\e u}{2\ell}\pO\)^{2\ell w}.
\]
Observe that, for pairs~$(U,W)$ as in~(\ref{cond-UW}), we
have~$u\leq(\pO n)^{\ell-3}\le An^{(\ell-3)/(\ell-1)}$ for some
constant~$A=A(H,B)>0$.  Moreover, we have~$u\leq w=o(n)$
as~$n\to\infty$, and hence~${n\choose u}{n\choose w}\leq{n\choose
w}^2$.  Therefore, the expected number of pairs~$(U,W)$
satisfying~(\ref{cond-UW}) but not~(\ref{ineq-UW}) is at most
\[ 
\sum_{w=1}^{\lfloor n/2\rfloor}
      w{n\choose w}^2\(\frac{\e u}{2\ell}\pO\)^{2\ell w} 
  \leq\sum_{w=1}^{\lfloor n/2\rfloor}
         w\(n^{1/\ell}\frac{\e^{1+1/\ell}}{2\ell}
                An^{(\ell-3)/(\ell-1)}\pO\)^{2\ell w} 
  =o(1)
\]
(cf.~(\ref{tilde-p-asymp})) and the lemma follows from Markov's
inequality. \endproof

\subsubsection{The distribution of isolated copies of~$H$ in $G_p$}
\label{dist-isolated-H}

In this section we prove a simple lemma concerning the existence of a
large number of isolated copies of~$H$ in~$G_p$ when~$p$ is as given
in Theorem~\ref{MainThm-1}. In fact, for technical reasons, we shall
need to look at the existence of such copies of~$H$ with each of their
vertices taken from specified subsets of vertices of~$G_p$.

Label the vertices of~$H$ by~$v_1,\dots,v_h$ where $h=|H|$.
Suppose~$W_1,\dots,W_h$ are pairwise disjoint subsets of vertices
of~$G_p$.  Put~$\bfW=(W_i)_{i=1}^h$. Here we are interested in the
number~$Z=Z_\bfW(G_p)$ of injections~$\iota\:V(H)\to V(G_p)$
taking~$v_i$ into~$W_i$ for all~$1\leq i\leq h$, and such
that~$\iota(v_i)\iota(v_j)\in E(G_p)$ whenever~$v_iv_j\in E(H)$. We
shall refer to such maps~$\iota$ as {\it$\bfW$-embeddings\/} of~$H$
in~$G_p$. Moreover, we say that the subgraph of~$G_p$ with vertex
set~$\iota(V(H))$ and edge set~$\{\iota(v_i)\iota(v_j)\:v_iv_j\in
E(H)\}$ is the \textit{image}~$\im\iota$ of~$\iota$.

Finally, let us define~$Y=Y_\bfW(G_p)$ to be the number of
$\bfW$-embeddings~$\iota$ of~$H$ in~$G_p$ with~$\im\iota$ an isolated
$H$-subgraph of~$G_p$.

\begin{lem}\label{lem:well-dist}
  Suppose~$B>0$ is a constant and~$\beta$ is as defined
  in~$(\ref{beta-C-H})$.  Then, for~$p=Bn^{-\beta}$, almost
  every~$G_p$ has the following property.  For any
  vector~$\bfW=(W_i)_{i=1}^h$ of pairwise disjoint sets~$W_i\subseteq
  [n]$ $(1\leq i\leq h)$, each of cardinality at least~$n/\log n$, we
  have~$Y=Y_\bfW(G_p)\geq(1/2)\E(Z_\bfW)$.
\end{lem}
\proof Define $\cU$ to be the set of all graphs that can be written as
a union of two copies of $H$ intersecting in at least one edge, not
including~$H$ itself. Let then $X=X(G_p)$ count the number of graphs
from $\cU$ present in $G_p$.  We first aim at bounding~$X$.
From~$m_2(C^\ell)<m_2(H)$ it is easy to see that~$\beta>1/m_2(H)$.
Let~$\delta=\beta-1/m_2(H)>0$.  As $H$ is 2-balanced we have that for
any proper subgraph~$J$ of~$H$ containing at least one edge
\[  
  \frac{|H|-|J|}{e(H)-e(J)}\leq\frac{1}{m_2(H)}\ = \beta-\delta. 
\]
Therefore, writing~$\sum_{K^2\subseteq J\subset H}$ for the sum over all
proper subgraphs~$J\subset H$ containing at least one edge, we have
\begin{eqnarray*}
  \E(X)&=&\sum_{U\in\cU}{(n)_{|U|}\over|\Aut(U)|}p^{e(U)}  \\
       &=&O\bigg(\sum_{K^2\subseteq J\subset H}
                       n^{2|H|-|J|}p^{2e(H)-e(J)}\bigg)\\ 
       &=&O\bigg(\sum_{K^2\subseteq J\subset H}
                   n^{2|H|-|J|-\beta(2e(H)-e(J))}\bigg)\\ 
       &=&O\(n^{|H|-\beta e(H)-\delta(e(H)-e(J))}\) \\
       &=&O(n^{1+1/(\ell-1)-\delta(e(H)-e(J))}).
\end{eqnarray*}
Next we use Janson's inequality~(\ref{Janson-ineq}) to show that~$Z_\bfW$ is
with high probability not too small.  So fix~$\bfW=(W_i)_{i=1}^h$ and
let~$\(H_\alpha\:\alpha\in\cA\)$ be the family of all graphs which are
isomorphic to~$H$ and whose vertex set can be written as $\{v_1,\ldots, v_h\}$
with~$v_i\in W_i$ for all~$1\leq i\leq h$.
Thus~$|\cA|=|W_1|\dots|W_h|\geq(n/\log n)^h$, and the random variable~$S$
defined in Section~\ref{sec:Janson-ineq} coincides with~$Z_\bfW$.  We have
that
\[
\E(Z_\bfW)\geq\(n\over\log n\)^{|H|}B^{e(H)}n^{-\beta e(H)}
          =B^{e(H)}n^{1+1/(\ell-1)-|H|\log\log n/\log n}.
\] 
By Markov's inequality we have that~$X=o(\E(Z_\bfW))$ almost surely and
therefore also~$\Delta\leq2X=o(\E(Z_\bfW))$ where~$\Delta$ is as defined
in~(\ref{def-Delta}).  Then
Janson's inequality  %Lemma~\ref{lem:Janson-ineq}
implies that
\[ 
\P\left[Z_\bfW\leq\frac{3}{4}\E(Z_\bfW)\right]
  \leq\exp\(-{1\over33}\E(Z_\bfW)\)
  \leq\exp(-n^{1+1/\ell}), 
\]
if~$n$ is large enough. On the other hand, there are at most~$2^{hn}$
choices for~$\bfW$. Thus for almost every~$G_p$ we have
$Z_\bfW\geq(3/4)\E(Z_\bfW)$ for every~$\bfW$. Furthermore we almost
surely have that~$X\leq\E(Z_\bfW)/8$ and therefore
also~$Y_\bfW(G_p)\ge Z_\bfW-2X \ge \E(Z_\bfW)/2$ for every~$\bfW$,
almost surely, as required.  
\endproof

\subsection{The key counting lemma}
\label{sec:count-lemma}

Throughout this section, $\ell\geq3$~is a fixed integer
and~$\bfV=(V_1,\dots,V_\ell)$ is a fixed vector of pairwise disjoint
sets~$V_1,\dots,V_\ell$, all of the same cardinality, say~$m$.

In this section we shall be interested in counting certain graphs~$F$
whose vertex set is~$V(F)=\bigcup_{i=1}^\ell V_i$ and all whose edges
join vertices in consecutive classes~$V_i$. More precisely, if~$e$ is
an edge of~$F$, then its two endpoints will belong to~$V_{i-1}$
and~$V_i$, respectively, for some~$1\leq i\leq\ell$.  Here and below,
the indices of the sets~$V_i$ will be taken modulo~$\ell$.  For
conciseness, given~$\bfV=(V_i)_{i=1}^\ell$, let us say that a
graph~$F$ as described above is a {\it$\bfV$-graph\/}.  To define the
precise subclass of $\bfV$-graphs~$F$ that we shall be interested in,
however, we need to introduce some more parameters and definitions.

Let~$0<\epsilon\leq1$, $\bB> 0$, $0<\gamma_0\leq1$, $C\geq1$,
and~$D\geq1$ be real numbers and let~$\bT$ be a positive integer. We
shall write
\[
  \cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)
\]
for the set of $\bfV$-graphs~$F$ satisfying conditions~({\it
  i\/})--({\it iv\/}) given below.
\begin{list}{(iii)}{\itemsep-1mm}
\item[({\it i\/})] The graph~$F$ has~$\bT$ edges.
\item[({\it ii\/})] The graph~$F$ is such that all the
  pairs~$(V_{i-1},V_i)$ ($1\leq i\leq\ell$) are
  $(\epsilon,F,\bp)$-regular, where~$\bp=\bp(m)=\bB m^{-1+1/(\ell-1)}$.
\item[({\it iii\/})] The
  $\bp$-density~$\gamma_{i-1,i}=d_{F,\bp}(V_{i-1},V_i)$
  of~$F$ between the sets~$V_{i-1}$ and~$V_i$ is such that, for
  all~$1\leq i\leq\ell$, we have 
\begin{equation}
  \gamma_0\leq\gamma_{i-1,i}\leq D.
  \label{bounded-gammas}
\end{equation}
\item[({\it iv\/})] For all~$U\subseteq V_{i-1}$ and~$W\subseteq V_i$
  ($2\leq i<\ell$) with
\begin{equation}
  |U|\leq|W|\leq\bd|U|\leq\bd^{\ell-2}, 
  \label{cond-UW-def-F}
\end{equation}
where~$\bd=\bp m$, we have
\begin{equation}
  e_F(U,W)\leq C|W|.
  \label{ineq-UW-def-F}
\end{equation}
\end{list}

Let us now define the class
\[  
\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)
    \subseteq\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)
\]
as the class of graphs~$F\in\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$
that do not contain a copy of~$C^\ell$ as a subgraph. Our aim in this
section is to estimate the
cardinality~$f_m'(\epsilon,\bB,\gamma_0,C,D;\bT)$
of~$\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$ from above.

\begin{lem}\label{count-lemma}
  Let an integer~$\ell\geq3$ be fixed, and let
  constants~$0<\alpha\leq1$, 
  $0<\gamma_0\leq1$, $C\geq1$, and~$D\geq1$ be given. Then there are
  constants~$0<\epsilon\leq1$, $\bB_0>0$, and~$m_0$ that depend only
  on~$\ell$, $\alpha$, $\gamma_0$, $C$, and~$D$ such that, for all
  integers~$m\geq m_0$ and~$\bT\geq1$ and real numbers~$\bB\geq\bB_0$, 
  we have 
 \begin{equation}
    f_m'(\epsilon,\bB,\gamma_0,C,D;\bT)
      \leq\alpha^\bT{(\ell+2) m^2\choose\bT}.
    \label{count-lemma-ineq}
  \end{equation}
\end{lem}

The proof of Lemma~\ref{count-lemma} is based on a technical lemma,
Lemma~\ref{tech-lemma}, that we now describe. Let a constant~$0<\delta\leq1$
be given, and suppose we have real numbers~$0<\epsilon\leq1$,
$0<\gamma_0\leq1$, $\bB$, $C$, $D\geq1$, and an integer~$\bT\geq1$. Let
\[  
  F\in\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)
\]
be fixed. Lemma~\ref{tech-lemma} will concern the $(\ell-1)$-partite
subgraph~$\dF=F[V_1,\dots,V_{\ell-1}]$ of~$F$ induced by the vertex
classes~$V_1,\dots,V_{\ell-1}$.  Suppose~$y_1,\dots,y_{j-1}\in V_1$
are~$j-1$ given vertices of~$V_1$, where~$1\leq j\leq\delta m/2$. Let 
\begin{equation}
  U_1=V_1\setminus\{y_1,\dots,y_{j-1}\}
  \label{def-U-1}
\end{equation}
and
\begin{equation}
  U_{\ell-1}=V_{\ell-1}
     \setminus\bigcup_{q=1}^{j-1}\dGamma^{(\ell-2)}_F(y_q), 
  \label{def-U-ell-1}
\end{equation}
where~$\dGamma^{(\ell-2)}_F$ denotes the $(\ell-2)$-fold iteration
of~$\dGamma_F=\Gamma_\dF$.  Suppose~$|U_{\ell-1}|\geq\delta m$. Our
technical lemma tells us that then, provided~$\epsilon$ is small
enough, most vertices in~$U_1$ are `good', in the sense that their
$(\ell-2)$nd $\dF$-neighbourhood within~$U_{\ell-1}$ is large. 

\begin{lem}\label{tech-lemma}
  Let~$0<\delta\leq 1$, $0<\gamma_0\leq 1$, $\bB>0$, $C\geq1$,
  and~$D\geq1$ be given. Then
  if~$0<\epsilon\leq\min\{\delta/4,\gamma_0/(8\gamma_0+2)\}$, 
  and~$m$ and~$\bT$ are integers, any
  graph~$F\in\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$ is such that at
  least~$(1-\delta)|U_1|$ vertices~$y\in U_1$ satisfy
  \begin{equation}
  \Big|\dGamma^{(\ell-2)}_F(y)\cap U_{\ell-1}\Big|
    \geq2^{-\ell+2}{\gamma_0^{\ell-2}\over
      C^{\ell-3}}\delta\bd^{\ell-2}, 
    \label{large-ell-2-nbhd}
  \end{equation}
  where~$\bd=\bp m$.
\end{lem}

\proofof Lemma~\ref{count-lemma}. Let~$\ell$, $\alpha$, $\gamma_0$,
$C$, and~$D$ as in the statement of our lemma be given.  Let us define
the constants
\begin{eqnarray*}
  \delta&=&\min\{1/2, (\alpha^{\ell D}2^{-5D})^{8/\gamma_0}\}, \\
  \eps&=&\min\{\delta/4,\gamma_0/(8\gamma_0+2)\}, \\
  \bB_0&=&\left(
             \frac{4C^{\ell-3}}
                  {2^{-\ell+2}\gamma_0^{\ell-1}\delta}
          \right)^{1/(\ell-1)}, \\
  m_0&=&\left(\frac{3}{2}D\bB_0\right)^{(\ell-1)/(\ell-2)}.
\end{eqnarray*}
Our aim is to show that~$\epsilon, \bB_0$ and~$m_0$ given above will
do in Lemma~\ref{count-lemma}. Thus, let integers~$m\ge m_0$ and~$\bT$
and a real~$\bB\geq\bB_0$ be given. We have to show
that~(\ref{count-lemma-ineq}) holds.  We
estimate~$f_m'(\epsilon,\bB,\gamma_0,C,D;\bT)$ from above by
estimating the number of ways we may `generate' an element
from~$\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$.

In order to generate a graph~$F$ from
$\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$, we first choose
$\bT_1=e_F(V_1,V_\ell)$ and $\bT_{\ell-1}=e_F(V_{\ell-1},V_\ell)$.
Later on we shall sum over all possible values of~$\bT_1$
and~$\bT_{\ell-1}$.  Observe that for~$i\in\{1,\ell\}$ we have
\begin{equation}
  \gamma_0\bB m^{1+1/(\ell-1)}
     \leq\bT_i=d_{F,\bp}(V_i,V_\ell)\bp m^2 
     \leq D\bB m^{1+1/(\ell-1)}.
  \label{bound-T-i}
\end{equation}
Put $\bT_0=\bT-\bT_1-\bT_{\ell-1}$. Next we fix
$\dF=F[V_1,\dots,V_{\ell-1}]$, for which we have not more
than~${(\ell-2)m^2\choose \bT_0}$ possibilities. By
Lemma~\ref{MinDegree} for~$t=3$, we know that for any choice of the
edges of~$F$ incident to~$V_\ell$ there have to be sets~$\bV_i\subseteq
V_i$ $(i\in\{1,\ell-1,\ell\})$ such that for any~$x\in \bV_\ell$ and
any $i\in\{1,\ell-1\}$ we have
\begin{equation}
  \label{reg-vert}
  d_i(x)=|\Gamma_F(x)\cap \bV_i| 
        =(1+O_1(A\eps))\frac{\bT_i}{\bp|V_\ell||V_i|}\bp|V_i|
        =(1+O_1(A\eps))\frac{\bT_i}{m},
\end{equation}
where~$A=4+1/\gamma_0$. Call the $F$-edges in~$\bV_\ell\times \bV_i$
($i\in\{1,\ell-1\}$) {\it regular\/} edges and the remaining $F$-edges
between~$V_\ell$ and~$V_i$ {\it irregular} edges.
For~$i\in\{1,\ell-1\}$, denote by~$\bT\irr_i$ the number of irregular
edges incident to~$V_i$.  Summing up we have that, for given~$\bT_0$
and~$\bT\irr_i$, there are at most
\begin{equation}
  \label{numb-irreg}
  {(\ell-2)m^2\choose\bT_0}{m^2\choose\bT\irr_1}{m^2\choose\bT\irr_{\ell-1}}  
\end{equation}
ways of choosing the set of edges of~$F$, except for the regular edges
incident to~$V_\ell$.

Now we have to bound the number of choices for the regular edges. Let
us first choose the degree sequences~$(d_i(x))_{x\in V_\ell}$ of the
vertices in~$V_\ell$, where~$d_i(x)=|\Gamma_F(x)\cap \bV_i|$
for~$i\in\{1,\ell-1\}$.  For a vertex $x\in \bV_\ell$ we may assume
by~(\ref{bound-T-i}), (\ref{reg-vert}) and the definition of $m_0$
that
\begin{equation}
   \dmin:= {1\over2}\gamma_0\bB m^{1/(\ell-1)}\le d_i(x)\le m. 
  \label{d-i-min}
\end{equation}
Let us now fix a vertex~$x$ in~$\bV_\ell$, and let us say that a
set~$Y\subseteq V_1$ of size~$\dmin\leq d'=|Y|\leq m$ is \textit{good}
if $|\dGamma_F^{(\ell-2)}(Y)\cap V_{\ell-1}|\ge(1-\delta)m$.  The idea
is that if we choose a good set~$Y$ to be the neighbourhood of~$x$
within~$V_1$, then the number of vertices in~$V_{\ell-1}$ that are
allowed to be adjacent to~$x$ in~$F$ is very small, namely, at
most~$\delta m$, since we are supposed to generate a $C^\ell$-free
graph~$F$.  Now, if a $d'$-set~$Y\subseteq V_1$ as above is not good
then, for any ordering $y_1,y_2,\ldots,y_{d'}$ of the vertices of~$Y$,
there are at least~$d'/2$ indices~$i$ with
\[ 
\bigg|\dGamma_F^{(\ell-2)}(y_i)
     \setminus\bigcup_{q=1}^{i-1}\dGamma^{(\ell-2)}_F(y_q)
\bigg|<\frac{(1-\delta)m}{d'/2}
      \le2^{-\ell+2}{\gamma_0^{\ell-2}\over C^{\ell-3}}\delta\bd^{\ell-2}, 
\]
where the last inequality follows from the definition of~$\bB_0$ 
and~(\ref{d-i-min}).
For these indices~$i$, by Lemma~\ref{tech-lemma}, there are only $\delta m$
choices for~$y_i$ once $y_1,\ldots,y_{i-1}$ are chosen.  Therefore the number
of bad sets~$Y$ of size~$\dmin\leq d'\leq m$ is at most
\[
  {d'\choose\lceil d'/2\rceil}\delta^{d'/2}\frac{m^{d'}}{d'!}
      \le2^{d'}\delta^{\dmin/2}\e^{d'}{m\choose d'}.
\]
If the neighbourhood~$\Gamma_F(x)\cap V_1$ of the vertex $x\in
\bV_\ell$ in~$V_1$ is good then, since~$C^\ell\not\subseteq F$, there
are only ${\delta m\choose
d_{\ell-1}(x)}\le\delta^{d_{\ell-1}(x)}{m\choose d_{\ell-1}(x)}$
choices for the neighbourhood~$\Gamma_F(x)\cap V_{\ell-1}$ of~$x$
within~$V_{\ell-1}$. On the other hand, if~$\Gamma_F(x)\cap V_1$
happens to be bad, then trivially there are at most~${m\choose
d_{\ell-1}(x)}$ choices for this neighbourhood.  Therefore there are
at most
\begin{eqnarray*}
  \label{numb-reg}
  {m\choose d_{1}(x)}\delta^{d_{\ell-1}(x)}{m\choose d_{\ell-1}(x)}
    +\delta^{\dmin/2}2^{3d_1(x)}{m \choose d_1(x)}{m\choose d_{\ell-1}(x)}
    \qquad\\ 
    \le\quad\delta^{\dmin/2}2^{3d_1(x)+1}
                       {m \choose d_1(x)}{m\choose d_{\ell-1}(x)}
\end{eqnarray*}
ways of choosing the regular edges incident to our vertex~$x\in\bV_\ell$. 

Let us write~$\sum_\bT'$ for the sum over all
partitions~$\bT_0+\bT_1+\bT_{\ell-1}=\bT$ of~$\bT$, and
similarly~$\sum_{\bT_1}'$ and~$\sum_{\bT_{\ell-1}}'$ for the sums over all
partitions $\bT_1\irr+d_1+\ldots+d_m=\bT_1$ of~$\bT_1$
and~$\bT_{\ell-1}\irr+d'_1+\ldots+d'_m=\bT_{\ell-1}$ of~$\bT_{\ell-1}$.  Let
us also write~$\sum_{\bV_\ell}$ for the sum over all possible choices
of~$\bV_\ell$.  Then, recalling the bound~(\ref{numb-irreg}), we see
that~$f_m'(\epsilon,\bB,\gamma_0,C,D;\bT)$ is at most
\begin{eqnarray*}
\sum_\bT\nolimits'\sum_{\bT_1}\nolimits'\sum_{\bT_{\ell-1}}\nolimits'
  \sum\nolimits_{\bV_\ell}
  {(\ell-2)m^2\choose\bT_0}{m^2\choose\bT\irr_1}
  {m^2\choose\bT\irr_{\ell-1}} \qquad\qquad\qquad\qquad\\
  \qquad\quad\times\delta^{|\bV_\ell|\dmin/2}
  \prod_{j=1}^m\(2^{3d_j+1}{m\choose d_j}{m\choose d'_j}\)\quad\\ 
  \le\delta^{m\dmin/4}2^{3\bT_1+2m}{(\ell+2)m^2\choose\bT} 
  \quad\le\quad\alpha^{\bT}{(\ell+2) m^2 \choose \bT},
\end{eqnarray*}
where we apply Vandermonde's identity and the fact that, trivially, there are
at most~$2^m$ choices for~$\bV_\ell$ to deduce the first inequality and we
use~(\ref{bound-T-i}),~(\ref{d-i-min}),
 that~$\bT\le\ell D\bB m^{1+1/(\ell-1)}$, and the
definition of~$\delta$ to deduce the second inequality.  
\endproof

\proofof Lemma~\ref{tech-lemma}. Let~$\epsilon$, $\bB$, $\gamma_0$,
$C$, $D$, and~$\bT$ be as in the statement of our lemma.  Fix a
graph~$F\in\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$ and let us
consider~$\dF=F[V_1,\dots,V_{\ell-1}]$. Recall~(\ref{def-U-1})
and~(\ref{def-U-ell-1}) and put~$U_i=V_i$ for all~$2\leq
i\leq\ell-2$. The first step is to apply Lemma~\ref{MinDegree}
with~$t=\ell-1$ to get rid of vertices of small degree. We obtain
sets~$\bU_i\subseteq U_i$ ($1\leq i<\ell$) with
\begin{equation}
  \label{lower-bd-V-i-prime}
  |\bU_i|\geq(1-4\epsilon)|U_i|\ge (1-\delta)|U_i|
\end{equation}
for all~$1\leq i<\ell$, and such that, for all~$2\leq i<\ell$ and all
$x\in\bU_{i-1}$, we have
\begin{eqnarray}
  d_{i-1,i}(x)
    &=&|\Gamma_F(x)\cap\bU_i|  \nonumber\\
    &\geq&\(1-\(4\gamma_0+1\over\gamma_0\)\eps\) 
                        d_{F,\bp}(U_{i-1},U_i)\bp|U_i|  \nonumber\\
    &\geq&(\gamma_0/2)\bp|U_i|. 
  \label{min-degree-ineq}
\end{eqnarray}
In the case~$\ell=3$ we are already finished if we let~$i=2$
in~(\ref{min-degree-ineq}).  If~$\ell>3$ we use property~({\it iv\/})
of~$F$ to prove the following assertion by induction on~$i$.

\begin{cl}
  For any~$y\in \bU_1$ and any~$2\leq i\leq\ell-2$, we have
\[
    \Big|\dGamma^{(i-1)}_F(y)\cap \bU_i\Big|
       \geq2^{-i+1}{\gamma_0^{i-1}\over C^{i-2}}\bd^{i-1}.
\]
\end{cl}
The claim for~$i=2$ is just~(\ref{min-degree-ineq}). For
$2<i\leq\ell-2$, let $U\subseteq\dGamma^{(i-2)}_F(y)\cap \bU_{i-1}$ be a
set of size $\lceil2^{-i+2}\gamma_0^{i-2}C^{-i+3}\bd^{i-2}\rceil$.
Assume that $W=\Gamma_F(U)\cap\bU_i$ has less than
$2^{-i+1}\gamma_0^{i-1}C^{-i+2}\bd^{i-1}$ elements.
Because~$|U|\le\bd^{\ell-3}$, we may apply~(\ref{ineq-UW-def-F}) to
yield
\[ 
e_F(U,W)\leq C|W|<\frac{\gamma_0\bd}{2}|U|.
\]
Because~$\bd=\bp|U_i|$ for~$i\leq\ell-2$ this is a contradiction
to~(\ref{min-degree-ineq}), and hence the claim is proven.

Finally, using the fact
that $\bp|U_{\ell-1}|\geq\bp\delta m=\delta\bd$, the same
expansion argument implies that for any~$y\in\bU_1$ we have
\begin{equation}
  \Big|\dGamma^{(\ell-2)}_F(y)\cap \bU_{\ell-1}\Big|
     \geq2^{-\ell+2}{\gamma_0^{\ell-2}\over C^{\ell-3}}
            \delta\bd^{\ell-2}.
  \label{final-expan-ineq}
\end{equation}
We have thus shown that any~$y\in \bU_1$ is such
that~(\ref{large-ell-2-nbhd}) holds. Since
by~(\ref{lower-bd-V-i-prime}) we have~$|\bU_1|\geq(1-\delta)|U_1|$,
the proof of the lemma is finished.  \endproof

\subsection{Proof of Theorem~\ref{MainThm-1}}
\label{sec:the-proof}

\proofof Theorem~\ref{MainThm-1}. Let~$\ell$ and~$H$ be as in the
statement of the theorem.  We shall start by defining some constants.
Let first $k_0$ and $c$ be the constants from Lemma~\ref{QRamsey}
applied to the triple $(C^\ell,H,K^2)$. Set $C=2\ell e(H)$, $D=3e(H)$,
\begin{eqnarray}
  \label{def-gamma-0}
  \gamma_0&=&\min\{1,c2^{-h-1}/e(H)\},\\ 
  \label{def-alpha}
  \alpha&=&\min\{1,\gamma_0/(\ell+2)\},
\end{eqnarray}
where $h=|H|$ as usual.  Apply Lemma~\ref{count-lemma} to the set of
constants~$\ell$, $\alpha$, $\gamma_0$, $C$ and~$D$ to obtain the
constants~$\epsilon$, $\bB_0$, and~$m_0$ whose existence is guaranteed
by that lemma.  Clearly, we may and shall assume
that~$\epsilon\leq\min\{1/2,2c\}$.  Finally, let~$K_0=K_0(\eps,k_0,D)$
and~$\eta=\eta(\eps,k_0,D)$ be the constants from Lemma~\ref{SSz} and
set
\begin{equation}
  \label{def-B}
  B=B_{\ell,H}=B=|\Aut(H)|K_0\bB_0.
\end{equation}
In the remaining of the proof, we shall show that this choice
of~$B=B_{\ell,H}$ will do. Recall that we consider~$p=p(n)=Bn^{-\beta}$,
where~$\beta$ is as given by~(\ref{beta-C-H}). In the sequel we shall also
use~$\pO$ and~(\ref{tilde-p-asymp}).

As before, let~$\tH=\tH(G)$ be the spanning subgraph of~$G$ with edge
set~$E(\tH)=\bigcup_{1\leq i\leq T}E(H_i)$, where~$H_1,\ldots,H_T$ are
the isolated copies of~$H$ in~$G$. Let us now define~$\cG=\cG^n$ to be
the family of graphs~$G$ of order~$n$ satisfying
properties~(\textit{a})--(\textit{c}) below.
\begin{list}{(a)}{\itemsep-1mm}
\item[({\it a\/})] $\tH(G)$ is $(\eta,D,\pO)$-upper-uniform.
\item[({\it b\/})] If~$\bfW=(W_i)_{i=1}^h$ is a vector of pairwise disjoint
  subsets of vertices of~$G$ with~$|W_i|\geq n/\log n$ for all~$1\leq i\leq
  h$, then~$Y_\bfW=Y_\bfW(G)\geq(1/2)|W_1|\dots|W_h|p^{e(H)}$, where~$Y_\bfW$
  is as defined in Section~\ref{dist-isolated-H}.
\item[({\it c\/})] For any vector~$\bfV=(V_i)_{i=1}^\ell$
        of pairwise disjoint $m$-subsets of vertices of~$G$, 
        where $n/2K_0\leq m\leq n/k_0$, 
        if a $\bfV$-graph~$F$ (cf.~Section~\ref{sec:count-lemma})  
        with~$E(F)\sqsubset E(\tH(G))$ is such that all 
        pairs~$(V_{i-1},V_i)$ with~$1\leq i\leq\ell$
        are~$(\eps,F,\pO)$-regular and 
        satisfy~$\dFpO(V_{i-1},V_i)\ge\gamma_0$, then~$F$ contains a 
        copy of~$C^\ell$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\item[({\it c\/})]Let integers~$n/2K_0\leq m\leq n/k_0$
%and~$\gamma_0\ell\pO 
% m^2\leq\bT\leq D\ell\pO m^2$ be given, and let~$\bB=\bB_m>0$ be such
%that~$\pO=\bB m^{-1+1/(\ell-1)}$. Also, let~$\bfV=(V_i)_{i=1}^\ell$ be a
%vector of pairwise disjoint subsets of vertices of~$G$ with~$|V_i|=m$
%for 
%all~$1\leq i\leq\ell$. Then, $G$~contains no
%subgraph~$F\in\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$
%with~$E(F)\sqsubset E(G)$ for any choice of~$m$,~$\bT$ and~$\bfV$ as 
%above.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{list}

The proof of Theorem~\ref{MainThm-1} will be finished if we establish
the following two claims.

\begin{cl} \label{cl:GpincG}
  Almost every~$G_p$ belongs to~$\cG$.
\end{cl}

\begin{cl} \label{cl:GincGgood}
  Every member~$G$ of~$\cG$ satisfies~$G\to(C^\ell,H)$ provided~$n$ is
  large enough.
\end{cl}

\proofof Claim~\ref{cl:GpincG}.  Lemma~\ref{upper-unif-1} implies that
almost every~$G=G_p$ satisfies condition~(\textit{a}) above, whereas
Lemma~\ref{lem:well-dist} implies that almost every~$G=G_p$
satisfies~(\textit{b}).  To prove that~(\textit{c}) is almost surely
true for~$G=G_p$, we first want to argue that any~$F$ as in the
statement of~(\textit{c}) is an element of
$\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$, where $\bT=e(F)$
and~$\bB=\bB_m>0$ is such that~$\pO=\bB m^{-1+1/(\ell-1)}$.  Note that
by the choices of our constants we have~$\bB=\pO m^{1-1/(\ell-1)}\geq
e(H)B^{e(H)}/(|\Aut(H)|K_0)\geq\bB_0$ (cf.~(\ref{def-B})).
Conditions~(\textit{i}) and~(\textit{ii}) in the definition of~$\cF$
are clearly satisfied.  Condition~(\textit{iii}) follows from the
upper uniformity of~$\tH$ (cf.~(\textit{a})) and from the assumption
on the density of the pairs~$(V_{i-1},V_i)$.  Finally,
condition~(\textit{iv}) in the definition of~$\cF$ follows from
Lemma~\ref{upper-unif-2}.  Now if any such~$F$ does not contain a copy
of~$C^\ell$ then this implies that~$\tH$ contains an element of
$\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$ for some choice of~$m$,
$\bT$, and~$\bfV$.  The probability of this event is by
Lemmas~\ref{neg-cor} and~\ref{count-lemma} at most
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%use Lemmas~\ref{neg-cor} and~\ref{count-lemma}.
%Let~$m$, $\bT$, $\bB$, and~$\bfV$ be as set out in~(\textit{c}).
%Note that 
%by the choices of our constants we have~$\bB=\pO m^{1-1/(\ell-1)}\geq
%e(H)B^{e(H)}/(|\Aut(H)|K_0)\geq\bB_0$ (cf.~(\ref{def-B})).  Then the
%expected
%number of subgraphs~$J\subseteq G_p$ as in the statement
%of~(\textit{c}) is, 
%by Lemma~\ref{neg-cor} and~\ref{count-lemma}, at most
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{eqnarray}
 \nonumber 
 |\cF_m'(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)|\pO^\bT
  &\leq&\alpha^\bT{(\ell+2) m^2\choose\bT}\pO^\bT \\ \label{eq:expec}
  &\le&\left(\alpha \frac{\e(\ell+2)m^2}{\gamma_0\ell\pO
   m^2}\pO\right)^\bT \quad \le\quad \left(\frac{\e}{\ell}\right)^\bT.
\end{eqnarray}
Summing~(\ref{eq:expec}) over all possible choices of~$m$, $\bT$,
and~$\bfV$ gives us an additional factor of at most 
$n^3 2^{\ell n}$. Using the fact that~$\bT$ is superlinear in~$n$, 
we deduce by Markov's inequality that~(\textit{c}) holds
for almost every~$G_p$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% [\ykcomm I
%haven't put in the calculations here for now but they should be done,
%sorry. 
%bk: I think this is fine now or do you think it needs some more 
%explanations ?]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This finishes the proof of Claim~\ref{cl:GpincG}.

\proofof Claim~\ref{cl:GincGgood}.  Let~$G\in\cG$ be fixed, and
suppose~$G$ is given a blue-red edge-colouring that contains no
red~$H$.  Our aim is to show that then there is a blue copy
of~$C^\ell$ in our graph~$G$.  Recall that~$G$ contains~$T$ isolated
copies~$H_1,\dots,H_T$ of~$H$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% (as long as~$n$ is
%sufficiently large. [bk: why did you mention this here?])
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Clearly, we may pick one blue edge~$e_i\in E(H_i)$ for
each~$1\leq i\leq T$.  We shall prove that, however we choose these~$T$ blue
edges~$e_i$, we shall necessarily select the edges of a~$C^\ell\subseteq G$.

We start by letting~$J$ be the spanning subgraph of~$G$ with edge
set~$E(J)=\{e_i\:1\leq i\leq T\}$.  From property~(\textit{a}) above,
we know that~$\tH$ is $(\eta,D,\pO)$-upper-uniform, and hence so
is~$J$.  We may thus apply Lemma~\ref{SSz} to~$J$ and obtain an
$(\epsilon,k)$-equitable $(\epsilon,J,\pO)$-regular
partition~$\Pi=(V_i)_{i=0}^k$ of~$V(J)$ with~$k_0\le k\le K_0$.
Write~$m$ for the cardinality of the~$V_i$ ($1\leq i\leq k$).

We now consider a complete graph~$K^k$ on the vertex set~$[k]$, and
consider the $3$-edge-colouring defined as follows: colour the
edge~$ij$ with colour~$3$ if the pair~$(V_i,V_j)$ is not
$(\epsilon,J,\pO)$-regular; otherwise, colour the edge~$ij$ colour~$1$
if~$\gamma_{ij}=\dJpO(V_i,V_j)\geq\gamma_0$, and colour~$2$
if~$\gamma_{ij}<\gamma_0$.  We then apply Lemma~\ref{QRamsey} for the
triple~$(C^\ell,H,K^2)$ to the $3$-edge-coloured complete graph~$K^k$.
For later convenience, for all~$i\neq j$ ($i$, $j\in[k]$), let us
colour the edges of~$G$ that join the classes~$V_i$ and~$V_j$ with the
colour used to colour the edge~$ij\in E(K^k)$.  Note that we now have
two colours associated to each edge of~$G$.

Suppose first that there is a monochromatic copy of~$C^\ell$ of
colour~$1$ in our~$K^k$.  Let~$\bfV=(V_1,\ldots,V_\ell)$ be the~$\ell$
vertex classes corresponding to this copy of~$C^\ell$ and let~$F$ be
the $\bfV$-graph on~$\bigcup_{i=1}^\ell V_i$ containing the $J$-edges
between consecutive classes. By property~(\textit{c}) we have that~$F$
contains a~$C^\ell$, and we are home.

We now observe that our~$K^k$ must contain fewer
than~$\epsilon{k\choose2}\leq2c{k\choose2}<ck^2$ edges coloured with
colour~$3$, since the partition~$\Pi$ is $(\epsilon,J,\pO)$-regular.
Therefore, we know by Lemma~\ref{QRamsey} that we may find at
least~$ck^h$ monochromatic copies of~$H$ of colour~$2$ in our~$K^k$.
We shall see in the sequel that this leads us to a contradiction, and
the proof of Claim~\ref{cl:GincGgood} will be finished.

Observe first that~$m\geq n/2k\geq n/\log n$ if~$n$ is large enough.
In what follows, we may and shall assume that~$m\geq n/\log n$.
Therefore we may deduce from property~(\textit{b}) above that each
$H$-subgraph of~$K^k$ of colour~$2$ determines at
least~$m^hp^{e(H)}/2$ isolated copies of~$H$ in~$G$.  Clearly,
distinct copies of~$H$ in~$K^k$ determine distinct isolated copies
of~$H$ in~$G$.  We may thus conclude that~$G$ contains at least
\[
  {1\over2}ck^hm^hp^{e(H)}\geq{1\over2}ck^h\(\frac{n}{2k}\)^hp^{e(H)}
     \geq c2^{-h-1}B^{e(H)}n^{1+1/(\ell-1)}
\]
isolated copies of~$H$, all edges of which are coloured with colour~$2$. 
Hence the number~$T'$ of edges of~$J$ that are coloured~$2$ satisfies 
\begin{equation}
  \label{J-edges-lower-bd}
  T'\geq c2^{-h-1}B^{e(H)}n^{1+1/(\ell-1)}.
\end{equation}
However, we also have an upper bound for~$T'$, coming from the fact that this
quantity counts only edges of~$G$ that are coloured~$2$.  Let us
write~$\sum_{ij}^2$ for the sum over all edges~$ij$ of~$K^k$ that are
coloured~$2$.  Then, by the definition of the colouring of~$K^k$,
by~(\ref{tilde-p-asymp}), and using that~$m\leq n/k$, we may conclude that
\[  
  T'\leq\sum\nolimits_{ij}^2\dJpO(V_i,V_j)\pO m^2 
     <{k\choose 2} \gamma_0 \pO m^2
     \leq\gamma_0e(H)B^{e(H)}n^{1+1/(\ell-1)},
\]
which, together with the definition of~$\gamma_0$ given
in~(\ref{def-gamma-0}), contradicts~(\ref{J-edges-lower-bd}). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%We now argue that~$F$ belongs
%to~$\cF=\cF_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$, where, naturally,
%$\bfV=(V_i)_{1\leq i\leq\ell}$ and~$\bT=e(F)$.  Conditions~(\textit{i})
%and~(\textit{ii}) in the definition of~$\cF$ are clearly satisfied.  The lower
%bound in~(\ref{bounded-gammas}) in condition~(\textit{iii}) follows from the
%definition of the colouring of~$K^k$, and the upper bound
%in~(\ref{bounded-gammas}) follows from the $(\eta,D,\pO)$-upper-uniformity
%of~$J$.  Condition~(\textit{iv}) in the definition of~$\cF$ follows from
%property~(\textit{a}) satisfied by~$G$: it suffices to see that~$F$ is locally
%$(\pO,C,\ell)$-upper-uniform since~$\tH$ is.  We have thus checked
%that, %indeed, 
%we have~$F\in\cF$.  Now, it follows from property~(\textit{c}) above
%that~$F$ must contain a~$C^\ell$, as otherwise~$F$ would belong
%to~$\cF'_m(\epsilon,\bB,\gamma_0,C,D;\bfV,\bT)$, contradicting that
%property.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This finishes the proof of Claim~\ref{cl:GincGgood}, and hence the proof of
Theorem~\ref{MainThm-1} is complete.  
\endproof

\subsection{Sketch of the proof of Theorem~\ref{Gen1State}} 
\label{sec:the-proof-gen}

In this section we describe the alterations in the proof of
Theorem~\ref{MainThm-1} that yield a proof of Theorem~\ref{Gen1State}.
We start by defining a new class~$\cG'$ of graphs to replace~$\cG$
from the proof of Theorem~\ref{MainThm-1}.  In what follows, ({\it
a\/}), ({\it b\/}), and~({\it c\/}) refer to conditions~({\it a\/}),
({\it b\/}), and~({\it c\/}) in the definition of the class~$\cG$.

Let us write~($b'$) for the statement we obtain from~({\it b\/})
by replacing the constant~$1/2$ in~({\it b\/}) by~$1/3$.  Moreover, to
stress the length of the cycle that is involved in statement~({\it
c\/}), let us write~($c_\ell$) for that condition.

The $n$-vertex graphs that we put in the new class~$\cG'$ are the ones
that satisfy~({\it a\/}), ($b'$)
and~$(c_{\ell_2})\wedge\cdots\wedge(c_{\ell_r})$.  We now consider the
following two claims.

\begin{cl} \label{cl:GpincG2}
  There is a constant~$\kappa>0$ such that almost every~$G_p$ has the
  property that, however we delete~$\leq\kappa
  n^{1+1/(\ell_2-1)}/(\log n)^{|H|}$
  edges from~$G_p$, we obtain a subgraph~$G'$ of~$G_p$ that belongs 
  to~$\cG'$.  
\end{cl}

\begin{cl} \label{cl:GincGgood2}
  Every member~$G'$ of~$\cG'$
  satisfies~$G'\to(H,C^{\ell_2},\ldots,C^{\ell_r})$ provided~$n$ is
  large enough. 
\end{cl}

\proofof Claim~\ref{cl:GpincG2}. (Sketch)~Condition~({\it a\/}) holds
for any subgraph of~$G_p$ almost surely.  Condition~($b'$) may be made
to hold almost surely by choosing~$\kappa>0$ sufficiently small.  We
now consider condition~$(c_{\ell_2})\wedge\cdots\wedge(c_{\ell_r})$.
Let~$q\geq\ell_2$ be be a fixed integer.  We argue that~($c_q$) holds
for every subgraph~$G'$ of~$G_p$ as in the statement of our claim 
almost surely.  Let~$p'=p'(n)=B_qn^{-\beta_q}$, where~$B_q=B_{q,H}$ is
as given in~(\ref{def-B}) and~$\beta_q=\beta(C^q,H)$.  We already know
that~($c_q$) holds for almost every~$G_{p'}$.  Notice that, since we
are now talking about a random graph of different edge-probability,
the value of~$p_0$ in~($c_q$) is different from the value of~$p_0$
in~($c_\ell$).  

Suppose for a contradiction that~($c_q$) does not hold almost surely
for every subgraph~$G'$ of~$G_p$ as specified.  We may generate the
random graph~$G_{p'}$ by first generating~$G_p$, and then randomly
deleting edges from~$G_p$ with probability~$1-p'/p$.  It is then easy
to check that our hypothesis on~($c_q$) failing for~$G_p$ implies
that~($c_q$) does not hold almost surely for~$G_{p'}$, which is a
contradiction.  The interested reader may find the missing details in
the proof of a closely related statement proved in~\cite{KLR2} (see
Lemma~19 in~\cite{KLR2}).  
\endproof

\proofof Claim~\ref{cl:GincGgood2}. (Sketch)~Following the proof of
Claim~\ref{cl:GincGgood}, we define graphs~$J_i$ ($2\leq i\leq r$) in
a similar way: each isolated copy of~$H$ in~$G_p$ contains an edge of
colour~$i$ for some~$2\leq i\leq r$.  Use these edges to define the
graphs~$J_i$.  Now apply Lemma~\ref{SSz} simultaneously to all
the~$J_i$ to obtain a partition~$(V_j)_{j=0}^k$ of~$V(G_p)$ that is
$\epsilon$-regular with respect to all the~$J_i$ ($2\leq i\leq r$).  

We now encode the regularity/non-regularity and density of the
pairs~$(V_a,V_b)$ with respect to~$J_i$ in an edge-coloured complete
graph~$K^k$.  If a pair~$(V_a,V_b)$ is not $\epsilon$-regular with
respect to some~$J_i$, we colour the edge~$ab$ of~$K^k$ colour~$r+1$
right away.  Otherwise, if~$(V_a,V_b)$ is a `dense' pair with respect
to~$J_i$, for some~$2\leq i\leq r$, we colour $ab\in E(K^k)$
colour~$i$.  The remaining edges we colour with colour~$1$.  We then
apply Lemma~\ref{QRamsey} to the $(r+1)$-tuple of
graphs~$(H,C^{\ell_2},\ldots,C^{\ell_r},K^2)$.

As in the proof of Theorem~\ref{MainThm-1}, if we find in our
edge-coloured~$K^k$ a monochromatic cycle~$C^{\ell_i}$ of colour~$i$,
for some~$2\leq i\leq r$, then we are done by invoking
statement~($c_{\ell_i}$).  The possibility that we shall find many
edges of~$K^k$ coloured with colour~$r+1$ is ruled by the
$\epsilon$-regularity of our partition~$(V_j)_{j=0}^k$ (here we need
that~$\epsilon$ is small enough).  Finally, the possibility that we
shall find many monochromatic copies of~$H$ of colour~$1$ may be ruled
out as in the proof of Claim~\ref{cl:GincGgood} (here we need
that~$\gamma_0$ should be small enough).  We omit the details.
\endproof

Theorem~\ref{Gen1State} is immediate from Claims~\ref{cl:GpincG2}
and~\ref{cl:GincGgood2}.

\vfill\eject

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of the 0-statement}
\label{sec:proofof0}

\proofof Theorem~\ref{thm:0-statement}.  Since the case~$\ell=k$ is
contained in Theorem~\ref{thm:RR}, we assume in the sequel that
$\ell>k$.  Similarly to~\cite{Kr} and~\cite{RR1}, given a graph~$G$,
we define a hypergraph~$\cG=\cG(G)$ whose hyperedges correspond to
the~$\ell$- and $k$-cycles of~$G$.  Let
\begin{eqnarray*}
  &\cE_1=\cE_1(G)=\{E(C)\:C\mbox{ is an $\ell$-cycle in }G\},\\
  &\cE_2=\cE_2(G)=\{E(C)\:C\mbox{ is a     $k$-cycle in }G\}.
\end{eqnarray*}
We put~$\cG=\cG(G)=\cE_1\cup\cE_2$.  We refer to the hyperedges
in~$\cE_i$ as hyperedges of \textit{type~$i$} ($i\in\{1,2\}$).

If~$\cH$ is a subhypergraph of~$\cG=\cG(G)$, that is,
if~$\cH\subseteq\cG$, then we define the \textit{underlying
graph}~$G(\cH)$ of~$\cH$ to be the subgraph of~$G$ spanned
by~$\bigcup\cH$.  In other words, $G(\cH)=G[\bigcup\cH]$.  Moreover,
if~$E\in\cG$, then we write~$V(E)$ for~$V(G(E))$, the set of vertices
of~$G$ incident to the edges in~$E$.  We now notice
that~$G\to(C^\ell,C^k)$ simply means that
\begin{enumerate}
\item[(*)]\textsl{for every colouring of the hypervertices of~$\cG$
  with two colours, blue and red, say, there is either a blue
  hyperedge of type~1 or a red hyperedge of type~2.}
\end{enumerate}

\noindent
A subhypergraph~$\cG_0\subseteq\cG$ of~$\cG$ is said to be
\textit{critical} with respect to property~(*) if~$\cG_0$ fulfils~(*)
but if we remove any hyperedge of any type from~$\cG_0$ then the
resulting hypergraph fails to have~(*).  The following very simple but
useful claim is similar to Claim~1 in the proof of Theorem~2(a)
in~\cite{Kr}.

\begin{ecl}
\label{ecl1}
  If~$\cG_0$ is critical with respect to~{\rm(*)} then for any
  hyperedge~$E$ of type~$i$ $(i\in \{1,2\})$ and any hypervertex~$e\in
  E$ there exists a hyperedge~$F$ of type~$3-i$ such that~$E\cap
  F=\{e\}$.
\end{ecl}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%We shall say that the hyperedge~$F$ in Claim~\ref{ecl1} above is a
%\textit{hyperedge corresponding} to the pair~$(E,e)$.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We now need to define some constants. Set
\begin{equation}
  \label{edefalpha}
  \alpha=k-2-\beta(k-1)=\frac{k-\ell}{k(\ell-1)}.
\end{equation}
Observe that
\begin{equation}
  \label{eindalpha}
  -1<\alpha<0.
\end{equation}
Furthermore, let
\begin{equation}
  \label{edefdelta}
  \delta=\min\left\{-\alpha,\frac1{\ell-1},1-\beta\right\}, 
\end{equation}
and notice that then~$0<\delta<1+\alpha$.  Indeed, the first
inequality follows from the definition of~$\beta$
and~(\ref{eindalpha}), and the second follows from~$1-\beta<1+\alpha$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{equation}
%\label{edefalpha}
%\alpha \quad :=\quad k-2 -\beta(k-1)\quad =\quad
% \frac{k -\ell}{k(\ell-1)}.
%\end{equation}
%Observe that
%\begin{equation}
%\label{eindalpha}
%-1\quad<\quad\alpha\quad<\quad0
%\end{equation}
%Furthermore define 
%\begin{equation}
%\label{edefdelta}
%\delta\quad :=\quad\min\{-\alpha,1+\alpha,\frac{1}{\ell+1}, 1-\beta\}.
%\end{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Now assume that~$G$ is a graph and that~$\cG_0\subseteq\cG(G)$ is
critical with respect to~(*).  As in~\cite{Kr}, we will use
Claim~\ref{ecl1} in order to look for a subhypergraph~$\cH$ of~$\cG_0$
whose underlying graph~$G(\cH)$ is dense.

We shall give a procedure, Procedure \Hypertree, that will build a
subhypergraph of~$\cG_0$ that may contain some hypercycles, but will
generally have a `hypertree structure'.  Any hypergraph that may be
produced by this procedure will be said to be an \textit{alternating
hypertree}.  The key observation concerning hypertrees is that
{\it the number of those alternating hypertrees whose underlying graph
is not dense is small.\/}

Let us now describe Procedure \Hypertree.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule
\vspace{3pt}
\begin{tabbing}
{\bf Procedure} {\Hypertree}\\ 
{\bf Input:}\qquad\=\it a hypergraph~$\cG_0=\cE_1\cup\cE_2$ critical 
                    with respect to~{\rm(*)}\\
{\bf Output:}    \>\it a triple~$(m,\cH_m,I_m)$ 
                    where~$\cH_m=\{E_0,\ldots,E_m\}\subseteq\cG_0$\\
                 \>and~$I_m\subseteq[m]\times\{1,2\}$\\
\lan{\it main body\/}\ran
\end{tabbing}
\hbox to\hsize{\hfill}\vspace{-\baselineskip}
\vspace{-4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Thus, the input to Procedure {\Hypertree} is a subhypergraph~$\cG_0$
of~$\cG(G)$, for some graph~$G$, with~$\cG_0$ critical with respect
to~(*).  Its output is a triple~$(m,\cH_m,I_m)$, where~$m$ is an
integer, $\cH_m=\{E_0,\ldots,E_m\}$ is a subhypergraph of~$\cG_0$,
and~$I_m\subseteq[m]\times\{1,2\}$ is a certain set indicating the
\textit{degeneracies} present in~$\cH_m$.  Loosely speaking, the
set~$I_m$ says how far~$\cH_m$ is from being a `genuine' hypertree.

Below we shall show that (\dag)~{\it either the set~$I_m$ is large and
hence the underlying graph of~$\cH_m$ is dense, or else~$I_m$ is small
and the number of alternating hypertrees with such a small set of
degeneracies is small.\/} As an illustration, we mention that
if~$\cH_m$ has no degeneracies at all, then~$\cH_m$ is uniquely
determined up to isomorphism, as is the underlying graph~$G(\cH_m)$
of~$\cH_m$, regardless of the input hypergraph~$\cG_0$.
Assertion~(\dag) above will imply that~$G_p$,
with~$p=p(n)=bn^{-\beta}$ and sufficiently small~$b$, almost surely
does not contain a copy of the underlying graph of any alternating
hypertree.  This assertion will establish
Theorem~\ref{thm:0-statement}.

The main body of Procedure {\Hypertree} is given in
Figure~\ref{fig:mainbody}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule
\vspace{3pt}
\begin{tabbing}
\lan \it main body$\rangle\equiv{}$%
\={\bf begin} \=$i:=0$; {\it pick~$E_0\in\cE_2$ arbitrarily\/}; 
              $\cH_0:=\{E_0\}$;\\ 
\>          \>\llap{(1)~}{\it rank and direct the edges in~$E_0$};\\ 
\>          \>$I_0:=\emptyset$; $A_0:=\emptyset$;\\
\>          \>{\bf repeat} \lan\it extend current hypertree\ran\\
\>          \>{\bf until} $|G(\cH_i)|-\beta e(G(\cH_i))\leq-1/500$
                          {\it or} $i\geq \log n$\\
\>{\bf end}
\end{tabbing}
\vspace{-7pt}
\hrule
\vspace{-4pt}
\caption{Main body of Procedure \Hypertree}
\label{fig:mainbody}
\vspace{4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Thus, Procedure {\Hypertree} starts by setting up a
hypergraph~$\cH_0=\{E_0\}$ containing a single hyperedge that
corresponds to a $k$-cycle of~$G$, and then goes into an iterative
process.  Before we go on to detail this iterative procedure, we need
to explain what is meant in line~(1) in \lan{\it main body\/}\ran.
The hypervertices of the hypertree will be ranked with ranks starting
from~$1$.  Every time we add a new hypervertex to our hypertree, it
gets a rank that is by one larger than that of its predecessor.  As
the hyperedges correspond to cycles in~$G$, we can first direct the
edges of a new hyperedge in a cyclic order and then rank the edges
following the same order.  For simplicity, we shall not make this
directing and ranking procedure explict.

We now turn to the iterative procedure.  This process will create
sequences~$\cH_0\subseteq\cH_1\subseteq\cdots$ and~$I_0\subseteq
I_1\subseteq\cdots$ that will eventually produce the desired
output~$(m,\cH_m,I_m)$.  For all~$0\leq i\leq m$, we shall
have~$\cH_i=\{E_0,\ldots,E_i\}$ and~$I_i\subseteq[i]\times\{1,2\}$.
In the $i$th iteration we add the hyperedge~$E_i$ to~$\cH_{i-1}$ and
we \textit{may} add one of the pairs~$(i,1)$ or~$(i,2)$ to~$I_{i-1}$.
The latter addition to the set of degeneracies happens if~$E_i$
intersects~$\cH_{i-1}$ `substantially'.  The procedure will also need
to construct a sequence~$A_0,A_1,\ldots$ of sets of edges,
with~$A_i\subseteq\bigcup\cH_i$ for all~$0\leq i\leq m$.  The edges
in~$A_i$ are said to be the \textit{assets} of~$\cH_i$. 

The general iterative step is as follows.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule 
\vspace{3pt}
\begin{tabbing}
\lan\it extend current hypertree$\rangle\equiv$\\
\quad\={\bf if} \={\it there is~$F\in\cE_2$ such that 
                       $F\not\subseteq\bigcup\cH_i$ and 
                       $|V(F)\cap V(G(\cH_i))|\geq2$}\\
\>       \>{\bf then} \=\lan{\it add~$F$ to~$\cH_i$}\ran\\
\>       \>{\bf else} \>\lan{\it look for and add 
                               a type~1 hyperedge to~$\cH_i$}\ran
\end{tabbing}
\hbox to\hsize{\hfill}\vspace{-\baselineskip}
\vspace{-4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
When we try to extend our current hypertree~$\cH_i$, if it so happens
that there is a type~2 hyperedge~$F$ `for free' (that is, as specified
in the \textbf{if} condition of \lan{\it extend current
hypertree\/}\ran), then we take it and add it to~$\cH_i$.  The idea
here is that this addition will increase the density of the underlying
graph of the current hypertree.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule 
\vspace{3pt}
\begin{tabbing}
\lan\it add~$F$ to~$\cH_i\rangle\equiv{}$%
\=$i:=i+1$; $E_i:=F$; $\cH_i:=\cH_{i-1}\cup\{E_i\}$;\\
\>   {\it rank and direct the edges 
            in~$E_i\setminus\bigcup\cH_{i-1}$\/};\\
\>   $I_i:=I_{i-1}\cup\{(i,1)\}$; $A_i:=\emptyset$
\end{tabbing}
\hbox to\hsize{\hfill}\vspace{-\baselineskip}
\vspace{-4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

If such a `free' type~2 hyperedge~$F$ does not exist, then we have to
do some more work, which we describe in two stages:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule
\vspace{5pt}
\lan{\it look for and add a type~1 hyperedge to~$\cH_i$}\ran
${}\equiv{}$\lan{\it stage~I\/}\ran; \lan{\it stage~II\/}\ran
\vspace{4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In \lan{\it stage I\/}\ran\ we look for and add a type~1 hyperedge to
our current hypertree~$\cH_i$.  This will, unfortunately, decrease the
density of the current underlying graph.  Therefore, in \lan{\it
stage~II\/}\ran, we try to add as many type~2 hyperedges to our
hypertree as possible; these hyperedges all `hang' on hypervertices
that were added to the hypertree by the addition of the type~1
hyperedge.  These hypervertices are the `assets' that we acquired with
the addition of the type~1 hyperedge.  One may think of the process of
adding type~2 hyperedges in {\lan{\it stage~II\/}\ran} as a process of
turning these assets into `cash' (\textit{i.e.}, density).
See Figures~\ref{fig:stageI} and~\ref{fig:stageII}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule
\vspace{3pt}
\begin{tabbing}
\lan\it stage~I\/$\rangle\equiv{}$%
\={\it let~$f$ be the edge of smallest rank in~$\bigcup\cH_i$}\\
\>\qquad\={\it for which there is a hyperedge~$E\in\cE_1$ 
               with~$E\not\subseteq\bigcup\cH_i$};\\
\>      \>$\{$NB.~The existence of the edge~$f$ above is proved in
                  Claim~\ref{ecl5}.$\}$\\
\>    $i:=i+1$;\\
\>    {\it pick~$E_i\in\cE_1$ with~$E_i\not\subseteq\bigcup\cH_i$
           and~$f\in E_i$};\\ 
\>    $\cH_i:=\cH_{i-1}\cup\{E_i\}$;\\
\>    {\it rank the edges in~$E_i\setminus\bigcup\cH_{i-1}$ 
         following the cyclic order of~$E_i=C^\ell$}\\
\>\>     {\it given by the orientation of~$f$, starting from the
              successor of~$f$\/};\\
\>\>     {\it suppose these edges are, in increasing order of rank,
              $g_1,\ldots,g_a$\/};\\ 
\>  {\bf if} $|V(E_i)\cap V(G(\cH_{i-1}))|=2$ 
             \={\bf then} \=$I_i:=I_{i-1}$
               {\bf else} $I_i:=I_{i-1}\cup\{(i,2)\}$;\\
\>\llap{(1)~}$A_i:=\{g_1,\ldots,g_a\}$; \quad
    $\{$NB.~$|A_{i-1}|=0$ and
            $a=|A_i|=\ell-1$ if~$(i,2)\notin I_i\}$
\end{tabbing}
\vspace{-7pt}
\hrule
\vspace{-4pt}
\caption{Adding a type~1 hyperedge}
\label{fig:stageI}
\vspace{4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule
\vspace{3pt}
\begin{tabbing}
\lan\it stage~II\/$\rangle\equiv{}$%
\=$F:=E_i$; 
  \quad$\{$NB.~This is the $\ell$-cycle we have just added$\}$\\
\>{\bf for} \=$j:=1$ {\bf to} $a$ {\bf do}\\
\>  \>{\bf if} \=$g_j\in A_i$ {\bf then begin}\\
\>  \>    \>$i:=i+1$; 
          {\it pick~$E_i\in\cE_2$ with~$E_i\cap F=\{g_j\}$\/};\\
\>  \>    \>$\cH_i:=\cH_{i-1}\cup\{E_i\}$;\\
\>\>      \>{\it rank and direct the edges 
               in~$E_i\setminus\bigcup\cH_{i-1}$ following\/}\\
\>  \>    \>\quad\={\it the cyclic order of~$E_i=C^k$ given by the
      orientation of~$g_j$,\/}\\
\>  \>    \>     \>{\it starting from the successor of~$g_j$\/};\\  
\>  \>    \>{\bf if} \=$|V(E_i)\cap V(G(\cH_{i-1}))|=2$\\
\>  \>    \>         \>{\bf then} \={\bf begin} \=$I_i:=I_{i-1}$;
                                  $A_i:=A_{i-1}\setminus\{g_j\}$
                       {\bf end}\\
\>  \>    \>         \>{\bf else} \>{\bf begin} 
                                       $I_i:=I_{i-1}\cup\{(i,2)\}$;
                                       {\lan{\it compute~$A_i$}\ran} 
                                    {\bf end}\\
\>  \>    \>{\bf end}
\end{tabbing}
\vspace{-7pt}
\hrule
\vspace{-4pt}
\caption{Adding as many type~2 hyperedges as possible}
\label{fig:stageII}
\vspace{4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In \lan{\it stage~II\/}\ran, the computation of~$A_i$ requires a
little care.  Roughly speaking, if a $k$-cycle~$E_i$ we add in
\lan{\it stage~II\/}\ran\ contains a vertex~$w$ added to the
underlying graph of the current hypertree by the addition of the
$\ell$-cycle in \lan{\it stage~I\/}\ran, then we have to consider an
asset~$g\in A_{i-1}$ incident to~$w$ no longer an asset.  In this case
we say that~$g$ was \textit{spoiled} by~$E_i$.  See
Figure~\ref{fig:computeAi}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[here]
\hrule
\vspace{3pt}
\begin{tabbing}
\lan\it compute~$A_i\rangle\equiv{}$%
\=$A_i':=A_{i-1}\setminus\{g_j\}$;\\
\>{\bf for} \=$p:=j+1$ {\bf to} $a$ {\bf do}\\
\>  \>{\bf if} \={\it the head~$w_p$ of $g_p$ belongs to~$V(E_i)$} 
                  {\bf then} $A_i':=A_i'\setminus\{g_p\}$;\\
\>  \>$\{$NB.~In this case we say that~$E_i$ \textit{spoiled}~$g_p\}$\\ 
\>$A_i:=A_i'$
\end{tabbing}
\vspace{-7pt}
\hrule
\vspace{-4pt}
\caption{Computing~$A_i$}
\label{fig:computeAi}
\vspace{4pt}
\hrule
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The integer~$m=|\cH_m|-1\leq\log n$ returned by Procedure {\Hypertree}
is the \textit{length} of~$\cH_m$.  Our alternating hypertree~$\cH_m$
is said to be \textit{degenerate} at level~$i$ if~$(i,1)$ or~$(i,2)\in
I_m$.

Let~$f(i)=|G(\cH_i)|-\beta e(G(\cH_i))=|G(\cH_i)|-
\beta\big|\bigcup\cH_i\big|$.  Then, for~$p=p(n)=n^{-\beta}$, the
expected number of copies of~$G(\cH_i)$ in~$G_p$ is~$O(n^{f(i)})$.
In the series of claims given below, we investigate the effect of the
degeneracies on the behaviour of the function~$f$.

For brevity, let~$a_i=|A_i|$ ($0\leq i\leq m$).  In the sequel, it
will be important that~$\cH_i$ may have a non-zero number of assets
only from the point in which we have just added a type~1 hyperedge up
to the point in which we have cashed all available assets in the {\bf
for} loop in {\lan{\it stage~II\/}\ran}.  In other words, $a_i>0$ can
only occur between line~(1) in {\lan{\it stage~I\/}\ran} and the end
of {\lan{\it stage~II\/}\ran}.  In particular, $a_0=a_m=0$.

\begin{ecl}\label{ecl2}
  For all~$1\leq i\leq m$, if $(i,1)$, $(i,2)\not\in I_i$ then
  $f(i)+\alpha a_i=f(i-1)+\alpha a_{i-1}$.  
\end{ecl}
\proof Consider first the case in which~$E_i$ is of type~1.
Then~$a_{i-1}=0$ and moreover~$a_i=\ell-1$, since~$(i,2)\notin I_i$
(cf.~the remark in line~(1) of \lan{\it stage~I\/}\ran).
Therefore~$E_i$ contributes exactly~$\ell-2$ new vertices and
exaclty~$\ell-1$ new edges to~$\cH_{i-1}$. Hence,  
\begin{eqnarray*}
f(i)+\alpha a_i
  &=&f(i-1)+\ell-2-\beta(\ell-1)+(k-2-\beta(k-1))(\ell-1) \\
  &=&f(i-1)+(k-1)(\ell-1)-1-\beta k(\ell-1)\\
  &=&f(i-1)+\alpha a_{i-1}.
\end{eqnarray*}
If~$E_i$ is of type~2 then~$a_i=a_{i-1}-1$ and
\begin{eqnarray*}
f(i)+\alpha a_i
  &=&f(i-1)+(k-2)-\beta(k-1)+\alpha(a_{i-1}-1)\\
  &=&f(i-1)+\alpha a_{i-1},
\end{eqnarray*}
as required.
\endproofnosquare

\begin{ecl}\label{ecl3}
  For all~$1\leq i\leq m$, if~$(i,1)\in I_i$ then $f(i)+\alpha a_i\leq 
  f(i-1)+\alpha a_{i-1}-\delta$.  
\end{ecl}
\proof Let~$H\subseteq C^k$ be the graph with vertex set~$V(E_i)\cap
V(G(\cH_{i-1}))$ and edge set~$E_i\cap\bigcup\cH_{i-1}$, that is,
$H$ is the \textit{intersection} of~$(V(E_i),E_i)$ and~$G(\cH_{i-1})$. 
Clearly, $H$ is a disjoint union of paths.  Moreover, $G(\cH_i)$
has~$k-|H|$ new vertices and~$k-e(H)$ new edges.  Therefore,
by~$|H|\ge e(H)+1$, $|H|\ge 2$, and~$\beta\le1$, and  
by the definitions of $\alpha$ and $\delta$ (cf.~(\ref{edefalpha})
and~(\ref{edefdelta})), we have
\begin{eqnarray*}
f(i)&=&f(i-1)+k-|H|-\beta(k-e(H))\\
    &\le&f(i-1)+k-2-\beta(k-1)\\
    &\le&f(i-1)-\delta,
\end{eqnarray*}
which implies the claim, since $a_{i-1}=a_i=0$. 
\endproofnosquare

\begin{ecl} \label{ecl4}
  For all~$1\leq i\leq m$, if~$(i,2)\in I_i$ then $f(i)+\alpha
  a_i\leq f(i-1)+\alpha a_{i-1}-\delta$.  
\end{ecl}
\proof Consider first the case in which~$E_i$ is of type~1.
Let~$H\subseteq C^\ell$ be the intersection of the two
graphs~$(V(E_i),E_i)$ and~$G(\cH_{i-1})$.  Then $a_i=\ell-e(H)$ 
and 
\begin{eqnarray}
\nonumber f(i)+\alpha a_i
  &=&f(i-1)+\ell-|H|-\beta(\ell-e(H))+\alpha(\ell-e(H))\\
\nonumber  &=&f(i-1)+(\ell-e(H))(k-1-k\beta)+e(H)-|H|\\
\label{in-f-i}  &=&f(i-1)+\frac{\ell-e(H)}{\ell-1}+e(H)-|H|.
  \end{eqnarray}
If~$e(H)\geq2$ then we conclude from~$|H|\ge e(H)+1$ that 
$(\ell-e(H))/(\ell-1)+e(H)-|H|\le -1/(\ell-1)\le-\delta$
(cf.~(\ref{edefdelta})). If~$e(H)=1$ then~$|H|\ge3$ and thus
$(\ell-e(H))/(\ell-1)+e(H)-|H|\le-\delta$. 
Because of~$a_{i-1}=0$ we have that~(\ref{in-f-i}) is in both cases 
at most $f(i-1)+\alpha a_{i-1}-\delta$.

Let now~$E_i$ be of type~2 and let~$H\subseteq C^k$ be the
intersection of the two graphs~$(V(E_i),E_i)$ and~$G(\cH_{i-1})$.  We
first deduce from the fact that~$g_j$ is an asset before we add~$E_i$,
that is, $g_j\in A_{i-1}$, that~$H\not=C^k$.  Indeed, let~$E_{i'}$ be
the hyperedge of type~1 that~$E_i$ is attached to; \textit{i.e.},
$E_i\cap E_{i'} =\{g_j\}$.  Because of the {\bf if} condition in
\lan{\it extend current hypertree\/}\ran, the hyperedge~$E_i$ is
disjoint from~$\bigcup\cH_{i'-1}$.  Let~$w$ be the head of~$g_j$.
Then if~$E_i\subseteq\bigcup\cH_{i-1}$, the vertex~$w$ must be
incident to some edge in~$\bigcup\cH_{i-1}\setminus\bigcup\cH_{i'}$.
This means that~$g_j$ was spoiled before, \textit{i.e.}, $g_j\notin
A_{i-1}$, which is a contradiction.  Hence~$H\not=C^k$.

Let~$b$ be such that~$a_i=a_{i-1}-b$.  Observe that~$b\ge1$.  If~$E_i$
spoils an edge~$g_h$ then the head~$w_h$ of $g_h$ is isolated in~$H$.
Indeed, $E_i$ contains no edge from~$\bigcup\cH_{i'-1}$, no edge
from~$E_{i'}$ incident to~$w_h$, and, since~$g_h$ has not been spoiled
before, $w_h$~is incident to no edge in~$\bigcup
\cH_{i-1}\setminus\bigcup\cH_{i'}$. Therefore, there does not exist
any edge in~$E_i\cap\bigcup\cH_{i-1}$ incident to~$w_h$.  Hence~$w_h$
is indeed isolated in~$H$.  Setting $J:=
H\setminus\{w_f\:g_f\,\mbox{is spoiled by}\,E_i\}$ we get
that~$|H|=|J|+b-1$.  Moreover,
\begin{eqnarray*} 
\lefteqn{f(i)+\alpha a_i}\quad && \\ 
  &=&f(i-1)+k-|J|-(b-1)-\beta(k-e(J))+\alpha(a_{i-1}-b)\\
  &=&f(i-1)+\alpha a_{i-1}-(b-1)(\alpha+1)
                    +k-|J|-\beta(k-e(J))-\alpha\\ 
  &\le&f(i-1)+\alpha a_{i-1}-(b-1)(\alpha+1)
                    +(e(J)-|J|+1)+(e(J)-1)(\beta-1).
\end{eqnarray*}
The three last terms are non-positive. If $b\ge 2$ then the first
term is smaller than  $-\delta$ because of $\delta <1+\alpha$. If $b=1$
then $J$ is a proper subgraph of $E_i=C^k$ with $J \not=K^2$ and therefore
either $e(J)>1$ or $|J|>e(J)+1=2$ implying that one of the two
last terms is smaller or equal than $-\delta$, and the claim is proven. 

\endproofnosquare

\begin{ecl}
\label{ecl5}
  The edge~$f$ as specified in~\lan{\it stage~I\/}\ran\ always exists. 
\end{ecl}
\proof Assume that Procedure {\Hypertree} gets stuck at the beginning
of {\lan{\it stage~I\/}\ran} at iteration~$i$ because the edge~$f$ as
specified does not exist.  Our aim is to reach a contradiction. 

Let~$G_i=G(\cH_i)$ be the underlying graph of~$\cH_i$, so that~$G_i$
is spanned by its edge set~$E(G_i)=\bigcup\cH_i$.  We start with the
following assertion.

\begin{enumerate}
\item[(**)]\textsl{For both~$q\in\{1,2\}$, if~$e\in E\subseteq E(G_i)$
and~$E\in\cE_q$, then there exists a hyperedge~$F\in\cE_{3-q}$ such
that~$e\in F\subseteq E(G_i)$ and moreover~$E\cap F=\{e\}$.}
\end{enumerate}
\casebody
Let us prove assertion~(**).  Suppose first that~$q=1$.  Then
Claim~\ref{ecl1} gives a hyperedge~$F\in\cE_2$ with~$E\cap F=\{e\}$.
The {\bf if} condition in {\lan{\it extend current hypertree\/}\ran}
implies that~$F\subseteq\bigcup\cH_i=E(G_i)$, as required.  If~$q=2$,
then Claim~\ref{ecl1} gives~$F\in\cE_1$ with~$E\cap F=\{e\}$.  Since
we did not find an edge~$f$ as specified on the first line of
{\lan{\it stage~I\/}\ran}, we must
have~$F\subseteq\bigcup\cH_i=E(G_i)$.  Assertion~(**) is proved. 
\endcasebody

An immediate corollary to~(**) is the following assertion.

\begin{enumerate}
\item[(\ddag)]\textsl{Every edge~$e$ of~$G_i$ is contained in an
$\ell$-cycle~$C_1$ and in a $k$-cycle~$C_2$ with~$E(C_q)\in\cE_q$
$(q\in\{1,2\})$ and~$E(C_1)\cap E(C_2)=\{e\}$.}
\end{enumerate}

\noindent
In particular, we have the following observation.

\assertion({\it i\/}) The minimal degree of~$G_i$ is at least~$3$. 
\endassertion

Let us now consider the simpler case in which~$k\geq4$.  Because
of~$\ell>k$, it is easily seen
that~$\beta(C^\ell,C^k)\ge\beta(C^5,C^4)=11/16$.  On the other hand,
by~(\textit{i}), we have~$e(G_i)\ge(3/2)|G_i|$ and therefore in this
case we have 
\[
f(i)\;=\;|G_i|-\beta e(G_i)
    \;\le \;|G_i|\(1-\frac{3}{2}\times\frac{11}{16}\)
    \;\le\;-\frac{1}{500}.
\]
We have thus reached a contradiction, since this implies that
Procedure {\Hypertree} should have stopped with~$m=i$. 

We now turn to the case $k=3$.  We shall have to argue more carefully
here.  We introduce some notation in order to avoid repetition.
Suppose~$x_1$, $x_2$, and~$x_3$ are three vertices of~$G_i$.  We shall
write~$T(x_1,x_2,x_3)$ when these vertices induce a triangle in~$G_i$
and moreover~$\{x_1x_2,x_2x_3,x_1x_3\}\in\cE_2$.  Similarly,
if~$x_1,\ldots,x_\ell$ define, in this order, an $\ell$-cycle~$C^\ell$  
of~$G_i$ and furthermore~$E(C^\ell)\in\cE_1$, then we shall
write~$C(x_1,\ldots,x_\ell)$.  

Let~$A(x_1x_2,T(x_1,x_2,x_3))$ stand for the application of~(**) to
the edge~$x_1x_2$ and the type~2 hyperedge corresponding
to~$\{x_1,x_2,x_3\}$.  Thus~$A(x_1x_2,T(x_1,x_2,x_3))$ gives us the
existence of vertices~$y_3,\ldots,y_\ell\in
V(G_i)\setminus\{x_1,x_2\}$ with~$y_3\neq x_3\neq y_\ell$ and such
that $C(x_1,x_2,y_3,\ldots,y_\ell)$.  Similarly,
let~$A(x_1x_2,C(x_1,\ldots,x_\ell))$ stand for the corresponding
statement guaranteeing the existence of a vertex~$y_3\in
V(G_i)\setminus\{x_1,x_2,x_3,x_\ell\}$ with $T(x_1,x_2,y_3)$.  Now we
prove in a couple of steps that~$G_i$ has large density.

\assertion(\textit{ii}) A vertex of degree~$3$ in~$G_i$ is only
adjacent to vertices of degree at least~$4$.  
\endassertion
\casebody
To prove the assertion above, assume that there are two vertices of
degree~3, say, $x$ and $y$, that are adjacent in~$G_i$.  By~(\ddag), we
have a vertex~$z$ such that~$T(x,y,z)$.  We now argue as follows. 
\begin{list}{(iii)}{\itemsep-1mm}
%\begin{enumerate}
\item[({\it a\/})] $A(xy,T(x,y,z))$ gives~$2$ distinct vertices~$v$ 
and~$w\notin\{x,y,z\}$ with~$C(v,x,y,w,\ldots)$. 
\item[({\it b\/})] $A(yz,T(x,y,z))$ gives~$C(w,y,z,\ldots)$, 
since~$d(y)=3$.
\item[({\it c\/})] $A(wy,C(w,y,z,\ldots))$ gives~$T(w,y,x)$,
since~$d(x)=d(y)=3$.  
\end{list}
%\end{enumerate}
\noindent 
However, $T(w,y,x)$ implies that~$v=w$, which is a contradiction.
Assertion~({\it ii\/}) is proved. 
\endcasebody

\assertion(\textit{iii}) Every vertex of~$G_i$ has a neighbour of
degree at least~$4$. 
\endassertion
\casebody
Indeed, let~$x$ be a vertex of~$G_i$, and let~$y$ be a neighbour
of~$x$.  Then, by~(\ddag), there exists a vertex~$z$ with~$T(x,y,z)$. 
By~(\textit{ii}), either~$y$ or~$z$ has degree at least~4,
and~(\textit{iii}) is proven.  
\endcasebody

Consider first the case~$\ell\geq5$.  Denote by~$a$ and~$b$ the number
of vertices of degree exactly~$3$ and at least~$4$ in~$G_i$,
respectively.  Assertions~(\textit{ii}) and~(\textit{iii}) imply
that $\sum_{d(v)\ge 4}d(v)\ge3a+b$.  Therefore 
\[ 
\frac{2e(G_i)}{|G_i|}\ge\max\left\{\frac{3a+4b}{a+b},\frac{6a+b}{a+b}  
\right\} \ge \min_{x\ge 0} \max\{4-x,1+5x\} =\frac{7}{2}.
\]
Using $\beta(C^\ell,C^3)\ge\beta(C^5,C^3)=7/12$ we have that
$$
f(i)\;=\;|G_i|-\beta e(G_i)\;\le\;
|G_i|\(1-\frac{7}{12}\times\frac{7}{4}\)\; 
\leq\;-{1\over500}.
$$
 In the sequel we assume
that~$\ell=4$. 
\assertion(\textit{iv}) Every vertex of degree~$3$ in~$G_i$ has a
  neighbour of degree at least~$5$.  
\endassertion
\casebody
Assume to the contrary that there is a vertex~$v\in V(G_i)$ of
degree~$3$ with neighbours~$x$, $y$, and~$z$ all having degree~$4$.
Recalling~(\ddag), we may assume without loss of generality
that~$T(v,x,y)$ and~$T(v,y,z)$.  Now we argue as  
follows.
%\begin{enumerate}
\begin{list}{(iii)}{\itemsep-1mm}
\item[({\it a\/})] Since~$d(v)=3$, we have that~$A(vy,T(v,y,z))$ gives
a vertex~$w\in V(G_i)\setminus\{v,x,y,z\}$ such that~$C(w,x,v,y)$. 
\item[({\it b\/})] $A(vy,T(v,x,y))$ similarly gives a vertex~$w'\in 
V(G_i)\setminus\{v,x,y,z\}$ such that~$C(w',z,v,y)$.  However,
$d(y)=4$, and hence~$w=w'$.
\item[({\it c\/})] Since~$d(v)=3$, we have that~$A(vz,C(w,y,v,z))$
gives that~$T(v,z,x)$. 
\item[({\it d\/})] $A(yz,T(v,y,z))$ gives either~$C(y,z,x,w)$ or
else~$C(y,z,w,x)$. 
\end{list}
%\end{enumerate}
\noindent
We reach a contradiction analysing the two possibilities in~({\it
d\/}) separately.  If~$C(y,z,x,w)$, consider~$A(xw,C(y,z,x,w))$ to
get~$T(x,w,v)$.  But then~$vw\in E(G_i)$, contradicting~$d(v)$=3.  On
the other hand, if~$C(y,z,w,x)$, consider~$A(xw,C(x,y,z,w))$ to
deduce~$T(x,w,v)$ again.  Therefore assertion~({\it iv\/}) is proved.
\endcasebody

We now estimate the density of~$G_i$ from below.  Let~$a$ and~$b$
denote the number of vertices of degree~$3$ and~$4$ in~$G_i$,
respectively, and let~$c$ be the number of vertices of degree at
least~$5$.  By~(\textit{ii}) and~(\textit{iii}) we have that
$\sum_{d(v)\ge4} d(v)\ge3a+b+c$.  Assertions~(\textit{iii}) and
(\textit{iv}) imply that $\sum_{d(v)\ge5}d(v)\ge a+c$. Therefore we
have 
\[ 
\frac{2e(G_i)}{|G_i|}\quad\ge\quad \max\left\{\frac{3a+4b+5c}{a+b+c},
\frac{6a+b+c}{a+b+c},\frac{4a+4b+c}{a+b+c}\right\}.
\]
Setting $x=a/(a+b+c)$ and $y=c/(a+b+c)$, this implies
\[ 
\frac{2e(G_i)}{|G_i|}\quad\ge\quad \min_{x,y\ge0}
\max\{4-x+y,1+5x,4-3y\}\quad=\quad\frac{83}{23}, 
 \]
as one may easily check. Furthermore $\beta(C^4,C^3)=5/9$.  Thus 
\[
f(i)\;=\;|G_i|-\beta e(G_i)\;\le\; |G_i|\(1-\frac{83}{46}\times
\frac{5}{9}\)
\;\le\; -\frac{1}{500},\]
and Claim~\ref{ecl5} is proven.
\endproofnosquare

\begin{ecl}
\label{ecl6}
  Let $(m,\cH_m,I_m)$ be the output of Procedure~\Hypertree.
  Then the following assertions hold:
  \begin{enumerate}
  \item[{\rm({\it a\/})}] $f(m)\leq f(0)=1+1/(\ell-1)\leq3/2$,
  $m\leq\log n+\ell$, and
  \begin{equation}
  \label{eq:ineqIm}
  |I_m|\quad\le\quad M
     \quad:=\quad\ell+
       \left\lceil\frac{f(0)+1/500}{\delta}\right\rceil-1.
  \end{equation}
  \item[{\rm({\it b\/})\/}] Either {\rm({\it i\/})\/}~$m\geq\log n$ 
       or else {\rm({\it ii\/})}~$f(m)\leq-1/500$.
  \end{enumerate}
\end{ecl}
\proof ({\it a\/})~The inequality for~$f(m)$ follows easily from
Claims~\ref{ecl2}, \ref{ecl3}, and~\ref{ecl4}, and the fact
that~$a_0=a_m=0$. Suppose now that~$m\geq\log n$.  Then, letting~$i$
be the largest integer strictly smaller than~$\log n$, we see
that~$m\leq i+\ell<\log n+\ell$, as required.  To
see~(\ref{eq:ineqIm}), suppose for a contradiction that~$|I_m|\geq
M+1$.  This time let~$i$ be the maximal integer not greater than~$m$
for which~$a_i=0$.  Then~$m\leq i+\ell$, and
hence~$|I_i|=|I_m\cap([i]\times\{1,2\})|\geq
M+1-\ell\geq\lceil(f(0)+1/500)/\delta\rceil$.  Observing
that~$a_0=a_m=0$, we have, applying Claims~\ref{ecl2}, \ref{ecl3},
and~\ref{ecl4}, that
\[ 
f(i)\quad\le\quad f(0)
           -\delta\left\lceil\frac{f(0)+1/500}{\delta}\right\rceil
    \quad\le\quad -\frac{1}{500}.
\]
However, this shows that Procedure {\Hypertree} should have stopped
after the~$i$th iteration (see Figure~\ref{fig:mainbody}), which is a 
contradiction.

Assertion~({\it b\/}) follows trivially from the {\bf until} condition
in~\lan{\it main body\/}\ran.  This finishes the proof of
Claim~\ref{ecl6}.  
\endproofnosquare

The heart of the proof of Theorem~\ref{thm:0-statement} is
Claim~\ref{ecl8} below.  Loosely speaking, the idea is as follows.
If~$G_p\to(C^\ell,C^k)$, then~$\cG(G_p)$ contains a
subhypergraph~$\cG_0$ critical with respect to~(*).  We may then feed
this hypergraph~$\cG_0$ into Procedure~{\Hypertree}, and obtain a
hypertree~$\cH_m\subseteq\cG_0$ satisfying the conditions given in
Claim~\ref{ecl6}.  Using these conditions, we show in Claim~\ref{ecl8}
that a.e.~$G_p$ does not contain the underlying graph~$G(\cH_m)$
of~$\cH_m$ if~$p=p(n)=bn^{-\beta}$ and~$b$ is small enough.  However,
this is a contradiction, since clearly~$G(\cH_m)\subseteq G_p$.
We shall have thus proved Theorem~\ref{thm:0-statement}.

To detail the argument sketched above, we need to introduce some
definitions.  Fix a graph~$G$ on~$n$ vertices such
that~$G\to(C^\ell,C^k)$.  Consider all possible choices
for~$\cG_0\subseteq\cG(G)$, the (*)-critical subhypergraph
of~$\cG(G)$.  Recall that Procedure {\Hypertree} is a
non-deterministic procedure, and, for each~$\cG_0$ as above, consider
all sequences~$\cH_0\subseteq\cH_1\subseteq\cdots$ that may be
generated by Procedure {\Hypertree}.  Now, for each~$i\geq0$,
let~$\cF(i)$ be the set of all hypergraphs~$\cH_i$ that may be
obtained in the process described above, letting the graph~$G$ vary
over all graphs~$G'$ with vertex set~$[n]$ and
satisfying~$G'\to(C^\ell,C^k)$.

For each~$i\geq0$, let~$\bfG(i)$ be the family of all graphs,
\textit{up to isomorphism}, that are underlying graphs of the
hypergraphs~$\cH_i$ in~$\cF(i)$.  Now recall that
each~$\cH_i\in\cF(i)$ has an associated set of
degeneracies~$I_i=I_i(\cH_i)\subseteq[i]\times\{1,2\}$.  For
all~$0\leq j\leq i$, let~$\bfG(i,j)$ be the collection of all
graphs~$G\in\bfG(i)$ that are underlying graphs of
hypergraphs~$\cH_i\in\cF(i)$ with~$j$ degeneracies, that is,
with~$|I_i(\cH_i)|=j$.  Finally,
let~$\bfG_\leq(m,d)=\bigcup\bfG(i,j)$, where the union is taken over
all~$0\leq i\leq m$ and~$0\leq j\leq d$.

The crucial lemma in the proof of Claim~\ref{ecl8} is as follows.

\begin{ecl}
\label{ecl7}
\begin{enumerate}
\item[{\rm({\it i\/})}] For all~$0\leq j\leq i$, we 
have~$|\bfG(i,j)|\leq i^j(i\ell)^{j\ell}$.  
\item[{\rm({\it ii\/})}] For all~$m\geq1$ and~$0\leq d\leq m$, we 
have~$|\bfG_\leq(m,d)|\leq(m+1)m^{d+1}(m\ell)^{\ell(d+1)}$.   
\end{enumerate}
\end{ecl}
\proof ({\it i\/})~For a hypergraph~$\cH_i$ in~$\cF(i)$,
let~$J_i(\cH_i)\subseteq[i]$ be the set of integers~$j$ for
which~$\cH_i$ is degenerate at level~$j$.  In other words, $j\in
J_i(\cH_i)$ if and only if one of~$(j,1)$, $(j,2)$ belongs
to~$I_i(\cH_i)$.  For a set~$J\subseteq[i]$, let~$\bfG(i,J)$ be the
set of all graphs~$G\in\bfG(i,|J|)$ that are underlying graphs
of~$\cH_i\in\cF(i)$ with~$J_i(\cH_i)=J$.  For simplicity,
put~$g(i,j)=|\bfG(i,j)|$ and~$g(i,J)=|\bfG(i,J)|$. 

Let us first fix~$J\subseteq[i]$ and estimate~$g(i,J)$.  We claim that 
\begin{equation}
\label{eq:recur}
g(i,J)\quad\leq\quad
          \left\{\begin{array}{ll} 
                   g(i-1,J)&\mbox{\quad if~$i\notin J$}\\
                   \vspace{-10pt}\\
                   g(i-1,J\setminus\{i\})(i\ell)_\ell
                           &\mbox{\quad if~$i\in J$,}
                 \end{array}
          \right.
\end{equation}
where, as usual, $(a)_b=a(a-1)\cdots(a-b+1)$.  Let us first suppose
that~$i\notin J$.  Let~$G\in\bfG(i,J)$, and suppose that~$G=G(\cH_i)$
with~$J_i(\cH_i)=J$.  Since~$i\notin J$, the ranks of the elements of
the $i$th hyperedge~$E_i$ of~$\cH_i$ are uniquely determined
once~$\cH_{i-1}=\cH_i\setminus\{E_i\}$ is given.  At this point it is
crucial that in Procedure {\Hypertree}, when adding a non-degenerate
hyperedge to our current hypertree, we choose the hypervertex
\textit{with lowest rank} to `hang' our new hyperedge on.  A moment's
thought now shows that we have thus implicitly defined an
injection~$\bfG(i,J)\hookrightarrow\bfG(i-1,J)$, since here we are
dealing with graphs up to isomorphism.

Suppose now that~$i\in J$.  Let~$G$, $\cH_i$, and~$E_i$ be as before.
Then the number of ways we can choose the cycle~$C$ of~$G$ that
corresponds to the hyperedge~$E_i$ can be bounded very generously
by~$(i\ell)_\ell$.  Indeed, the underlying graph~$G(\cH_{i-1})$
of~$\cH_{i-1}=\cH_{i-1}\setminus\{E_i\}$ has at most~$i\ell$ vertices,
and to define~$C$ it suffices to select its vertices
from~$V(G(\cH_{i-1}))$.  This completes the proof of~(\ref{eq:recur}).

By induction, we may deduce from~(\ref{eq:recur})
that~$g(i,J)\leq\{(i\ell)_\ell\}^{|J|}$, since~$g(i,\emptyset)\leq1$
for any~$i\geq 0$.  Therefore
$$
  g(i,j)=|\bfG(i,j)|=\Big|\bigcup_{J\subseteq[i]}\bfG(i,J)\Big|
        \leq{i\choose j}\{(i\ell)_\ell\}^j\leq i^j(i\ell)^{j\ell}, 
$$
completing the proof of~({\it i\/}).  Assertion~({\it ii\/}) follows
easily from~({\it i\/}), since
$$
|\bfG_\leq(m,d)|\leq\sum_{i=0}^m\sum_{j=0}^dg(i,j)
  \leq\sum_{i=0}^m\sum_{j=0}^di^j(i\ell)^{j\ell}
  \leq\sum_{i=0}^m\{i(i\ell)^\ell\}^{d+1}
  \leq(m+1)m^{d+1}(m\ell)^{\ell(d+1)}, 
$$
as required.
\endproofnosquare

In the sequel, we apply Claim~\ref{ecl7}({\it ii\/}) for~$m=O(\log n)$
and~$d=O(1)$.  Our claim tells us that, in this case, $\bfG_\leq(m,d)$
has polylogarithmic size only.

Before stating our last claim, we need to introduce a piece of
notation.  Below, we shall write~$\tbfG_\leq(m,d)$ for the family of
graphs~$G\in\bfG_\leq(m,d)$ that are isomorphic to underlying
graphs~$G(\cH_m)$ of \textit{outputs}~$\cH_m$ of
Procedure~{\Hypertree}.  

\begin{ecl}
\label{ecl8}
  Put~$p=p(n)=\e^{-2}n^{-\beta}$, $m'=\lfloor\log n+\ell\rfloor$, and 
  let~$M$ be as in~{\rm(\ref{eq:ineqIm})}.  Then the expected number
  of subgraphs of~$G_p$ that are isomorphic to members
  of~$\tbfG_\leq(m',M)$ is~$o(1)$. 
\end{ecl}
\proof An element~$G$ of~$\tbfG_\leq(m',M)$ corresponds to an
output~$\cH_m$ of Procedure {\Hypertree}, and hence the assertions in
Claim~\ref{ecl6} hold for~$\cH_m$.  In particular, we may
write~$\tbfG_\leq(m',M)=\tbfG_\leq^{(i)}(m',M)
\cup\tbfG_\leq^{(ii)}(m',M)$, where the elements~$G$
in~$\tbfG_\leq^{(i)}(m',M)$ correspond to~$\cH_m$ satisfying
Claim~\ref{ecl6}({\it b\/})({\it i\/}), and similarly
to~$\tbfG_\leq^{(ii)}(m',M)$. 

We now claim that the expected number of subgraphs of~$G_p$ that
are isomorphic to members of~$\tbfG_\leq^{(i)}(m',M)$ is~$o(1)$.
Fix~$G\in\tbfG_\leq^{(i)}(m',M)$.  Writing~$\#\{G\subseteq G_p\}$
for the number of subgraphs of~$G_p$ isomorphic to~$G$, we have
$$
\E(\#\{G\subseteq G_p\})\leq\(1\over\e^2\)^{e(G)}n^{|G|-\beta e(G)}
  \leq\(1\over\e^2\)^{\log n}n^{f(0)}\leq n^{-1/2}.
$$
Our claim then follows as~$|\tbfG_\leq^{(i)}(m',M)|$ is, by
Claim~\ref{ecl7}, only polylogarithmic in~$n$.

Similarly, we claim that the expected number of subgraphs of~$G_p$
that are isomorphic to members of~$\tbfG_\leq^{(ii)}(m',M)$ is~$o(1)$.
Indeed, for any~$G\in\tbfG_\leq^{(ii)}(m',M)$, we have
$$
\E(\#\{G\subseteq G_p\})\leq n^{|G|-\beta e(G)}\leq n^{-1/500}, 
$$
but again~$|\tbfG_\leq^{(ii)}(m',M)|$ is only polylogarithmic in~$n$. 
This finishes the proof of Claim~\ref{ecl8}. 
\endproofnosquare

To finish the proof of Theorem~\ref{thm:0-statement}, it suffices to
recall that, by Claim~\ref{ecl6}, the event~$G_p\to(C^\ell,C^k)$
implies that~$G_p$ contains a subgraph isomorphic to an element
of~$\tbfG_\leq(m',M)$, where~$m'$ and~$M$ are as in Claim~\ref{ecl8}.
\endproof

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Deterministic consequences}
\label{sec:det-conseq}

\proofof Corollary~\ref{cor:large-girth}.
Let~$\beta=\beta(C^{\ell_2},H)$.  Let~$B$ and~$\kappa$ be the
constants from Theorem~\ref{Gen1State} for $\ell_2,\ldots,\ell_r$
and~$H$.  Let
\[ 
  \eps = \min\{1+1/(\ell_2-1)-|F|+\beta(C^{\ell_2},H)e(F)\}, 
\]
where the minimum is taken over all graphs~$F\in\cV_{\ell_2,H,t}$.
Then~$\eps>0$ and the expected number of copies of graphs
from~$\cV_{\ell_2,H,t}$ in~$G_p$, where $p=Bn^{-\beta}$, is ${\cal
O}(n^{1+1/(\ell_2-1)-\eps})$. Therefore, by Markov's inequality, the
number of copies of graphs from~$\cV_{\ell_2,H,t}$ is almost surely at
most $\kappa n^{1+1/(\ell_2-1)}/(\log n)^{|H|}$.  If $G_p$ is a random
graph having this property and fulfilling the statement of
Theorem~\ref{Gen1State} then we define a graph~$G$ by removing one
edge from every copy of a graph of~$\cV_{\ell_2,H,t}$ in~$G_p$. 
The graph~$G$ has the required properties.
\endproof

\proofof Theorem~\ref{rainf}. 
We show that for any $t$ there exists a 
graph on more than $t$ vertices which is critical 
for $(C^{\ell_i})_{1\le i\le r}$. Let $B$ and $\beta=\beta(C^{\ell_2},
C^{\ell_1})$ 
be the constants from Corollary~\ref{cor:many-cycles}.
Let~${\cal T}=\{F\:|F|\le t\mbox{ and }|F|-\beta e(F)\le-1/500\}$. 
For $p=Bn^{-\beta}$, almost all graphs $G_p$ do not contain any graphs
from ${\cal T}$. Furthermore $G_p\to (C^{\ell_1},\ldots,C^{\ell_r})$ 
almost surely by Corollary~\ref{cor:many-cycles}. 
Therefore there exists a graph~$H$ on~$n\ge t$
vertices with $H\to(C^{\ell_1},\ldots,C^{\ell_r})$ and not
containing any graph from~$\cal T$ as a subgraph. Assume that there
exists a subgraph~$K$ of~$H$ on~$t$ vertices 
such that $K\to(C^{\ell_1},\ldots,C^{\ell_r})$. Hence in particular
$K\to(C^{\ell_1},C^{\ell_2})$. Let~$\cal K$ be the hypergraph with
hyperedges being the $\ell_1$-and $\ell_2$-cycles of~$K$. Let 
${\cal K}_0$ be a critical subgraph of~$\cal K$ with respect to
property (*) from Section~\ref{sec:proofof0}. We now run  
{\bf Procedure} {\Hypertree} on the input~${\cal K}_0$
but where we exit the {\bf repeat}-loop in {\lan{\it main
body\/}\ran} only if  $|G(\cH_i)|-\beta e(G(\cH_i))\leq-1/500$ thus
possibly creating hypertrees that are of length more than~$\log t$. It
follows easily from the proof of the 0-statement (cf., \textit{e.g.}, 
Claim~\ref{ecl6}) that the output
${\cal H}_m$ is such that its underlying graph~$G({\cal H}_m)$ is 
in~${\cal T}$, contradicting the fact that~$H$ is ${\cal T}$-free.
It follows that some subgraph of~$H$
containing more than~$t$ vertices is critical for $(C^{\ell_i})_{1\le 
i\le r}$.  
\endproof

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\nocite{*}
%\bibliographystyle{plain}
%\bibliography{bibl}
\begin{thebibliography}{10}

\bibitem{BBrgs}
B.~Bollob{\'a}s.
\newblock {\em Random Graphs}.
\newblock Academic Press, 1985.

\bibitem{GRS}
R.L. Graham, B.~Rothschild, and J.H. Spencer.
\newblock {\em Ramsey Theory}.
\newblock Wiley-Interscience Series in Discrete Mathematics and Optimization.
  John Wiley {\&} Sons, New York, second edition, 1990.

\bibitem{HKLb}
P.E. Haxell, Y.~Kohayakawa, and T.~{\L}uczak.
\newblock Tur\'an's extremal problem in random graphs: forbidding odd cycles.
\newblock {\em \Comb}.
\newblock To appear.

\bibitem{HKL}
P.E. Haxell, Y.~Kohayakawa, and T.~{\L}uczak.
\newblock Tur\'an's extremal problem in random graphs: forbidding even cycles.
\newblock {\em \JCTB}, 64:273--288, 1995.

\bibitem{Ja}
S.~Janson.
\newblock {Poisson} approximation for large deviations.
\newblock {\em \RSA}, 1(2):221--229, 1990.

\bibitem{Ko}
Y.~Kohayakawa.
\newblock The regularity lemma of {S}zemer\'edi for sparse graphs.
\newblock Manuscript, 1993.

\bibitem{KKS}
Y.~Kohayakawa, B.~Kreuter, and A.~Steger.
\newblock An extremal problem for random graphs and the number of graphs with
  large even-girth.
\newblock Submitted, 1995.

\bibitem{KLR1}
Y.~Kohayakawa, T.~{\L}uczak, and V.~R{\"o}dl.
\newblock Arithmetic progressions of length three in subsets of a random set.
\newblock {\em Acta Arithmetica}.
\newblock To appear.

\bibitem{KLR2}
Y.~Kohayakawa, T.~{\L}uczak, and V.~R{\"o}dl.
\newblock On {$K^4$}-free subgraphs of random graphs.
\newblock Submitted, 1995.

\bibitem{Kr}
B.~Kreuter.
\newblock Threshold functions for asymmetric {R}amsey properties with respect
  to vertex colorings.
\newblock Submitted, 1995.

\bibitem{Lu}
T.~{\L}uczak.
\newblock On {R}amsey minimal graphs.
\newblock {\em The Electronic Journal of Combinatorics}, 1:R{\#}4, 1994.

\bibitem{LRV}
T.~{\L}uczak, A.~Ruci\'nski, and B.~Voigt.
\newblock {Ramsey} properties of random graphs.
\newblock {\em \JCTB}, 56:55--68, 1992.

\bibitem{RR1}
V.~R{\"o}dl and A.~Ruci\'nski.
\newblock Lower bounds on probability thresholds for {R}amsey properties.
\newblock In {\em Combinatorics---Paul Erd\H{o}s is Eighty {\rm (Volume~1)}},
  Bolyai Soc. Math. Studies, pages 317--346, Budapest, 1993.

\bibitem{RRtrigs}
V.~R{\"o}dl and A.~Ruci\'nski.
\newblock Random graphs with monochromatic triangles in every edge coloring.
\newblock {\em \RSA}, 5(2):253--270, 1994.

\bibitem{RR2}
V.~R{\"o}dl and A.~Ruci\'nski.
\newblock Threshold functions for {R}amsey properties.
\newblock {\em \JAMS}, 8(4):917--942, 1995.

\bibitem{Szem}
E.~Szemer\'edi.
\newblock Regular partitions of graphs.
\newblock In J.-C. Bermond, J.-C. Fournier, M.~Las~Vergnas, and D.~Sotteau,
  editors, {\em Probl\`emes Combinatoires et Th\'eorie des Gra\-phes, Proc.
  Colloque Inter. CNRS}, pages 399--401, Paris, 1978. CNRS.

\end{thebibliography}


\end{document}



