%Time-stamp: <Wednesday 02 Oct 2002 08:28:12pm BRT yoshi@erdos.ime.usp.br>
\documentclass[twocolumn]{article}
\usepackage{amsmath,amsfonts}
\usepackage[colorlinks,backref]{hyperref}
\pagestyle{empty}

%set dimensions of columns and gap between columns
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.5pc}
\setlength{\textwidth}{6.9in}
\setlength{\topmargin}{-0.5in}
\setlength{\oddsidemargin}{-.3in}
\setlength{\parindent}{1pc}

% section titles 
\makeatletter
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip
\abovedisplayskip \abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt
plus3pt minus3pt\let\@listi\@listI} 

\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

\def\section{\@startsection{section}{1}{\z@}{24pt plus 2 pt minus 2 pt} {12pt
    plus 2pt minus 2pt}{\large\bf}} 

\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
  {12pt plus 2pt minus 2pt}{\subsize\bf}} 
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{teo}{Theorem}  
\newtheorem{corol}[teo]{Corollary}
\newtheorem{propo}[teo]{Proposition} 
\newtheorem{claim}[teo]{Claim}
\newtheorem{lema}[teo]{Lemma} 
\newtheorem{conjec}[teo]{Conjecture} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\cC{{\mathcal C}}
\def\cE{{\mathcal E}}
\def\cG{{\mathcal G}}
\def\cF{{\mathcal F}}
\def\cH{{\mathcal H}}
\def\tE{{\widetilde E}}
\def\tH{{\widetilde H}}
\def\bfV{{\mathbf V}}
\def\bfW{{\mathbf W}}
\def\cal{\mathcal}  
\def\eps{\varepsilon}
\let\epsilon=\varepsilon
\let\rho=\varrho
\def\:{\colon}  
\def\<{\leq}  
\def\>{\geq} 
\def\({\left(}
\def\){\right)}  
%\def\contido{\subseteq}
\let\contido=\subset
\def\N{\mathbb N}
\def\chao#1{\lfloor #1 \rfloor}
\def\teto#1{\lceil #1 \rceil}
\newcommand{\pden}[3]{{d}_{#1}( #2,#3 )}% #1-densidade de par (#2,#3)
\newcommand{\prob}[1]{{\mathbb P}\left( #1 \right)}%probabilidade
\newcommand{\esp}[1]{{\mathbb E}\, #1 }%probabilidade
\newcommand{\pr}[2]{{\mathbb P}_{{ #1}}\left\{ #2 \right\}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Do amsart.cls
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\DeclareRobustCommand{\qed}{%
  \ifmmode \mathqed
  \else
    \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill
    \quad\hbox{\qedsymbol}%
  \fi
}
\let\QED@stack\@empty
\let\qed@elt\relax
\newcommand{\pushQED}[1]{%
  \toks@{\qed@elt{#1}}\@temptokena\expandafter{\QED@stack}%
  \xdef\QED@stack{\the\toks@\the\@temptokena}%
}
\newcommand{\popQED}{%
  \begingroup\let\qed@elt\popQED@elt \QED@stack\relax\relax\endgroup
}
\def\popQED@elt#1#2\relax{#1\gdef\QED@stack{#2}}
\newcommand{\qedhere}{%
  \begingroup \let\mathqed\math@qedhere
    \let\qed@elt\setQED@elt \QED@stack\relax\relax \endgroup
}
\newif\ifmeasuring@
\newif\iffirstchoice@ \firstchoice@true
\def\setQED@elt#1#2\relax{%
  \ifmeasuring@
  \else \iffirstchoice@ \gdef\QED@stack{\qed@elt{}#2}\fi
  \fi
  #1%
}
\def\qed@warning{%
  \PackageWarning{amsthm}{The \@nx\qedhere command may not work
    correctly here}%
}
\newcommand{\mathqed}{\quad\hbox{\qedsymbol}}
\def\linebox@qed{\hfil\hbox{\qedsymbol}\hfilneg}
\@ifpackageloaded{amsmath}{%
  \def\math@qedhere{%
    \@ifundefined{\@currenvir @qed}{%
      \qed@warning\quad\hbox{\qedsymbol}%
    }{%
      \@xp\aftergroup\csname\@currenvir @qed\endcsname
    }%
  }
  \def\displaymath@qed{%
    \relax
    \ifmmode
      \ifinner \aftergroup\linebox@qed
      \else
        \eqno
        \let\eqno\relax \let\leqno\relax \let\veqno\relax
        \hbox{\qedsymbol}%
      \fi
    \else
       \aftergroup\linebox@qed
    \fi
  }
  \@xp\let\csname equation*@qed\endcsname\displaymath@qed
  \def\equation@qed{%
    \iftagsleft@
      \hbox{\phantom{\quad\qedsymbol}}%
      \gdef\alt@tag{%
        \rlap{\hbox to\displaywidth{\hfil\qedsymbol}}%
        \global\let\alt@tag\@empty
      }%
    \else
      \gdef\alt@tag{%
        \global\let\alt@tag\@empty
        \vtop{\ialign{\hfil####\cr
                \tagform@\theequation\cr
                \qedsymbol\cr}}%
        \setbox\z@
      }%
    \fi
  }
  \def\qed@tag{%
    \global\tag@true \nonumber
    &\omit\setboxz@h {\strut@ \qedsymbol}\tagsleft@false
    \place@tag@gather
    \kern-\tabskip
    \ifst@rred \else \global\@eqnswtrue \fi \global\advance\row@\@ne \cr
  }
  \def\split@qed{%
    \def\endsplit{\crcr\egroup \egroup \ctagsplit@false \rendsplit@
      \aftergroup\align@qed
    }%
  }
  \def\align@qed{%
    \ifmeasuring@ \tag*{\qedsymbol}%
    \else \let\math@cr@@@\qed@tag
    \fi
  }
  \@xp\let\csname align*@qed\endcsname\align@qed
  \@xp\let\csname gather*@qed\endcsname\align@qed
%% Needs some patching up for amsmath 1.2
}{% end of amsmath branch, start plain LaTeX branch
  \def\math@qedhere{%
    \@ifundefined{\@currenvir @qed}{%
      \qed@warning \aftergroup\displaymath@qed
    }{%
      \@xp\aftergroup\csname\@currenvir @qed\endcsname
    }%
  }
  \def\displaymath@qed{%
    \relax
    \ifmmode
      \ifinner \aftergroup\aftergroup\aftergroup\linebox@qed
      \else
        \eqno \def\@badmath{$$}%
        \let\eqno\relax \let\leqno\relax \let\veqno\relax
        \hbox{\qedsymbol}%
      \fi
    \else
       \aftergroup\linebox@qed
    \fi
  }
  \@ifundefined{ver@leqno.clo}{%
    \def\equation@qed{\displaymath@qed \quad}%
  }{%
    \def\equation@qed{\displaymath@qed}%
  }
  \def\@tempa#1$#2#3\@nil{%
    \def\[{#1$#2\def\@currenvir{displaymath}#3}%
  }%
  \expandafter\@tempa\[\@nil
}
\@ifpackageloaded{amstex}{%
  \def\@tempa{TT}%
}{%
  \@ifpackageloaded{amsmath}{%
    \def\@tempb#1 v#2.#3\@nil{#2}%
    \ifnum\@xp\@xp\@xp\@tempb\csname ver@amsmath.sty\endcsname v0.0\@nil
       <\tw@
      \def\@tempa{TT}%
    \else
      \def\@tempa{TF}%
    \fi
  }{%
    \def\@tempa{TF}
  }%
}
\if\@tempa
  \renewcommand{\math@qedhere}{\quad\hbox{\qedsymbol}}%
\fi
\newcommand{\openbox}{\leavevmode
  \hbox to.77778em{%
  \hfil\vrule
  \vbox to.675em{\hrule width.6em\vfil\hrule}%
  \vrule\hfil}}
\DeclareRobustCommand{\textsquare}{%
  \begingroup \usefont{U}{msa}{m}{n}\thr@@\endgroup
}
%\@ifclasswith{\@classname}{noamsfonts}{%
%  \providecommand{\qedsymbol}{\openbox}%
%}{}%
\providecommand{\qedsymbol}{\textsquare}%
\newenvironment{proof}[1][\proofname]{\par
  \pushQED{\qed}%
  \normalfont \topsep6\p@\@plus6\p@\relax
  \trivlist
  \item[\hskip\labelsep
        \itshape
    #1\@addpunct{.}]\ignorespaces
}{%
  \popQED\endtrivlist\@endpefalse
}
\newcommand{\proofname}{Proof}
\hyphenation{acad-e-my acad-e-mies af-ter-thought anom-aly anom-alies
an-ti-deriv-a-tive an-tin-o-my an-tin-o-mies apoth-e-o-ses
apoth-e-o-sis ap-pen-dix ar-che-typ-al as-sign-a-ble as-sist-ant-ship
as-ymp-tot-ic asyn-chro-nous at-trib-uted at-trib-ut-able bank-rupt
bank-rupt-cy bi-dif-fer-en-tial blue-print busier busiest
cat-a-stroph-ic cat-a-stroph-i-cally con-gress cross-hatched data-base
de-fin-i-tive de-riv-a-tive dis-trib-ute dri-ver dri-vers eco-nom-ics
econ-o-mist elit-ist equi-vari-ant ex-quis-ite ex-tra-or-di-nary
flow-chart for-mi-da-ble forth-right friv-o-lous ge-o-des-ic
ge-o-det-ic geo-met-ric griev-ance griev-ous griev-ous-ly
hexa-dec-i-mal ho-lo-no-my ho-mo-thetic ideals idio-syn-crasy
in-fin-ite-ly in-fin-i-tes-i-mal ir-rev-o-ca-ble key-stroke
lam-en-ta-ble light-weight mal-a-prop-ism man-u-script mar-gin-al
meta-bol-ic me-tab-o-lism meta-lan-guage me-trop-o-lis
met-ro-pol-i-tan mi-nut-est mol-e-cule mono-chrome mono-pole
mo-nop-oly mono-spline mo-not-o-nous mul-ti-fac-eted mul-ti-plic-able
non-euclid-ean non-iso-mor-phic non-smooth par-a-digm par-a-bol-ic
pa-rab-o-loid pa-ram-e-trize para-mount pen-ta-gon phe-nom-e-non
post-script pre-am-ble pro-ce-dur-al pro-hib-i-tive pro-hib-i-tive-ly
pseu-do-dif-fer-en-tial pseu-do-fi-nite pseu-do-nym qua-drat-ic
quad-ra-ture qua-si-smooth qua-si-sta-tion-ary qua-si-tri-an-gu-lar
quin-tes-sence quin-tes-sen-tial re-arrange-ment rec-tan-gle
ret-ri-bu-tion retro-fit retro-fit-ted right-eous right-eous-ness
ro-bot ro-bot-ics sched-ul-ing se-mes-ter semi-def-i-nite
semi-ho-mo-thet-ic set-up se-vere-ly side-step sov-er-eign spe-cious
spher-oid spher-oid-al star-tling star-tling-ly sta-tis-tics
sto-chas-tic straight-est strange-ness strat-a-gem strong-hold
sum-ma-ble symp-to-matic syn-chro-nous topo-graph-i-cal tra-vers-a-ble
tra-ver-sal tra-ver-sals treach-ery turn-around un-at-tached
un-err-ing-ly white-space wide-spread wing-spread wretch-ed
wretch-ed-ly Eng-lish Euler-ian Feb-ru-ary Gauss-ian
Hamil-ton-ian Her-mit-ian Jan-u-ary Japan-ese Kor-te-weg
Le-gendre Mar-kov-ian Noe-ther-ian No-vem-ber Rie-mann-ian Sep-tem-ber}
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%no date printed
\date{}

\title{\LARGE\bf Ramsey Minimal Graphs\vspace{18pt}}

\author{B\'ela Bollob\'as\thanks{Partially supported by NSF grant DMS-9971788
    and DARPA grant F33615-01-C-1900.}\\
  Department of Mathematical Sciences\\
  University of Memphis\\
  Memphis TN 38152--6429, U.S.A.\\
  and\\
  Trinity College\\
  Cambridge CB2~1TQ, U.K.\\
  \textit{e-mail}: \texttt{bollobas@msci.memphis.edu}
  %
  \and
  %
  Jair Donadelli\thanks{Supported by a CNPq Doctorate Scholarship
    (Proc.~141633/1998-0).} \null\ and Yoshiharu Kohayakawa\thanks{Partially
    supported by MCT/CNPq through ProNEx Programme (Proc.\ CNPq 664107/1997-4)
    and by CNPq (Proc.\ 300334/93-1, 468516/2000-0, and 910064/99-7).}\\
  Instituto de Matem\'atica e Estat\'\i stica\\
  Universidade de S\~ao Paulo\\
  Rua do Mat\~ao 1010\\
  05508--090 S\~ao Paulo~SP, Brazil\\
  \textit{e-mail}: \texttt{\{jair,\ yoshi\}@ime.usp.br}
  %
  \and
  %
  Richard H.~Schelp\\
  Department of Mathematical Sciences\\
  University of Memphis\\
  Memphis TN 38152--6429, U.S.A.\\
  \textit{e-mail}: \texttt{schelpr@msci.memphis.edu}\vspace{15pt}\\
  \textit{Dedicated to Professor Jayme L.~Szwarcfiter on the occasion of his
  60th birthday}}

\maketitle\thispagestyle{empty}

\begin{abstract}\noindent
  As usual, for graphs~$\Gamma$, $G$, and~$H$, we write $\Gamma\to(G,H)$ to
  mean that any red-blue colouring of the edges of~$\Gamma$ contains a red
  copy of~$G$ or a blue copy of~$H$.  A pair of graphs~$(G,H)$ is said to be
  \textit{Ramsey-infinite} if there are infinitely many \textit{minimal}
  graphs~$\Gamma$ for which we have $\Gamma\to(G,H)$.
  
  Let~$\ell\geq4$ be an integer.  We show that if~$H$ is a $2$-connected graph
  that does not contain induced cycles of length at least~$\ell$, then the
  pair $(C^k,H)$ is Ramsey-infinite for any~$k\geq\ell$, where~$C^k$ denotes
  the cycle of length~$k$.
\end{abstract}

\vspace{10pt}

\noindent{\bf Keywords: } Ramsey critical graphs, Szemer\'edi's regularity lemma

\section{Introduction}
\label{sec:intro}
\noindent
Let us say that a graph~$\Gamma$ is \textit{Ramsey} for a pair of
graphs~$(G,H)$ if any red-blue edge-colouring of~$\Gamma$ contains a red copy
of~$G$ or a blue copy of~$H$.  Furthermore, let us say that a Ramsey graph
for~$(G,H)$ is \textit{critical} if no proper subgraph of it is Ramsey
for~$(G,H)$.  A pair of graphs~$(G,H)$ is said to be \textit{Ramsey-infinite}
if there are arbitrarily large critical Ramsey graphs for~$(G,H)$.  For
example, the pair $(P^3, P^3)$, consisting of two paths on three vertices, is
Ramsey-infinite as is shown by the family of all cycles of odd length.  If a
pair~$(G,H)$ is not Ramsey-infinite, then it is said to be
\textit{Ramsey-finite}.

Let us briefly discuss some results concerning the concepts above.  The
problem of characterizing those pairs of graphs~$(G,H)$ that are
Ramsey-infinite was first addressed by Ne{\v{s}}et{\v{r}}il and
R{\"o}dl~\cite{MR54:173} in~1976.  Among other results, those authors
proved~\cite{MR80c:05102} in~1978 that~$(G,H)$ is Ramsey-infinite in the
following three cases: (\textit{i}) both~$G$ and~$H$ are forests containing a
path of length three, (\textit{ii}) both are $3$-connected graphs, and
(\textit{iii}) both have chromatic number at least three. In 1978, Burr et
al.~\cite{MR80m:05081} proved that if~$G$ is a matching then~$(G,H)$ is
Ramsey-finite for all graphs $H$. In 1986, Burr~\cite{MR87m:05126} proved that
if~$G$ is a~$2$-connected graph that remains connected after deleting any two
non-adjacent vertices, then the pair~$(G,G)$ is Ramsey-infinite.

In 1991, Faudree~\cite{MR92i:05151} basically \textit{characterized} all
Ramsey-finite pairs consisting of two forests.  In 1994, \L
uczak~\cite{MR95b:05149} proved that if~$G$ is a forest other than a matching
and~$H$ contains a cycle, then~$(G,H)$ is a Ramsey-infinite pair.

Using Corollary~4 from \cite{MR96h:05141} and Theorem~6
from~\cite{MR95b:05150}, both results of R\"odl and Ruci\'nski, one may deduce
that the pair~$(G,G)$ is Ramsey-infinite for all~$G$ containing a cycle.
%The
%proofs in \cite{MR99g:05159} and \cite{MR96h:05141} make use of Szemer\'edi's
%regularity lemma as an auxiliary tool.

Schaefer~\cite{MR1798082,MR2002a:68049} has recently proved some related, very
interesting results concerning the computational complexity of the problem of
deciding, given graphs~$\Gamma$, $G$, and~$H$, whether the Ramsey
property~$\Gamma\to(G,H)$ holds.

Burr et al.~\cite{MR83c:05092} proposed the following notable conjecture
in~1980.

\begin{conjec}
  The pair~$(G,H)$ is Ramsey-infinite unless both~$G$ and~$H$ are stars with
  an odd number of edges or at least one of~$G$ and~$H$ contains a single edge
  component.
\end{conjec}

Faudree et al.~\cite{MR97m:05134} observe that ``an interesting case of the
above conjecture is when~$G$ is a cycle and~$H$ is two-connected.  No
technique is presently known for showing such a pair is Ramsey-infinite''.
Although we are not able to deal with this case completely, we shall show that
if we impose further restrictions on~$H$, then such a pair~$(G,H)$ is indeed
Ramsey-infinite.

This note is organized as follows.  In \S\ref{sec:state}, we state our main
result, Theorem~\ref{teo:secundario}.  In \S\ref{sec:auxs}, we introduce the
main technical lemmas that we shall need.  In \S\ref{sec:outline}, we give an
informal description of the proof of Theorem~\ref{teo:secundario}.  Our proof
strategy will be based on the probabilistic method; in \S\ref{sec:construcao},
we give the definition of a random graph~$\Gamma$ that will be crucial, and we
prove some lemmas concerning the structure of~$\Gamma$.
Theorem~\ref{teo:secundario} is proved in \S\ref{sec:the_proof}.  We close
this note with some related observations.

\subsection{Terminology and the main result}
\label{sec:state}
\noindent
Let us recall some standard notation and state the main result of this note.
A connected graph~$H$ is \textit{$2$-connected} if it has at least~$3$
vertices, and the deletion of any vertex does not disconnect~$H$.  We call
$e\in E(H)$ a \textit{chord} in a cycle~$C$ of~$H$ if~$e$ joins a pair of
vertices of~$C$ that are not adjacent in~$C$.

We shall use the arrow notation from Ramsey theory: we shall write $\Gamma\to
(G,H)$ if the graph~$\Gamma$ is Ramsey for the pair $(G,H)$.  Moreover, given
an integer~$t>0$, let us write~$\Gamma \not\to_t (G,H)$ if for each~$U\contido
V(\Gamma)$ with~$|U|\<t$ we have~$\Gamma[U] \not\to (G,H)$, that is, the graph
induced by~$U$ in~$\Gamma$  is not Ramsey for~$(G,H)$.

For any integer~$\ell\geq4$, we denote by~$\cal{C}(\ell)$ the class of all
$2$-connected graphs~$H$ that have no induced cycle of length~$\geq\ell$.
Equivalently, $\cC(\ell)$~consists of the $2$-connected graphs~$H$ with the
property that every cycle of~$H$ with~$\geq\ell$ edges has a chord.  For
instance, $\cC(4)$~is the well known family of chordal graphs.  Clearly,
$$
\cC(4)\subset\cC(5)\subset\cC(6)\subset\dots
$$
In this note, we prove the following result.

\begin{teo}\label{teo:secundario}
  Given integers~$\ell\geq4$ and~$t\>1$ and a graph~$H\in \cal{C}(\ell)$,
  there exists a graph~$\Gamma$ such that $\Gamma\to(C^{\ell},H)$
  but~$\Gamma\not\rightarrow_{t} (C^{\ell},H)$.
\end{teo}

We may immediately deduce the following corollary.

\begin{corol}
  \label{cor:R-infty}
  Let~$\ell\geq4$ be an integer and suppose~$H\in\cC(\ell)$.  Then the
  pair~$(C^k,H)$ is Ramsey-infinite for any~$k\geq\ell$.
\end{corol}

Our proof of Theorem~\ref{teo:secundario} is probabilistic.  It would be
interesting to prove this result by explicit constructions.

Before we proceed, we recall some standard definitions.  As usual, we write
\textit{almost surely} to mean `with probability tending to~$1$
as~$n\to\infty$'.  If~$f(n)$ and~$g(n)$ are two functions of~$n$, we write
$f(n)\asymp g(n)$ to mean that there is a positive constant~$C$ for which we
have $g(n)/C\leq f(n)\leq Cg(n)$ for all large enough~$n$.  Our asymptotic
notation will always be with respect to~$n\to\infty$ and, in fact, we often
tacitly assume that~$n$ is large enough for our inequalities to hold.  All
graphs are assumed to be undirected and simple.

Let~$h\geq2$ be an integer.  An \textit{$h$-uniform hypergraph} on a set of
\textit{vertices}~$V$ is a collection~$\cal{E}$ of subsets of~$V$, called
\textit{hyperedges}, each of cardinality~$h$.  Thus, in the case in
which~$h=2$, we have ordinary graphs.  A hypergraph is \textit{linear} if any
two members of~$\cal E$ intersect in at most one vertex.  A \textit{hypercycle
  of length~$2$} is any pair of hyperedges meeting in more than one vertex,
whereas a \textit{hypercycle of length~$k$} ($k>2$) is a (linear) hypergraph
given by hyperedges~$\cal{E}=\{E_1,\dots,E_k\}$ on~$\bigcup \cal{E}$ such
that~$|E_i \cap E_j|=1$ if and only if~$i$ and~$j$ are such that~$j=i+1$
or~$i=k$ and~$j=1$.  We sometimes use the term \textit{$k$-hypercycle} to
refer to a hypercycle of length~$k$.  The \textit{girth} of a (hyper)graph is
the length of a shortest (hyper)cycle in the (hyper)graph.  When there is no
danger of confusion, we use the simpler terms `edge' and `cycle' even when
referring to hypergraphs.

It will be convenient to write~$G=G^n$ to indicate that the graph~$G$ has~$n$
vertices.  We write~$e(G)$ for the number of edges in a graph~$G$.

\section{Auxiliary results}
\label{sec:auxs}
\noindent

\subsection{Szemer\'edi's regularity lemma}
\label{sec:regularity}
\noindent
We now describe a version of Szemer\'edi's regularity lemma for sparse graphs.
Given a graph~${G}=(V,E)$, for any pair of disjoint sets~$U$, $W \subset V$,
we denote the set of edges in the bipartite subgraph induced by~$U$ and~$W$
in~$G$ by $E_{{G}}(U,W)$, and let
\begin{align*}
  e_G(U,W)&=\left|E_{G}(U,W) \right| \\
  &=\big| \big\{ \{a,b\} \in E\: a\in U \textrm{ and } b\in W \big\} \big|.  
\end{align*}

Suppose~$0<\eta \<1$, $D\>1$, and~$0<p\<1$ are given real numbers.  We say
that~${G}$ is~$(\eta,D,p)$-\textit{sparse} if, for any pair of disjoint sets
$U$, $W\subset V$ with~$|U|$, $|W|\>\eta |V|$, we have
$$
e_G(U,W) \< Dp|U||W|.
$$
Strictly speaking, in the definition of $(\eta,D,p)$-sparseness above, we
could have the product~$Dp$ as a single parameter, and would thus have the
notion of, say, `$(\eta,D')$-sparseness' (with~$D'=Dp$).  However, as it will
become clear in the applications, we shall be dealing with cases in which
there is a natural, underlying `density'~$p$ in the context.

The \textit{$p$-density} of the pair~$(U,W)$ in~${G}$ is
$$
\pden{{G},p}{U}{W}=\frac{ e_G(U,W)}{p|U||W|}.
$$
For any~$0<\eps\<1$, the pair of disjoint non-empty sets~$(U,W)$, with~$U$,
$W\subset V$, is said to be~$(\eps,{G},p)$-\textit{regular} if, for all
$U'\subset U$ and all~$W'\subset W$ with~$|U'|\>\eps |U|$
and~$|W'|\>\eps|W|$, we have
$$
\big|\pden{{G},p}{U}{W}-\pden{{G},p}{U'}{W'}\big|<\eps.
$$

We say that a partition~$\Pi=(V_0,V_1,\dots,V_k)$ of~$V$ is
\textit{$(\eps,k,{G},p)$-regular} if~$|V_0|\< \eps |V|$ and~$|V_i|=|V_j|$ for
all~$i$, $j\in[k]=\{1,\dots,k\}$, and for~$\geq(1-\eps)\binom{k}{2}$
pairs~$\{i,j\}\subset[k]$ we have that~$(V_i,V_j)$ is $(\eps,{G},p)$-regular.

In this note, we shall use the following lemma, which is a natural variant of
Szemer\'edi's regularity lemma for sparse graphs observed independently by
Kohayakawa and R\"odl (see, e.g.,~\cite{MR99g:05145}).

\begin{lema}\label{le:yoshi}
  For all real numbers~$\eps>0$, $D\>1$, and integer~$k_0\geq 1$, there exist
  constants~$\eta=\eta(\eps,k_0,D)>0$ and~$K_0=K_0(\eps,k_0,D)\geq k_0$ such
  that, for any~$0<p=p(n)\leq1$, any sufficiently large $(\eta,D,p)$-sparse
  graph~${G}={G}^n$ admits an $(\eps,k,{G},p)$-regular partition for
  some~$k_0\leq k\leq K_0$.
\end{lema}

\subsection{A counting lemma}
\label{sec:counting}
\noindent
Suppose~$m>0$ and~$\ell\>3$ are fixed integers and
$\mathbf{V}^{(m)}=(V_i)_{i=1}^{\ell}$ is a fixed vector of pairwise disjoint
sets of vertices, each of cardinality~$m$.  Below, the indices of the~$V_i$'s
will be taken modulo~$\ell$.  Let~$B>0$, $C\>1$, $D\>1$, $\eps\< 1$,
and~$\rho\<1$ be positive real numbers and let an integer~$M\>1$ be given.
We call a graph~${F}$ on~$\bigcup_{1\leq i\leq\ell}V_i$
an~\textit{$(\eps,\rho ,B,C,D;\mathbf{V}^{(m)},M)$-graph} if
\begin{enumerate}\renewcommand{\labelenumi}{(\textit{\roman{enumi}})}
\item $E({F})=\bigcup_{i=1}^{\ell} E_F(V_i,V_{i+1})$ and~$|E({F})| = M$,
\item for all~$1\<i\<\ell$ we have that the pairs~$(V_i,V_{i+1})$
  are~$(\eps,{F},\overline{p})$-regular,
  where~$\overline{p}=Bm^{-1+1/(\ell-1)}$, and their~$\overline{p}$-densities
  satisfy
  $$
  \rho\< \pden{{F},\overline{p}}{V_i}{V_{i+1}} \< D,
  $$
\item for any~$1\<i<\ell-1$, if~$U\subset V_i$ and~$W \subset V_{i+1}$ are
  such that
  $$
  |U|\<|W|\<\overline{p}m|U|\<\left(\overline{p}m\right)^{\ell-2},
  $$
  then
  \begin{equation}\label{eq:localsparseness}
    e_F(U,W)\< C|W|.
  \end{equation}
\end{enumerate}

The main technical result that we shall need is the following
`\textit{counting lemma}', from Kohayakawa and Kreuter~\cite{MR99g:05159}. 

\begin{lema}\label{le:contagem}
  Let an integer~$\ell\geq3$ be fixed, and let constants $0<\alpha\leq1$,
  $0<\rho \leq1$, $C\geq1$, and~$D\geq1$ be given.  Then there exist positive
  constants $\eps=\eps(\ell,\alpha,\rho ,C,D)\leq1$,
  $B_0=B_0(\ell,\alpha,\rho ,C,D)>0$, and $m_0=m_0(\ell,\alpha,\rho ,C,D)$
  such that, for all integers~$m\geq m_0$ and~$M\geq1$, and all real~$B\geq
  B_0$, the number of $(\eps,\rho ,B,C,D;\mathbf{V}^{(m)},M)$-graphs
  containing no cycle~${C}^{\ell}$ is at most
  \begin{equation*}
%    \label{eq:expbound}
    \alpha^M \binom{({\ell}+2)m^2}{M}.
  \end{equation*}
\end{lema}

In what follows, $\bfV^{(m)}$ will always denote a vector~$(V_i)_{i=1}^\ell$
of pairwise disjoint sets of vertices, each of cardinality~$m$.  If~$\Gamma$
is a graph and~$U=\bigcup_{1\leq i\leq\ell}V_i\subset V(\Gamma)$,
then~$\Gamma[\bfV^{(m)}]$ will denote the $\ell$-partite subgraph of~$\Gamma$
with vertex set~$U$ and edge set
$$
\bigcup_{1\leq i\leq\ell}E_\Gamma(V_i,V_{i+1}),
$$
where, as usual, the indices are taken modulo~$\ell$.

\subsection{Ramsey's theorem}
\label{sec:Ramsey}
\noindent
The following is an easy consequence of Ramsey's theorem
(see, e.g.,~\cite{MR99g:05159}).

\begin{lema}\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^{|V(H_i)|}$ monochromatic copies of~$H_i$ of colour~$i$.
\end{lema}

\section{Outline of the proof of Theorem~\ref{teo:secundario}}
\label{sec:outline}
\noindent
In this section, we describe informally the strategy we employ in the proof of
Theorem~\ref{teo:secundario}.

Let~$H$ be a graph in~$\cC(\ell)$ on $h$~vertices, where~$\ell\geq4$.  We
start by fixing a large positive constant~$A$ and by setting
$p_H=An^{-(h-1)+1/(\ell-1)}$.  We then generate a random $h$-uniform
hypergraph~$\cH_{n,p_H}$ on~$[n]=\{1,\dots,n\}$ according to the binomial
model, that is, we independently let each element of
$$
\binom{[n]}{h}=\{E\subset[n]\:|E|=h\}
$$
be a hyperedge of~$\cH_{n,p_H}$ with probability~$p_H$.  Owing to the
choice of~$p_H$, almost surely each hyperedge of~$\cH_{n,p_H}$ belongs to a
large number of hypercycles of length~$\ell$.  Moreover, one may also check
that the number of hypercycles of length~$<\ell$ in~$\cH_{n,p_H}$ is almost
surely~$o(|E(\cal{H}_{n,p_H})|)$.

We now obtain a linear hypergraph~$\cG$ of girth~$\ell$ from~$\cH_{n,p_H}$ by
removing a hyperedge from each of the $o(|E(\cal{H}_{n,p_H})|)$ hypercycles
of~$\cH_{n,p_H}$ of length~$<\ell$.  We now define a graph~$\Gamma=\Gamma^n$
from~$\cG$ embedding a copy of~$H$ in each hyperedge of~$\cG$ arbitrarily.
The fact that~$H$ belongs to~$\cC(\ell)$ implies that
\begin{enumerate}
\item[(*)]\emph{the only copies of~$H$ that occur in~$\Gamma$ are the ones
    that we have embedded in the hyperedges of~$\cG$}.
\end{enumerate}
In particular, all the copies of~$H$ in~$\Gamma$ are \textit{induced} copies.
Also worth noting is that
\begin{enumerate}
\item[(**)]\emph{if~$e\in E(\Gamma)$, then there is a unique copy~$H'$ of~$H$
    in~$\Gamma$ that contains this edge~$e$ of~$\Gamma$.}
\end{enumerate}
We claim that~$\Gamma$ will do in Theorem~\ref{teo:secundario}.

First, we wish to show that in every colouring of the edges of~$\Gamma$ with
colours red and blue either there is a red copy of~$C^\ell$ or else there is a
blue copy of~$H$.  Let an adversary pick a colouring.  \emph{We may suppose
  that our adversary has coloured red exactly one edge from each of the copies
  of~$H$ that we embedded in the hyperedges of~$\cG$.}  Indeed, our adversary
has to colour red \textit{at least} one edge from each such copy of~$H$;
moreover, because of~(*), having \textit{one} red edge in each such copy
of~$H$ suffices.  We have to show that these red edges must necessarily create
a copy of~$C^\ell$.

Let~$\Gamma^{(e)}$ be the spanning subgraph of~$\Gamma$ whose edges are the
red edges in the colouring of our adversary.  Note that~$\Gamma^{(e)}$
has
$$
|\cG|=(1+o(1))|E(\cal{H}_{n,p_H})| \asymp n^{1+1/(\ell-1)}
$$
edges.  Furthermore, as we shall show, there are positive constants~$A'$
and~$D$ for which the graph~$\Gamma^{(e)}$ is $(\eta,D,p_e)$-sparse, where
$$
p_e=A'n^{-1+1/(\ell-1)}
$$
and~$\eta$ is an arbitrarily small constant.

Although not directly relevant to this proof, we observe that the random
graph~$G_{n,p_e}$ is such that, almost surely, each of its edges belongs to a
large number of~$\ell$-cycles, and in fact, by the well known theorem of
R\"odl and Ruci\'nski~\cite{MR96h:05141}, we
have~$G_{n,p_e}\to(C^\ell,C^\ell)$ if~$A'$ is a large enough constant.

We now go back to the proof of Theorem~\ref{teo:secundario}.  As the
graph~$\Gamma^{(e)}$ is~$(\eta,D,p_e)$-sparse, we may apply the regularity
lemma (Lemma~\ref{le:yoshi}), with some appropriate choices for~$k_0$
and~$\epsilon$, to obtain an~$\ell$-tuple $(V_1,\dots,V_\ell)$ of subsets
of~$V(\Gamma)$ with~$(V_i,V_{i+1})$ $(\epsilon;p_e)$-regular and
with~$p_e$-density bounded away from~$0$, for all~$1\leq i\leq\ell$, where the
indices are taken modulo~$\ell$.  By the counting lemma
(Lemma~\ref{le:contagem}), it will follow that almost surely~$\Gamma$ is so
that such an $\ell$-tuple~$(V_1,\dots,V_\ell)$ must span an
$\ell$-cycle~$C^\ell$ in~$\Gamma^{(e)}$.  By the definition of~$\Gamma^{(e)}$,
this cycle is monochromatic of colour red.  Thus~$\Gamma\to(C^\ell,H)$.

In order to show that~$\Gamma \not\to_t (C^\ell,H)$ for any fixed integer~$t$,
we use the fact that almost surely~$\Gamma$ is such that, for any~$U\subset
V(\Gamma)$ with~$|U|\leq t$, the graph~$\Gamma[U]$ induced by~$U$ in~$\Gamma$
contains a vertex that belongs to at most one copy of~$H$ that is completely
contained in~$U$.  Using this fact, we may inductively colour the edges
of~$\Gamma[U]$ red and blue to show that~$\Gamma[U]\not\to (C^\ell,H)$.

\section{The construction of~$\Gamma = \Gamma^n(\ell,t,H)$}
\label{sec:construcao}
\noindent
In this section, we introduce the definition of the random graph~$\Gamma$ that
is used in the proof of Theorem~\ref{teo:secundario}, and state and prove its
relevant properties.

\subsection{The construction}
\label{sec:construction}
\noindent
Suppose we are given an integer~$\ell\geq4$ and a graph~$H\in \cal{C}(\ell)$
of order~$h\>3$.  Let~$V(\Gamma)=[n]=\{1,\dots,n\}$ and put
\begin{equation}
  \label{eq:ph}
  p_H=p_H(n)= A n^{-(h-1)+1/(\ell-1)},  
\end{equation}
where~$A$ is a positive constant to be defined later.  We consider the random
$h$-uniform hypergraph~$\cal{H}_{n,{p_H}}$ on~$[n]$, in the standard binomial
model.  Almost surely, the number of hyperedges~$e(\cal{H}_{n,p_H})$ in
$\cal{H}_{n,{p_H}}$ is 
$$
(1+o(1))({A}/{h!})n^{1+1/(\ell-1)}.
$$

Define the hypergraph~$\cal G$ from~$\cal{H}_{n,{p_H}}$ deleting one edge from
each of the hypercycles of length~$2\leq k<\ell$.  The expected number of
such hypercycles in~$\cal{H}_{n,{p_H}}$ is
\begin{multline}
  \label{eq:hypercircuitoscurtos}
  c(h,k)\binom{n}{k}\binom{n-k}{k(h-2)}{p_H}^k \asymp n^{k/(\ell-1)}\\
  \leq n=o(e(\cal{H}_{n,p_H})),  
\end{multline}
where~$c(h,k)$ is a constant that depends only on~$h$ and~$k$.  By Markov's
inequality, the number of hypercycles of length~$2\leq k<\ell$ is almost
surely~$O(n\omega)$, for any function~$\omega=\omega(n)$ such
that~$\omega\to\infty$ as~$n\to\infty$.  In particular, this number
is~$o(e(\cal{H}_{n,p_H}))$.  Therefore, we have
$$
e(\cal{G})=(1+o(1))e(\cal{H}_{n,p_H}).
$$
Now, for each hyperedge~$F\in\cG$ we arbitrarily embed a copy of~$H$
in~$F$; that is, we consider arbitrary injections
$$ 
\iota_F \: V(H) \hookrightarrow {F},
$$
for all~$F\in\cG$.

Finally, define~$\Gamma=(V,E)$ by putting~$V=[n]$ and
$$
E=\bigcup_{F\in\cG} \Big\{ \{\iota_F(x),\iota_F(y)\}\:
\{x,y\}\in E(H) \Big\}.
$$

Note that~$\Gamma$ is, roughly speaking, a union of several copies of~$H$.  It
will be important later to distinguish between two types of copies of~$H$
in~$\Gamma$.  For all~$F\in\cG$ we call the subgraph $\iota_F(H)\contido
\Gamma$ a \textit{non-spontaneous copy} of~$H$ in~$\Gamma$.  All the other
copies of~$H$ in~$\Gamma$ we call \textit{spontaneous copies}.

In the next section, we prove a few properties concerning subgraphs
of~$\Gamma$. 

\subsection{Subgraphs of~$\Gamma$}
\label{subsec:subgrafos}
\noindent
We shall use the following notation below.  We shall write~$\Gamma^{(e)}$ for
a spanning subgraph of~$\Gamma$ that has the property that each edge
of~$\Gamma^{(e)}$ may be extended to a \textit{distinct} non-spontaneous copy
of~$H$ in~$\Gamma$.  Recalling the definition of~$\Gamma$, this means that the
graph~$\Gamma^{(e)}$ admits a subhypergraph~$\cG(\Gamma^{(e)})\subset\cG$
of~$\cG$ with
$$
\cG(\Gamma^{(e)})=\{E_f\:f\in E(\Gamma^{(e)})\}
$$
and with the map~$f\in E(\Gamma^{(e)})\mapsto
E_f\in\cG(\Gamma^{(e)})\subset\cG$ injective. 

We shall now estimate that probability that~$\Gamma$ should contain a
subgraph~$\Gamma^{(e)}$ that has a fixed graph on~$[n]$ as a subgraph.  Thus,
let~$J$ be a graph on~$[n]$ with edge set~$\{e_1,\dots,e_M\}\contido
\binom{[n]}{2}$.  Suppose~$\Gamma$ admits a subgraph~$\Gamma^{(e)}$
with~$J\subset\Gamma^{(e)}$.  Then there must exist an~$M$-tuple of hyperedges
\begin{multline*}
%  \label{eq:subgrafo}
  (E_1,\dots,E_M)\in\cG^M=\cG\times\dots\times\cG\\
  \subset\cH_{n,p_H}\times\dots\times\cH_{n,p_H}
\end{multline*}
with~$e_i\in E_i$ for all~$1\leq i\leq M$ and with all the~$E_i$ distinct.
If~$X=X(\cal{H}_{n,p_H})$ is the number of such~$M$-tuples of distinct
hyperedges in~$\cal{H}_{n,p_H}$, then
$$
\esp X \< {\binom{n}{h-2}}^M{p_H}^M < (An^{-1+1/(\ell -1)})^M.
$$
Therefore, by Markov's inequality, we have
$$
\pr{}{\exists\Gamma^{(e)}\subset\Gamma\:J\contido \Gamma^{(e)}}
\leq
\esp X<{p_e}^M,
$$
where
$$
p_e=An^{-1+1/(\ell -1)}.
$$

\subsubsection{Bipartite subgraphs of~$\Gamma$}
\label{sec:bip_sgrs}
\noindent
We shall now discuss some results on~$\Gamma$ that assert that no bipartite
subgraph of~$\Gamma$ has too high a density.  The first result says that large
bipartite subgraphs of~$\Gamma$ do not induce an unexpectedly large number of
edges in~$\Gamma$.  The second result deals with bipartite subgraphs
of~$\Gamma$ on a more local scale.

\begin{propo}\label{propo:esparso}
  For all positive~$\eta$ the graph~$\Gamma$ is almost surely
  $(\eta,\mathrm{e}2e(H),p_e)$-sparse.
\end{propo}
\begin{proof}
  Suppose~$U$, $W\contido V=V(\Gamma)=[n]$ are disjoint subsets of~$V(\Gamma)$
  with cardinality $|U|=|W|=\teto{\eta n}$ such that~$e_{\Gamma}(U,W) >
  {\mathrm{e}2e(H) p_e |U||W|}$.  Then we have~$e_{\Gamma^{(e)}}(U,W) \>
  \teto{\mathrm{e}2 p_e |U||W|}$, for some~$\Gamma^{(e)}\contido \Gamma$.  The
  event that there should be~$\Gamma^{(e)}\subset\Gamma$
  with~$e_{\Gamma^{(e)}}(U,W)\geq M=\teto{\mathrm{e}2 p_e
    |U||W|}=\Omega(n^{1+1/(\ell-1)})$ has probability at most
  $$
  \binom{|U||W|}{M}{p_e}^M \< \left( \mathrm{e}
    \frac{|U||W|p_e}{M}\right)^M \< \left(\frac{1}{2} \right)^M.
  $$
  The number of disjoint subsets~$U$, $W\contido V$ with cardinality
  $\teto{\eta n}$ is smaller than~$2^{2n}$.  Therefore, the expected number of
  pairs of subsets~$(U,W)$ spanning~$>\mathrm{e}2e(H)p_e|U||W|$ edges
  of~$\Gamma$ between them is at most $2^{2n}2^{-M}=o(1)$.  Our proposition
  follows from Markov's inequality.
\end{proof}

We shall say that a graph on~$V=[n]$ is \textit{$(p_e,C,\ell)$-locally-sparse}
if, for all disjoint subsets~$U$ and~$W$ of~$V$
with~$|U|\<|W|\<(p_en)|U|\<(p_en)^{\ell-2}$, we have~$e(U,W)\<C|W|$.

\begin{propo}\label{propo:localesparso}
  Almost surely the graph~$\Gamma$ is
  $(p_e,4(\ell-1)e(H),\ell)$-locally-sparse.
\end{propo}
\begin{proof}
  We proceed as in the previous proof.  For convenience, let
  $$
  C=4(\ell-1)e(H)
  $$
  %  \quad\text{and}\quad
  and
  $$
  C'=C/e(H)=4(\ell-1).
  $$
  Note that if~$e_\Gamma(U,W)>C|W|$, then there
  is~$\Gamma^{(e)}\subset\Gamma$ with~$e_{\Gamma^{(e)}}(U,W)>C'|W|$.  If~$U$
  and~$W\subset V=[n]$ are fixed, we have
  \begin{multline*}
  \prob{\exists\Gamma^{(e)}\subset\Gamma\:e_{\Gamma^{(e)}}(U,W) > C'|W|}\\
  \<
  \binom{|U||W|}{\teto{C'|W|}}{p_e}^{\teto{C'|W|}} \< \left(
    \frac{\mathrm{e}|U|}{C'}p_e\right)^{C'|W|}.
  \end{multline*}
  By definition, we are concerned with~$U$ and~$W$
  with~$|U|\<|W|\<(p_en)|U|\<(p_en)^{\ell-2}$.  Notice that~$p_e|U| \<
  (p_en)^{\ell-2}/n \<A^{\ell-2}n^{{-1}/({\ell -1})}$.  From the fact that
  $|U|\<|W|<\lambda n$ for any~$\lambda>0$ for large enough~$n$, we conclude
  that
  $$
  \binom{n}{|U|} \< \binom{n}{|W|}
  $$
  and, therefore,
  $$
  \binom{n}{|U|}\binom{n}{|W|} \< \binom{n}{|W|}^2.
  $$
  These inequalities imply that the expected number of
  pairs~$(U,W)$ with~$U$ and~$W$ of cardinalities~$u$ and~$w$ such
  that
  $$
  u\<w\<(p_en)u\<(p_en)^{\ell-2}
  $$
  and such that~$e_{\Gamma}(U,W)>Cw$ is smaller than
  $$
  \sum_{1\leq w<\lambda n}\sum_{1\leq u\leq w}
  \binom{n}{u}\binom{n}{w}\left( \frac{\mathrm{e}}{C'}\cdot{p_eu}
  \right)^{C'w},
  $$
  which is at most
  \[
  \begin{split}
    &\sum_{1\leq w<\lambda n}w\binom{n}{w}^2
    \left(\frac{\mathrm{e}}{C'}A^{\ell-2}n^{{-1}/({\ell-1})}\right)^{C'w} \\
    &\quad\<\sum_{1\<w<\lambda n}w
    \left(\frac{\mathrm{e}n}{w}\right)^{2w} \left( \frac{\mathrm{e}}{C'}
      A^{\ell-2}n^{{-1}/({\ell-1})}\right)^{C'w} \\
    &\quad=\sum_{1\<w<\lambda n} \frac{w}{w^{2w}}\left(
      \frac{\mathrm{e}^{1+2/C'}}{C'}A^{\ell-2}
      n^{(2/C') - (1/(\ell -1))}\right)^{C'w}\\
    &\quad\leq\sum_{1\<w<\lambda n}\left( \frac{\mathrm{e}^{1+{2}/C'}}{C'}
      A^{\ell-2} n^{{-2}/{C'}}\right)^{C'w}\\
    &\quad=o(1).
  \end{split}
  \]
  Our result follows from Markov's inequality.
\end{proof}

\subsubsection{$\mathbf{V}^{(m)}$-subgraphs of~$\Gamma$}
\label{sec:V-sgrs}
\noindent
Suppose a constant~$\rho >0$ is fixed, and suppose~$\alpha>0$ is a constant
with 
$$
\alpha\leq{\rho \ell\over\mathrm{e}^2(\ell+2)}.
$$
Put
$$
C=4(\ell-1)e(H)
\quad\text{and}\quad
D=\mathrm{e}2e(H),
$$
and fix~$k_0 \in \N$.  Let~$\eps$, $B_0$, and~$m_0$ be the constants whose
existence is guaranteed by Lemma~\ref{le:contagem} for the constants above,
and let~$\eta$ and~$K_0$ be the constants given by Lemma~\ref{le:yoshi} for
these values of~$\epsilon$, $D$, and~$k_0$.  Recall we
write~$\mathbf{V}^{(m)}$ for a vector~$(V_i)_{i=1}^{\ell}$ of pairwise
disjoint, $m$-element subsets of~$V(\Gamma)=[n]$.  Recall~$p_e=An^{-1+1/(\ell
  -1)}$.

\begin{propo}
  Suppose~$A\>2B_0 K_0$.  Then almost surely~$\Gamma$ has the following
  property.  If~$\mathbf{V}^{(m)}$ and~$\Gamma^{(e)}\subset\Gamma$ are such
  that
  $$
  m\geq{n\over2K_0}
  $$
  and the pairs~$(V_i,V_{i+1})$ are~$(\eps, \Gamma^{(e)}, p_e )$-regular of
  density at least~$\rho $ for all~$1\leq i\leq\ell$,
  then~$\Gamma^{(e)}[\bfV^{(m)}]$ spans a~$C^{\ell}$.
\end{propo}
\begin{proof}
  We shall make use of Lemma~\ref{le:contagem} and
  Propositions~\ref{propo:esparso}~and~\ref{propo:localesparso}.  Let~$B$ be
  such that
  $$
  p_e=Bm^{-1+1/(\ell-1)}.
  $$
  Let~$\mathbf{V}^{(m)}$ and~$\Gamma^{(e)}$ be as in the statement of our
  proposition. 
  
  By the choices of~$B$, $C$, and~$D$, and by
  Propositions~\ref{propo:esparso}~and~\ref{propo:localesparso}, we may and
  shall suppose that $\Gamma^{(e)}[\mathbf{V}^{(m)}]$ is an
  $(\eps,\rho ,{B},C,D;\mathbf{V}^{(m)},M)$-graph, where~$M$ is at least
  $\rho p_em^2\ell$.
  
  Now notice that 
  \begin{multline*}
    B=p_e m^{1-1/(\ell-1)}=A(m/n)^{1-1/(\ell-1)}\\
%    \geq2B_0K_0(m/n)^{1-1/(\ell-1)}\\
    >B_0(2K_0m/n)^{1-1/(\ell-1)} \> B_0,
  \end{multline*}
  where the last inequality comes from~$m\geq n/2K_0$.  Note that if~$n$ is
  sufficiently large, then~$m\>m_0$, where~$m_0$ is as in
  Lemma~\ref{le:contagem}.  %We may therefore apply Lemma~\ref{le:contagem}. 
  
  By Lemma~\ref{le:contagem}, the expected number of
  $(\eps,\rho ,{B},C,D;\mathbf{V}^{(m)},M)$-subgraphs in~$\Gamma^{(e)}$ that
  contains no cycle of length~$\ell$ is, for a fixed~$\bfV^{(m)}$, at most
  \begin{multline*}
%    \label{eq:V_fixed}
%    \quad
    \alpha^M \binom{(\ell+2)m^2}{M} {p_e}^M\\
    \<\left(\alpha\frac{\mathrm{e}(\ell+2) m^2}{M}{p}_e\right)^M
    \< \left(\frac{\mathrm{e}\alpha(\ell+2)}{\ell\rho }\right)^M \\
    = \left(\frac{\mathrm{1}}{\mathrm{e}} \right)^M
    \< \exp\left\{ - \rho p_em^2\ell\right\}.
  \end{multline*}
  Summing over all choices for~$\bfV^{(m)}$, we deduce that the expected
  number of $(\eps,\rho ,{B},C,D;\mathbf{V}^{(m)},M)$-subgraphs
  of~$\Gamma^{(e)}$ with no~$C^\ell$, where~$\bfV^{(m)}$ is arbitrary, is
  \begin{multline*}
  \leq{n}^{\ell m}\exp\left\{-\rho p_em^2\ell\right\}\\
  \<\exp\left\{(\log n)m\ell-\rho p_em^2\ell\right\}
  =o(n^{-3}),
  \end{multline*}
  for all integers~$m$ and~$M\>\rho p_em^2\ell$.  Summing over all choices
  for $1\leq m\leq n$ and~$1\leq M\leq\binom{n}{2}$, we have a factor of at
  most~$n^3$.  Therefore, our result follows by Markov's inequality.
\end{proof}

For technical reasons that will become clear only when we prove
that~$\Gamma\to(C^\ell,H)$ holds almost surely, we shall need to know the
number of certain edges that occur in induced~$h$-partite subgraphs
of~$\Gamma$.

We shall write~$\bfW^{(m)}$ for $h$-tuples~$(W_i)_{i=1}^h$ of pairwise
disjoint sets of vertices of~$\Gamma$, each of cardinality~$m$.

\begin{propo}\label{propo:arestas}
  Suppose~$A \> (h+1)/\mathrm{e}^h$.  For all
  $\mathbf{W}^{(m)}=(W_{j})_{j=1}^h$ with $n/\log n\leq m\leq n/h$, the
  $h$-partite subgraph of~$\Gamma$ induced by~$\mathbf{W}^{(m)}$ almost surely
  spans at least
  $$
  \frac14e(H)m^hp_H
  $$
  edges that may be extended to
  non-spontaneous copies of~$H$ in~$\Gamma$ with all its vertices
  within
  $$
  U=\bigcup_{1\leq j\leq h} W_j.
  $$
\end{propo}
\begin{proof}
  Fix the~$h$-tuple~$\bfW=\bfW^{(m)}=(W_{j})_{j=1}^h$ of pairwise disjoint
  subsets of vertices of~$\Gamma$ of cardinality~$m$ each and let
  $U=\bigcup_{j=1}^{h}W_j$ be as in the statement of our proposition.  Define
  the random variable~$X_\bfW$ as the number of hyperedges in~$\cH_{n,p_H}$
  with exactly one vertex from each~$W_i$.
  
  The expectation of~$X_\bfW$ is~$\esp{X_\bfW}={m}^{h}p_H$.
%  portanto,
%  $$
%  \left(\frac{m}{n}\right)^{h-1-1/(\ell -1)}
%  \<\frac{\esp{X_\bfW}}{Am^{1+1/(\ell -1)}} \<
%  \mathrm{e}^h\left(\frac{m}{n}\right)^{h-1-1/(\ell -1)}.
%  $$
% 
  Using Chernoff's inequality we have
  \begin{align*}
  &\prob{X_\bfW \< \frac{1}{2}\esp{X_\bfW}}\\ 
  &\qquad\qquad\<\exp \left\{-{1\over8}\esp{X_\bfW}\right\} \\
  &\qquad\qquad\<\exp \left\{ {-\frac{A}{8} m^h n^{-h+1+1/(\ell-1)}} \right\}\\
  &\qquad\qquad\<\exp \left\{ {-\frac{A}{8} \left(\frac{n}{\log n}\right)^{h} 
  {n}^{-h+1+1/(\ell-1)}} \right\} \\
  &\qquad\qquad\<\exp\left\{-\frac{An^{1+1/(\ell-1)}}{8(\log n)^h}\right\},    
  \end{align*}
  and, as the number of choices for~$\bfW=\bfW^{(m)}=(W_{j})_{j=1}^h$ is at
  most~$2^{hn}$, the probability that there should exist~$\bfW$ such that
  $X_\bfW\<(1/2)\esp{X_\bfW}$ is smaller than
  $$
%  \exp \left\{ hn -
%  \frac{A}{8}m^{1+1/(\ell-1)}\left(\frac{m}{n}\right)^{h-1-1/(\ell-1)}\right\} 
  \exp \left\{ \left(h - \frac{An^{1/(\ell-1)}}{8(\log n)^h}\right)n\right\}
  =o(1).
  $$
  That is, almost surely~$X_\bfW > (1/2)\esp{X_\bfW}$.
  
  The number of hyperedges deleted from~$\cal{H}_{n,p_H}$ to get rid of short
  hypercycles is~$O(n\omega)$, for any function~$\omega=\omega(n)\to\infty$
  as~$n\to\infty$.  Therefore the number of hyperedges induced by~$\bfW$
  in~$\cG$ is almost
  surely~$\geq(1/2)\esp{X_\bfW}-O(n\omega)\>(1/4)\esp{X_\bfW}$.  Each such
  hyperedge gives~$e(H)$ edges of~$\Gamma$.  Notice that, in fact, all these
  edges we have just considered are edges that \textit{extend to
    non-spontaneous copies of~$H$ in~$\Gamma$ within~$U$}, as required in our
  proposition.  This completes the proof of our result.
%   As the hyperedges form edge-disjoint copies of~$H$ we have
%   more than~$(1/4)e(H)\esp{X_\bfW}$ edges induced by~$U$ in~$\Gamma$.
\end{proof}

\subsubsection{Small subgraphs of~$\Gamma$}
\label{sec:small_sgrs}
\noindent
Given a vertex~$v\in V=[n]$, the number of hyperedges of~$\cal{G}$ that
contain the vertex~$v$ will be called the \textit{hyperdegree} of~$v$
in~$\cal{G}$, and will be denoted by~$d_\cal{G}(v)$.  Let us denote
by~$\cal{G}[U]$ the sub-hypergraph of~$\cal{G}$ induced by~$U\contido[n]$.
Thus, $\cG[U]=\{E\in\cG\: E\subset U\}$.

\begin{propo}\label{propo:grau}
  Let~$t$ be any fixed positive integer.  Then almost surely every subset~$U
  \contido V=[n]$ with~$|U|\leq t$ contains a vertex~$v$ whose hyperdegree
  in~$\cH_{n,p_H}$, and hence in~$\cG$, is at most~$1$, that is,
  $d_{\cal{G}[U]}(v)\leq d_{\cH_{n,p_H}[U]}\<1$.
\end{propo}
\begin{proof}
  Let~$U\contido V$ be a subset of cardinality~$u$.  If~$U$ induces~$m$
  hyperedges and all vertices in~$U$ have hyperdegree at least~$2$,
  then~$m\>2u/h$.  Thus
  \begin{align*}
    &\prob{d_{\cH_{n,p_H}[U]}(v)\geq2\text{ all }v\in U}\\
    &\qquad\qquad\qquad\leq\prob{m\>\frac{2u}{h}}\\
    &\qquad\qquad\qquad\<\binom{\binom{u}{h}}{\teto{2u/h}}{p_H}^{\teto{2u/h}}\\
    &\qquad\qquad\qquad=O\(n^{-2u+(2u/h)\left(1+1/(\ell-1)\right)}\).
  \end{align*}
  Therefore, the probability that there should exist a subset~$U\subset V$
  violating our condition is
  \begin{multline}
    \label{eq:bad_Us}
    \binom{n}{u}O\(n^{-2u+(2u/h)\left(1+1/(\ell-1)\right)}\)\\
    =O\(n^{-u+(2u/h)\left(1+1/(\ell-1)\right)}\).    
  \end{multline}
  As~$\ell\geq4$, the quantity in~\eqref{eq:bad_Us} is~$o(1)$ for
  all~$h\geq3$.  Hence such a set~$U$ almost surely does not exist, and our
  result follows.
\end{proof}

\section{Proof of Theorem~\ref{teo:secundario}}
\label{sec:the_proof}
\noindent
Suppose we are given integers~$\ell\geq4$ and~$t\>1$ and a graph~$H\in
\cal{C}(\ell)$ of order~$h\geq3$.  In our proof, we shall need a number of
constants given by Lemmas~\ref{le:yoshi}, \ref{le:contagem},
and~\ref{QRamsey}.  First, let
\[  
k_0 = k_0 (K^2,C^{\ell},K^h) \; \mathrm{\ and\ } \;  c =
c(K^2,C^{\ell},K^h)
\]
be the constants given by Lemma~\ref{QRamsey}.  Set
$$
  \rho     = \frac{c}{2^{h+2}},\quad
  \alpha   = \frac{\rho \ell}{\mathrm{e}^2(\ell+2)},\quad
  C        = 4(\ell-1)e(H),
$$
and
$$
D        = \mathrm{e}2e(H).
$$
Next, let
$$
\eps =\eps(\ell,\alpha,\rho ,C,D),
\qquad
B_0=B_0(\ell,\alpha,\rho ,C,D),
$$
and 
$$
m_0=m_0(\ell,\alpha,\rho ,C,D)
$$
be the constants whose existence is guaranteed by Lemma~\ref{le:contagem},
and let
\begin{eqnarray*}
  \eta=\eta(\eps,k_0,D)\;\mathrm{\ and \ }\;  K_0=K_0(\eps,k_0,D) 
\end{eqnarray*}
be the constants given by Lemma~\ref{le:yoshi}.  We may assume that~$\eps
<\mathrm{min}\{1/2,2c\}$.  Finally, let
$$
A = \max\left\{2B_0 K_0, (h +1){\mathrm{e}^{-h}} \right\}.
$$

We now consider a certain family~$\cF=\cF(H)$ of graphs~$\Gamma$ on~$V=[n]$.
First of all, our graphs~$\Gamma$ may be written as a union of~$M$ copies
of~$H$, say~$H_1,\dots,H_M$, with~$M\asymp {n\choose h}p_H$ and with any two
distinct~$H_i$ sharing at most one vertex.  In fact, for each~$\Gamma$ in our
family, we \textit{single out a specific family}~$H_i$ ($1\leq i\leq M$), and
refer to these~$H_i$ as \textit{non-spontaneous} copies of~$H$ in~$\Gamma$.
All other copies of~$H$ in~$\Gamma$ are said to be \textit{spontaneous}.
Furthermore, our graphs~$\Gamma=\bigcup_{1\leq i\leq M}H_i\in\cF=\cF(H)$
satisfy the following properties:
\begin{enumerate}
  \renewcommand{\labelenumi}{(P\arabic{enumi})}
  \label{propriedades}
\item the hypergraph on~$V=[n]$ given by
  $$
  \cG=\{V(H_i)\:1\<i\<M\}
  $$
  has girth~$\ell$;
\item $\Gamma$~is~$(\eta,D,p_e)$-sparse and~$(p_e,C,\ell)$-locally-sparse;
\item for all~$\mathbf{V}^{(m)}=(V_1,\dots,V_{\ell})$, where
  $n/2K_0\<m\<n/k_0$, if $\Gamma^{(e)}\contido \Gamma[\mathbf{V}^{(m)}]$ is
  such that the pairs~$(V_i,V_{i+1})$ are~$(\eps,\Gamma^{(e)},p_e)$-regular of
  $p_e$-density at least~$\rho $ for all~$1\leq i\leq\ell$,
  then~$\Gamma^{(e)}$ contains~$C^\ell$;
\item every~$\mathbf{W}^{(m)}=(W_1,\dots,W_{h})$ with~$m\>n/\log n$ induces 
  $$
  \geq{1\over4}e(H)m^hp_H
  $$
  edges of~$\Gamma$ that may be extended to non-spontaneous copies~$H_i$
  of~$H$ within
  $$
  U=\bigcup_{1\leq j\leq h}W_j;
  $$
\item all~$U\contido V=[n]$ with~$t$ vertices contains a vertex~$v_U$ that
  belongs to at most one non-spontaneous copy~$H_i$ of~$H$ such
  that~$V(H_i)\contido U$.
\end{enumerate}

By Propositions~\ref{propo:esparso}--\ref{propo:grau} in
\S\ref{subsec:subgrafos}, the family~$\cF=\cF(H)$ is not empty.  The fact
that~$H$ belongs to~$\cal{C}(\ell)$ together with~(P1) imply the following
additional property, whose proof is postponed to \S\ref{sec:negativa}.
\begin{enumerate}\renewcommand{\labelenumi}{(P\arabic{enumi})}
  \setcounter{enumi}{5}
\item $\Gamma$~does not contain spontaneous copies of~$H$.
\end{enumerate}
Let us fix a graph~$\Gamma$ in~$\cF=\cF(H)$.  We claim that this choice
for~$\Gamma$ will do in Theorem~\ref{teo:secundario}.  We prove this claim
in~\S\S\ref{sec:+_statement} and~\ref{sec:inducao} below.

\subsection{Proof of~${\Gamma}\to (C^{\ell},H)$} 
\label{sec:+_statement}
\noindent
Let~$\Gamma^{(e)}$ be the spanning subgraph of~$\Gamma$ defined by colouring
{red} exactly one edge from each non-spontaneous copy~$H_i$ ($1\leq i\leq M$)
of~$H$ in~$\Gamma$.  We shall show that~$\Gamma^{(e)}$ contains a
cycle~$C^{\ell}$.  This clearly proves that~$\Gamma\to(C^\ell,H)$.

By~(P2) we know that~$\Gamma^{(e)}$ is~$(\eta, D, p_e)$-sparse. Applying
Lemma~\ref{le:yoshi} we get an~$(\epsilon,k,\Gamma^{(e)},p_e)$-regular
partition~$\Pi=\big(V_0,V_1,\dots,V_{k}\big)$ with~$k_0\leq k\leq K_0$.
Denote by~$m$ the common cardinality of the~$V_i$ ($1\leq i\leq k$).  We have
$$
{n\over2K_0}\leq{n\over2k}\leq m\leq{n\over k}\leq{n\over k_0}.
$$
Let~$K^k$ be the complete graph on~$V(K^k)=\{V_1,\dots,V_k\}$, and consider
the following~$3$-colouring of the edges of~$K^k$:
\begin{itemize}
\item[(\textit{a})] colour~$\{V_i,V_j\}$ with~$1$ if~$(V_i,V_j)$ is not
  $\eps$-regular,
\item[(\textit{b})] colour~$\{V_i,V_j\}$ with~$2$ if~$(V_i,V_j)$ is
  $\epsilon$-regular of density~$\geq\rho $,
\item[(\textit{c})] colour~$\{V_i,V_j\}$ with~$3$ if~$(V_i,V_j)$ is
  $\epsilon$-regular of density~$<\rho $.
\end{itemize}
Since~$k\>k_0$, we have by Lemma~\ref{QRamsey} that in this colouring of~$K^k$
there must be
\begin{enumerate}\renewcommand{\labelenumi}{(\textit{\roman{enumi}})}
\item at least~$ck^2$      copies of  $K^2$      with all edges of colour  $1$, or
\item at least~$ck^{\ell}$ copies of  $C^{\ell}$ with all edges of colour  $2$, or
\item at least~$ck^h$      copies of  $K^h$      with all edges of colour  $3$.
\end{enumerate}
Note that~(\textit{i}) cannot hold, because the number of pairs that are not
$\eps$-regular is~$\leq\eps\binom{k}{2}\<2c\binom{k}{2}<ck^2$.
If~(\textit{ii}) holds, any~$C^\ell \contido K^k$ of colour~$2$ determines a
vector, say $\bfV^{(m)}=(V_i)_{i=1}^{\ell}$, of pairwise disjoint subsets of
vertices of~$\Gamma$ such that, according to~(P3), will happily give us
a~$C^\ell\contido \Gamma^{(e)}$.  Let us suppose that~(\textit{iii}) holds and
let us derive a contradiction.  This will then force~(\textit{ii}) to hold,
completing our proof.

The number of edges in~$\Gamma^{(e)}$ that belong to
the~$E_{\Gamma^{(e)}}(V_i,V_j)$ that correspond to colour~$3$ edges from~$K^k$
is
\begin{multline}
  \label{eq:upbd}
  \sum\Big\{e_{\Gamma^{(e)}}(V_i,V_j)
  \:\{V_i,V_j\}\in E(K^k)\text{ of colour }3\Big\}\\
  <\binom{k}{2} \rho p_e m^2 \leq \binom{k}{2} \rho  p_e
  \left(\frac{n}{k}\right)^2\\
  <{1\over2} \rho A n^{1+{1}/(\ell-1)} < \frac{c}{2^{h+3}}A
  n^{1+{1}/(\ell-1)}.
\end{multline}
On the other hand, by~(\textit{iii}), we have at least~$ck^h$ copies of~$K^h$
that are monochromatic of colour~$3$ in~$K^k$.  Fix one such~$K^h$, and
let~$J$ be the $h$-partite subgraph of~$\Gamma$ naturally associated with
this~$K^h$.  Each vertex class of~$J$ has~$m\>n/2K_0\>n/\log n$ vertices.

By Property~(P4), we know that~$J$ spans~$\geq(1/4)e(H)m^hp_H$ edges that may
be extended to non-spontaneous copies of~$H$ within~$V(J)$.  Therefore, we
have~$\geq(1/4)m^hp_H$ non-spontaneous copies of~$H$ within~$J$, and hence we
have~$\geq(1/4)m^hp_H$ edges from~$\Gamma^{(e)}$ within~$J$.  Finally, note
that if we have two distinct~$K^h$ monochromatic of colour~$3$ in~$K^k$, then
each `contributes' with~$\geq(1/4)m^hp_H$ distinct edges in our edge count
for~$\Gamma^{(e)}$.  Indeed, this comes from our somewhat peculiar definition
of the edges that are counted in~(P4), and the fact that any two
non-spontaneous copies~$H_i$ of~$H$ in~$\Gamma$ have no common edges. 

Since we have~$\geq ck^h$ copies of~$K^h$ that are monochromatic of colour~$3$
in~$K^k$, we have at least
\begin{multline}
  \label{eq:lwbd}
  ck^h\frac{1}{4}m^hp_H \> ck^h \frac{1}{4} \left(\frac{n}{2k}\right)^h
  An^{-h+1+1/(\ell-1)}\\
  \> \frac{c}{2^{h+2}}An^{1+1/(\ell-1)}
\end{multline}
edges that belong to the~$E_{\Gamma^{(e)}}(V_i,V_j)$ that correspond to
colour~$3$ edges from~$K^k$.  However, inequalities~\eqref{eq:upbd}
and~\eqref{eq:lwbd} contradict each other, and hence we may conclude
that~(\textit{iii}) cannot hold.  This completes our proof of the fact
that~$\Gamma\to(C^\ell,H)$.

\subsection{Proof of~$\Gamma \not\rightarrow_t (C^{\ell},H)$}%
\label{sec:inducao}
\noindent
In this section we prove, by induction in~$|U|$, that any induced subgraph
$\Gamma[U]$ on at most~$t$ vertices is not Ramsey for the pair~$(C^\ell,H)$.
Let $U\contido V=[n]$.  If~$|U|<\max\{\ell,h\}$ then, clearly,
$\Gamma[U]\not\to (C^\ell,H)$.

Let us suppose that~$\max\{\ell,h\}\leq|U|\leq t$ and that in any
subset~$U'\subset V$ of smaller cardinality the induced subgraph is not Ramsey
for the pair~$(C^\ell,H)$.  By~(P5) there exists a vertex~$v_U$ that belongs
to at most one non-spontaneous copy~$H_i$ of~$H$ in~$\Gamma$ such that
$V(H_i)\contido U$; for convenience, let~$H_{i_0}$ be this~$H_i$ if it exists.
Now, fix a red-blue edge-colouring of~$\Gamma[U\setminus\{v_U\}]$ with neither
a red copy of~$C^\ell$ nor a blue copy of~$H$.  Such a colouring exists by the
induction hypothesis.

Colouring red only one edge~$e$ incident to~$v_U$ does not create a
red~$C^\ell$ in~$\Gamma[U]$.  The other edges incident to~$v_U$ we colour
blue.  Note that we may choose the edge~$e$ in such a way that we do not
create a blue copy of~$H$: it suffices to pick~$e$ from~$H_{i_0}$ (if it
exists; otherwise the choice is arbitrary).  With this choice, if we do create
a blue copy of~$H$ in~$\Gamma[U]$, then we must have a spontaneous copy of~$H$
in~$\Gamma[U]\subset\Gamma$.  However, spontaneous copies of~$H$ do not exist
by~(P6) and hence we have indeed found a colouring of~$\Gamma[U]$ without a
red~$C^\ell$ and without a blue~$H$.  This completes the induction step and
the proof is complete.

\subsection{On the property~(P6)}
\label{sec:negativa}
\noindent
Let us consider a graph~$\Gamma=\bigcup_{1\leq i\leq M}H_i$ in the
family~$\cF=\cF(H)$, with~$H\in\cC(\ell)$.  We wish to show that~$\Gamma$ does
not contain spontaneous copies of~$H$.  We shall deduce this from~(P1) in the
definition of the family~$\cF=\cF(H)$.  The reader will see that this is not
particularly difficult to prove, but we shall present a detailed proof.

The proof is by contradiction.  Suppose~$\widetilde{H}$ is a spontaneous copy
of~$H$ in~$\Gamma$.  Let~$\tE=V(\tH)$ and~$E_i=V(H_i)$ ($1\leq i\leq M$).
Recall that~(P1) states that the hypergraph~$\cG=\{E_i\:1\leq i\leq M\}$ has
girth~$\ell$.  Note that this implies that all the~$H_i$ are induced subgraphs
of~$\Gamma$, as~$\ell>2$.  Since~$\tH$ is spontaneous, it follows
that~$\tE\not\in\cG$.

Below, we shall often use the following fact: if~$e$ is an edge
of~$\Gamma=\bigcup_{1\leq i\leq M}H_i$, then~$e\in E(H_i)$ for a uniquely
determined index~$1\leq i=i(e)\leq M$.  Clearly, the uniqueness of~$i=i(e)$
follows from the fact that~$\cG$ is a linear hypergraph.

We shall call a cycle~$C$ in~$\tH$ \textit{useful} if it has edges in at least
two distinct~$H_i$~$(1\leq i\leq M)$.

\begin{claim}
  \label{claim:cycle}
  The graph~$\tH$ contains a useful cycle.
\end{claim}
\begin{proof}
  Let~$x\in\tE$ be an arbitrary vertex in~$\tE=V(\tH)$, and let~$e=\{x,x'\}$
  be an edge of~$\tH$ incident to~$x$.  Let~$1\leq i_0=i_0(e)\leq M$ be such
  that~$e\in E(H_{i_0})$.  We cannot have~$\tE\subset
  E_{i_0}=V(H_{i_0})\in\cG$.  Let~$y\in\tE\setminus E_{i_0}$, and
  let~$f=\{y,y'\}$ be an edge of~$\tH$ incident to~$y$.  There is a
  unique~$1\leq j_0=j_0(f)\leq M$ with~$f\in E(H_{j_0})$.  Clearly, $j_0\neq
  i_0$.
  
  As~$H$ is~$2$-connected, the edges~$e=\{x,x'\}\in E(H_{i_0})$
  and~$f=\{y,y'\}\in E(H_{j_0})$ lie on a cycle of~$\tH$.  Thus~$\tH$ contains
  a cycle that has edges in distinct~$H_i$, as claimed.
\end{proof}

Let us now observe that any useful cycle~$C\subset\tH$ may be written as a
concatenation of~$q=q(C)\geq2$ paths~$P_1,\dots,P_q$ such that
\begin{enumerate}
\item[(\textit{i})]each~$P_i$ ($1\leq i\leq q$) has at least one edge,
\item[(\textit{ii})]each~$P_i$ ($1\leq i\leq q$) is contained in an~$H_j$,
  where~$j=j(i)$ is uniquely determined,
\item[(\textit{iii})]we have~$j(i-1)\neq j(i)$ for all~$1\leq i\leq q$, where
  the indices~$i$ are taken modulo~$q$.
\end{enumerate}
Let~$C_0\subset\tH$ be a useful cycle of minimal length, and put~$q_0=q(C_0)$.

Recall that we write~$E_j$ for~$V(H_j)\in\cG$ ($1\leq j\leq M$).  Consider the
cyclic sequence~$E_{j(1)},\dots,E_{j(q_0)}$ of hyperedges of~$\cG$ determined
by~$C_0$ (see~(\textit{ii}) above).  A moment's thought now shows that there
must be a segment of this sequence with~$q'$ elements ($2\leq q'\leq q_0$)
that forms a hypercycle in~$\cG$.  Since~$\cG$ has girth~$\ell$, we
have~$q_0\geq q'\geq\ell$.  Because of~(\textit{i}) above, we have that~$C_0$
has length~$\geq q_0\geq\ell$.

We now use the definition of the family~$\cC(\ell)$ and the fact
that~$\tH\in\cC(\ell)$ to deduce that the cycle~$C_0\subset\tH$ must have a
chord, say~$c\in E(\tH)$.  This chord~$c$ belongs to some~$H_i$ ($1\leq i\leq
M$), say~$H_{i(c)}$.  Recall~$C_0$ is a useful cycle, and let~$i(1)\neq i(2)$
be such that~$C_0$ contains edges from both~$H_{i(1)}$ and~$H_{i(2)}$.
Adjusting the notation, we may further assume that~$i(c)\neq i(1)$.

Let~$C_1$ and~$C_2$ be the two cycles sharing the chord~$c$ that together
form~$C_0+c$.  By adjusting the notation again, we may assume that there is an
edge of~$H_{i(1)}$ in~$C_1$.  Since~$c\in E(C_1)\cap E(H_{i(c)})$
and~$i(c)\neq i(1)$, the cycle~$C_1\subset\tH$ is useful.  As~$C_1$ is shorter
than~$C_0$, we have a contradiction to the choice of~$C_0$.  This
contradiction shows that no spontaneous copy of~$H$ may occur in~$\Gamma$, and
our proof is complete.

\section{Concluding remarks}
\label{sec:concluding}
\noindent
Our proof of the fact that the Ramsey property~$\Gamma \to (C^\ell,H)$ holds
almost surely follows~\cite{MR99g:05159} closely, although the random
graph~$\Gamma$ presents some different technical difficulties
(in~\cite{MR99g:05159}, Ramsey properties of the usual binomial random
graph~$G_{n,p}$ are investigated).  The construction of~$\Gamma$ has already
been used to prove Ramsey type results for orderings and vertex colourings
(see, e.g., Ne\v set\v ril and R\"odl~\cite{MR80a:05158}).

The strong assumption given by property~(P6) was crucial in our proof of the
fact that~$\Gamma \not\to_t (C^\ell,H)$ holds almost surely.  It was in
fact~(P6) that led us to restrict~$H$ to $2$-connected graphs without long
induced cycles.  It would be very interesting to drop this hypothesis on long
cycles, or at least find further natural, weaker conditions that ensures~(P6)
given that~(P1) holds.  

Going in another direction, we mention that Burr, Faudree, and
Schelp~\cite{MR87f:05118} proved that~$(G,H)$ is Ramsey-infinite if all the
pairs~$(G_i,H_j)$ are Ramsey-infinite, where the~$G_i$ are the blocks of~$G$
and the~$H_j$ are the blocks of~$H$.

We close by mentioning that we have in fact proved a stronger Ramsey property
for~$\Gamma$.  Indeed, we proved that, almost surely, $\Gamma$~is such that,
in any colouring of its edges with red and blue, either there is an
induced~$C^\ell$ all the edges of which are coloured red, or else there is an
induced copy of~$H$ all the edges of which are coloured blue.  Therefore, we
have proved that the pair~$(C^\ell,H)$ is what is called
\textit{strong-Ramsey-infinite}.  This concept has been investigated in
Burr~\cite{MR87m:05126}, Burr, Faudree, and Schelp~\cite{MR87f:05118}, and
Ne\v set\v ril and R\"odl~\cite{MR80c:05102}, among others.


\section{Acknowledgements}
\label{sec:ack}
\noindent
The authors are grateful to the referee for his or her comments.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%References
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{MR87m:05126}
Stefan~A. Burr, \emph{Some {R}amsey-infinite graphs in the diagonal case}, Ars
  Combin. \textbf{21} (1986), 173--178. \MR{87m:05126}

\bibitem{MR83c:05092}
Stefan~A. Burr, Paul Erd{\H{o}}s, Ralph~J. Faudree, Cecil~C. Rousseau, and
  Richard~H. Schelp, \emph{Ramsey-minimal graphs for matchings}, The theory and
  applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, 1981,
  pp.~159--168. \MR{83c:05092}

\bibitem{MR80m:05081}
Stefan~A. Burr, Paul Erd{\H{o}}s, Ralph~J. Faudree, and Richard~H. Schelp,
  \emph{A class of {R}amsey-finite graphs}, Proceedings of the Ninth
  Southeastern Conference on Combinatorics, Graph Theory, and Computing
  (Florida Atlantic Univ., Boca Raton, Fla., 1978) (Winnipeg, Man.), Utilitas
  Math., 1978, pp.~171--180. \MR{80m:05081}

\bibitem{MR87f:05118}
Stefan~A. Burr, Ralph~J. Faudree, and Richard~H. Schelp, \emph{On graphs with
  {R}amsey-infinite blocks}, European J. Combin. \textbf{6} (1985), no.~2,
  129--132. \MR{87f:05118}

\bibitem{MR92i:05151}
Ralph Faudree, \emph{Ramsey minimal graphs for forests}, Ars Combin.
  \textbf{31} (1991), 117--124. \MR{92i:05151}

\bibitem{MR97m:05134}
Ralph~J. Faudree, Cecil~C. Rousseau, and Richard~H. Schelp, \emph{Problems in
  graph theory from {M}emphis}, The mathematics of Paul Erd\H os, II, Springer,
  Berlin, 1997, pp.~7--26. \MR{97m:05134}

\bibitem{MR99g:05145}
Y.~Kohayakawa, \emph{Szemer\'edi's regularity lemma for sparse graphs},
  Foundations of computational mathematics (Rio de Janeiro, 1997), Springer,
  Berlin, 1997, pp.~216--230. \MR{99g:05145}

\bibitem{MR99g:05159}
Y.~Kohayakawa and B.~Kreuter, \emph{Threshold functions for asymmetric {R}amsey
  properties involving cycles}, Random Structures Algorithms \textbf{11}
  (1997), no.~3, 245--276. \MR{99g:05159}

\bibitem{MR95b:05149}
Tomasz {\L}uczak, \emph{On {R}amsey minimal graphs}, Electron. J. Combin.
  \textbf{1} (1994), Research Paper 4, approx.\ 4 pp.\ (electronic).
  \MR{95b:05149}

\bibitem{MR54:173}
Jaroslav Ne{\v{s}}et{\v{r}}il and Vojt{\v{e}}ch R{\"o}dl, \emph{Partitions of
  vertices}, Comment. Math. Univ. Carolinae \textbf{17} (1976), no.~1, 85--95.
  \MR{54 \#173}

\bibitem{MR80a:05158}
\bysame, \emph{On a probabilistic graph-theoretical method}, Proc. Amer. Math.
  Soc. \textbf{72} (1978), no.~2, 417--421. \MR{80a:05158}

\bibitem{MR80c:05102}
\bysame, \emph{The structure of critical {R}amsey graphs}, Acta Math. Acad.
  Sci. Hungar. \textbf{32} (1978), no.~3-4, 295--300. \MR{80c:05102}

\bibitem{MR95b:05150}
Vojt{\v{e}}ch R{\"o}dl and Andrzej Ruci{\'n}ski, \emph{Lower bounds on
  probability thresholds for {R}amsey properties}, Combinatorics, Paul Erd\H os
  is eighty, Vol.\ 1, J\'anos Bolyai Math. Soc., Budapest, 1993, pp.~317--346.
  \MR{95b:05150}

\bibitem{MR96h:05141}
\bysame, \emph{Threshold functions for {R}amsey properties}, J. Amer. Math.
  Soc. \textbf{8} (1995), no.~4, 917--942. \MR{96h:05141}

\bibitem{MR1798082}
Marcus Schaefer, \emph{Graph {R}amsey theory and the polynomial hierarchy
  (extended abstract)}, Annual ACM Symposium on Theory of Computing (Atlanta,
  GA, 1999), ACM, New York, 1999, pp.~592--601 (electronic). \MR{1 798 082}

\bibitem{MR2002a:68049}
\bysame, \emph{Graph {R}amsey theory and the polynomial hierarchy}, J. Comput.
  System Sci. \textbf{62} (2001), no.~2, 290--322, Special issue on the
  Fourteenth Annual IEEE Conference on Computational Complexity (Atlanta, GA,
  1999). \MR{2002a:68049}

\end{thebibliography}
\end{document}
