RAMSEY-TYPE RESULTS FOR ORIENTED TREES

YOSHIHARU KOHAYAKAWA†, TOMASZ ŁUCZAK‡ and VOJTĚCH RÖDL*

Abstract. For a graph G and a digraph H⃗, we write G→H⃗ (respectively, G→^{a}H⃗) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of H⃗. In this note we study how small the graphs G such that G→H⃗ or such that G→^{a}H⃗ may be, if H⃗ is a given oriented tree T⃗^{n} on n vertices. We show that there is a graph on O(n^{4} log n) vertices and O(n^{6}(log n)^{2}) edges such that G→T⃗^{n} for every n-vertex oriented tree T⃗^{n}. We also prove that there exists a graph G with O(n^{2} log n) vertices and O(n^{3}(log n)^{2}) edges such that G→^{a}T⃗^{n} for any such tree T⃗^{n}. This last result turns out to be nearly best possible as it is shown that any graph G with G→^{a}P⃗^{n}, where P⃗^{n} is the directed path of order n, has more than n^{2}/2 vertices and more than ⌊n/3⌋^{3} edges if n ≥ 3.

1991 Mathematics subject classifications: Primary 05C55, 05C20, 05C05; Secondary 05C80

Key words: Ramsey theory, trees, directed graphs, orientations of graphs, random graphs

1. Introduction. In this note we are concerned with some Ramsey-theoretical properties of orientations of graphs. We shall use the term directed graph or digraph to mean a graph in which the edges have been given a fixed orientation; in particular, between two distinct vertices x and y of a digraph H⃗ we may have at most one of the directed edges \overrightarrow{xy} and \overrightarrow{yx}. An orientation G⃗ of a graph G is a digraph whose underlying graph is G.

In analogy to the arrow notation of Rado, for a given graph G and an acyclic digraph H⃗, we write G→H⃗ if every orientation of the edges of G leads to an induced copy of H⃗. Similarly, G→^{a}H⃗ will mean that every acyclic orientation of G contains an induced copy of H⃗. For any given acyclic digraph H⃗, the existence of a graph G satisfying G→^{a}H⃗ follows from a result of Rödl [5], and the fact that there is a graph G such that G→H⃗ was shown by Cochand and Duchet [2]. For convenience, for any class D of digraphs, let us write G→D (respectively, G→^{a}D) if any orientation of G (respectively, any acyclic orientation of G) contains an induced copy of every H⃗ ∈ D.

In this note we study how small the graphs G such that G→T⃗^{n} or such that G→^{a}T⃗^{n} may be, where T⃗^{n} is the class of all oriented trees on n vertices. The existence results mentioned above give rather poor upper bounds for the order |G| = |V (G)| and size e(G) = |E(G)|

† Instituto de Matemática e Estatística, Universidade de São Paulo, Caixa Postal 20570, 01452– 990 São Paulo, SP, Brazil. Research partially supported by FAPESP (Proc. 93/0603–1) and by CNPq (Proc. 300334/93–1 and ProTeM–CC–II Project ProComb).

‡ Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322. On leave from the Mathematical Institute of the Polish Academy of Sciences, and Adam Mickiewicz University, Poznań, Poland. Research partially supported by KBN grant 2 1087 91 01.

* Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322. Research partially supported by NSF grant DMS–9401559.

of such graphs G. For instance, Cochand and Duchet’s method in [2] gives that, for some absolute constant c and every integer n ≥ 1, there is a graph G = G_{n} of order at most 2^{2^{cn}} such that G→T⃗^{n}. Moreover, it is conjectured in [2] that in this result the double exponential upper bound for the order of G_{n} may be replaced by an exponential upper bound. As observed by Brightwell and Kohayakawa [1], the existence of a graph G_{n} with G_{n}→T⃗^{n} and |G_{n}| ≤ n^{(2+o(1))n} follows by considering graphs with high girth and high chromatic number. Our first result states that much more is in fact true.

