\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsthm,amsmath,amssymb}
\usepackage{verbatim}

\newtheorem{theorem}             {Theorem}[section]
\newtheorem{lemma}     [theorem] {Lemma}        
\newtheorem{conjecture}[theorem] {Conjecture}   
\newtheorem{property}  [theorem] {Property}   
\newtheorem{definition}[theorem] {Definition}   
\newtheorem{proposition}[theorem] {Proposition}   
\newtheorem{corollary} [theorem] {Corollary}
\newtheorem{remark}    [theorem] {Remark}
\newtheorem{fact}      [theorem] {Fact}   
\newtheorem{claim}     [theorem] {Claim}   

\def\ex{\mathop{\text{\rm ex}}\nolimits}

\def\circ{C^\circlearrowright}
\def\seta{\vec}
\def\circBar{D^\circlearrowright}

\def\sp{\mathop{\text{\rm span}}\nolimits}
\def\o{\mathop{\text{\rm O}}\nolimits}
\def\e{{\mathop{\text{\rm E}}\nolimits}}
\def\rr{{\mathop{\text{\rm R}}\nolimits}}
\def\b{\mathop{\text{\rm B}}\nolimits}
\def\f{{\mathop{\text{\rm F}}\nolimits}}
\def\teo{\mathop{\text{\rm T.}}\nolimits}
\def\fac{\mathop{\text{\rm F.}}\nolimits}
\def\lem{\mathop{\text{\rm L.}}\nolimits}
\def\edge{\mathop{\text{\rm EDGE}}\nolimits}
\def\deg{\mathop{\text{\rm DEG}}\nolimits}
\def\sup{\mathop{\text{\rm sup}}\nolimits}
\def\dist{\mathop{\text{\rm dist}}\nolimits}
\def\diag{\mathop{\text{\rm diag}}\nolimits}
\def\diam{\mathop{\text{\rm diam}}\nolimits}
\def\im{\mathop{\text{\rm im}}\nolimits}
\def\Pr{\mathop{\text{\rm Pr}}\nolimits}
\def\var{\mathop{\text{\rm var}}\nolimits}
\def\cov{\mathop{\text{\rm cov}}\nolimits}
\def\inj{\mathop{\text{\rm inj}}\nolimits}
\def\ind{\mathop{\text{\rm ind}}\nolimits}
\def\emb{\mathop{\text{\rm emb}}\nolimits}
\def\aut{\mathop{\text{\rm aut}}\nolimits}

\def\DISC{\mathop{\text{\rm DISC}}\nolimits}
\def\CYCLE{\mathop{\text{\rm CYCLE}}\nolimits}
\def\CIRCUIT{\mathop{\text{\rm CIRCUIT}}\nolimits}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\mdc{\mathop{\text{\rm mdc}}\nolimits}
\def\prior{\mathop{\text{\rm prior}}\nolimits}
\def\vol{\mathop{\text{\rm vol}}\nolimits}
\def\sen{\mathop{\text{\rm sen}}\nolimits}

\def\entrop{\mathop{\text{\rm H}}\nolimits}


\def\equaldef{\smash{\displaystyle
  \mathrel{\mathop{=}\limits^{\hbox{\rm\tiny def}}}}}
\def\tr{\mathop{\textrm{\rm tr}}\nolimits}

\let\:=\colon

\def\bba{{\mathbb A}}
\def\bbb{{\mathbb B}}
\def\bbc{{\mathbb C}}
\def\bbd{{\mathbb D}}
\def\bbe{{\mathbb E}}
\def\bbf{{\mathbb F}}
\def\bbg{{\mathbb G}}
\def\bbh{{\mathbb H}}
\def\bbi{{\mathbb I}}
\def\bbj{{\mathbb J}}
\def\bbk{{\mathbb K}}
\def\bbl{{\mathbb L}}
\def\bbm{{\mathbb M}}
\def\bbn{{\mathbb N}}
\def\bbo{{\mathbb O}}
\def\bbp{{\mathbb P}}
\def\bbq{{\mathbb Q}}
\def\bbr{{\mathbb R}}
\def\bbs{{\mathbb S}}
\def\bbt{{\mathbb T}}
\def\bbu{{\mathbb U}}
\def\bbv{{\mathbb V}}
\def\bbw{{\mathbb W}}
\def\bbx{{\mathbb X}}
\def\bby{{\mathbb Y}}
\def\bbz{{\mathbb Z}}

\def\cala{{\mathcal A}}
\def\calb{{\mathcal B}}
\def\calc{{\mathcal C}}
\def\cald{{\mathcal D}}
\def\cale{{\mathcal E}}
\def\calf{{\mathcal F}}
\def\cF{{\mathcal F}}
\def\calg{{\mathcal G}}
\def\calh{{\mathcal H}}
\def\cali{{\mathcal I}}
\def\calj{{\mathcal J}}
\def\calk{{\mathcal K}}
\def\call{{\mathcal L}}
\def\calm{{\mathcal M}}
\def\caln{{\mathcal N}}
\def\calo{{\mathcal O}}
\def\calp{{\mathcal P}}
\def\cP{{\mathcal P}}
\def\calq{{\mathcal Q}}
\def\calr{{\mathcal R}}
\def\cals{{\mathcal S}}
\def\calt{{\mathcal T}}
\def\calu{{\mathcal U}}
\def\calv{{\mathcal V}}
\def\calw{{\mathcal W}}
\def\calx{{\mathcal X}}
\def\caly{{\mathcal Y}}
\def\calz{{\mathcal Z}}

\def\aG{{\vec G}}
\def\aR{{\vec R}}
\let\aD\circBar
\def\tilden{{\widetilde n}}

\let\epsilon\varepsilon
\def\sup{\mathop{\text{\rm sup}}\nolimits}
\def\dist{\mathop{\text{\rm dist}}\nolimits}
\def\diag{\mathop{\text{\rm diag}}\nolimits}
\def\diam{\mathop{\text{\rm diam}}\nolimits}
\def\im{\mathop{\text{\rm im}}\nolimits}
\def\Pr{\mathop{\text{\rm Pr}}\nolimits}
\def\var{\mathop{\text{\rm var}}\nolimits}
\def\cov{\mathop{\text{\rm cov}}\nolimits}
\def\inj{\mathop{\text{\rm inj}}\nolimits}
\def\ind{\mathop{\text{\rm ind}}\nolimits}
\def\emb{\mathop{\text{\rm emb}}\nolimits}
\def\aut{\mathop{\text{\rm aut}}\nolimits}
\def\ex{\mathop{\text{\rm ex}}\nolimits}
\def\DISC{\mathop{\text{\rm DISC}}\nolimits}
\def\CYCLE{\mathop{\text{\rm CYCLE}}\nolimits}
\def\CIRCUIT{\mathop{\text{\rm CIRCUIT}}\nolimits}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\mdc{\mathop{\text{\rm mdc}}\nolimits}
\def\prior{\mathop{\text{\rm prior}}\nolimits}
\def\vol{\mathop{\text{\rm vol}}\nolimits}
\def\sen{\mathop{\text{\rm sen}}\nolimits}

\def\equaldef{\smash{\displaystyle
  \mathrel{\mathop{=}\limits^{\hbox{\rm\tiny def}}}}}
\def\tr{\mathop{\textrm{\rm tr}}\nolimits}


% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


\title{\bf On the number of orientations of random graphs with no directed cycles of
    a given length\thanks{An extended abstract of this work appeared in the Proc.\ of
  LAGOS~'11, Latin-American Algorithms, Graphs and Optimization
  Symposium [\textit{A note on counting orientations},
  Electron.\ Notes in Discrete Math.~\textbf{37} (2011),
  3--8]. The authors gratefully acknowledge the support of NUMEC/USP, Project
  MaCLinC/USP, and a CAPES/DAAD PROBRAL project
  (415/ppp-probral/po/D08/11629, Proj.~no.~333/09).}}

\author{P. Allen\thanks{Supported by FAPESP (2010/09555-7).}\\
\small Department of Mathematics\\[-0.8ex]
\small London School of Economics\\[-0.8ex]
\small Houghton Street, London WC2A 2AE, UK\\
\small\tt p.d.allen@lse.ac.uk\\
\and
Y. Kohayakawa\thanks{Partially supported by FAPESP (2013/03447-6,
2013/07699-0), CNPq (308509/2007-2,~477203/2012-4) and the NSF
(DMS~1102086).}\ \ \ \ \ \ \ \ G. O. Mota\thanks{Supported by FAPESP (2009/06294-0,
  2012/00036-2, 2013/20733-2) and CNPq (140882/2009-0, 477203/2012-4).}\ \ \ \ \ \ \ \ R. F. Parente\thanks{Supported by CNPq (131973/2009-6, 
  140987/2012-6).}\\
\small Instituto de Matem\'atica e Estat\'{\i}stica\\[-0.8ex]
\small Universidade de S\~ao Paulo\\[-0.8ex]
\small Rua do Mat\~ao 1010, 05508--090 S\~ao Paulo, Brazil\\
\small\tt \{yoshi|mota|robertop\}@ime.usp.br}


  
  
\date{\dateline{Sep 5, 2013}{Feb 20, 2014}\\
\small Mathematics Subject Classifications: 05C20, 05C35, 05C38}
  
\begin{document}

\maketitle


