%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTeX file for
%
% ``A density result for random sparse oriented graphs and [...]'' 
%
% by Jair Donadelli and Yoshiharu Kohayakawa (8 pages)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Sunday 23 Jul 2000 04:57:20pm BRT yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[reqno]{amsart}

\newtheorem{teo}{Theorem}
\newtheorem{corol}[teo]{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{lema}[teo]{Lemma}
\newtheorem{conjec}{Conjecture}

\def\cal{\mathcal}
\def\eps{\varepsilon}
\let\epsilon=\varepsilon
\def\:{\colon}
\def\<{\leq}
\def\>{\geq}
\def\N{\mathbb N}

\newcommand{\pden}[3]{{d}_{#1}( #2,#3 )}% p-densidade de par (#1,#2)
\newcommand{\ars}[3]{{e}_{#3}( #1,#2 )}% no. de arestas e_#3(#1,#2)
\newcommand{\ex}[2]{\protect\operatorname{ex}( #1,#2 )}%no. de turan
\newcommand{\prob}[1]{{\mathbb P}\left( #1 \right)}%probabilidade

\begin{document}

\begin{abstract}
We shall prove that for all $\ell \>3$ and $\beta >0$ 
there exists a sparse oriented graph of arbitrarily large order with  
oriented girth $\ell$ and such that any $1/2 + \beta$ proportion of its
arcs induces an oriented cycle of length $\ell$. 
\end{abstract}

\title[A density result for random sparse oriented graphs]{A density result
  for random sparse oriented graphs and its relation to a conjecture of
  Woodall} 
\author{Jair Donadelli}
\author{Yoshiharu Kohayakawa}
\address{Instituto de Matem\'atica e Estat\'{\i}stica, Universidade de 
S\~ao Paulo, Rua do Mat\~ao 1010, 05508--900~S\~ao Paulo, Brazil}
\email{jair@ime.usp.br, yoshi@ime.usp.br}

\thanks{The first author was supported by a CNPq doctorate Studentship
  (Proc.~141633/1998-0). The second author was partially supported by
  FAPESP (Proc.~96/04505-2), by CNPq (Proc.~300334/93-1), and by
  MCT/FINEP/CNPq under PRONEX project 107/97.
}
\subjclass{05C20, 05C38, 05C80}
\keywords{Oriented graphs, Szemer\'edi's lemma, Random graphs}
\maketitle
\thispagestyle{empty}

\section{Introduction}

We call the pair~$\vec{G}=(V,E)$ an \textit{oriented graph} if the
set of vertices~$V$ is a finite set and the set of oriented
edges~$E\subseteq V\times V$, which we call \textit{arcs}, is such
that~$(v,v)\not\in E$ for any $v\in V$ and if~$(u,v)\in E$
then~$(v,u)\not\in E$. 
Our notation will basically follow \cite{MR80a:05120}.

The main result of this note, Theorem~\ref{teo:principal}, is related 
to a conjecture of Woodall, which we now describe.
Given an oriented graph~$\vec{G}=(V,E)$, we say that a subset
$B\subseteq E$ of  $E$ is an 
\textit{oriented cut} in $\vec{G}$ if there exists a subset $W\subseteq
V$ of $V$ such that $B=E(\vec{G})\cap(W\times\overline{W})$ and
$E(\vec{G})\cap(\overline{W}\times W)=\emptyset$, where
$\overline{W}=V\setminus W$.  
A subset~$F\subseteq E$ of~$E$ is a \textit{transversal} of the family
of oriented cuts of $\vec{G}$ if $F\cap B\neq \emptyset$ for all
oriented cuts $B$ in $\vec{G}$.

In 1978, Woodall~\cite{MR80a:05064} conjectured that, for any oriented
graph $\vec{G}$,  a minimum oriented cut in $\vec{G}$ has cardinality
equal to the maximum cardinality of a family of pairwise disjoint
transversals of  oriented cuts.
Woodall's conjecture has been proved in some particular cases. 
Feofiloff  and Younger~\cite{MR88j:05019}, and independently
Schrijver~\cite{MR84c:05045}, proved this conjecture for
source-sink connected graphs.  
An oriented graph is called \textit{source-sink connected} if it is
acyclic and each source is joined to each sink by an oriented path.  
Lee and Wakabayashi~\cite{lee:_nao} recently proved the conjecture for
series-parallel oriented graphs. 

To relate this conjecture to Theorem~\ref{teo:principal}, we consider
its dual version in the case of planar oriented  graphs. 
By the \textit{oriented girth} of $\vec{G}$, we mean the length
of a shortest oriented cycle in~$\vec{G}$. 
We call a subset~$D\subseteq E$ of the set of arcs~$E$ a
\textit{transversal} of the family of oriented cycles of $\vec{G}$ if
$D$ intersects all oriented cycles of~$\vec{G}$. From 
now on,  by a \textit{transversal} in an oriented graph $\vec{G}$, 
we mean a transversal of the family of oriented cycles of $\vec{G}$.

A dual version of Woodall's conjecture may be stated as follows: for
any planar oriented graph~$\vec{G}$, the oriented girth of $\vec{G}$
is equal to the maximum cardinality of a family of pairwise disjoint
transversals. 
In other words, this version of the conjecture states that if $\ell$ is
the oriented girth of $\vec{G}$ then $\ell$ is the largest $k\in
\mathbb{N}$ for which there exists a $k$-coloring of $E(\vec{G})$, say
$\varphi\colon E(\vec{G})\to [k]$, such that any oriented cycle of~$\vec G$
meets all the~$k$ colours, that is, $|\varphi(\vec{C})|=k$ for all oriented
cycles $\vec{C}\subseteq \vec{G}$.

We have learnt from D.~Younger~\cite{dy} that we cannot remove the
hypothesis of planarity from the dual  of Woodall's conjecture. 
Indeed, Thomassen constructed a tournament~$T$ on~$15$ vertices with
oriented girth~$3$ for which the smallest number of arcs we have to
delete to get rid of all oriented cycles is more than one third of its
arcs. Hence, the oriented girth of $T$ is larger than the maximum
cardinality of a family of pairwise disjoint transversals and,
therefore, $T$ is a counterexample to this generalized  dual statement. 

Thomassen's tournament is as follows. 
Take~$V(T)$ as the disjoint union of the sets
\[
\begin{split}
  X = \{x_1, x_2, x_3, x_4, x_5\}, \; Y = \{y_1, y_2, y_3, y_4,
  y_5\} \textrm{ and } Z = \{z_1, z_2, z_3, z_4, z_5\}.
\end{split}
\]

We define $E(T)$ first putting arcs on each of the subsets $X$, $Y$ and
$Z$, in such a way that we must delete at least three arcs from each of the
induced subgraphs $T[X]$, $T[Y]$ and $T[Z]$ to get rid of all the oriented
cycles in these subgraphs. 
For example, we may take the arcs on $X$ to be the 
union of the following three oriented cycles:
$(x_1,x_2)(x_2,x_3)(x_3,x_1)$, $(x_1,x_4)(x_4,x_5)(x_5,x_1)$ and
$(x_2,x_5)(x_5,x_3)(x_3,x_4)(x_4,x_2)$.   

Now add the arcs~$(y_i, x_i)$, $(x_i, z_i)$ and~$(z_i, y_i)$, for
each~$i\in\{1,2,3,4,5\}$. 
We complete the description of the set of arcs putting in
$E(T)$ the arcs $(x_i,y_j)$, for each pair $i\neq j \in
\{1,2,3,4,5\}$, plus the arcs $(y_i,z_j)$, for each pair $i\neq j \in
\{1,2,3,4,5\}$ and, finally, the arcs~$(z_i,x_j)$, for each pair
$i\neq j \in \{1,2,3,4,5\}$.  

A tedious case analysis shows that to destroy all oriented cycles
of~$T$ we have to delete a minimum of $20 + 5 + 5 + 3 + 3 +
3=39>35=105/3$ arcs, out of a total of $105$. 
Note that, in Thomassen's example $T$ above, we have that any subset of
$E(T)$ with at least $2/3$ of the 
arcs of $T$ induces an oriented cycle in $T$.
In this note we prove the following result. We write~$\vec{G}^n$ for
an oriented graph on $n$ vertices.  
%
\begin{teo}\label{teo:principal}
 Let an integer $\ell\>3$ and a real number $\beta >0$ be given. 
 For any  sufficiently large $n$, there exists an
 oriented graph $\vec{G}^n$ with $O(n^{1+1/(\ell-1)})$ arcs and
 oriented girth $\ell$ such that  any 
 $1/2 + \beta$ proportion of the arcs of $\vec{G}^n$ induces an
 oriented cycle of length $\ell$.
\end{teo}

This theorem is best possible in the following sense: any oriented
graph $\vec{G}$ contains a subgraph without oriented cycles and with
at least a half of its arcs, as may be seen by taking a random linear
ordering on $V(\vec{G})$. 

Theorem~\ref{teo:principal} goes beyond Thomassen's counterexample in 
that it
tells us that there exists an infinite
family of oriented graphs showing that the planarity hypothesis may
not be dropped from the dual version of Woodall's conjecture. 
More importantly, the graphs given by Theorem~\ref{teo:principal} are 
sparse, with vanishing density. 

\begin{corol}\label{corol:woodall}
  There exist infinitely many oriented graphs with vanishing density 
  whose oriented girth is larger than the maximum cardinality of a
  family of pairwise disjoint transversals.  
\end{corol}

This note is organized as follows. In the next section we shall
describe  the tools we need to prove Theorem~\ref{teo:principal}. 
The proofs of Theorem~\ref{teo:principal} and
Corollary~\ref{corol:woodall} are given in Section~\ref{sec:proofs}.  
We close with a remark in Section~\ref{sec:remark}.
In what follows, we often tacitly assume that~$n$ is large enough for
our inequalities to hold.

\section{Auxiliary results}

\subsection{Szemer\'edi's regularity lemma}
We now describe a version of Szemer\'edi's regularity lemma for sparse
oriented graphs.  

Given an oriented graph~$\vec{G}=(V,E)$, for any pair of disjoint
sets~$U$, $W \subseteq V$, we denote the set of arcs and the number of
arcs from~$U$ to~$W$ by $E_{\vec{G}}(U,W)$ and by
$$
\ars{U}{W}{\vec{G}} =\left|E_{\vec{G}}(U,W) \right| =\big| \left\{
  (a,b) \in E\: a\in U \textrm{ and } b\in W \right\} \big|,
$$
respectively.

Suppose that~$0<\eta \<1$, $D>1$ and~$0<p\<1$ are given real numbers. 
We say that~$\vec{G}$ is $(\eta,D,p)$-\textit{bounded} if, for any
pair of disjoint sets $U$, $W\subseteq V$ 
with~$|U|$, $|W|\>\eta |V|$, we have 
$$
\ars{U}{W}{\vec{G}}\<\frac{1}{2}Dp|U||W|.
$$
We define the~\textit{oriented $p$-density} from~$U$ to~$W$ in
$\vec{G}$ by
$$
\pden{\vec{G},p}{U}{W}=\frac{\ars{U}{W}{\vec{G}}}{(p/2)|U||W|}.
$$

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

We say that a partition~$\cal{P}=\{V_0,V_1,\dots,V_k\}$ of $V$ is
\textit{$(\eps,k,\vec{G},p)$-regular} if~$|V_0|\< \eps |V|$
and~$|V_i|=|V_j|$ for all~$i$, $j\in \{1,2,\dots,k\}$, and for more
than~$(1-\eps)\binom{k}{2}$ pairs~$\{i,j\}\subseteq \{1,2,\dots,k\}$,
$i\neq j$, 
we have that~$(V_i,V_j)$ and~$(V_j,V_i)$ are both
$(\eps,\vec{G},p)$-regular.  

In this note, we shall use the following lemma, which is a natural
variant of Szemer\'edi's regularity lemma.
In fact, this is a version for sparse oriented graphs of a lemma
observed independently by Kohayakawa and R\"odl (see,
e.g.,~\cite{MR99g:05145}).  
%
\begin{lema}\label{le:regularidade}
  For any real number $\eps>0$, integer $k_0\geq1$  and  real number 
   $D>1$, there exist constants 
  $\eta=\eta(\eps,k_0,D)>0$ and $K=K(\eps,k_0,D)\geq k_0$ such that,  
  for any  $0<p=p(n)\leq1$, any $(\eta,D,p)$-bounded oriented graph 
  $\vec{G}=\vec{G}^n$ admits an $(\eps,k,\vec{G},p)$-regular partition
   for some $k_0\leq k\leq K$. \qed 
\end{lema}
%

\subsection{A counting lemma}
Suppose that~$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, 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$, $\gamma \<1$ be positive real
numbers and let an integer $T\>1$ be given. 
We call~$\vec{F}$
an~\textit{$(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graph} if  
\begin{enumerate}\renewcommand{\labelenumi}{(\roman{enumi})}
\item $E(\vec{F})=\bigcup_{i=1}^{\ell} E(V_i,V_{i+1})$ 
  and~$|E(\vec{F})| = T$.
\item For all~$1\<i\<\ell$ we have that the pairs~$(V_i,V_{i+1})$
  are~$(\eps,\vec{F},\overline{p})$-regular,
  with~$\overline{p}=Bm^{-1+1/(\ell-1)}$, and their
  oriented~$\overline{p}$-density satisfies 
$$
\gamma \< \pden{\vec{F},\overline{p}}{V_i}{V_{i+1}} \< D.
$$
\item For any~$U\subseteq V_i$ and~$W \subseteq V_{i+1}$, where
  $1\<i<\ell-1$, such that 
  $$|U|\<|W|\<\frac{1}{2}\overline{p}m|U|\<\left(\frac{1}{2}\overline{p}m\right)^{\ell-2},$$ 
we have 
\begin{equation}\label{eq:localsparseness}
\ars{U}{W}{}\< C|W|.
\end{equation}
\end{enumerate}

The main technical result that we shall need is as follows. 
We denote by~$\vec{C}^{\ell}$ the oriented cycle of length~$\ell$.  

\begin{lema}\label{le:contagem}
  Let an integer~$\ell\geq3$ be fixed, and let constants $\sigma>0$, 
  $0<\alpha\leq1$, $0<\gamma\leq1$, $C\geq1$ and $D\geq1$.
  be given.  
  Then there exist positive constants
  $\eps=\eps(\ell,\sigma,\alpha,\gamma,C,D)\leq1$,
  $B_0=B_0(\ell,\sigma,\alpha,\gamma,C,D)>0$, and  
  $m_0=m_0(\ell,\sigma,\alpha,\gamma,C,D)$ such
  that, for all integers $m\geq   m_0$ and $T\geq1$, and all
  real~$B\geq B_0$, the following holds.  
  The number of $(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graphs 
  containing less than $\sigma m^{\ell/(\ell -1 )}$ cycles
  $\vec{C}^{\ell}$ is at most    
  \begin{equation}\label{eq:expbound}
  \alpha^T \binom{({\ell}+2)m^2}{T}.
  \end{equation}\qed
\end{lema}

We shall not prove Lemma~\ref{le:contagem} here.  The interested reader may
check Kohayakawa and Kreuter~\cite{MR99g:05159}, where it is proved that the
number of $(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graphs containing
\textit{no} $\vec{C}^{\ell}$'s is at most as given by~(\ref{eq:expbound})
above.  It may be checked that the proof of this result in~\cite{MR99g:05159},
with some more bookkeeping, does in fact prove Lemma~\ref{le:contagem} above.

\section{Proof of Theorem~\ref{teo:principal}}\label{sec:proofs}

To prove our main result, we first need to recall some standard
definitions.  
Given~$0<p\<1$, for any positive integer~$n$ we write~$G_{n,p}$
for the random graph in the standard binomial model, where~$n$ is
the number of vertices and $p$ is the probability of edges. From~$G_{n,p}$ 
we get the \textit{random oriented
  graph}~$\vec{G}_{n,p}$ by putting, for each edge $\{u,v\}\in
E(G_{n,p})$ in $G_{n,p}$,  
$$
\prob{(u,v)\in  E(\vec{G}_{n,p})}=1 - \prob{(v,u)\in
  E(\vec{G}_{n,p})}=1/2,
$$
with all these orientations independent.

Let us now start our proof.  Let~$\ell\geq3$ and~$\beta>0$ be as given in
Theorem~\ref{teo:principal}.  Put $\delta=\beta/2$ and set 
\[ 
\gamma =\frac{{\delta}}{5}, \; \alpha = \frac{\gamma
  \ell}{\textrm{e}^2(\ell+2)}, \; C = 4(\ell-1), \; D = 2, \; \sigma =
  \frac{1}{2}, \textrm{ and }  \varrho 
  = \frac{\delta}{4}.
\]
Then, there are constants~$\eps$, $B_0$, and~$m_0$ for which the upper  
bound of Lemma~\ref{le:contagem} holds for the constants $\ell$, $\sigma$, 
$\alpha$, $\gamma$, $C$, and~$D$ as above.
We may suppose~$\eps <\delta/16$.  

In order to apply Lemma~\ref{le:regularidade},
take
\begin{equation}
  \label{eq:k_0_def}
  k_0=\max\{4/{\delta},s\},
\end{equation}
where $s$ is such that for any 
integer $k\>s$ we have that
$\ex{k}{C^\ell}<(1/2+\varrho)\binom{k}{2}$, where $\ex{k}{C^\ell}$ 
is the Tur\'an number (see, e.g.,~\cite{MR80a:05120}) for the cycle 
$C^{\ell}$ of length $\ell$. 
We observe that when $\ell$ is even, we could even omit ``1/2'' in the
definition of $s$, as $\ex{k}{C^{\ell}}=o(k^2)$.
 
Let~$\eta$ and~$K$ be the constants given by
Lemma~\ref{le:regularidade} when applied to~$\epsilon$, $k_0$, and~$D$ as
above. 
We may suppose~$\eta < \delta/20$.  
Put $$ A = B_0 
K^{1-{1}/{(\ell-1)}} \quad \textrm{ and } \quad p=An^{-1+1/(\ell-1)}.$$

We prove Theorem~\ref{teo:principal} using the claims below, whose
proofs we postpone.

Define~$\cal{OG}=\cal{OG}(n)$, for all $n\in\N$, as the set of all
oriented graphs~$\vec{G}^n$ on $V=V(\vec{G}^n)=[n]$ satisfying 
the following properties:
\begin{enumerate}\renewcommand{\labelenumi}{(\roman{enumi})}
\item $\vec{G}^n$ is $(\eta,1+\eta, p)$-bounded,
\item $e(\vec{G}^n)=(1+o(1))\binom{n}{2}p$,
\item for any pair of disjoint non-empty 
sets~$U$, $W\subseteq V$ satisfying
\begin{equation}
  \label{eq:local}
  |U|\<|W|\<\frac{1}{2}pn|U|\<\left(\frac{1}{2}pn\right)^{\ell-2},
\end{equation}
the upper bound on the number of arcs~(\ref{eq:localsparseness})
holds.
\end{enumerate}

Using Lemma~\ref{le:regularidade} we prove that graphs in $\cal{OG}$
contain $(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graphs in a very
robust way.

\begin{claim}\label{cl:deterministic}
  For any $\vec{G}^n \in \cal{OG}$ with large enough~$n$, we have that any 
  subgraph $\vec{J}\subseteq 
  \vec{G}^n$ of $\vec{G}^n$ with
  \begin{equation}\label{eq:ars}
  e(\vec{J})\>\left(\frac{1}{2}+\delta \right)\frac{n^2p}{2}
  \end{equation}
  arcs contains a subgraph isomorphic to an 
  $$
  (\eps,\gamma,pm^{1-1/(\ell-1)},C,D;\mathbf{V}^{(m)},T) \textrm{-graph}, 
  $$ 
  for some integer $m$, with $n/2K\<m\<n/k_0$, and some integer~$T\>1$. 
\end{claim}
%

Let $\cal{OG}'$ be the set of graphs~$\vec G^n$ from $\cal{OG}$ such that
\begin{enumerate}\renewcommand{\labelenumi}{(\roman{enumi})}\setcounter{enumi}{3}
\item any subgraph of $\vec{G}^n$ isomorphic to  an
  $(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graph, 
  where $n/2K\<m\<n/k_0$, $B=pm^{1-1/(\ell-1)}$ and $T\>1$, contains
at least $ \sigma_0n^{\ell/(\ell-1)}$ oriented cycles
$\vec{C}^{\ell}$, where $\sigma_0=\sigma (2K)^{-\ell/(\ell-1)}$,  
\item the number of oriented cycles of length at most $\ell - 1$ in
$\vec{G}^n$ is no larger than $\bar{A}n^{\ell/(\ell-1)}/\log \log n$, where
$\bar{A}=(1/16)\max\{\ell -1,(\ell -1)A^{\ell -1}\}$.
\end{enumerate}
The family $\cal{OG}'$ is not empty; in fact, most graphs~$\vec{G}_{n,p}$ are
in~$\cal{OG}'$, as our next result states.

\begin{claim}\label{cl:probabilistic}
With probability tending to~$1$ as~$n$
tends to infinity, we have $\vec{G}_{n,p}\in \cal{OG}'$.
\end{claim}

We may now complete the proof of Theorem~\ref{teo:principal} using
Claims~1 and~2.

Fix a graph~$\vec{F}^n \in \cal{OG}'$. 
Let $\vec{G}^n$ be a  graph obtained from $\vec{F}^n$ deleting one arc
from each of the at most $\bar{A}{n^{\ell/(\ell -1)}}/\log \log n$
cycles of length at most $\ell -1$ in $\vec{F}^n$. 
Then, as it is easily seen, we have $\vec{G}^n\in \cal{OG}$, and, by Claim~1, 
any subgraph 
$\vec{J}\subseteq \vec{G}^n$ with $e(\vec{J})\>(1/2
+\beta)e(\vec{G}^n)\>(1/2+\delta)n^2p/2$ contains an
$$
\text{$(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graph,}
$$
where~$B=pm^{1-1/(\ell-1)}$.  
As $\vec{G}^n
\subseteq \vec{F}^n \in \cal{OG}'$ we have, by (iv) from definition of
$\cal{OG}'$, that each $\vec{J}$ as above contains
$(1-o(1))\sigma_0n^{\ell/(\ell -1)}>0$ oriented cycles $\vec{C}^{\ell}$.

We have thus obtained an oriented graph satisfying the conclusions of
Theorem~\ref{teo:principal}, as required. \qed

\subsection{Proof of Claim 1}
Let $\vec{J}$ be an oriented graph as in the statement of Claim~1. 
Clearly, $\vec{J}$ is $(\eta, 1+\eta,p)$-bounded (hence,
$(\eta,D,p)$-bounded). 

Let~$\cal{P}=(V_i)_{i=0}^{k}$ be an~$(\eps,k,\vec{J},p)$-regular
partition given by Lemma~\ref{le:regularidade} with the above choices
of $\varepsilon$, $k_0$ and $D$. 
Put~$m=|V_i|\<n/k$, for any~$i\in [k]=\{1,\dots,k\}$. 

Call $R$ the graph whose vertex set is~$\{V_1,\dots,V_k\}$
with~$\{V_i,V_j\}$ an edge in $R$
if both densities~$\pden{\vec{J},p}{V_i}{V_j}$ and
$\pden{\vec{J},p}{V_j}{V_i}$ are at least $\gamma$ and $(V_i,V_j)$
and $(V_j,V_i)$ are $(\eps,\vec{J},p)$-regular. 
Suppose that~$e(R)<(1/2+\varrho)\binom{k}{2}$.

The number of arcs in $\vec{J}$ is 
\[
\begin{split}
  e(\vec{J})\<
 & \bigg\{\eps  n^2+k\binom{n/k}{2} +
  \eps\binom{k}{2}\left(\frac{n}{k}\right)^2 +
  \gamma\binom{k}{2}\left(\frac{n}{k}\right)^2 +\\ 
  & \qquad \qquad \qquad \qquad \qquad \qquad %\qquad \qquad \qquad
  +\left(\frac{1}{2}+\varrho
  \right)\binom{k}{2}\left(\frac{n}{k}\right)^2 \bigg\}
(1+\eta){p}
 \\<
 &  \left( 4\eps + \frac{1}{k} + \gamma + \frac{1}{2} +
  \varrho \right)(1 + \eta)\frac{n^2p}{2}  \\<
 & \left( 4\eps +
  \frac{1}{k} + \gamma + \frac{1}{2} + \varrho  + \eta
  \right)\frac{n^2p}{2} \\  <
&  \left(\frac{1}{2} + \delta \right)\frac{n^2p}{2},
\end{split}
\]
contradicting~(\ref{eq:ars}).

Therefore, $R$ contains at least~$(1/2+\varrho)\binom{k}{2}$ edges
and, because of the choice of~$k_0$ (see~\eqref{eq:k_0_def}), we may conclude
that~$R$ contains a 
cycle~${V_{i_1}},\dots,{V_{i_{\ell}}}$. 

Thus, we have an
$(\eps,\gamma,pm^{1-1/(\ell-1)},C,D;\mathbf{V}^{(m)},T)$-graph given
by taking~$\textbf{V}^{(m)}$ as the vector
$({V_{i_1}},\dots,{V_{i_{\ell}}})$ of pairwise disjoint subsets of
$V(\vec{J})$, putting the set of arcs as the set~$\bigcup_{j=1}^{\ell}
E_{\vec{J}}({V_{i_j}},{V_{i_{j+1}}})$ (here the indices are taken
modulo~$\ell$), and letting~$T$ be the cardinality of 
this union. For these choices of $\mathbf{V}^{(m)}$ and $T$, and the
above choices for $\eps$, $\gamma$, $B$, $C$ and $D$ one may easily
check properties~(i)--(iii) from the definition 
of an~$(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-graph. This completes
the proof of {Claim 1}. 

\subsection{Proof of Claim 2}
We prove that $\vec{G}_{n,p}$, with the above choice
for $p$, satisfies items (i)--(iii) of the definition of $\cal{OG}$
and (iv) and (v) of the definition of $\cal{OG}'$ with
probability tending to $1$ as $n$ tends to infinity.

To check that (i) holds with high probability, observe that by
Chernoff's inequality, for all pairs of disjoint sets~$U$, $W \subseteq 
V$ with~$|U|$, $|W|\>\eta n$, we have  
\[
\begin{split}
\prob{\ars{U}{W}{} > (1+\eta)\frac{p}{2}|U||W|} & \< \mathrm{exp}
\left\{ -\frac{1}{3}\eta^2\frac{p}{2}|U||W|\right\} \\
& \< \textrm{exp}\left\{ -\frac{A}{6}\eta^4n^{1+1/(\ell-1)}\right\}.
\end{split}
\]
Then, the expected number of pairs of sets $U$, $W\subseteq V$, where
$V=V(G_{n,p})$, with at least $\eta n$  vertices and that violate the
$(\eta,1+\eta, p)$-boundedness condition is at most  
$4^n\textrm{exp}\{-A6^{-1}\eta^4n^{1+1/(\ell-1)}\}=o(1)$.  
Thus, if $X$ is the number of pairs of sets $U$, $W\subseteq V$ with at
least $\eta n$  vertices and that violate the
$(\eta,1+\eta,p)$-boundedness condition, then we have, by Markov's
inequality, that
$\prob{X>0}<4^n\textrm{exp}\{-A6^{-1}\eta^4n^{1+1/(\ell-1)}\}=o(1)$. 

We have (ii) with high probability from Chernoff's inequality. 
In fact, we easily verify that for any $\rho >0$ the probability that
$|e(\vec{G}_{n,p}) - p\binom{n}{2}| > \rho p \binom{n}{2}$ is
exponentially small in $pn^2$. 

In order to prove that properties~(iii) and~(iv) hold for $G_{n,p}$ with
probability $1-o(1)$, we again apply Markov's inequality to appropriate random
variables. 
 
Let us consider~(iii) first. 
Let~$U$, $W\subseteq V$ be disjoint sets satisfying~(\ref{eq:local}). 
To verify that (iii) holds with high probability, notice that the
probability that~(\ref{eq:localsparseness}) fails is 
$$
\prob{\ars{U}{W}{} > C|W|} \< \binom{|U||W|}{C|W|}\left( \frac{p}{2}
\right)^{C|W|} \<
\left(\frac{\textrm{e}}{C}\cdot\frac{p|U|}{2}\right)^{C|W|}.
$$

Observe that~$(1/2)p|U| \< ((1/2)pn)^{\ell-2}/n \< 
(A/2)^{\ell-2}n^{{-1}/({\ell -1})}$.  From 
$n-|U| \> n-|W| \> |W|$, where the last inequality comes 
from~$|W|=o(n)$, we may 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 subsets~$U$
and~$W$, with cardinalities~$u$ and 
$w$ respectively, for which~(\ref{eq:local})
holds and $e(U,W)>C|W|$, is at most
\[
\begin{split}
   \sum_{1\<w<n/2}\sum_{u=1}^{w}&
  \binom{n}{u}\binom{n}{w}\left(  \frac{\mathrm{e}}{C}\cdot\frac{pu}{2} \right)^{Cw}  
  \<  \sum_{1\<w<n/2} w \binom{n}{w}^2 \left(
  \frac{\mathrm{e}}{C} \left( \frac{A}{2}\right)^{\ell
  -2}n^{{-1}/({\ell -1})}\right)^{Cw}  \\ \<  
& \sum_{1\<w<n/2}w \left(\frac{\mathrm{e}n}{w}\right)^{2w} \left(
  \frac{\mathrm{e}}{C}\left( \frac{A}{2}
  \right)^{\ell-2}n^{{-1}/({\ell-1})}\right)^{Cw} \\ = 
& \sum_{1\<w<n/2} \frac{w}{w^{2w}}\left(
  \frac{\mathrm{e}^{1+2/C}}{C}\left(
  \frac{A}{2}\right)^{\ell-2} n^{(2/C) - (1/(\ell -1))}\right)^{Cw}\\ =
& \sum_{1\<w<n/2} \frac{w}{w^{2w}} \left(
  \frac{\mathrm{e}^{1+{2}/C}}{C}\left(
  \frac{A}{2}\right)^{\ell-2} n^{{-2}/{C}}\right)^{Cw} =  o(1),
\end{split}
\]
for $C=4(\ell -1)$.  Thus~(iii) holds with probability~$1-o(1)$.

We now turn to~(iv).  Notice that we have~$K\>n/m$, and hence
$$
B=pm^{1-1/(\ell-1)} \> B_0(Km/n)^{1-1/(\ell-1)} \> B_0.
$$ 
Observe that the number of arcs~$T$ is at least~$\gamma(p/2)m^2\ell$,
and the expected number of
$(\eps,\gamma,B,C,D;\mathbf{V}^{(m)},T)$-subgraphs of~$\vec{G}_{n,p}$
containing at most $\sigma_0 n^{\ell/(\ell -1)}\<\sigma
m^{\ell/(\ell -1)}$ cycles $\vec{C}^{\ell}$ 
of length $\ell$ is $o(1)$. 
In fact, for any given positive integers~$m$
and~$T\>\gamma(p/2)m^2\ell$, this expected 
number is, by Lemma~\ref{le:contagem},  at most 
\[
\begin{split}
  ({n})_{\ell m}\alpha^T \binom{(\ell+2)m^2}{T} \left( \frac{p}{2}
  \right)^T  & \<  n^{\ell m}  \left( \alpha \cdot \frac{\mathrm{e}
  (\ell+2) m^2}{T}\cdot \frac{p}{2} \right)^T \\ 
& \< n^{\ell m} \left(  \frac{\mathrm{e}\alpha(\ell+2)}{\ell\gamma}
  \right)^T  \\
& = n^{\ell m}  \left(  \frac{\mathrm{1}}{\mathrm{e}} \right)^T \\
& \<\exp\left\{ (\log n)m\ell  - \gamma(p/2)m^2\ell\right\}\\
& =o(n^{-3}).
\end{split}
\]
Summing over all possible choices for~$m$ and~$T$, we only have 
an additional factor of at most~$n^3$.  Thus~(iv) holds with
probability~$1-o(1)$ by Markov's inequality.

Finally, the  expected number of short oriented cycles is 
$$
\sum_{i=3}^{\ell -1}\frac{(n)_i}{2i}\left( \frac{p}{2} \right)^i \<
\frac{1}{16}\sum_{i=3}^{\ell -1}n^ip^i \< \bar{A}n.
$$

Invoking Markov's inequality again, we see that 
the probability that  the  number of
short oriented cycles should be greater than $\bar{A}
{n^{\ell/(\ell-1)}}/{\log \log n}$ is smaller than ${\log \log
  n}/{n^{1/(\ell -1)}}=o(1)$. 

\subsection{Proof of Corollary~\ref{corol:woodall}}
Let $\ell \>3$ be an integer. Set $\beta = 1/2 - 1/\ell$ and let
$\vec{G}^n$ be an oriented graph with oriented girth $\ell$ given by
Theorem~\ref{teo:principal}. 

Suppose we have a family $\cal{T}$ of pairwise disjoint transversals of
cardinality $|\cal{T}|=\ell$. Let $\vec{H}$ be the graph obtained from
$\vec{G}^n$ by deleting a transversal $T\in \cal{T}$ of this
family that satisfies $|T|\< e(\vec{G}^n)/\ell$. 
We have $e(\vec{H})\>(1-1/\ell)e(\vec{G}^n)=(1/2+\beta)e(\vec{G}^n)$
and, by Theorem~\ref{teo:principal}, the oriented graph $\vec{H}$ must
contain an oriented cycle, contradicting the fact that $T$ should be a
transversal. 

\section{Concluding remark}
\label{sec:remark}

Both Theorem~\ref{teo:principal} and Corollary~\ref{corol:woodall} assert the
existence of sparse oriented graphs, with some given oriented girth~$\ell$,
that contain oriented $\ell$-cycles in a very robust way.  Our proof technique
is non-constructive.  It would be interesting to see whether one is able to
prove these results constructively.

\bibliographystyle{amsplain}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{1}

\bibitem{MR80a:05120}
B{\'e}la Bollob{\'a}s, \emph{Extremal graph theory}, Academic Press Inc.
  [Harcourt Brace Jovanovich Publishers], London, 1978.

\bibitem{MR88j:05019}
P.~Feofiloff and D.~H. Younger, \emph{Directed cut transversal packing for
  source-sink connected graphs}, Combinatorica \textbf{7} (1987), no.~3,
  255--263.

\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.

\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.

\bibitem{lee:_nao}
Orlando Lee, \emph{Circuit covers in mixed graphs}, Doctoral thesis, Instituto
  de Matem\'atica e Estat\'{\i}stica, Universidade de S\~ao Paulo, 1999, in
  Portuguese.

\bibitem{MR84c:05045}
A.~Schrijver, \emph{Min-max relations for directed graphs}, Bonn Workshop on
  Combinatorial Optimization (Bonn, 1980), North-Holland, Amsterdam, 1982,
  pp.~261--280.

\bibitem{MR80a:05064}
D.~R. Woodall, \emph{Menger and {K}\"onig systems}, Theory and applications of
  graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976),
  Springer, Berlin, 1978, pp.~620--635.

\bibitem{dy}
D.H. Younger, \emph{Private communication to {Y}.~{W}akabayashi}.

\end{thebibliography}

\end{document}
