A DENSITY RESULT FOR RANDOM SPARSE ORIENTED GRAPHS AND ITS RELATION TO A CONJECTURE OF WOODALL

JAIR DONADELLI AND YOSHIHARU KOHAYAKAWA

Abstract. We shall prove that for all ℓ ≥ 3 and β > 0 there exists a sparse oriented graph of arbitrarily large order with oriented girth ℓ and such that any 1/2 + β proportion of its arcs induces an oriented cycle of length ℓ.

1. Introduction

We call the pair G⃗ = (V, E) an oriented graph if the set of vertices V is a finite set and the set of oriented edges E ⊆ V × V, which we call arcs, is such that (v, v) ∉ E for any v ∈ V and if (u, v) ∈ E then (v, u) ∉ E. Our notation will basically follow [1].

The main result of this note, Theorem 1, is related to a conjecture of Woodall, which we now describe. Given an oriented graph G⃗ = (V, E), we say that a subset B ⊆ E of E is an oriented cut in G⃗ if there exists a subset W ⊆ V of V such that B = E(G⃗) ∩ (W × \overline{W}) and E(G⃗) ∩ (\overline{W} × W) = ∅, where \overline{W} = V \ W. A subset F ⊆ E of E is a transversal of the family of oriented cuts of G⃗ if F ∩ B ≠ ∅ for all oriented cuts B in G⃗.

In 1978, Woodall [7] conjectured that, for any oriented graph G⃗, a minimum oriented cut in 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 [2], and independently Schrijver [6], proved this conjecture for source-sink connected graphs. An oriented graph is called source-sink connected if it is acyclic and each source is joined to each sink by an oriented path. Lee and Wakabayashi [5] recently proved the conjecture for seriesparallel oriented graphs.

To relate this conjecture to Theorem 1, we consider its dual version in the case of planar oriented graphs. By the oriented girth of G⃗, we mean the length of a shortest oriented cycle in G⃗. We call a subset D ⊆ E of the set of arcs E a transversal of the family of oriented cycles of G⃗ if D intersects all oriented cycles of G⃗. From now on, by a transversal in an oriented graph G⃗, we mean a transversal of the family of oriented cycles of G⃗.

A dual version of Woodall’s conjecture may be stated as follows: for any planar oriented graph G⃗, the oriented girth of 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 ℓ is the oriented girth of G⃗ then ℓ is the largest k ∈ ℕ for which there exists a k-coloring of E(G⃗), say φ: E(G⃗) → [k], such that any oriented cycle of G⃗ meets all the k colours, that is, |φ(C⃗)| = k for all oriented cycles C⃗ ⊆ G⃗.

1991 Mathematics Subject Classification. 05C20, 05C38, 05C80.

Key words and phrases. Oriented graphs, Szemerédi’s lemma, Random graphs.

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.

We have learnt from D. Younger [8] 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

X = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}, Y = {y_{1}, y_{2}, y_{3}, y_{4}, y_{5}} and Z = {z_{1}, z_{2}, z_{3}, z_{4}, z_{5}}.

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 ∈ {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 ≠ j ∈ {1, 2, 3, 4, 5}, plus the arcs (y_{i}, z_{j}), for each pair i ≠ j ∈ {1, 2, 3, 4, 5} and, finally, the arcs (z_{i}, x_{j}), for each pair i ≠ j ∈ {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 G⃗^{n} for an oriented graph on n vertices. Theorem 1. Let an integer ℓ ≥ 3 and a real number β > 0 be given. For any sufficiently large n, there exists an oriented graph G⃗^{n} with O(n^{1+1/(ℓ−1)}) arcs and oriented girth ℓ such that any 1/2 + β proportion of the arcs of G⃗^{n} induces an oriented cycle of length ℓ.

This theorem is best possible in the following sense: any oriented graph 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 (G⃗).

Theorem 1 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 1 are sparse, with vanishing density. Corollary 2. 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.

This note is organized as follows. In the next section we shall describe the tools we need to prove Theorem 1. The proofs of Theorem 1 and Corollary 2 are given in Section 3. We close with a remark in Section 4. In what follows, we often tacitly assume that n is large enough for our inequalities to hold.

2. Auxiliary results

2.1. Szemerédi’s regularity lemma. We now describe a version of Szemerédi’s regularity lemma for sparse oriented graphs.

Given an oriented graph G⃗ = (V, E), for any pair of disjoint sets U, W ⊆ V, we denote the set of arcs and the number of arcs from U to W by EG⃗(U, W) and by

eG⃗(U, W) = |EG⃗(U, W)| = | {(a, b) ∈ E: a ∈ U and b ∈ W } |,

respectively.

Suppose that 0 < η ≤ 1, D > 1 and 0 < p ≤ 1 are given real numbers. We say that G⃗ is (η, D, p)-bounded if, for any pair of disjoint sets U, W ⊆ V with |U|, |W | ≥ η|V |, we have

eG⃗(U, W) ≤ \frac{1}{2}Dp|U||W |.

We define the oriented p-density from U to W in G⃗ by

d_{G⃗,p}(U, W) = \frac{eG⃗(U, W)}{(p/2)|U||W |}.

For any 0 < ε ≤ 1 the pair of disjoint non-empty sets (U, W), with U, W ⊆ V, is said to be (ε, G⃗, p)-regular if for all U′ ⊆ U, with |U′| ≥ ε|U|, and all W′ ⊆ W, with |W′| ≥ ε|W |, we have

|d_{G⃗,p}(U, W) − d_{G⃗,p}(U′, W′)| < ε.

We say that a partition P = {V_{0}, V_{1}, …, V_{k}} of V is (ε, k, G⃗, p)-regular if |V_{0}| ≤ ε|V | and |V_{i}| = |V_{j}| for all i, j ∈ \{1, 2, …, k\}, and for more than (1 − ε)\binom{k}{2} pairs {i, j} ⊆ {1, 2, …, k}, i ≠ j, we have that (V_{i}, V_{j}) and (V_{j}, V_{i}) are both (ε, G⃗, p)-regular.

In this note, we shall use the following lemma, which is a natural variant of Szemerédi’s regularity lemma. In fact, this is a version for sparse oriented graphs of a lemma observed independently by Kohayakawa and Rödl (see, e.g., [3]). Lemma 3. For any real number ε > 0, integer k_{0} ≥ 1 and real number D > 1, there exist constants η = η(ε, k_{0}, D) > 0 and K = K(ε, k_{0}, D) ≥ k_{0} such that, for any 0 < p = p(n) ≤ 1, any (η, D, p)-bounded oriented graph G⃗ = G⃗^{n} admits an (ε, k, G⃗, p)-regular partition for some k_{0} ≤ k ≤ K. □

2.2. A counting lemma. Suppose that m > 0 and ℓ ≥ 3 are fixed integers and V^{(m)} = (V_{i})_{i=1}^{ℓ} is a fixed vector of pairwise disjoint sets, each of cardinality m. Below, the indices of the V_{i}’s will be taken modulo ℓ. Let B > 0, C ≥ 1, D > 1, ε ≤ 1, γ ≤ 1 be positive real numbers and let an integer T ≥ 1 be given. We call F⃗ an (ε, γ, B, C, D; V^{(m)}, T)-graph if

(i) E(F⃗) = ⋃_{i=1}^{ℓ} E(V_{i}, V_{i+1}) and |E(F⃗)| = T.

(ii) For all 1 ≤ i ≤ ℓ we have that the pairs (V_{i}, V_{i+1}) are (ε, F⃗ , \overline{p})-regular, with \overline{p} = Bm^{−1+1/(ℓ−1)}, and their oriented \overline{p}-density satisfies

γ ≤ d_{F⃗ ,\overline{p}}(V_{i}, V_{i+1}) ≤ D.

(iii) For any U ⊆ V_{i} and W ⊆ V_{i+1}, where 1 ≤ i < ℓ − 1, such that

|U| ≤ |W | ≤ \frac{1}{2}\overline{p}m|U| ≤ (\frac{1}{2}\overline{p}m)^{ℓ−2} ,

we have

e(U, W) ≤ C|W |.  (1)

The main technical result that we shall need is as follows. We denote by C⃗^{ℓ} the oriented cycle of length ℓ. Lemma 4. Let an integer ℓ ≥ 3 be fixed, and let constants σ > 0, 0 < α ≤ 1, 0 < γ ≤ 1, C ≥ 1 and D ≥ 1. be given. Then there exist positive constants ε = ε(ℓ, σ, α, γ, C, D) ≤ 1, B_{0} = B_{0}(ℓ, σ, α, γ, C, D) > 0, and m_{0} = m_{0}(ℓ, σ, α, γ, C, D) such that, for all integers m ≥ m_{0} and T ≥ 1, and all real B ≥ B_{0}, the following holds. The number of (ε, γ, B, C, D; V^{(m)}, T)-graphs containing less than σm^{ℓ/(ℓ−1)} cycles C⃗^{ℓ} is at most

α^{T} \binom{(ℓ + 2)m^{2}}{T}.  (2)
□

We shall not prove Lemma 4 here. The interested reader may check Kohayakawa and Kreuter [4], where it is proved that the number of (ε, γ, B, C, D; V^{(m)}, T)- graphs containing no C⃗^{ℓ}’s is at most as given by (2) above. It may be checked that the proof of this result in [4], with some more bookkeeping, does in fact prove Lemma 4 above.

3. Proof of Theorem 1

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 random oriented graph G⃗_{n,p} by putting, for each edge {u, v} ∈ E(G_{n,p}) in G_{n,p},

ℙ ((u, v) ∈ E(G⃗_{n,p})) = 1 − ℙ ((v, u) ∈ E(G⃗_{n,p})) = 1/2,

with all these orientations independent.

Let us now start our proof. Let ℓ ≥ 3 and β > 0 be as given in Theorem 1. Put δ = β/2 and set

γ = \frac{δ}{5}, α = \frac{γℓ}{e^{2}(ℓ + 2)}, C = 4(ℓ − 1), D = 2, σ = \frac{1}{2}, and ϱ = \frac{δ}{4}.

Then, there are constants ε, B_{0}, and m_{0} for which the upper bound of Lemma 4 holds for the constants ℓ, σ, α, γ, C, and D as above. We may suppose ε < δ/16.

In order to apply Lemma 3, take

k_{0} = max{4/δ, s},  (3)

where s is such that for any integer k ≥ s we have that ex(k, C^{ℓ}) < (1/2 + ϱ)\binom{k}{2}, where ex(k, C^{ℓ}) is the Turán number (see, e.g., [1]) for the cycle C^{ℓ} of length ℓ. We observe that when ℓ is even, we could even omit “1/2” in the definition of s, as ex(k, C^{ℓ}) = o(k^{2}).

Let η and K be the constants given by Lemma 3 when applied to ε, k_{0}, and D as above. We may suppose η < δ/20. Put

A = B_{0}K^{1−1/(ℓ−1)} and p = An^{−1+1/(ℓ−1)}.

We prove Theorem 1 using the claims below, whose proofs we postpone.

Define OG = OG(n), for all n ∈ ℕ, as the set of all oriented graphs G⃗^{n} on V = V (G⃗^{n}) = [n] satisfying the following properties:

(i) G⃗^{n} is (η, 1 + η, p)-bounded, (ii) e(G⃗^{n}) = (1 + o(1))\binom{n}{2}p, (iii) for any pair of disjoint non-empty sets U, W ⊆ V satisfying

|U| ≤ |W | ≤ \frac{1}{2}pn|U| ≤ (\frac{1}{2}pn)^{ℓ−2} ,  (4)

the upper bound on the number of arcs (1) holds.

Using Lemma 3 we prove that graphs in OG contain (ε, γ, B, C, D; V^{(m)}, T)- graphs in a very robust way.

Claim 1. For any G⃗^{n} ∈ OG with large enough n, we have that any subgraph J⃗ ⊆ G⃗^{n} of G⃗^{n} with

e(J⃗) ≥ (\frac{1}{2} + δ) \frac{n^{2}p}{2}  (5)

arcs contains a subgraph isomorphic to an

(ε, γ, pm^{1−1/(ℓ−1)}, C, D; V^{(m)}, T)-graph,

for some integer m, with n/2K ≤ m ≤ n/k_{0}, and some integer T ≥ 1.

Let OG′ be the set of graphs G⃗^{n} from OG such that

(iv) any subgraph of G⃗^{n} isomorphic to an (ε, γ, B, C, D; V^{(m)}, T)-graph, where n/2K ≤ m ≤ n/k_{0}, B = pm^{1−1/(ℓ−1)} and T ≥ 1, contains at least σ_{0}n^{ℓ/(ℓ−1)} oriented cycles C⃗^{ℓ}, where σ_{0} = σ(2K)^{−ℓ/(ℓ−1)},

(v) the number of oriented cycles of length at most ℓ − 1 in G⃗^{n} is no larger than Ān^{ℓ/(ℓ−1)}/ log log n, where Ā = (1/16) max{ℓ − 1, (ℓ − 1)A^{ℓ−1}}.

The family OG′ is not empty; in fact, most graphs G⃗_{n,p} are in OG′, as our next result states. Claim 2. With probability tending to 1 as n tends to infinity, we have G⃗_{n,p} ∈ OG′.

We may now complete the proof of Theorem 1 using Claims 1 and 2.

Fix a graph F⃗^{n} ∈ OG′. Let G⃗^{n} be a graph obtained from F⃗^{n} deleting one arc from each of the at most Ān^{ℓ/(ℓ−1)}/ log log n cycles of length at most ℓ − 1 in F⃗^{n}. Then, as it is easily seen, we have G⃗^{n} ∈ OG, and, by Claim 1, any subgraph J⃗ ⊆ G⃗^{n} with e(J⃗) ≥ (1/2 + β)e(G⃗^{n}) ≥ (1/2 + δ)n^{2}p/2 contains an

(ε, γ, B, C, D; V^{(m)}, T)-graph,

where B = pm^{1−1/(ℓ−1)}. As G⃗^{n} ⊆ F⃗^{n} ∈ OG′ we have, by (iv) from definition of OG′, that each J⃗ as above contains (1 − o(1))σ_{0}n^{ℓ/(ℓ−1)} > 0 oriented cycles C⃗^{ℓ}.

We have thus obtained an oriented graph satisfying the conclusions of Theorem 1, as required. □

3.1. Proof of Claim 1. Let J⃗ be an oriented graph as in the statement of Claim 1. Clearly, J⃗ is (η, 1 + η, p)-bounded (hence, (η, D, p)-bounded).

Let P = (V_{i})_{i=0}^{k} be an (ε, k, J⃗, p)-regular partition given by Lemma 3 with the above choices of ε, k_{0} and D. Put m = |V_{i}| ≤ n/k, for any i ∈ [k] = {1, …, k}.

Call R the graph whose vertex set is {V_{1}, …, V_{k}} with {V_{i}, V_{j}} an edge in R if both densities d_{J⃗,p}(V_{i}, V_{j}) and d_{J⃗,p}(V_{j}, V_{i}) are at least γ and (V_{i}, V_{j}) and (V_{j}, V_{i}) are (ε, J⃗, p)-regular. Suppose that e(R) < (1/2 + ϱ)\binom{k}{2}.

The number of arcs in J⃗ is

e(J⃗) ≤\{εn^{2} + k\binom{n/k}{2} + ε\binom{k}{2} (\frac{n}{k})^{2} + γ\binom{k}{2} (\frac{n}{k})^{2} +

+ (\frac{1}{2} + ϱ) \binom{k}{2} (\frac{n}{k})^{2} \}(1 + η)p

< (4ε + \frac{1}{k} + γ + \frac{1}{2} + ϱ) (1 + η)\frac{n^{2}p}{2}
< (4ε + \frac{1}{k} + γ + \frac{1}{2} + ϱ + η) \frac{n^{2}p}{2}
< (\frac{1}{2} + δ) \frac{n^{2}p}{2},

contradicting (5).

Therefore, R contains at least (1/2+ϱ)\binom{k}{2} edges and, because of the choice of k_{0} (see (3)), we may conclude that R contains a cycle V_{i_{1}}, …, V_{i_{ℓ}}.

Thus, we have an (ε, γ, pm^{1−1/(ℓ−1)}, C, D; V^{(m)}, T)-graph given by taking V^{(m)} as the vector (V_{i_{1}}, …, V_{i_{ℓ}}) of pairwise disjoint subsets of V (J⃗), putting the set of arcs as the set ⋃_{j=1}^{ℓ} EJ⃗(V_{i_{j}}, V_{i_{j+1}}) (here the indices are taken modulo ℓ), and letting T be the cardinality of this union. For these choices of V^{(m)} and T, and the above choices for ε, γ, B, C and D one may easily check properties (i)–(iii) from the definition of an (ε, γ, B, C, D; V^{(m)}, T)-graph. This completes the proof of Claim 1.

3.2. Proof of Claim 2. We prove that G⃗_{n,p}, with the above choice for p, satisfies items (i)–(iii) of the definition of OG and (iv) and (v) of the definition of 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 ⊆ V with |U|, |W | ≥ ηn, we have

\begin{aligned}ℙ (e(U, W) > (1 + η)\frac{p}{2}|U||W |) & ≤ exp \{−\frac{1}{3}η^{2} \frac{p}{2}|U||W |\} \\ & ≤ exp \{−\frac{A}{6}η^{4}n^{1+1/(ℓ−1)}\} . \end{aligned}

Then, the expected number of pairs of sets U, W ⊆ V, where V = V (G_{n,p}), with at least ηn vertices and that violate the (η, 1 + η, p)-boundedness condition is at most 4^{n}exp{−A6^{−1}η^{4}n^{1+1/(ℓ−1)}} = o(1). Thus, if X is the number of pairs of sets U, W ⊆ V with at least ηn vertices and that violate the (η, 1 + η, p)- boundedness condition, then we have, by Markov’s inequality, that ℙ (X > 0) < 4^{n}exp{−A6^{−1}η^{4}n^{1+1/(ℓ−1)}} = o(1).

We have (ii) with high probability from Chernoff’s inequality. In fact, we easily verify that for any ρ > 0 the probability that |e(G⃗_{n,p}) − p\binom{n}{2}| > ρ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 ⊆ V be disjoint sets satisfying (4). To verify that (iii) holds with high probability, notice that the probability that (1) fails is

ℙ (e(U, W) > C|W |) ≤ \binom{|U||W |}{C|W |} (\frac{p}{2})^{C|W |} ≤ (\frac{e}{C} · \frac{p|U|}{2})^{C|W |} .

Observe that (1/2)p|U| ≤ ((1/2)pn)^{ℓ−2}/n ≤ (A/2)^{ℓ−2}n^{−1/(ℓ−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 (4) holds and e(U, W) > C|W |, is at most

\begin{matrix}∑_{1≤w<n/2} ∑_{u=1}^{w} & \binom{n}{u}\binom{n}{w} (\frac{e}{C} · \frac{pu}{2})^{Cw} ≤ ∑_{1≤w<n/2} w\binom{n}{w}^{2} (\frac{e}{C} (\frac{A}{2})^{ℓ−2} n^{−1/(ℓ−1)})^{Cw} \\ ≤ & ∑_{1≤w<n/2} w (\frac{en}{w})^{2w} (\frac{e}{C} (\frac{A}{2})^{ℓ−2} n^{−1/(ℓ−1)})^{Cw} \\ = & ∑_{1≤w<n/2} \frac{w}{w^{2w}} (\frac{e^{1+2/C}}{C} (\frac{A}{2})^{ℓ−2} n^{(2/C)−(1/(ℓ−1))})^{Cw} \\ = & ∑_{1≤w<n/2} \frac{w}{w^{2w}} (\frac{e^{1+2/C}}{C} (\frac{A}{2})^{ℓ−2} n^{−2/C})^{Cw} = o(1), \end{matrix}

for C = 4(ℓ − 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/(ℓ−1)} ≥ B_{0}(Km/n)^{1−1/(ℓ−1)} ≥ B_{0}.

Observe that the number of arcs T is at least γ(p/2)m^{2}ℓ, and the expected number of (ε, γ, B, C, D; V^{(m)}, T)-subgraphs of G⃗_{n,p} containing at most σ_{0}n^{ℓ/(ℓ−1)} ≤ σm^{ℓ/(ℓ−1)} cycles C⃗^{ℓ} of length ℓ is o(1). In fact, for any given positive integers m and T ≥ γ(p/2)m^{2}ℓ, this expected number is, by Lemma 4, at most

(n)_{ℓm}α^{T} \binom{(ℓ + 2)m^{2}}{T} (\frac{p}{2})^{T} ≤ n^{ℓm} (α · \frac{e(ℓ + 2)m^{2}}{T} · \frac{p}{2})^{T}

≤ n^{ℓm} (\frac{eα(ℓ + 2)}{ℓγ})^{T}

= n^{ℓm} (\frac{1}{e})^{T}

≤ exp {(log n)mℓ − γ(p/2)m^{2}ℓ}

= o(n^{−3}).

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

∑_{i=3}^{ℓ−1} \frac{(n)_{i}}{2i} (\frac{p}{2})^{i} ≤ \frac{1}{16} ∑_{i=3}^{ℓ−1} n^{i}p^{i} ≤ Ān.

Invoking Markov’s inequality again, we see that the probability that the number of short oriented cycles should be greater than Ān^{ℓ/(ℓ−1)}/log log n is smaller than log log n/n^{1/(ℓ−1)} = o(1).

3.3. Proof of Corollary 2. Let ℓ ≥ 3 be an integer. Set β = 1/2 − 1/ℓ and let G⃗^{n} be an oriented graph with oriented girth ℓ given by Theorem 1.

Suppose we have a family T of pairwise disjoint transversals of cardinality |T | = ℓ. Let H⃗ be the graph obtained from G⃗^{n} by deleting a transversal T ∈ T of this family that satisfies |T | ≤ e(G⃗^{n})/ℓ. We have e(H⃗) ≥ (1 − 1/ℓ)e(G⃗^{n}) = (1/2 + β)e(G⃗^{n}) and, by Theorem 1, the oriented graph H⃗ must contain an oriented cycle, contradicting the fact that T should be a transversal.

4. Concluding remark

Both Theorem 1 and Corollary 2 assert the existence of sparse oriented graphs, with some given oriented girth ℓ, that contain oriented ℓ-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.

References

1. Béla Bollobás, Extremal graph theory, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1978.

2. P. Feofiloff and D. H. Younger, Directed cut transversal packing for source-sink connected graphs, Combinatorica 7 (1987), no. 3, 255–263.

3. Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216–230.

4. Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures & Algorithms 11 (1997), no. 3, 245–276.

5. Orlando Lee, Circuit covers in mixed graphs, Doctoral thesis, Instituto de Matemática e Estatística, Universidade de São Paulo, 1999, in Portuguese.

6. A. Schrijver, Min-max relations for directed graphs, Bonn Workshop on Combinatorial Optimization (Bonn, 1980), North-Holland, Amsterdam, 1982, pp. 261–280.

7. D. R. Woodall, Menger and König systems, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Springer, Berlin, 1978, pp. 620–635.

8. D.H. Younger, Private communication to Y. Wakabayashi.

Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo, Brazil

   E-mail address: jair@ime.usp.br, yoshi@ime.usp.br