Theorem 1. There exists an absolute constant C such that for every integer n ≥ 1 there is a graph G with at most Cn^{4} log n vertices and at most Cn^{6}(log n)^{2} edges such that G→T⃗^{n}.

We now turn to the relation →^{a}, and start by observing that the property G→^{a}H⃗ is, in some sense, a little easier to handle and hence we may expect stronger results. One such result is due to Rödl and Winkler [6], which implies that, for every graph H = H^{n} of order n, there is a graph G of order O(n^{3}(log n)^{2}) such that G→^{a}H⃗ for any acyclic orientation H⃗ of H. A related result was obtained by Brightwell and Kohayakawa [1], who proved the existence of a graph G with at most ⌊(4/9)n2^{n/2}⌋ vertices such that G→^{a}D^{n}, where D^{n} is the class of all acyclic digraphs of order n. Let us also mention that the two results above are, in a precise sense, essentially best possible (see [1, 6] for details.) However, for the particular case of oriented trees, they can be considerably improved.

Theorem 2. There exists an absolute constant D such that for every integer n ≥ 1 there is a graph G with at most Dn^{2} log n vertices and at most Dn^{3}(log n)^{2} edges such

that G→^{a}T⃗^{n}.

One may ask how good the bounds given in Theorems 1 and 2 are. Unfortunately, we do not know whether the powers of n in the bounds O(n^{4} log n) and O(n^{6}(log n)^{2}) in Theorem 1 may be reduced to smaller powers. Nevertheless, the following result implies that the bounds given in Theorem 2 cannot be improved except possibly for a logarithmic factor. Let P⃗^{n} be the directed path of order n.

Theorem 3. Suppose a graph G is such that G→^{a}P⃗^{n} for some integer n ≥ 3. Then G has more than n^{2}/2 vertices and more than ⌊n/3⌋^{3} edges.

2. Proof of Theorem 1. Suppose G is a graph on N ≥ 3 vertices with the following two properties:

(a) every subset S ⊆ V (G) of vertices of G with s = |S| ≥ s_{0} = ⌊10e^{2}(N log N)^{1/2}⌋ induces at least (1/4e^{2})s^{2}(log N)^{1/2}N^{−1/2} edges;

(b) for every S ⊆ V (G) and every v ∈ V (G) \ S, the number of vertices x ∈ V (G) \ (S ∪ {v}) that are adjacent to v and to some vertex in S is at most |S| log N.

We shall prove that then G→T⃗^{n} for n = ⌊(1/5e^{2})(N/ log N)^{1/4}⌋. More specifically, we shall show that if r is a positive integer, then

(†) for every U ⊆ V (G) with |U| ≥ 5e^{2}r^{2}(N log N)^{1/2} the subgraph G[U] of G

induced by U in G is such that G[U]→T⃗^{r}.

We shall prove (†) by induction on r. The statement is trivial for r = 1. Let us then assume that r ≥ 1 and that (†) holds for this value of r. Let us prove (†) for r + 1. Thus, assume that U ⊆ V (G) with |U| ≥ 5e^{2}(r + 1)^{2}(N log N)^{1/2} is given, set H = G[U], and fix an arbitrary orientation H⃗ of H and an arbitrary oriented (r + 1)-vertex tree T⃗^{r+1}. We aim at showing that H⃗ contains an induced copy of T⃗^{r+1}. We shall assume that there is a pendant vertex u ∈ V (T⃗^{r+1}) that is an out-neighbour of some v ∈ V (T⃗^{r+1}). An obvious alteration to the argument below deals with the case in which every pendant vertex of T⃗^{r+1} is a source. Let W ⊆ U = V (H) be the set of vertices x ∈ V (H⃗) with H⃗-out-degree d+ ; H⃗(x) ≤ 2(r − 1) log N.