\begin{abstract}
  Let $\seta H$ be an orientation of a graph $H$.  Alon and Yuster
  [The number of orientations having no fixed tournament, {\em
    Combinatorica}, \textbf{26} (2006), no.~1, 1--16] proposed the
  problem of determining or estimating~$D(n,m,\seta H)$, the maximum
  number of \textit{$\seta H$-free orientations} a graph with $n$
  vertices and $m$ edges may have. We consider the maximum number of
  $\seta H$-free orientations of typical graphs $G(n,m)$ with $n$
  vertices and $m$ edges. Suppose $\seta H=\circ_\ell$ is the directed cycle of
  length~$\ell\geq 3$. We show that if ${m\gg n^{1+1/(\ell-1)}}$,
  then this maximum is $2^{o(m)}$, while if ${m\ll n^{1+1/(\ell-1)}}$,
  then it is $2^{(1-o(1))m}$.
\end{abstract}

\section{Introduction}
\label{sec:introducao}

Given a simple graph $H$, an \textit{orientation} $\seta H$ of $H$ is
obtained by assigning an `orientation' or `direction' to each of its
edges. Such an $\seta H$ is called \textit{oriented graph}. Given a
simple graph~$G$ and an oriented graph~$\seta H$, let~$D(G,\seta H)$
be the number of orientations of~$G$ with no copy of~$\seta H$ and
let~$D(n,\seta H) = \max\{D(G,\seta H) \colon |V(G)| =n\}$. The
problem of estimating~$D(n,\seta H)$ was posed by Paul
Erd\H{o}s~\cite[p.~45]{Er74} in~1974.  We investigate a similar
problem, where we consider `typical' graphs $G(n,m)$ with $n$ vertices
and $m$ edges. Our terminology and notation are standard (see, e.g.,
\cite{Bo01,JLR00}). In particular, we use the notation $a \ll b$ as shorthand
for the statement $a/b\to 0$ as $n\to\infty$.

Alon and Yuster~\cite{AlYu06} proved that, if~$n$ is sufficiently
large, then~$D{(n,T_k) = 2^{\ex(n,K_k)}}$ for any tournament~$T_k$
with~$k$ vertices, i.e., any orientation of the complete
graph~$K_k$. Here we work with \textit{directed cycles} $\circ_{\ell}$
of length $\ell$ as opposed to tournaments and we consider random
graphs.  Let us state our main theorem in terms of the binomial random
graph~$G(n,p)$ (one may derive corresponding results for the~$G(n,m)$
model from the $G(n,p)$ results below by standard means; the reader is referred to~\cite[Section~1.4]{JLR00} for this `equivalence' of the models $G(n,p)$ and 
$G(n,m)$).

\begin{theorem}
  \label{thm:mainResult}
  Fix~$\ell\geq 3$.  For every~$0<\gamma<1$, there exist~$c$ and~$C$
  for which the following hold for~$G=G(n,p)$ with probability tending
  to~$1$ as~$n\to\infty$.
  \begin{itemize}
  \item[(i)] If $p\geq Cn^{-1+1/(\ell-1)}$, then
    $D(G,\circ_{\ell})\leq 2^{\gamma {n\choose 2}p}$.
  \item[(ii)] If $n^{-2}\ll p\leq cn^{-1+1/(\ell-1)}$, then 
    $D(G,\circ_{\ell})\geq 2^{(1-\gamma){n\choose 2}p}$.
\end{itemize}
\end{theorem}

We refer to cases~(i) and~(ii) above, respectively, as the
\textit{supercritical} and the \textit{subcritical} cases.

Since our results are mostly asymptotic, in the next sections, when
  convenient, we freely and tacitly suppose that~$n$ is larger than a
  suitably large constant.

\section{Preliminaries}
\label{sec:preliminaries}

Let~$0 < p \leq 1$ be given and let~$\seta G=(V,E)$ be an oriented
graph. Let~$A$ and $B$ be non-empty disjoint subsets of $V$. We write
$e_{\seta G}(A,B)$ for the number of edges of $\aG$ oriented from $A$
to $B$. Define the \textit{$p$-density} of $(A,B)$ as~${ d_{\seta
    G,p}(A,B) = e_{\seta G}(A,B)/p|A||B|}$. For~${0 < \varepsilon \leq
  1}$, the pair~$(A,B)$ is called \textit{$(\varepsilon,\seta
  G,p)$-regular} if, for all~$X{\subset A}$ and~${Y\subset B}$ such
that~${|X|\geq\varepsilon|A|}$ and~${|Y|\geq\varepsilon|B|}$, we have
${|d_{\seta G,p}(X,Y) - d_{\seta G,p}(A,B)|\leq\varepsilon}$.  We
consider analogous definitions for graphs.  In particular,
if~${G=(A,B;E)}$ is a bipartite graph and $(A,B)$ is an
$(\varepsilon,G,p)$-regular pair, then we say that~$G$
is~${(\varepsilon,G,p)\text{-regular}}$. If the bipartite graph~$G$
is~$(\varepsilon,G,d)$-regular, where~${d=e_{G}(A,B)/|A||B|}$, then we
say that~$G$ is \textit{$(\varepsilon)$-regular}. More explicitly, in
an $(\varepsilon)$-regular bipartite graph $G=(A,B;E)$, for all
$X\subset A$ and $Y\subset B$ such that $|X|\geq \varepsilon |A|$ and
$|Y|\geq \varepsilon |B|$, we have
\begin{equation}
\left|e_G(X,Y) - \frac{e_G(A,B)}{|A||B|}|X||Y|\right|\leq \varepsilon \frac{e_G(A,B)}{|A||B|}|X||Y|.
\end{equation}


Given an oriented $n$-vertex graph~$\seta G$ and a
constant~$\varepsilon>0$, a partition~${\{V_0,V_1,\ldots,V_k\}}$ of
the vertex set of~$\seta G$ is
called~${(\varepsilon,k)\textit{-equitable}}$ if~${|V_0|\leq
  \varepsilon n}$ and~$|V_1|=\ldots=|V_k|$.  Furthermore, we say that
an \text{$(\varepsilon,k)$-equitable} partition
is~${(\varepsilon,\seta G,p)\textit{-regular}}$ if, for~${1 \leq i, j
  \leq k}$, at most~$\varepsilon k^2$ pairs~$(V_i,V_j)$ are
not~$(\varepsilon,\seta G,p)$-regular.  Given~$0<\eta$, $p=p(n)\leq
1$, an~${n\text{-vertex}}$ graph~$G$ is
called~${(\eta,p)\textit{-upper uniform}}$ if, for all
subsets~$X$,~$Y\subset V(G)$ with~$X\cap Y=\emptyset$ such
that~${|X|\geq\eta n}$ and~${|Y|\geq\eta n}$, we
have~${e_G(X,Y)\leq(1+\eta)p|X||Y|}$.  Now we give a version of
Szemer{\'e}di's Regulari\-ty Lemma for sparse oriented graphs~(see,
e.g.,~\cite{Ko97,KoRo03}, where the non-oriented case is considered).

\begin{theorem}\label{thm:Szemeredi}
  For all~$\varepsilon>0$ and positive integer~$m$, there exist~${\eta >0}$ and~${M \geq m}$, such that, for any~$0< p\leq 1$ and
  any orientation~$\seta G$ of a sufficiently large~${(\eta,p)\text{-upper}}$ uniform
  graph~$G$, there exists
  an~${(\varepsilon,\seta G,p)\text{-regular}}$ partition of the
  vertex set of~$\seta G$ into~$k + 1$ classes, where~$m\leq k\leq M$.
\end{theorem}

Let $\seta G$ be an oriented $n$-vertex graph and let
$W_1,\ldots,W_{\ell}\subset V(\seta G)$ be a family of pairwise
disjoint sets with $|W_1|=\dots=|W_{\ell}|\geq \sigma n$.  We say
that $(W_1,\ldots,W_{\ell})$ induces an
\textit{$(\varepsilon,\delta,\sigma)$-blow-up of~$\circ_{\ell}$}
in~$\aG$ if, for $1\leq i\leq \ell$, the pairs $(W_i,W_{i+1})$ are
$(\varepsilon,\seta G,p)$-regular with $d_{\seta G,p}(W_i,W_{i+1})\geq
\delta$, where we set $W_{\ell+1}=W_1$.  Naturally, here, we are
thinking of the oriented subgraph~$\bigcup_{1\leq
  i\leq\ell}\aG[W_i,W_{i+1}]$ of~$\aG$, where~$\aG[W_i,W_{i+1}]$ has
vertex set~$W_i\cup W_{i+1}$ and contains precisely the oriented edges
of~$\aG$ starting in~$W_i$ and ending in~$W_{i+1}$.

A \textit{digraph} $\seta D$ is a pair $(V,E)$ where $V$ is the vertex
set of $\seta D$ and $E$ is a set of {\it arcs}, or {\it oriented
  edges}, that is, ordered pairs $(u,v)$, where $u$, $v\in V$ and
$u\neq v$.  Let~$0<\varepsilon$, $\delta$, $p=p(n)\leq 1$ be given and
let~$\seta G$ be an $n$-vertex oriented graph. Let ${\calp =
  \{V_0,V_1,\ldots,V_k\}}$ be an $(\varepsilon,k)$-equitable partition
of the vertex set of~$\seta G$.  The \textit{coloured reduced digraph}
$\seta R=\seta R(\seta G,\varepsilon,\delta,\calp)$ associated
with~$\calp$ has vertex set~$[k]=\{1,\dots,k\}$ and, for
every~$\{i,j\}\in{[k]\choose2}$, the pair~$(i,j)$ is an arc in~$\aR$
if and only if the pair~$(V_i,V_j)$ is~$(\varepsilon,\aG,p)$-regular;
moreover, an arc~$(i,j)$ in~$\aR$ is coloured \textit{grey}
if~$d_{\aG,p}(V_i,V_j)<\delta$ and is coloured \textit{blue}
if~$d_{\aG,p}(V_i,V_j)\geq\delta$.

Given a graph~$H$, a real number~$\varepsilon>0$, and positive
integers $n$ and $m$, we define $\mathcal{G}(H,n,m,\varepsilon)$ as
the family of graphs~$G$ with vertex set $V=\bigcup_{x\in V(H)}V_x$,
where the sets~$V_x$ have cardinality~$n$ each and are pairwise
disjoint, and with edge set of the form $E=\bigcup_{\{x,y\}\in
  E(H)}E_{xy}$, where each~$E_{xy}$ is the edge set of
an~${(\varepsilon)\text{-regular}}$ graph with exactly~$m$ edges
between $V_x$ and $V_y$ for all $\{x, y\}\in E(H)$.  We denote
by~$\mathcal{F}(H,n,m,\varepsilon)$ the set of graphs in
$\mathcal{G}(H,n,m,\varepsilon)$ that do \textit{not} contain
\textit{transversal copies} of $H$, i.e., copies of $H$ with exactly
one vertex in each~$V_x$. The following result is proved
in~\cite{GeKoRoSt07} (for a weaker result, see~\cite{KoKr97}).

\begin{theorem}\label{thm:KLR}
  Let $C_\ell$ be a cycle with~${\ell \geq 3}$.  For any~$0<\alpha<1$,
  there exists $\varepsilon_0>0$ such that, for all~${\mu>0}$, there
  exists~$C\geq 1$ such that, for all~${p\geq Cn^{-1 + 1/(\ell-1)}}$
  and ${0<\varepsilon <\varepsilon_0}$, the random graph $G(n,p)$
  contains a.a.s.\ no subgraphs
  in~$\cF(C_\ell,\widetilde{n},\lfloor\alpha\widetilde{n}^2p\rfloor,\varepsilon)$
  for any~$\widetilde{n}\geq\mu n$. 
\end{theorem}

Now we give a definition and some results that are useful in the proof
of Theorem~\ref{thm:mainResult}(i).

\begin{definition}
  Let~$\sigma$, $\varepsilon>0$ and $0<p=p(n)\leq 1$ be given.  We say
  that an $n$-vertex graph~$G$ satisfies~$\edge(\sigma,\varepsilon,p)$
  if, for every $U\subset V(G)$ with $|U|\geq\sigma n$, we have
  $\big|e_G(U) - {|U| \choose 2}p\big| < \varepsilon p{|U| \choose 2}$.
\end{definition}

\begin{lemma}
  \label{lemma:propREG}
  For every $0<\delta<1/2$, there exists $\varepsilon>0$ such that,
  for every $\sigma>0$, if $\seta G$ is an orientation of an
  $n$-vertex graph~$G$ that satisfies
  $\edge\big(\sigma,\varepsilon,p\big)$ for some $0<p=p(n)\leq 1$,
  then, for every disjoint $X$, $Y\subset V(G)$ with $|X|=|Y|\geq
  \sigma n$, we have $e_G(X,Y)\geq (1-3\delta)p|X||Y|$.  Furthermore,
  either $d_{\seta G,p}(X,Y)\geq\delta$ or~$d_{\seta
      G,p}(Y,X)\geq\delta$.
\end{lemma}

\begin{proof}
  Fix $0<\delta< 1/2$ and put $\varepsilon=\min\{(1-2\delta)/3,
  \delta\}$. Fix~$\sigma>0$.  Let $\seta G$ be an orientation of an
  $n$-vertex graph $G$ and consider $0<p=p(n)\leq 1$. Suppose $G$
  satisfies $\edge\big(\sigma,\varepsilon,p\big)$ and let $X$ and $Y$
  be disjoint subsets of $V(G)$ with $|X|=|Y|\geq \sigma n$.  Then
  \begin{align}\label{eq:limitaEViVj}
    e_G(X,Y)&= e_G(X \cup Y) - e_G(X) - e_G(Y) \nonumber\\ 
    &> (1-\varepsilon)\binom{|X|+|Y|}{2}p - (1+\varepsilon)\binom{|X|}{2}p - 
    (1+\varepsilon)\binom{|Y|}{2}p \nonumber\\  
    & = (1- 3\varepsilon + 2\varepsilon/|X|)p|X||Y| >
    (1-3\varepsilon)p|X||Y|,
  \end{align}
  where the first inequality follows from the definition
  of~$\edge\big(\sigma,\varepsilon,p\big)$.  Thus, since
  ${\varepsilon\leq \delta}$, we deduce that ${e_G(X,Y)\geq
    (1-3\delta)p|X||Y|}$.  Furthermore, using the fact
  $\varepsilon\leq (1-2\delta)/3$, we have ${e_G(X,Y)\geq 2\delta
    p|X||Y|}$. Therefore, we conclude that ${d_{\seta G,p}(X,Y) \geq
    \delta}$ or~${d_{\seta G,p}(Y,X) \geq \delta}$.
\end{proof}

The following three simple facts will be useful in
Section~\ref{sec:proofResults}. For a proof of
Fact~\ref{fact:spanningRegular}, the reader is referred
to~\cite{GeSt05}. Fact~\ref{fact:EDGE} follows from Chernoff bounds
and Fact~\ref{fact:EDGE->Upper} follows from calculations similar to
those in the proof of Lemma~\ref{lemma:propREG}.

\begin{fact}\label{fact:spanningRegular}
  For all~${0 < \varepsilon \leq1/6}$, there exists a constant~$C>0$
  such that any ${(\varepsilon)\text{-regular}}$ bipartite
  graph~${B=(V_1 , V_2; E)}$ contains a
  spanning~${(2\varepsilon)\text{-regular}}$ subgraph with exactly~$m$
  edges, for all $C(|V_1|+|V_2|)\leq m \leq |E|$.
\end{fact}

\begin{fact}\label{fact:EDGE}
  For every $0<\sigma,\,\varepsilon < 1$, if $p=p(n)\gg 1/n$, then,
  a.a.s., $G(n,p)$ satisfies $\edge(\sigma,\varepsilon,p)$.
\end{fact}

\begin{fact}\label{fact:EDGE->Upper}
  For every $\eta>0$, there exist $\varepsilon>0$ and $\sigma>0$ such
  that, if $0<p\leq 1$ and $G$ is an $n$-vertex graph satisfying
  $\edge(\sigma,\varepsilon,p)$, then $G$ is $(\eta,p)$-upper uniform.
\end{fact}

\section{Proof of Theorem~\ref{thm:mainResult}}
\label{sec:proofResults}

Let us briefly sketch the main idea of the proof of part~(i). Given $p\ge
Cn^{-1+1/(\ell-1)}$ and a graph $G=G(n,p)$, we will
consider the set of $(\varepsilon,\seta
G,p)$-regular partitions of its $\circ_\ell$-free orientations. Since these
partitions are into a number of parts bounded by $M=M(\varepsilon)$, there are
at most $M^n$ of them, and the total number of coloured reduced digraphs is
bounded by a constant. It follows that, if $G$ has more than $2^{\gamma\tbinom{n}{2}p}$
orientations that are $\circ_\ell$-free, then there is one partition of $V(G)$
and one coloured reduced digraph $\seta R$ that account for more than
$2^{\tfrac{\gamma}{2}\tbinom{n}{2}p}$ of these orientations of $G$.

Now we consider the number of ways we can orient the edges of $G$ so that we
obtain the reduced digraph $\seta R$. We will see that if there are only few
pairs of clusters with blue arcs in both directions, then there are at most
$2^{\tfrac{\gamma}{2}\tbinom{n}{2}p}$ possible orientations. But if there are
many pairs of clusters with blue arcs in both directions---which there must be
for the total number of $\circ_\ell$-free orientations of $G$ to be at
least $2^{\gamma\tbinom{n}{2}p}$---then we can find a triple of clusters
in $\seta R$ which contains a directed blue $3$-cycle plus one extra blue arc.
We will prove that, since $p\ge C
n^{-1+1/(\ell-1)}$, the graph~$G$ has a.a.s.\ the property that the
directed edges in $\seta G$ between the clusters of any such triple must contain
a copy of
$\circ_\ell$, and this contradiction will imply the result.

The only step at which we used the probability bound of part~(i) was
the final step of finding a copy of $\circ_\ell$ given the triple with
a directed blue $3$-cycle plus a blue arc in $\seta R$.  That step
fails if $p\le c n^{-1+1/(\ell-1)}$ for some small constant~$c$, and
it does so for the simple reason that for such values of $p$, most
edges of $G$ are not contained in any copy of $C_\ell$. We can fix a
$\circ_\ell$-free orientation of those edges of $G$ that \emph{are}
contained in copies of $C_\ell$s, and then any orientation of the
remaining edges is automatically $\circ_\ell$-free. Since almost all
edges do not belong to~$C_\ell$s, part~(ii) follows.

\subsection{Two auxiliary lemmas}
\label{sec:two-auxiliary-lemmas}

We now give two lemmas that concern orientations~$\aG$ of $n$-vertex
graphs~$G$ for which the following two conditions hold, for certain
parameters~$\sigma$, $\epsilon_{\e}$, $p=p(n)$, $\tilden$, $\delta$
and~$\epsilon_{\f}$, to be specified later:
\begin{enumerate}
\item[(H1)] $G$ satisfies ${\edge\big(\sigma,\varepsilon_{\e},p\big)}$,

\item[(H2)] $G$ contains no member
  of~$\calf(C_\ell,\tilden,\lfloor\delta\tilden^2p\rfloor,\epsilon_{\f})$. 
\end{enumerate}

In the first lemma (Lemma~\ref{lemma:embedding}), we suppose
that~$\aG$ contains an $\ell$-tuple of sets $(W_1,\ldots,W_{\ell})$
inducing an appropriate blow-up of~$\circ_\ell$, and deduce that~$\aG$
itself contains a~$\circ_\ell$.  In the second lemma
(Lemma~\ref{lemma:technical}), we suppose that the regularity lemma
has been applied to~$\aG$ and that the associated coloured reduced
digraph~$\aR$ contains a certain subdigraph~$\aD$ made up of blue
arcs; we then conclude that~$\aG$ contains a~$\circ_\ell$, finding
first a suitable $\ell$-tuple of sets $(W_1,\ldots,W_{\ell})$ and then
applying Lemma~\ref{lemma:embedding}.

\begin{lemma}
  \label{lemma:embedding}
  For every $0<\delta$, $\varepsilon_{\f}<1/3$ and $\ell\geq3$,
  there exists $\varepsilon_{\e}$ such that, for every $0<\sigma<1$, 
  the following holds.

  Suppose~$\seta G$ is an orientation of $G$, where $G$ is an
  $n$-vertex graph that satisfies both {\rm(H1)} and {\rm(H2)}
  above for some $\sigma n\leq\tilden\leq n$
  and~$p=p(n)\gg 1/n$.  If $(W_1,\ldots,W_{\ell})$
  with~$|W_1|=\dots=|W_\ell|=\tilden$ induces an
   $(\varepsilon_{\rr},\delta,\sigma)$-blow-up of $\circ_{\ell}$, where
  $\varepsilon_{\rr}=\varepsilon_{\f}(1-3\delta)/2$, then~$\seta G$
  contains a copy of $\circ_{\ell}$.
\end{lemma}


\begin{proof}
  Fix $0<\delta$, $\varepsilon_{\f}<1/3$ and $\ell\geq 3$.  Let
  $\varepsilon_{\e}$ be given by an application of
  Lemma~\ref{lemma:propREG} with parameter $\delta$.  Fix
  $0<\sigma<1$ and define $C_{(\fac\ref{fact:spanningRegular})}$ as the
  constant obtained by an application of
  Fact~\ref{fact:spanningRegular} with parameter~$\varepsilon_{\f}/2$. Now
  suppose that~$G$, $\aG$ and $(W_1,\ldots,W_{\ell})$ are as in the
  statement of the lemma and $p=p(n)\gg 1/n$.

  % Suppose $\seta G$ is an orientation of $G$, where $G$ is an
  % $n$-vertex graph with $n\geq n_0=C$ that satisfies
  % $\edge(\sigma,\varepsilon_{\e},p)$, where~$p=p(n)\geq C/n$.  Suppose
  % $(W_1,\ldots,W_{\ell})$ induces
  % $(\varepsilon_{\rr},\delta,\sigma)$-blow-up of~$\circ_{\ell}$, where
  % $\varepsilon_{\rr}=\varepsilon_{\f}(1-3\delta)/2$ and suppose $G$
  % contains no subgraphs from
  % $\calf(C_\ell,|W_1|,\lfloor\delta|W_1|^2p\rfloor,\varepsilon_{\f})$.

  For convenience, put $W_{\ell+1}=W_1$.  Let~$\aG_\ell=\bigcup_{1\leq
    i\leq\ell}\aG[W_i,W_{i+1}]$ be the subdigraph of~$\aG$ associated
  with the $(\varepsilon_{\rr},\delta,\sigma)$-blow-up
  of~$\circ_{\ell}$ induced by the sets~$W_i$.  Also, let~$G_\ell$ be the
  underlying graph of~$\aG_\ell$, that is, the graph obtained
  from~$\aG_\ell$ by ignoring the orientation of its edges. 

  Fix $i\in[\ell]$. Since $p\gg 1/n$ we
  have~${\lfloor\delta|W_i||W_{i+1}|p\rfloor \geq C_{(\fac\ref{fact:spanningRegular})}(|W_i| +
    |W_{i+1}|)}$ and, by the definition of
  $(\varepsilon_{\rr},\delta,\sigma)$-blow-up of $\circ_{\ell}$, we
  have~${\lfloor\delta|W_i||W_{i+1}|p\rfloor \leq
    e_{G_\ell}(W_i,W_{i+1})}$.  Furthermore, since~$G$ satisfies
  $\edge\big(\sigma,\varepsilon_{\e},p\big)$, by
  Lemma~\ref{lemma:propREG}, we have $e_{G_\ell}(W_i,W_{i+1})\geq
    (1-3\delta)p|W_i||W_{i+1}|$. Thus, since $(W_i,W_{i+1})$ is
  $(\varepsilon_{\rr},G_{\ell},p)$-regular, we conclude that the
  induced bipartite subgraph $G_\ell[W_i\cup W_{i+1}]$ of $G_\ell$ is
  \text{$(\varepsilon_{\f}/2)$-regular}. Therefore, we can apply
  Fact~\ref{fact:spanningRegular} on the bipartite graphs
  $G_\ell[W_i\cup W_{i+1}]$ for $1\leq i\leq \ell$, obtaining spanning
  $(\varepsilon_{\f})$-regular subgraphs $G^{\sp}_\ell[W_i\cup
  W_{i+1}]$ of $G_\ell[W_i\cup W_{i+1}]$ with
  exactly~$\lfloor\delta|W_i||W_j|p\rfloor$ edges.

  Let $J\subset G_\ell$ be the graph with vertex set
  $\bigcup_{i=1}^{\ell} W_i$ and edge set $\bigcup_{i=1}^{\ell}
  E(G_{\ell}^{\sp}[W_i\cup W_{i+1}])$. The graph~$J$ is clearly a
  graph of the
  family~$\calg(C_\ell,|W_1|,\lfloor\delta|W_1|^2p\rfloor,\varepsilon_{\f})$.
  Recalling that~$G$ contains no subgraphs
  from~$\calf(C_\ell,|W_1|,\lfloor\delta|W_1|^2p\rfloor,\varepsilon_{\f})$,
  we deduce that~$J\subset G_\ell$ contains a~$C_\ell$.  This~$C_\ell$
  corresponds to a~$\circ_\ell$ in~$\aG_\ell\subset\aG$, and the proof
  is complete.
\end{proof}

Let~$\circBar_3$ be obtained from the cycle~$\circ_3$ of length~$3$ by
the addition of an extra arc, forming a directed cycle of length~$2$
with some arc of~$\circ_3$.  As in the previous lemma, we shall
consider in our next lemma an orientation~$\aG$ of an $n$-vertex
graph~$G$ that satisfies both~(H1) and~(H2).  However, in
Lemma~\ref{lemma:technical} below, our hypothesis will be that~$\aG$
has been regularized with some suitably small parameter~$\varepsilon_{\rr}$
and that the associated coloured reduced
digraph~$\aR=\aR(\aG,\varepsilon_{\rr},\delta,\cP)$ contains a
blue~$\circBar_3$.  In the lemma below, we are interested in
\textit{odd} cycles $\circ_\ell$.  (The case in which~$\ell$ is even
is similar and simpler.  For even~$\ell$, it is enough that~$\aR$
should contain a blue directed $2$-cycle~$\circ_2$; we omit the details.)

\begin{lemma}
  \label{lemma:technical}
  Fix~$z\geq1$ and set~$\ell=2z+1$.  For every positive $\delta<1/3$
  and $\varepsilon_{\f}<1/z$ and $M\geq 1$, there exist
  $\varepsilon_{\e}$ and $\sigma$ such that the following
  holds.  Suppose~$G$ is an $n$-vertex graph that
  satisfies~{\rm(H1)} and~{\rm(H2)} for some~$\tilden$ and~$p=p(n)\gg
  1/n$.  Furthermore, suppose that~$\aG$ is an orientation of~$G$ and
  that~${\calp = \{V_0,V_1,\ldots,V_k\}}$ is an
  $(\varepsilon_{\rr},\aG,p)$-regular $(\varepsilon_{\rr},k)$-equitable partition
  of the vertex set of~$\aG$, where
  $\varepsilon_{\rr}=\min\big\{\epsilon_\f\big(1-3(\delta/2)\big)/2,\delta/2\big\}$
  and~$k\leq M$.  If~$\tilden=\lfloor|V_1|/z\rfloor$ and the coloured
  reduced digraph $\aR=\aR(\aG,\varepsilon_{\rr},\delta,\calp)$ associated
  with~$\calp$ contains a blue copy of~$\circBar_3$, then~$\aG$
  contains a copy of~$\circ_\ell=\circ_{2z+1}$.
\end{lemma}


\begin{proof}
  Fix $z\geq 1$, $0<\delta<1/3$, $0<\varepsilon_{\f}<1/z$ and $M\geq
  1$. Set $\ell=2z+1$. Let
  $\varepsilon_{\e}=\varepsilon_{\e(\lem\ref{lemma:embedding})}$ be
  given by an application of Lemma~\ref{lemma:embedding} with
  parameters $\delta_{(\lem\ref{lemma:embedding})}=\delta/2$,
  $\varepsilon_{\f(\lem\ref{lemma:embedding})}=z\varepsilon_{\f}$ and
  $\ell$. In order to apply~Lemma~\ref{lemma:embedding}, put
  $\varepsilon_{\rr(\lem\ref{lemma:embedding})}=\varepsilon_{\f(\lem\ref{lemma:embedding})}
  \big(1-3\delta_{(\lem\ref{lemma:embedding})} \big)/2$.  Let
  $\varepsilon_{\rr}=\min\{\epsilon_{\rr(\lem\ref{lemma:embedding})}/z,\delta/2\}$
  and set $\sigma=(1-\varepsilon_{\rr})/zM$ (we shall apply
  Lemma~\ref{lemma:embedding} with this~$\sigma$).  We have now
  defined all the required constants.
  
  We now suppose that~$G$, $\aG$, $\cP=\{V_0,\dots,V_k\}$,
  and~$\aR=\aR(\aG,\varepsilon_{\rr},\delta,\calp)$ are as in the statement
  of the lemma and $p=p(n)\gg 1/n$. We prove that~$\aG$ must contain a~$\circ_\ell$.

  Adjusting the notation suitably, assume that~$(v_1,v_2)$,
  $(v_2,v_1)$, $(v_2,v_3)$ and~$(v_3,v_1)$ are the arcs of
  a blue~$\circBar_3$ in~$\aR$.  Thus, we know that the corresponding
  pairs~$(V_i,V_j)$ are $(\varepsilon_{\rr},\aG,p)$-regular with density at
  least~$\delta$ in~$\aG$.

  For~$z=1$, the result follows directly from
  Lemma~\ref{lemma:embedding}.  Suppose~$z\geq2$.  For $i=1$, $2$
  and~$3$, consider pairwise disjoint subsets $V_i^1,\ldots,V_i^z$
  of~$V_i$ with~$|V_i^1| = \ldots = |V_i^z| =
    \lfloor|V_i|/z\rfloor$.  To apply Lemma~\ref{lemma:embedding}, we
  shall prove that the sequence $(V_1^1,V_2^1\ldots,V_1^z,V_2^z,V_3^1)$ induces an
  $(\epsilon_{\rr(\lem\ref{lemma:embedding})},
  \delta_{(\lem\ref{lemma:embedding})}, \sigma)$-blow-up of
  $\circ_\ell$ in~$\aG$.  If~$u$, $v\in [z]$ and~$X\subset V_1^u$
  and~$Y\subset V_2^v$ have cardinalities $|X|
  \geq\epsilon_{\rr(\lem\ref{lemma:embedding})}|V_1^u|
  \geq\varepsilon_{\rr}|V_1|$ and~$|Y|
  \geq\epsilon_{\rr(\lem\ref{lemma:embedding})}|V_2^v|
  \geq\varepsilon_{\rr}|V_2|$, then, since $(V_1,V_2)$ is
  $(\varepsilon_\rr,\aG,p)$-regular, we have that $|d_{\seta G,p}(X,Y) - d_{\seta G,p}(V_1^u,V_2^v)|$ is at most
  \begin{eqnarray}
    |d_{\seta G,p}(X,Y) - d_{\seta G,p}(V_1,V_2)| + |d_{\seta G,p}(V_1,V_2) - 
    d_{\seta G,p}(V_1^u,V_2^v)|\leq  2\varepsilon_{\rr}\leq 
    z\varepsilon_{\rr}\leq\varepsilon_{\rr(\lem\ref{lemma:embedding})}.	
  \end{eqnarray}
  Applying the same argument we have~$|d_{\seta G,p}(Y,X) - d_{\seta
    G,p}(V_2^v,V_1^u)|\leq
  \varepsilon_{\rr(\lem\ref{lemma:embedding})}$. Therefore, for all
  $u$, $v\in [z]$, the pairs~$(V_1^u,V_2^v)$ and~$(V_2^u,V_1^v)$
  are~${(\varepsilon_{\rr(\lem\ref{lemma:embedding})},\seta
    G,p)\text{-regular}}$.  Similarly, for all $u$, $v\in [z]$, the
  pairs~$(V_3^1,V_1^u)$ and $(V_2^v,V_3^1)$
  are~${(\varepsilon_{\rr(\lem\ref{lemma:embedding})},\seta
    G,p)\text{-regular}}$.

  As~${d_{\seta G,p}(V_i,V_j)\geq\delta}$ and $(V_i,V_j)$ is
  $(\varepsilon_{\rr},\seta G,p)$-regular for
  every pair~$(i,j)$ in the set $\{(1,2),(2,1),(2,3),(3,1)\}$, we have, for all $u$,
  $v\in [z]$, that
  \begin{align}
    d_{\aG,p}(V_1^u,V_2^v),\, d_{\aG,p}(V_2^v,V_1^u),\,
    d_{\aG,p}(V_2^v,V_3^1),\, d_{\aG,p}(V_3^1,V_1^u)
    &\geq\delta-\varepsilon_{\rr}
    \geq\delta/2=\delta_{(\lem\ref{lemma:embedding})},
  \end{align}
  where the last inequality follows from $\varepsilon_{\rr}\leq
  \delta/2$.  Therefore, $V_1^1,V_2^1,\dots,V_1^z,V_2^z,V_3^1$ does
  induce an $(\epsilon_{\rr(\lem\ref{lemma:embedding})},
  \delta_{(\lem\ref{lemma:embedding})}, \sigma)$-blow-up of
  $\circ_{2z+1}=\circ_\ell$ in~$\aG$.  Recalling that~(H1) and~(H2) hold
  for~$G$, we see that~$G$ satisfies
  $\edge\big(\sigma,\epsilon_{\e(\lem\ref{lemma:embedding})},p\big)$
  and $G$ contains no member of
  $$\cF(C_\ell,\lfloor|V_1|/z\rfloor,
  \lfloor\delta_{(\lem\ref{lemma:embedding})}
  \lfloor|V_1|/z\rfloor^2p\rfloor,
  \epsilon_{\f(\lem\ref{lemma:embedding})}).
  $$
  Thus, all conditions of Lemma~\ref{lemma:embedding} are satisfied
  and we conclude that~$\aG$ contains a copy of~$\circ_\ell$.
\end{proof}

\subsection{Main lemma for the supercritical case}

The next result (Lemma~\ref{lemma:mainSuper}) is the main lemma in the
proof of Theorem~\ref{thm:mainResult}(i).  As in
Lemmas~\ref{lemma:embedding} and~\ref{lemma:technical} in
Section~\ref{sec:two-auxiliary-lemmas}, in Lemma~\ref{lemma:mainSuper}
below we consider an $n$-vertex graph~$G$ that satisfies~(H1) and~(H2)
given at the beginning of Section~\ref{sec:two-auxiliary-lemmas}, but
suppose that~(H2) holds for a range of values of~$\tilden$, namely,
for all~$\tilden\geq cn$ for a certain constant~$c>0$.  The conclusion
in Lemma~\ref{lemma:mainSuper} is that, for any given~$\gamma>0$, with
the constants in~(H1) and~(H2) chosen suitably, such a graph~$G$ has
at most~$2^{\gamma{n\choose 2}p}$ orientations avoiding~$\circ_\ell$.

\begin{lemma}
  \label{lemma:mainSuper}
  Fix~$\ell\geq 3$.  For every $0<\gamma<1$, there exists $\delta>0$
  such that, for every~$0<\epsilon_\f<1/\ell$, there exist
  $\epsilon_\e$ and~$\sigma>0$ and an integer~$M$ such that,
  if $1/n\ll p=p(n)\leq 1$, then the
  following holds.  Let~$G$ be an $n$-vertex graph
  satisfying~{\rm(H1)} and~{\rm(H2)} for all~$\tilden\geq\lfloor
  n/\ell M\rfloor$.  Then we have
  \begin{equation}
    \label{eq:or_bound_lemma}
    D(G,\circ_\ell)\leq2^{\gamma{n\choose2}p}.
  \end{equation}
\end{lemma}

\begin{proof}
  We assume that~$\ell$ is odd, since the even case is similar and
  easier.  Suppose~$\ell=2z+1$.  Fix~$0<\gamma<1$.  Let $\delta>0$
  satisfy $4\delta+3\entrop(\delta)<\gamma/32$ and $\delta<1/3$, where
  $\entrop$ is the binary entropy function, that is,
  $\entrop(x)=-x\log_2x-(1-x)\log_2(1-x)$ for all $0<x<1$ and
  $\entrop(0)=\entrop(1)=0$.  Fix
  $\epsilon_{\f(\lem\ref{lemma:technical})}=\epsilon_\f<1/\ell$ and
  put $\varepsilon_{\rr}=\min\{\epsilon_\f\big(1-3(\delta/2)\big)/2,
  \delta/2, (\gamma/64)^2\}$.

  Let~$\eta_1$ and~$M$ be the constants obtained by an
  application of Theorem~\ref{thm:Szemeredi} with parameters~$\varepsilon_{\rr}$
  and~$m=\lceil1/\varepsilon_{\rr}\rceil$.  Put $\eta=\min\{\eta_1, 1/2M,
  \varepsilon_{\rr}/2\}$ and let $\epsilon_{\e(\lem\ref{lemma:technical})}$ 
  and $\sigma_{\e(\lem\ref{lemma:technical})}$ be obtained
  by an application of Lemma~\ref{lemma:technical} with parameters
  $z$, $\delta$, $\epsilon_\f$ and~$M$.

  Now let $\varepsilon_{\e(\fac\ref{fact:EDGE->Upper})}$ and
  $\sigma_{\e(\fac\ref{fact:EDGE->Upper})}$ be obtained by an
  application of Fact~\ref{fact:EDGE->Upper} with parameter~$\eta$.
  Set~$\sigma=\min\{\sigma_{\e(\lem\ref{lemma:technical})},
  \sigma_{\e(\fac\ref{fact:EDGE->Upper})}, \eta\}$ and let
  $\epsilon_{\e(\lem\ref{lemma:propREG})}$ be obtained by an
  application of Lemma~\ref{lemma:propREG} with parameter~$\delta$.
  Set $\epsilon_{\e}=\min\{\varepsilon_{\e(\lem\ref{lemma:propREG})},
  \epsilon_{\e(\fac\ref{fact:EDGE->Upper})},
  \epsilon_{\e(\lem\ref{lemma:technical})}\}$.  Suppose $1/n\ll
  p=p(n)\leq 1$ and~$n$ is large enough.
  
  Now let~$G$ be an $n$-vertex graph that satisfies~(H1) and~(H2) for
  all~$\tilden\geq\lfloor n/\ell M\rfloor$.  We shall show that
  $D(G,\circ_\ell)\leq2^{\gamma{n\choose2}p}$.  For convenience, let
  us state our hypotheses on~$G$ explicitly here: we suppose that~$G$
  satisfies $\edge(\sigma,\epsilon_\e,p)$ and suppose that~$G$
  contains no graph in~$\cF(C_\ell,\tilde n,\lfloor(\delta/2)\tilde
  n^2p\rfloor,z\epsilon_\f)$ as a subgraph for any $\tilden\geq\lfloor
  n/\ell M\rfloor$.

  Denote by~$\calr$ the set of digraphs
  $\aR=\aR(\aG,\varepsilon_{\rr},\delta,\cP)$ whose arcs are coloured grey
  and blue such that there exists a $\circ_\ell$-free
  orientation~$\aG$ of~$G$ where~$\aR$ is the coloured reduced digraph of
  an $(\varepsilon_{\rr},\aG,p)$-regular partition $\calp$ of~$\seta G$ with
  $k+1$ classes with $m\leq k \leq M$.  Given~$\seta R \in \calr$, we
  denote by~$D_{\seta R}(G,\circ_\ell)$ the number of
  $\circ_\ell$-free orientations~$\aG$ of~$G$ satisfying the extra
  condition that~$\aR$ should be a coloured reduced digraph of an
  $(\varepsilon_{\rr},\aG,p)$-regular partition of $\aG$.

  By Theorem~\ref{thm:Szemeredi}, for every orientation $\seta G$
  of~$G$, there exists an $(\varepsilon_{\rr}, \aG,p)$-regular partition of
  $G$ with $k+1$ classes, where $m\leq k\leq M$. Note that, since
  there are~$3^2$ possible kinds of connections between two vertices
  in a coloured reduced digraph, there exist at most $9^{i\choose 2}$
  different coloured reduced graphs with~$i$ vertices.  Thus,
  \begin{align}
    \label{eq:or_global}
    D(G,\circ_\ell)\leq\sum_{m\leq i\leq M}
    \sum_{\aR\colon|V(\aR)|=i}D_{\aR}(G,\circ_\ell)
    \leq M9^{M\choose2}\max_\aR D_\aR(G,\circ_\ell).
  \end{align}
  We now make the following claim.

  \begin{claim}
    \label{claim:or_bound}
    For any coloured reduced digraph~$\aR$, we have
    \begin{equation}
      \label{eq:or_bound}
      D_\aR(G,\circ_\ell)\leq2^{{\frac{\gamma}{2}}{n\choose 2}p}.
    \end{equation}
  \end{claim}

  Given that~$M$ is a constant and~$p\gg1/n$,
  inequalities~\eqref{eq:or_global} and~\eqref{eq:or_bound}
  imply~\eqref{eq:or_bound_lemma} for all large enough~$n$, and the
  proof of Lemma~\ref{lemma:mainSuper} is complete.  It now remains to
  prove Claim~\ref{claim:or_bound}.
\end{proof}

\begin{proof}[Proof of Claim~\ref{claim:or_bound}]
  Fix a coloured reduced digraph~$\aR$.  We first claim that~$\aR$
  does not contain too many blue directed $2$-cycles~$\circ_2$.  More
  precisely, our claim is as follows.  Let~$R_2$ be the graph
  on~$[k]=V(\aR)$ where~$\{i,j\}$ is an edge of~$R_2$ if and only if both
  arcs~$(i,j)$ and~$(j,i)$ belong to~$\aR$ and are blue.  We claim
  that
  \begin{equation}
    \label{eq:R_2_sparse}
    e(R_2)=|E(R_2)|\leq\varepsilon_{\rr}^{1/2}k^2.
  \end{equation}
  Suppose for a contradiction that~\eqref{eq:R_2_sparse} fails.  Then
  there is a vertex~$a$ in~$R_2$ with degree~$d_{R_2}(a)$ larger
  than~$2\varepsilon_{\rr}^{1/2}k$ in~$R_2$.
  Therefore~${d_{R_2}(a)\choose2}>\varepsilon_{\rr} k^2$, and it follows
  from the fact that~$\aR$ is the coloured reduced digraph of an
  $(\varepsilon_{\rr},\aG,p)$-regular partition~$\cP=\{V_0,\dots,V_k\}$ that
  there is a pair~$(b,c)$ with both~$b$ and~$c$ adjacent to~$a$
  in~$R_2$ with both~$(V_b,V_c)$ and~$(V_c,V_b)$
  $(\varepsilon_{\rr},\aG,p)$-regular pairs.  By Lemma~\ref{lemma:propREG},
  we know that either~$d_\aG(V_b,V_c)\geq\delta$
  or~$d_\aG(V_c,V_b)\geq\delta$, and hence at least one of~$(b,c)$
  and~$(c,b)$ is blue in~$\aR$.  It thus follows that~$\aR$ contains a
  blue copy of~$\circBar_3$ with vertex set~$\{a,b,c\}$.  It now
  suffices to apply Lemma~\ref{lemma:technical} to conclude that~$\aG$
  contains a copy~$\circ_\ell$, contradicting that~$\aG$ is a
  $\circ_\ell$-free orientation of~$G$.  This completes the proof
  of~\eqref{eq:R_2_sparse}.  We now move on to the proof
  of~\eqref{eq:or_bound}.

  The digraph~$\aR$ can be associated with at most $(M+1)^n$
  partitions of~$V(G)$ into at most~$M+1$ parts.  Let
  $\cP=\{V_0,V_1,\ldots,V_k\}$ be one of those partitions,
  where~$m\leq k\leq M$.  To estimate $D_\aR(G,\circ_\ell)$, we
  shall estimate the number
  \begin{equation}
    \label{eq:D_cP_def}
    D(\cP,\aR)
  \end{equation}
  of $\circ_\ell$-free orientations~$\aG$ of~$G$ that admit~$\cP$ as
  an $(\varepsilon_{\rr},\aG,p)$-regular partition and, furthermore,
  $\aR$~is the coloured reduced digraph~$\aR(\aG,\varepsilon_{\rr},\delta,\cP)$.
  We shall then have
  \begin{equation}
    \label{eq:grand_total}
    D_\aR(G,\circ_\ell)=\sum_\cP D(\cP,\aR)\leq(M+1)^nD(\cP,\aR).
  \end{equation}
  
  By property~$\edge(\sigma,\varepsilon_{\e},p)$, there exist at most
  \begin{equation}
    \label{eq:es_within}
    (1+\epsilon_\e)p{n/k\choose2}k\leq2\varepsilon_{\rr} n^2p
  \end{equation}
  edges of~$G$ with both endpoints in the same~$V_i$ for some~$1\leq
  i\leq k$.

  Since $\sigma\leq\eta\leq\varepsilon_{\rr}/2$ and $|V_0|\leq\varepsilon_{\rr}
  n$, there is~$U_0\subset V(G)$ that contains~$V_0$ and with
  $|U_0|=\lfloor\varepsilon_{\rr} n\rfloor\geq\eta n\geq\sigma n$.
  Since~$G$ satisfies $\edge(\sigma,\varepsilon_{\e},p)$, by
  Fact~\ref{fact:EDGE->Upper}, we know that $G$ is $(\eta,p)$-upper
  uniform.  Thus, using $(\eta,p)$-upper uniformity, we know that the
  number of edges with only one endpoint in $U_0$ is at most
  $(1+\eta)\varepsilon_{\rr} n^2p$.  For the edges with both endpoints
  in $U_0$, we use the fact $G$ satisfies
  $\edge(\sigma,\varepsilon_{\e},p)$.  Recalling that $|U_0|\geq\sigma
  n$, we may conclude that the number of edges inside $U_0$ is at most
  $(1+\varepsilon_{\e})\varepsilon_{\rr}^2n^2p/2$.  Therefore, the number of
  edges with at least one endpoint in~$V_0\subset U_0$ is at most
  \begin{equation}
    \label{eq:V_0_edges}
    3\varepsilon_{\rr} n^2p.
  \end{equation}
  Let~$\aG$ be a $\circ_\ell$-free orientation of~$G$.  Note that the
  orientation of the at most~$5\varepsilon_{\rr} n^2p$ edges counted
  in~\eqref{eq:es_within} and~\eqref{eq:V_0_edges} does not affect
  whether or not~$\aG$ should be counted in~$D(\cP,\aR)$ (recall the
  definition of~$D(\cP,\aR)$, given near~\eqref{eq:D_cP_def}).
  Thus, the edges in~\eqref{eq:es_within} and~\eqref{eq:V_0_edges}
  contribute 
  \begin{equation}
    \label{eq:from_V_0}
    2^{5\varepsilon_{\rr} n^2p}
  \end{equation}
  to our count.  Now, the structure of~$\aR$ does impose
  restrictions on how the remaining edges of~$G$ may be oriented in
  any~$\aG$ that is counted in~$D(\cP,\aR)$.  We proceed to analyse
  those restrictions.  By the $(\eta,p)$-upper uniformity of~$G$ and
  the fact that~$|V_1|=\dots=|V_k|\geq n/2M\geq\eta n$, we know that
  \begin{equation}
    \label{eq:e(V_i,V_j)}
    e_G(V_i,V_j)\leq(1+\eta)\left(\frac{n}{k}\right)^2p\leq2\left(\frac{n}{k}\right)^2p, 
  \end{equation}
  for all~$1\leq i<j\leq k$.  Let us now count the number of ways
  those edges between~$V_i$ and~$V_j$ may be oriented in the~$\aG$
  counted in~$D(\cP,\aR)$.  To do so, let us observe that, clearly,
  any given pair~$\{i,j\}$ with~$1\leq i<j\leq k$ satisfies one of the
  following:
  \begin{enumerate}
  \item[(i)]At least one of~$(i,j)$ and~$(j,i)$ is not an arc
    of~$\aR$. 
  \item[(ii)]Both~$(i,j)$ and~$(j,i)$ are arcs of~$\aR$ and one of
    them is grey and the other one is blue.
  \item[(iii)]Both~$(i,j)$ and~$(j,i)$ are arcs of~$\aR$ and both of
    them are blue.
  \item[(iv)]Both~$(i,j)$ and~$(j,i)$ are arcs of~$\aR$ and both of
    them are grey.
  \end{enumerate}
  Note that, because of Lemma~\ref{lemma:propREG}, possibility~(iv) is
  excluded.  We now estimate in how many ways the edges
  in~\eqref{eq:e(V_i,V_j)} may be oriented, according to the `type' of
  the pair~$\{i,j\}$.

  \smallskip\noindent\textbf{Case 1.}\enspace\textit{The
    pair~$\{i,j\}$ is of type~{\rm(i)}.} The number of orientations of
  the edges in such pairs~$\{i,j\}$ is at
  most~$2^{\sum_{\{i,j\}}e_G(V_i,V_j)}$, where the sum ranges over all
  pairs~$\{i,j\}$ of this type.  Note that the number of
  such~$\{i,j\}$ is at most~$\varepsilon_{\rr} k^2$.  Hence,
  recalling~\eqref{eq:e(V_i,V_j)}, we see that
  \begin{equation}
    \label{eq:irreg}
    2^{\sum_{(i,j)}e_G(V_i,V_j)}\leq2^{2(n/k)^2p\varepsilon_{\rr} k^2}=2^{2\varepsilon_{\rr}
    n^2p}. 
  \end{equation}

  \smallskip\noindent\textbf{Case 2.}\enspace\textit{The
    pair~$\{i,j\}$ is of type~{\rm(ii)}.}
  Recalling~\eqref{eq:e(V_i,V_j)}, we see that the number of possible
  orientations of the edges in such a pair~$(V_i,V_j)$ is at most
  \begin{align}
    2\sum_{i=0}^{\lfloor\delta(n/k)^2p\rfloor}{(n/k)^2p(1+\eta)\choose i}
    &\leq2\delta\left(\frac{n}{k}\right)^2p{(n/k)^2p(1+\eta)\choose\delta(n/k)^2p(1+\eta)}\nonumber\\
    &\leq2\delta\left(\frac{n}{k}\right)^2p2^{\entrop(\delta)(n/k)^2p(1+\eta)}
    \leq2\delta\left(\frac{n}{k}\right)^2p2^{2\entrop(\delta)(n/k)^2p}.
  \end{align}
  The first inequality follows from the fact that~$\delta(1+\eta)<1/2$,
  and the second follows from the estimate~${x\choose\beta
    x}<2^{\entrop(\beta)x}$, valid for all~$0<\beta<1$ (see
  \cite{Ju11}, Corollary 22.9).  We now observe that the total
  contribution of the edges induced by pairs~$\{V_i,V_j\}$
  with~$\{i,j\}$ of type~(ii) is at most
  \begin{equation}
    \label{eq:sparse_pairs}
    \left(2\delta\left(\frac{n}{k}\right)^2p\right)^{k^2}2^{2\entrop(\delta)(n/k)^2pk^2}
    \leq n^{2k^2}2^{2\entrop(\delta)n^2p}
    \leq2^{3\entrop(\delta)n^2p},
  \end{equation}
  where we used that~$p\gg1/n$ to absorb~$n^{2k^2}$ into the
  exponential term.

  \smallskip\noindent\textbf{Case 3.}\enspace\textit{The
    pair~$\{i,j\}$ is of type~{\rm(iii)}.}  Recall that
  in~\eqref{eq:R_2_sparse} we proved that the number of
  pairs~$\{i,j\}$ of type~(iii) is at most~$\varepsilon_{\rr}^{1/2}k^2$.
  Calculations similar to the calculations in Case~1 show that the
  total contribution of the edges within pairs~$\{i,j\}$ of type~(iii)
  is at most
  \begin{equation}
    \label{eq:blue_pairs}
    2^{2\varepsilon_{\rr}^{1/2}n^2p}.
  \end{equation}

  \smallskip We now note that, by~\eqref{eq:from_V_0},
  \eqref{eq:irreg}, \eqref{eq:sparse_pairs} and~\eqref{eq:blue_pairs}
  and the choices of~$\delta$ and~$\varepsilon_{\rr}$, we have
  \begin{equation}
    \label{eq:D(P,R)}
    \log_2D(\cP,\aR)
    \leq5\varepsilon_{\rr} n^2p+2\varepsilon_{\rr} n^2p
    +3\entrop(\delta)n^2p+2\varepsilon_{\rr}^{1/2}n^2p
    \leq{\frac{\gamma}{4}}{n\choose2}p.
  \end{equation}
  From~\eqref{eq:grand_total}, \eqref{eq:D(P,R)} and the fact
  that~$p\gg1/n$, we deduce that
  \begin{equation}
    \label{eq:D_R(G,C_l)}
    D_\aR(G,\circ_\ell)
    \leq2^{n\log_2(M+1)+{\frac{\gamma}{4}}{n\choose2}p}
    \leq2^{\frac{\gamma}{2}{n\choose2}p},
  \end{equation}
  concluding the proof of Claim~\ref{claim:or_bound}.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:mainResult}}

We consider the supercritical and subcritical cases, respectively, in
Lemmas \ref{lemma:supercritical} and~\ref{lemma:subcritical}.
Theorem~\ref{thm:mainResult} follows from
Lemmas~\ref{lemma:supercritical} and~\ref{lemma:subcritical}.

\begin{lemma}
  \label{lemma:supercritical}
  Fix~$\ell\geq3$.  For every~$\gamma>0$ there exists~$C>0$ such that
  if~$p\geq Cn^{-1+1/(\ell-1)}$ and $G=G(n,p)$, then
  $D(G,\circ_\ell)\leq2^{\gamma{n\choose2}p}$ with probability
  $1-o(1)$.
\end{lemma}
\begin{proof}
  Let~$\ell\geq3$ and~$\gamma>0$ be given.  In what follows, we
  consider the case in which~$\ell$ is odd (the case in which~$\ell$
  is even is similar).  

  Let $\delta_{(\lem\ref{lemma:mainSuper})}$ be given by an
  application of Lemma~\ref{lemma:mainSuper} with parameters~$\ell$
  and~$\gamma$.  Let $\epsilon_{\rr(\teo\ref{thm:KLR})}$ be obtained
  by an application of Theorem~\ref{thm:KLR} with parameters~$\ell$
  and $\delta_{(\lem\ref{lemma:mainSuper})}/2$.  Following the
  quantification in Theorem~\ref{thm:KLR} applied with $\mu=1/2\ell
  M$, we obtain a constant~$C$.

  Suppose $p\geq Cn^{-1+1/(\ell-1)}$ and fix
  $\epsilon_{\f(\lem\ref{lemma:mainSuper})}<\min\{\epsilon_{\rr(\teo\ref{thm:KLR})}/\ell,
  1/\ell\}$. Now we continue the application of
  Lemma~\ref{lemma:mainSuper} with
  parameter~$\varepsilon_{\f(\lem\ref{lemma:mainSuper})}$, obtaining
  constants~$\varepsilon_{\e(\lem\ref{lemma:mainSuper})}$, $\sigma_{(\lem\ref{lemma:mainSuper})}$ and~$M$.

  Let $G = G(n,p)$. By Fact~\ref{fact:EDGE}
  applied with parameters~$\sigma_{(\lem\ref{lemma:mainSuper})}$
  and~$\varepsilon_{\e(\lem\ref{lemma:mainSuper})}$, we know $G$
  satisfies
  $\edge(\sigma_{(\lem\ref{lemma:mainSuper})},\varepsilon_{\e(\lem\ref{lemma:mainSuper})},p)$
  with probability $1-o(1)$. By Theorem~\ref{thm:KLR}, the graph $G$ contains no member
  of ${\calf(C_\ell, \tilde
    n,\lfloor(\delta_{(\lem\ref{lemma:mainSuper})}/2)\tilde
    n^2p\rfloor,z\varepsilon_{\f(\lem\ref{lemma:mainSuper})})}$ with
  probability ${1-o(1)}$, for
  any ${\tilde n \geq \lfloor n/\ell M\rfloor \geq \mu n}$. Therefore,
  by Lemma~\ref{lemma:mainSuper}, we conclude that $D(G,\circ_\ell)
  \leq 2^{ \gamma {n \choose 2}p}$ holds with probability $1- o(1)$.
\end{proof}

\begin{lemma}
  \label{lemma:subcritical}
  Fix~$\ell\geq3$.  For every~$\gamma>0$ there exists~$c>0$ such that
  if~${n\choose 2}^{-1}\ll p\leq c n^{-1+1/(\ell-1)}$ and~$G =
  G(n,p)$, then $D(G,\circ_\ell)\geq2^{(1-\gamma)\binom{n}{2}p}$
  with probability $1 - o(1)$.
\end{lemma}

\begin{proof}
  Let~$\ell\geq3$ and~$\gamma>0$ be given.
  Put~${c=\left(\gamma/16\ell\right)^{1/(\ell-1)}}$ and denote by
  $X_{C_\ell}$ the number of copies of $C_\ell$ in $G$.  We divide the
  proof in two cases, depending on the order of magnitude of~$p$.

  \smallskip\noindent\textbf{Case 1.}\enspace\textit{${n \choose
      2}^{-1} \ll p \ll n^{-1+1/(\ell -1)}$.}  It is easy to see that
  $\bbe(X_{C_\ell})\leq (np)^\ell$. Using Markov's inequality we have
  \begin{equation}
    \bbp\left( X_{C_\ell} \geq \frac{\gamma}{2\ell} {n \choose 2}p\right) \leq
    \frac{2\ell(np)^\ell}{\gamma{n\choose 2}p}. 
  \end{equation}
  Since~$p \ll n^{-1+1/(\ell -1)}$ we have~$\bbp\big( X_{C_\ell} \geq \gamma{n \choose 2}p/2\ell 
  \big) = o(1)$. Furthermore, since~${p \gg{n\choose 2}^{-1}}$, by Chernoff  
  bounds, $e\big(G(n,p)\big)\geq (1-\gamma/2){n\choose 2}p$ holds with probability $1-o(1)$.

  Assume that $X_{C_\ell} < (\gamma/2\ell)\binom{n}{2}p$. Consider the
  following procedure: fix the orientation of the edges that belong to
  cycles of length $\ell$ in $G$ according to some total order of the
  vertices of~$G$ and orient the remaining edges in any way.  An
  orientation generated by this procedure contains no copy of
  $\circ_\ell$. Therefore, with probability~$1-o(1)$, the
  number of such orientations is at least
  $2^{e(G(n,p))-(\gamma/2)\binom{n}{2}p}\geq
  2^{(1-\gamma)\binom{n}{2}p}$.

  \smallskip\noindent\textbf{Case 2.}\enspace\textit{$n^{-1} \ll p \leq
    c n^{-1+1/(\ell -1)}$.}  Since $p\gg n^{-1}$, we know
  that~$X_{C_\ell} < 2(np)^\ell$ holds with probability~${1-o(1)}$
  (see Theorem 4.4.4 in \cite{AlSp03}).  Furthermore, note that
  \begin{equation}
    \bbp\big(X_{C_\ell} \geq 2(np)^\ell\big) \geq \bbp\left(X_{C_\ell} \geq 
      \gamma\binom{n}{2}p/2\ell\right),
  \end{equation}
  and hence~$\bbp\big( X_{C_\ell} \geq \gamma{n \choose 2}p/2\ell
  \big) = o(1)$.  It now suffices to proceed as in Case~1.
\end{proof}

\section{Concluding remarks}
\label{sec:conclusion}

For simplicity, we restricted our attention to counting
$\circ_\ell$-free orientations.  Using versions of
Theorem~\ref{thm:KLR} that work for general graphs~$H$ (see, e.g.,
\cite{CoGoSaSc13+, SaTh13}), one may prove certain results on the
number of $\vec H$-free orientations of~$G(n,p)$ for
orientations~$\vec H$ of any given graph~$H$.

We have obtained satisfactory results for the random
variable~$D(G(n,p),\circ_{\ell})$ for~$p$ close to the
`threshold'. For $p$ substantially below the threshold (the subcritical case),
the value of~$D(G(n,p),\circ_{\ell})$ is a.a.s.\
$2^{e(G(n,p))-\Theta(p^\ell n^\ell)}$. A simple analysis of our proof
gives the lower bound part of this statement, while the upper bound part follows
from the fact that $\Omega(p^\ell n^\ell)$ edge-disjoint copies of $C_\ell$
exist in $G(n,p)$ in this range.

For $p$ substantially above the threshold (the supercritical case) we expect
that our results can be substantially improved. One may check that 
$D(K_n,\circ_\ell)$ is approximately $C^n n!$, where $C\ge 1$ depends
only on $\ell$
(and is equal to one if $\ell=3$). But this ceases to be true
for~$D(G(n,p),\circ_{\ell})$ when $p\ll 1$. It would be interesting to
determine more accurately the asymptotic value
of~$D(G(n,p),\circ_{\ell})$ as~$p$ varies from the threshold to~$1$.


%\bibliographystyle{amsplain}
%\bibliography{bibliografia}
\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}
\def\MR#1{\relax}
\begin{thebibliography}{10}