We now check that w = |W | < s_{0}r. If w ≥ s_{0}r ≥ s_{0}, then condition (a) implies that |E(G[W])| ≥ (1/4e^{2})w^{2}(log N)^{1/2}N^{−1/2} and, since |E(G[W])| ≤ 2w(r − 1) log N, we conclude that w ≤ 8e^{2}r(N log N)^{1/2} < s_{0}r, which is a contradiction. Thus indeed |W | < s_{0}r.

We now consider U′ = U \ W. As |W | < s_{0}r ≤ 10e^{2}r(N log N)^{1/2}, we have |U′| ≥ 5e^{2}r^{2}(N log N)^{1/2}. Therefore, by the induction hypothesis, H⃗[U′] contains an induced copy of T⃗^{r} = T⃗^{r+1} − u; say H⃗[S′] is isomorphic to T⃗^{r}, where S′ ⊆ U′. Let v′ ∈ S′ be the vertex in S′ that corresponds to v ∈ V (T⃗^{r}) through this isomorphism. Set S = S′ \ {v′}. Since v′ ∉ W, we have d+ ; H⃗(v′) > 2(r − 1) log N ≥ (r − 1)(1 + log N), and hence from (b) the vertex v′ has an H⃗-out-neighbour u′ ∈ V (H⃗) = U that does not belong to the neighbourhood of S. Thus H⃗[S ∪ {u′}] is an induced copy of T⃗^{r+1} in H⃗ and the induction step is complete. Thus assertion (†) holds.

To finish the proof of Theorem 1, it is enough to show that, for any large enough N, there is a graph G for which both (a) and (b) above hold. We consider the usual binomial random graph G(N, p), whose vertex set is [N] = {1, …, N} and each pair ij (1 ≤ i < j ≤ N) is present as an edge in G(N, p) independently with probability p = p(N). We shall take p = p(N) = e^{−2}((log N)/N)^{1/2}. We shall show that then (a) and (b) hold for G = G(N, p) almost surely, that is with probability tending to 1 as N → ∞.

Let us consider (a) first. Fix S ⊆ V (G) with s = |S| ≥ s_{0}. The number of edges e(G[S]) induced by S in G = G(N, p) is binomially distributed with parameters \binom{s}{2} and p. As is well known (see e.g. §5 in McDiarmid [4]), a binomial random variable X with parameters m and p is such that, for every 0 < ε < 1,

ℙ(X < (1 − ε)mp) ≤ exp \{−\frac{1}{2}ε^{2}mp\} .

Thus the probability that S induces fewer than (1/4e^{2})s^{2}((log N)/N)^{1/2} = s^{2}p/4 edges in G is at most exp{−(1/16+o(1))s^{2}p}. Thus the probability that (a) fails for G = G(N, p) is at most

∑_{s≥s_{0}} \binom{N}{s} exp \{− (\frac{1}{16} + o(1)) s^{2}p\} ≤ ∑_{s≥s_{0}} (\frac{eN}{s} exp \{− (\frac{1}{16} + o(1)) sp\})^{s}

≤ N (\frac{eN}{s_{0}} exp \{− (\frac{1}{16} + o(1)) s_{0}p\})^{s_{0}} .

Since s_{0}p ≥ 9 log N for large enough N, property (a) fails for G = G(N, p) with probability at most

N \{O ((\frac{N}{log N} )^{1/2} e^{−(9/16+o(1)) log N})\}^{N^{1/2}}= N \{O (N^{−1/16+o(1)})\}^{N^{1/2}}= o(1),

as required.

Let us now turn to (b). For convenience, write Γ(x) for the neighbourhood of x ∈ V (G) in G = G(N, p), and as customary put Γ(X) = ⋃_{x∈X} Γ(x) for any X ⊆ V (G). Moreover, let Γ̃(X) = Γ(X) \ X for any X ⊆ V (G). We now fix S ⊆ V (G), v ∈ V (G) \ S, and x ∈ V (G) \ (S ∪ {v}). Then clearly ℙ(x ∈ Γ̃(S) ∩ Γ(v)) ≤ p^{2}s. Thus ℙ{|Γ̃(S) ∩ Γ(v)| ≥ t} ≤ \binom{N}{t}(p^{2}s)^{t} for any t ≥ 0. For t = ⌈s log N⌉, where s = |S|, we have

ℙ\{|Γ̃(S) ∩ Γ(v)| ≥ s log N\} ≤ (\frac{eNp^{2}s}{t})^{t} ≤ (\frac{eNp^{2}}{log N} )^{s log N} ≤ N^{−3s}.

Thus the probability that (b) fails is at most

∑_{s≥1} \binom{N}{s}N^{1−3s} ≤ N ∑_{s≥1} (\frac{e}{sN^{2}} )^{s} = o(1).

3. Proof of Theorem 2. As in the previous section, let G(N, p) be the random graph with vertex set [N] = {1, 2, …, N} in which each pair of vertices is connected by an edge with probability p = p(N), independently for each pair. We claim that almost surely every acyclic orientation of G(N, p) contains every oriented tree on n = ⌊(N/150 log N)^{1/2}⌋ vertices as an induced subgraph if p = p(N) = 1/n. Clearly, this claim implies Theorem 2.

In the sequel, we denote by G⃗_{incr} = G⃗_{incr}(N, p) the acyclic orientation of G = G(N, p) where each edge ij ∈ E(G) (1 ≤ i < j ≤ N) is directed from the smaller vertex i to the larger vertex j. In order to prove our claim, we shall give an algorithm, Algorithm Find, that, for every given oriented n-vertex tree T⃗^{n}, finds an induced copy of T⃗^{n} in G⃗_{incr} = G⃗_{incr}(N, p) with probability at least 1 − N^{−2N}. Let us quickly check that the existence of such an algorithm proves our claim. Observe first that the number of acyclic orientations of a graph of order N is at most N!, and that the number of oriented n-vertex trees is at most 2^{n−1}n^{n−2} ≤ 2^{n}n^{n}. Thus it follows from the existence of Algorithm Find that the probability that G(N, p)→^{a}T⃗^{n} fails is smaller than N!2^{n}n^{n}N^{−2N} = o(1), as required.

Let us now sketch the idea behind Algorithm Find. Let an n-vertex oriented tree T⃗^{n} be given. Our algorithm searches for an induced copy of T⃗^{n} in G⃗_{incr}(N, p) calling a procedure, Procedure One-Round, several times until it either finds such a copy, or else it decides it has failed and it halts. (It is the probability that this latter case occurs that we have to show is no greater than N^{−2N}.) Procedure One-Round receives as input a set R = {r_{1}, …, r_{m}} ⊆ [N] (1 ≤ m ≤ N) of available vertices of G⃗_{incr} = G⃗_{incr}(N, p). The first time Procedure One-Round is executed we have m = N, that is all vertices of G⃗_{incr} are available, while in the subsequent calls of Procedure One-Round the set of available vertices is increasingly smaller. Algorithm Find tries to embed T⃗^{n} into G⃗_{incr}(N, p) in a natural way: each of its calls of One-Round constitutes a ‘greedy’ type attempt of embedding T⃗^{n} into G⃗_{incr}[R], the subgraph of G⃗_{incr} = G⃗_{incr}(N, p) induced by the current set R of available vertices. Then, either One-Round succeeds and returns an induced copy of T⃗^{n} in G⃗_{incr}[R], or else it fails, constructing only a “non-extendable” copy of a subtree T⃗^{n′} of T⃗^{n} (n′ < n). In the latter case, Procedure One-Round removes the vertices of this copy from R, returns an updated set of available vertices R′ ⊆ R, and reports failure. The key observation for the probabilistic analysis of Algorithm Find is the fact that, every time One-Round is executed and it searches for T⃗^{n} in G⃗_{incr}[R], R = {r_{1}, …, r_{m}}, all pairs r_{i}r_{j} (1 ≤ i < j ≤ m) are not yet “exposed”, i.e. not yet known or not known to belong to E(G(N, p)), so that we may treat the graph induced by R in G⃗_{incr}(N, p) as a random graph on R.

Now let us make the description of Algorithm Find a little more precise. Fix an arbitrary n-vertex oriented tree T⃗^{n}. Let v_{1}, …, v_{n} be any ordering of the vertices of T⃗^{n} such that every v_{i} (2 ≤ i ≤ n) has precisely one neighbour, say w_{i}, in the set {v_{1}, …, v_{i−1}}. We say that v_{i} is a right vertex if it is an out-neighbour of w_{i}, and otherwise we say that v_{i} is a left vertex. As mentioned above, Algorithm Find looks for an induced copy of T⃗^{n} in G⃗_{incr}(N, p) calling Procedure One-Round several times until it either finds such a copy, or else it gives up and halts. Procedure One-Round receives as input a set R = {r_{1}, …, r_{m}} ⊆ [N], r_{1} < ⋯ < r_{m} (m ≥ 1), of available vertices of G⃗_{incr} = G⃗_{incr}(N, p) with all pairs r_{i}r_{j} (1 ≤ i < j ≤ m) not yet known or not known to belong to E(G(N, p)). One-Round either returns an induced copy of T⃗^{n} in G⃗_{incr}[R], or else it returns an updated set of available vertices R′ ⊆ R and reports failure.

Procedure One-Round searches for a copy of T⃗^{n} in G⃗_{incr}[R] by trying to map suitably the vertices v_{1}, v_{2}, … of T⃗^{n} into R in this order, one by one. Our goal is to find r_{i_{1}}, …, r_{i_{n}} such that v_{j} ↦ r_{i_{j}} (1 ≤ j ≤ n) is an isomorphism of T⃗^{n} onto G⃗_{incr}[r_{i_{1}}, …, r_{i_{n}}]. More specifically, for each right (respectively left) vertex v_{j} (2 ≤ j ≤ n), we would like to have r_{i_{j}} > r_{i_{ℓ}} (respectively r_{i_{j}} < r_{i_{ℓ}}) for each 1 ≤ ℓ < j, and, furthermore, the only neighbour of r_{i_{j}} among the vertices r_{i_{1}}, …, r_{i_{j−1}} should be the one corresponding to w_{j} ∈ V (T⃗^{n}) in G⃗_{incr}[r_{i_{1}}, …, r_{i_{j−1}}].

Procedure One-Round starts by setting r_{i_{1}} = r_{⌊m/2⌋}, and by labelling r_{⌊m/2⌋} selected. Let us assume that v_{2} is a right (respectively left) vertex. One-Round then checks whether the vertex r_{⌊m/2⌋+1} (respectively r_{⌊m/2⌋−1}) is adjacent to r_{i_{1}} in G⃗_{incr}. If not, it labels it checked, and examines r_{⌊m/2⌋+2} (respectively r_{⌊m/2⌋} − 2). The procedure carries on in this manner until a neighbour of r_{i_{1}} is found. One-Round lets this neighbour be r_{i_{2}}, and labels it selected. In general, let us suppose that the vertices r_{i_{1}}, …, r_{i_{j−1}} (2 ≤ j ≤ n) have already been chosen, and that v_{j} is a right (respectively left) vertex. Then the procedure examines one by one the vertices that lie on the right (respectively left) of the vertex max{r_{i_{1}}, …, r_{i_{j−1}}} (respectively min{r_{i_{1}}, …, r_{i_{j−1}}}) until it finds a vertex that is adjacent to precisely the vertex that corresponds to w_{j}. One-Round then lets this vertex be r_{i_{j}}, labels it selected, and labels as checked all the other vertices that were examined but could not be chosen as r_{i_{j}}. In case One-Round fails to define r_{i_{j}}, it returns R′ = R \ S, where S ⊆ R is the set of vertices that have been labelled selected, and reports failure.

Clearly, if One-Round fails, then, while executing this procedure, we must have run out of vertices either on the left or on the right of r_{⌊m/2⌋}. In either case, at least half of all available m vertices must have been labelled selected or checked. Since the probability that a vertex we examine is labelled checked is at most 1 − p(1 − p)^{n−1}, the probability that our procedure fails is, if n = o(m), smaller than

\begin{aligned}2 ∑_{k=1}^{n−1} \binom{m}{k}(1 − p(1 − p)^{n})^{⌊m/2⌋−k} & ≤ 2n\binom{m}{n} exp \{− (\frac{1}{2} + o(1)) mp(1 − p)^{n}\} \\ & ≤ 2n (\frac{em}{n} exp \{− (\frac{1}{2} + o(1)) \frac{m}{n}p(1 − p)^{n}\})^{n} . \end{aligned}

Algorithm Find proceeds as follows. It first puts R = {r_{1}, …, r_{N}} = [N] and calls Procedure One-Round with this input. If T⃗^{n} is found, it returns this copy and halts. If One-Round reports failure, it calls One-Round with the set R′ returned by the previous call of One-Round as the input set R for this call. Find proceeds in this manner until it either finds an induced copy of T⃗^{n} in G⃗_{incr}, or else the set of available vertices R′ returned by some call of One-Round is such that |R′| ≤ N/2.

The key observation concerning One-Round is the following: if a call of One-Round fails, then the set R′ ⊆ R that it returns has at least |R| − n + 1 elements, and moreover no pair ij (i, j ∈ R′) has been checked for adjacency in G(N, p). Thus the several calls of One-Round examine independent random graphs.

Let us now note that, since Find only calls One-Round with sets R with m = |R| > N/2, each such call fails with probability at most

2n (\frac{eN}{n} exp \{− (\frac{1}{4} + o(1)) \frac{N}{n} pe^{−2pn}\})^{n} ≤ 2n (\frac{eN}{n} exp \{−\frac{149}{4e^{2}} log N\})^{n}

≤ 2n (\frac{eN}{n} e^{−5 log N})^{n} ≤ N^{−(4.5+o(1))n}.

Moreover, if Find fails, One-Round is called at least N/2n times. From the independence property among the calls of One-Round observed above, we deduce that Find fails to find an induced copy of T⃗^{n} in G⃗_{incr} = G⃗_{incr}(N, p) with probability at most {N^{−(4.5+o(1))n}}^{N/2n} ≤ N^{−2N}, as required.

4. Proof of Theorem 3. Let first an integer n ≥ 3 be fixed. We shall show that every graph G on at most n^{2}/2 vertices can be acyclically oriented in such a way that the resulting graph contains no induced copy of P⃗^{n}. We use induction on n. For n = 3 the assertion can be verified in a straightforward manner. Let G be a graph on at most n^{2}/2 vertices, n ≥ 4, and assume that the assertion holds for smaller values of n. If G contains no induced path of order n, there is nothing to prove. Thus, let us assume that a subset S ⊆ V (G) of vertices of G induces in G a path of order n. Note that the subgraph H = G − S has fewer than (n − 1)^{2}/2 vertices, and so by the induction hypothesis there exists an acyclic orientation H⃗ of H in which no directed path of order n − 1 is induced. We are now ready to define a suitable orientation G⃗ of G. First, direct all edges of the n-vertex path induced by S in such a way that no directed path of length two is created. Secondly, direct all edges between sinks of G[S] and V (H) towards S, and direct all edges between sources of G[S] and V (H) towards V (H). Finally direct the edges in H as in H⃗. Then, clearly, this orientation of G⃗ of G contains no induced directed path of order n, as required.

Let us now note that the second bound in Theorem 3 is trivial for n ≤ 5, and hence let us assume that n ≥ 6. Let G be a graph satisfying G→^{a}P⃗^{n}. For 0 ≤ r ≤ n − 3, let H_{r} be the subgraph of G induced by all the vertices of degree at least r in G. Note that H_{r} must contain more than (n − r)^{2}/2 vertices. Indeed, otherwise the edges of H_{r} could be oriented in such a way that no induced directed path of order n − r appears, and, furthermore, since the subgraph H̄_{r} = G − H_{r} has chromatic number at most r, its edges can be acyclically oriented in such a way that no path of order larger than r is created. Consequently, directing the edges between H_{r} and H̄_{r} from H_{r} to H̄_{r} we would obtain an orientation of G without an induced P⃗^{n}. Thus, the number of edges of G must be larger than

max_{1≤r≤n−3} \{\frac{r}{2} · \frac{(n − r)^{2}}{2} \} ≥ ⌊n/3⌋^{3} .

5. Final remarks. We note that there are oriented trees T⃗^{n} for which the order and size of the smallest graph G with G→T⃗^{n} can be easily determined up to a constant factor. For example, if S⃗_{n} is the directed star, i.e. the directed tree on n + 1 vertices in which one vertex has outdegree n, and K_{2n,2n} is the complete bipartite graph with 2n vertices in each class, then K_{2n,2n}→S⃗_{n}. On the other hand, obviously, if G→^{a}S⃗_{n} then G must have at least n + 1 vertices and at least n^{2}/2 edges. Similar results may also be obtained for few other rather special classes of directed trees.

Finally, let us mention an example of an oriented tree Z⃗_{n} for which there exist very sparse graphs G with G→Z⃗_{n}. Let Z⃗_{n} be the oriented tree whose underlying graph is the path of length n and the orientation is such that Z⃗_{n} contains no directed paths of length two. Then the following result holds.

Theorem 4. There exists an absolute constant A such that for every integer n ≥ 1 there is a graph G with at most An edges such that G→Z⃗_{n}.

Sketch of the proof. Haxell, Kohayakawa and Łuczak [3] showed that there exists an absolute constant A′ such that, for every integer n ≥ 3, there is a graph G_{n} with at most A′n edges such that each two-colouring of the edges of G_{n} leads to a monochromatic induced cycle of length n. From their proof it follows that in the case when n is even G_{n} can be chosen to be bipartite. Thus, let G_{2n} be a bipartite graph with bipartition (W_{1}, W_{2}) and at most 2A′n edges such that every two-colouring of the edges of G_{2n} results in an induced monochromatic cycle of length 2n. Take any orientation G⃗_{2n} of G_{2n}, and colour the edges oriented from W_{1} to W_{2} blue and the edges oriented from W_{2} to W_{1} red. Now the fact that there is a monochromatic induced 2n-cycle in G_{2n} implies that there exists an induced cycle of length 2n in G⃗_{2n} containing no oriented paths of length two, and so G_{2n}→Z⃗_{2n−2}, and hence obviously G_{2n}→Z⃗_{n} if n ≥ 2.

REFERENCES

[1] Brightwell, G.R. and Kohayakawa, Y., Ramsey properties of orientation of graphs, Random Structures & Algorithms, 4 (1993), pp. 413–428.

[2] Cochand, M. and Duchet, P., A few remarks on orientations of graphs and Ramsey theory, in “Irregularities of Partitions,” Algorithms and Combinatorics 8 (Halász, G. and Sós, V.T., eds), Springer-Verlag, Berlin, 1989, pp. 39–46.

[3] Haxell, P.E., Kohayakawa, Y. and Łuczak, T., The induced size-Ramsey number of cycles, Combinatorics, Probability & Computing (to appear).

[4] McDiarmid, C.J.H., On the method of bounded differences, in “Surveys in Combinatorics 1989,” London Mathematical Society Lecture Notes Series 141 (Siemons, J., ed.), Cambridge University Press, Cambridge, 1989, pp. 148–188.

[5] Rödl, V., A generalization of Ramsey theorem, in “Graphs, Hypergraphs and Block Systems,” Zielona Góra, 1976, pp. 211–220.

[6] Rödl, V. and Winkler, P., A Ramsey-type theorem for orderings of a graph, SIAM J. Discrete Math., 2 (1989), pp. 402–406.