\bibitem{AlSp03}
N.~Alon and J.~H. Spencer, \emph{The probabilistic method}, second ed.,
  Wiley-Interscience Series in Discrete Mathematics and Optimization,
  Wiley-Interscience [John Wiley \& Sons], New York, 2000, With an appendix on
  the life and work of {P}aul {E}rd{\H o}s. \MR{2003f:60003}

\bibitem{AlYu06}
N.~Alon and R.~Yuster, \emph{The number of orientations having no fixed
  tournament}, Combinatorica \textbf{26} (2006), no.~1, 1--16. \MR{MR2201280
  (2006j:05095)}

\bibitem{Bo01}
B.~Bollob{\'a}s, \emph{Random graphs}, second ed., Cambridge Studies in
  Advanced Mathematics, vol.~73, Cambridge University Press, Cambridge, 2001.
  \MR{1864966 (2002j:05132)}

\bibitem{CoGoSaSc13+}
D.~Conlon, T.~Gowers, W.~Samotij, and M.~Schacht, \emph{On the {K{\L}R}
  conjecture in random graphs}, Submitted.

\bibitem{Er74}
P.~Erd{\H{o}}s, \emph{Some new applications of probability methods to
  combinatorial analysis and graph theory}, Proceedings of the {F}ifth
  {S}outheastern {C}onference on {C}ombinatorics, {G}raph {T}heory and
  {C}omputing ({F}lorida {A}tlantic {U}niv., {B}oca {R}aton, {F}la., 1974)
  (Winnipeg, Man.), Utilitas Math., 1974, pp.~39--51. Congressus Numerantium,
  No. X. \MR{MR0364020 (51 \#275)}

\bibitem{GeKoRoSt07}
S.~Gerke, Y.~Kohayakawa, V.~R{\"o}dl, and A.~Steger, \emph{Small subsets
  inherit sparse {$\epsilon$}-regularity}, J. Combin. Theory Ser. B \textbf{97}
  (2007), no.~1, 34--56. \MR{2278123 (2007i:05091)}

\bibitem{GeSt05}
S.~Gerke and A.~Steger, \emph{The sparse regularity lemma and its
  applications}, Surveys in combinatorics 2005, London Math. Soc. Lecture Note
  Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp.~227--258.
  \MR{MR2187740 (2006m:05118)}

\bibitem{JLR00}
S.~Janson, T.~{\L}uczak, and A.~Ruci{\'n}ski, \emph{Random graphs},
  Wiley-Interscience, New York, 2000.

\bibitem{Ju11}
S.~Jukna, \emph{Extremal combinatorics}, second ed., Texts in Theoretical
  Computer Science. An EATCS Series, Springer, Heidelberg, 2011, With
  applications in computer science. \MR{2865719}

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

\bibitem{KoKr97}
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{1609513 (99g:05159)}

\bibitem{KoRo03}
Y.~Kohayakawa and V.~R{\"o}dl, \emph{Szemer\'edi's regularity lemma and
  quasi-randomness}, Recent advances in algorithms and combinatorics, CMS Books
  Math./Ouvrages Math. SMC, vol.~11, Springer, New York, 2003, pp.~289--351.
  \MR{1952989 (2003j:05065)}

\bibitem{SaTh13}
D.~Saxton and A.~Thomason, \emph{Hypergraph containers}, 2013, submitted.

\end{thebibliography}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (flyspell-mode t)
%%% eval: (LaTeX-math-mode t)
%%% TeX-master: t
%%% End: