INDUCED RAMSEY NUMBERS

Y. KOHAYAKAWA, H. J. PRÖMEL, AND V. RÖDL

Dedicated to the memory of Professor Paul Erdős

Abstract. We investigate the induced Ramsey number r_{ind}(G, H) of pairs of graphs (G, H). This number is defined to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with k = |V (G)| ≤ t = |V (H)|, we have

r_{ind}(G, H) ≤ t^{Ck log q},

where q = χ(H) is the chromatic number of H and C is some universal constant. Furthermore, we also investigate r_{ind}(G, H) imposing some conditions on G. For instance, we prove a bound that is polynomial in both k and t in the case in which G is a tree. Our methods of proof employ certain random graphs based on projective planes.

1. Introduction and Main Results

A fundamental problem in Ramsey theory is to determine or estimate the Ramsey number for complete graphs. Write R(k) for the smallest integer n with the property that, if one colours the edges of the complete graph on n vertices with colours red and blue, one necessarily obtains a complete subgraph on k vertices all of whose edges are coloured red, or else all of whose edges are coloured blue. The number R(k), the existence of which follows from a classical theorem of Ramsey [14], is the Ramsey number of the complete graph on k vertices.

The best bounds that are currently known for R(k) imply that

2^{1/2} ≤ lim inf_{k→∞} R(k)^{1/k} ≤ lim sup_{k→∞} R(k)^{1/k} ≤ 4.

1991 Mathematics Subject Classification. Primary 05C55, 05C80; Secondary: 05C35. Key words and phrases. Generalised Ramsey theory, induced subgraphs, random

graphs.

Research partially supported by PROBRAL project 026/95, a CAPES–DAAD exchange programme and Humboldt Stiftung. The first author was partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 300334/93–1 and ProTeM-CC-II Project ProComb), and by MCT/FINEP under PRONEX project 107/97. The second author was partially supported DFG project Pr 296/4–1. The third author was partially supported by NSF grant DMS–9401559.

Part of this work was done while the first and the third authors were visiting Humboldt-Universität zu Berlin.

Thus, even the precise rate of the exponential growth of R(k) is unknown. Indeed, deciding whether lim_{k→∞} R(k)^{1/k} exists, and if so determining its value, are outstanding problems in the area. For a pleasant introduction to Ramsey theory in general, the reader is referred to Graham, Rothschild, and Spencer [11]. Nešetřil [13] gives a relatively concise survey on this vast subject. Numerical problems in this area are discussed by Graham and Rödl [10].

In this paper, we are concerned with a counterpart to the theorem of Ramsey for non-complete graphs. Namely, we are interested in a result proved independently by Deuber [4], Erdős, Hajnal, and Pósa [9], and Rödl [15], which states that, for any pair of graphs G and H, there is a graph Γ such that

Γ → (G, H),  (1)

where the arrow notation in (1) above means that whenever we colour the edges of Γ red and blue, either a red induced copy of G arises, or else a blue induced copy of H arises. This variant of Ramsey’s theorem immediately raises a numerical problem.

For any given graphs G and H, let r_{ind}(G, H) denote the smallest integer n for which there exists a graph Γ on n vertices satisfying (1). We refer to r_{ind}(G, H) as the induced Ramsey number of the pair (G, H). Erdős wrote [7, §5] (with a little change in the notation): “Hajnal and I observed that if G_{1} and G_{2} have at most n vertices, then

r_{ind}(G_{1}, G_{2}) ≤ 2^{2^{n^{1+ε}}} .  (2)

We have never published the not entirely trivial proof of (2) since Hajnal and I thought that perhaps

max r_{ind}(G_{1}, G_{2}) = R(n).  (3)

“Conjecture (3) is perhaps a little too optimistic, but we have no counterexample. Perhaps there is a better chance to prove r_{ind}(G_{1}, G_{2}) ≤ 2^{cn}.”

Writing r_{ind}(H) for r_{ind}(H, H), this latter problem of Erdős [7], already implicit in [6, §III], is then the following:

Problem 1. Is there an absolute constant C such that for any graph H on t vertices we have r_{ind}(H) ≤ 2^{Ct}?

Techniques in Rödl [15] imply that r_{ind}(H, H) is indeed exponential in t = |V (H)| if H is bipartite. Note that if the answer to Problem 1 is positive, then the result is best possible up to the value of C, that is, there are graphs H for which r_{ind}(H) is exponential in t = |V (H)|. Indeed, it suffices to take H as the complete graph on t vertices.

Our main result below, Theorem 3, comes close to establishing a positive answer to Problem 1 in general. In particular, our result greatly strengthens the previous doubly exponential bound (2) of Erdős and Hajnal.

Quite curiously, our result also comes close to settling the following conjecture, which deals with the ‘asymmetric’ induced Ramsey number r_{ind}(G, H).

Here, we are concerned with the case in which G is some fixed graph and H is very large.

Conjecture 2. For any graph G, there is a constant f = f(G) that depends only on G such that, for any graph H on t vertices, we have

r_{ind}(G, H) ≤ t^{f}.

Our main result is as follows.

Theorem 3. Let G and H be graphs with |V (G)| = k and |V (H)| = t, where k ≤ t, and suppose q = χ(H) ≥ 2. Then

r_{ind}(G, H) ≤ t^{Ck log q}  (4)

for some absolute constant C.

Note that in the ‘diagonal case’, in which G = H, Theorem 3 gives the bound

r_{ind}(H) = r_{ind}(H, H) ≤ t^{Ct log q},

which only fails to be a purely exponential bound in t = |V (H)| by a factor of (log t)(log χ(H)) ≤ (log t)^{2} in the exponent. Furthermore, note that (4) in Theorem 3 fails to be polynomial in t only by a factor of log χ(H) in the exponent. Thus, Theorem 3 does indeed fall only a little short of settling Problem 1 and Conjecture 2.

Inequality (4) is proved by showing that there is a suitably small graph R for which R → (G, H) holds. This graph R = R(P, H) is randomly constructed using a projective plane P and the graph H. (The graph G plays no rôle in the definition of R.) Roughly speaking, the graph R is obtained from P and H by randomly embedding ‘blown-up copies’ of H in each line of P. (A ‘blow-up’ of H is simply a graph obtained from H by replacing each vertex of H by an independent set and each edge of H by a suitably large complete bipartite graph.)

The random graphs R = R(P, H) were considered before by Brown and Rödl [2] and Eaton and Rödl [5]. However, in [2, 5], the authors investigate Ramsey properties of these graphs with respect to vertex colourings. A similar construction is studied by Rödl and Winkler in [17], where Ramsey properties with respect to orientations of graphs are investigated. More recently, Łuczak and Rödl [12] confirmed a conjecture of Trotter by showing that r_{ind}(H) = t^{O(1)} if the t-vertex graph H has bounded maximum degree. The graph R = R(P, H) is crucial in [12].

Since (4) fails to prove Conjecture 2 in full generality, we consider graphs G with some special structure. To describe a class of graphs G for which we are able to prove Conjecture 2, we need to introduce a couple of definitions.

If G_{1} and G_{2} are two graphs, we let the join G_{1} ∨ G_{2} of G_{1} and G_{2} be the graph obtained from the disjoint union of G_{1} and G_{2} by adding all the G_{1}– G_{2} edges. Thus, for instance, K^{a,b} = E^{a} ∨ E^{b}, where K^{a,b} is the complete bipartite graph with vertex classes of cardinalities a and b, and E^{a} denotes the a-vertex graph with no edges, and similarly for E^{b}.

Let S denote the smallest class of finite graphs that contains the 1-vertex complete graph and is closed under taking disjoint unions and joins. Following Erdős and Hajnal [8], we call the graphs in S simple. Theorem 4 below verifies Conjecture 2 in the case in which G is a simple graph.

Theorem 4. For any simple graph G, there is a constant f = f(G) that depends only on G such that, for any graph H on t vertices, we have

r_{ind}(G, H) ≤ t^{f}.

The proof of Theorem 4 will also be based on the random graph R = R(P, H). However, quite naturally, the choice of certain parameters in the definition of this graph for this proof will be different from the choice to be made in the proof of Theorem 3.

A basic case that is not covered in Theorem 4 is the one in which G is a tree. As one may expect, this case can be handled quite easily.

Theorem 5. For any tree T and arbitrary graph H, we have

r_{ind}(T, H) ≤ ck^{2}t^{4} (\frac{log(kt^{2})}{log log log(kt^{2})})^{2} ,  (5)

where k = |V (T)|, t = |V (H)|, and c is some absolute constant.

Thus, Theorem 5 tells us that r_{ind}(T, H) is polynomial in both k = |V (T)| and t = |V (H)|. Our proof of this result is simple, and we have not put much effort in obtaining the best exponents in (5). Let us mention that Beck has investigated the problem of estimating the induced size-Ramsey number of a given tree T, which is defined to be the minimal number of edges in a graph Γ = Γ(T) such that Γ → (T, T). Indeed, in [1], Beck proves that if T is a tree with n edges and n is larger than some absolute constant, then there is a graph Γ with less than

n^{3}(log n)^{4}

edges such that Γ → (T, T).

This paper is organised as follows. The random graph R = R(P, H) is defined in Section 2, where auxiliary results concerning projective planes are also given. We also give in Section 2 a couple of properties of R = R(P, H) that are crucial later on in the proofs of Theorems 3 and 4, given in Sections 3 and 4. The induced Ramsey number for trees versus general graphs is studied in Section 5. Our very short final section is devoted to some concluding remarks.

As the reader will observe, we try to isolate, whenever possible, the probabilistic parts of our arguments in the proofs of Theorems 3 and 4. For instance, Section 3.2 is entirely deterministic in nature. The only probabilistic component in the proof of Theorem 3 is, in fact, an application of Corollary 11 of Section 2.3, made in Section 3.3. Needless to say, this probabilistic component is crucial for our argument.

Below, we write a ≪ b to mean that a/b → 0 as n → ∞, and similarly for ≫. We also write a ∼ b to mean that a/b → 1 as n → ∞. Moreover, for A > 0, B > 0 and δ > 0, we write A ∼_{δ} B if 1/(1 + δ) < A/B < 1 + δ. In the sequel, the logarithms without specified bases are to the base e.

2. The Construction and Preliminary Lemmas

2.1. The construction. Let a projective plane P = (V, L) with |V | = |L| = n and a graph H be given. We shall construct a random graph R = R_{n} = R_{n}(P, H) based on P and H that will have interesting Ramsey properties with respect to ‘small’ graphs G and the graph H. Note in particular that the definition of R will not depend on the graph G.

To describe our construction, suppose that, for each line L ∈ L, we have a partition L = ⋃_{v∈V (H)} L_{v} of L whose parts L_{v} are indexed by the vertices v ∈ V (H) of H. Denote this partition by Π_{L}, and set Π = (Π_{L})_{L∈L}. We define the graph R = R_{n}(P, H, Π) as follows. The vertex set of R is V. To define the edge set of R, suppose a, b ∈ V are two distinct points in P. Then there is a unique line L ∈ L that contains both a and b. Consider the partition Π_{L} ∈ Π of L, and suppose a ∈ L_{u} and b ∈ L_{v}. Then

ab ∈ E(R) if and only if uv ∈ E(H).

To define the random graph R = R_{n}(P, H), we pick the family of partitions (Π_{L})_{L∈L} randomly. For each L ∈ L, the partition Π_{L} is chosen uniformly at random from all the partitions of L indexed by V (H). Equivalently, for each x ∈ L, we choose a vertex v ∈ V (H) independently and uniformly at random and let x ∈ L_{v}. The choices of the Π_{L} are made independently for all L ∈ L. This defines a random family of partitions Π = (Π_{L})_{L∈L}, and we define our random graph R by letting

R = R_{n}(P, H) = R_{n}(P, H, Π).

Note that the randomness of R = R_{n}(P, H, Π) comes solely from the random choice of Π. Once Π is chosen, the graph R is determined.

2.2. Lemmas on projective planes. Naturally, the key to a good understanding of the random graph R = R_{n}(P, H) is a good understanding of the random family Π = (Π_{L})_{L∈L}. In this section, we shall review a few facts about projective planes that will be needed in Section 2.3, where we analyse the structure of a typical family Π = (Π_{L})_{L∈L}.

We start with a lemma due to Eaton and Rödl [5].

Lemma 6. Let (V, L) be a projective plane of order p and n = p^{2} + p + 1. Let X ⊂ V and Y ⊂ L be given, and suppose |X| = αn and |Y| = βn. Then

\frac{αβn^{2}}{p + \sqrt{p} + 1} (1 − \frac{1 + O(n^{−1/4})}{\sqrt{αβ\sqrt{n}}}) ≤ ∑_{L∈Y} |X ∩ L|

≤ \frac{αβn^{2}}{p + \sqrt{p} + 1} (1 + \frac{1 + O(n^{−1/4})}{\sqrt{αβ\sqrt{n}}}) .

Corollary 7. With the notation as above, if αβ ≥ ωn^{−1/2}, then

∑_{L∈Y} |X ∩ L| = (1 + O (\frac{1}{\sqrt{ω}} )) αβn^{3/2}.

In the corollary below, O_{1}(a) denotes a term b that satisfies |b| ≤ a.

Corollary 8. Suppose X ⊂ V and α = |X|/n. Then, if β = β(n) satisfies αβ ≥ 2ωn^{−1/2} for some function ω = ω(n) → ∞, we have

|X ∩ L| = (1 + O_{1} (\frac{log ω}{\sqrt{ω}} )) α\sqrt{n}  (6)

for all but fewer than βn lines L ∈ L, as long as n ≥ n_{0}(ω).

Proof. Suppose (6) fails. Then there is a set of lines Y ⊂ L with |Y| = ⌈βn/2⌉ such that either

|X ∩ L| > (1 + \frac{log ω}{\sqrt{ω}} ) α\sqrt{n}  (7)

for all L ∈ Y, or else

|X ∩ L| < (1 − \frac{log ω}{\sqrt{ω}} ) α\sqrt{n}  (8)

for all L ∈ Y. Suppose (7) happens. Summing (7) over all L ∈ Y, we have, by Corollary 7,

(1 + \frac{log ω}{\sqrt{ω}} ) α\sqrt{n}|Y| < ∑_{L∈Y} |X ∩ L| = (1 + O (\frac{1}{\sqrt{ω}} )) α\sqrt{n}|Y|,

which contradicts Corollary 7 if n ≥ n_{0}(ω), since ω = ω(n) → ∞. The case in which (8) holds for all L ∈ Y is similar.

Let us remark that, clearly, the O_{1} term in the result above may be chosen to be anything that is sufficiently larger than ω^{−1/2}. Note also that Corollary 8 only concerns sets X with |X| ≫ \sqrt{n}, since we need β ≤ 1 and hence αβ ≫ n^{−1/2} can only hold if α ≫ n^{−1/2}.

In view of Corollary 8, we make the following definition. Let X ⊂ V, L ∈ L, and δ > 0 be given. We say that the line L is (X, δ)-normal if

|X ∩ L| ∼_{δ} \frac{|X|}{\sqrt{n}} .

(We recall that we write A ∼_{δ} B if 1/(1 + δ) < A/B < 1 + δ.) Let us set

B(X, δ) = {L ∈ L: L is not (X, δ)-normal}.  (9)

Note that Corollary 8 implies that |B(X, δ)| < βn if X ⊂ V satisfies β|X| ≫ \sqrt{n} and n is large enough.

2.3. A few lemmas on Π = (Π_{L})_{L∈L}. To study the random graphs R = R_{n}(P, H), we need to investigate the random family of partitions Π = (Π_{L})_{L∈L} that is used to define those random graphs. In fact, in this section, we assume that Π = (Π_{L})_{L∈L} is a family of random partitions of the L ∈ L, with each Π_{L} an independent random partition of L, uniformly chosen from all the partitions of L indexed by [t] = {1, …, t}, for some given integer t. We shall only be concerned with large t and large n. Thus, the inequalities below need only hold for large enough t and n. Before we proceed, let us stress that the graph H will not play any rôle in this section.

We start with a definition that will be very important in the sequel. Let L ∈ L, X ⊂ V, and δ > 0 be given. Also, let a fixed family of [t]-indexed partitions Π = (Π_{L})_{L∈L} be given. We then say that L is (X, δ, Π)-normal if

|X ∩ L_{i}| ∼_{δ} \frac{|X|}{t\sqrt{n}}

for all 1 ≤ i ≤ t, where L_{i} is the ith block of the partition Π_{L} of L. A moment’s thought shows that if a line L is (X, δ, Π)-normal, then it is also (X, δ)-normal, whereas the converse holds only if the partition Π_{L} of L splits X ∩ L ‘judiciously.’

Let us set

B(X, δ, Π) = {L ∈ L: L is not (X, δ, Π)-normal}.  (10)

Our next simple lemma says that the probability that many (X, δ/2)-normal lines should fail to be (X, δ, Π)-normal is very small.

Lemma 9. Fix δ > 0 and X ⊂ V. Then

ℙ\{|B(X, δ, Π) \ B(X, δ/2)| ≥ t^{2}\sqrt{n}\} < exp (−c_{δ}t|X| + \frac{1}{2}t^{2}\sqrt{n} log n) ,

where c_{δ} is some positive constant that depends only on δ.

Proof. Let a (X, δ/2)-normal line L ∈ L\B(X, δ/2) be fixed (cf. (9)). Then, by definition,

|X ∩ L| ∼_{δ/2} \frac{|X|}{\sqrt{n}} .

Fix 1 ≤ i ≤ t. By Chernoff’s inequality, we have

ℙ \{|X ∩ L_{i}| ∼_{δ} \frac{|X|}{t\sqrt{n}}\} ≥ 1 − exp (−c_{δ} \frac{|X|}{t\sqrt{n}})

for some c_{δ} > 0 that depends only δ. Hence

ℙ (L is not (X, δ, Π)-normal) ≤ t exp (−c_{δ} \frac{|X|}{t\sqrt{n}}) .

Since the partitions Π_{L} (L ∈ L) are chosen independently, we have

ℙ\{|B(X, δ, Π) \ B(X, δ/2)| ≥ t^{2}\sqrt{n}\}

≤ \binom{n}{⌈t^{2}\sqrt{n}⌉} (t exp (−c_{δ} \frac{|X|}{t\sqrt{n}}))^{⌈t^{2}\sqrt{n}⌉}

≤ exp (−c_{δ}t|X| + \frac{1}{2}t^{2}\sqrt{n} log n) ,

as required.

Corollary 8 and Lemma 9 have the following immediate consequence.

Corollary 10. Let functions α = α(n) and β = β(n) such that αβ ≫ n^{−1/2} be given, and suppose that a constant δ > 0 is fixed. Then the probability that there is a set X ⊂ V with |X| ≥ αn such that

|B(X, δ, Π)| ≥ t^{2}\sqrt{n} + βn

is at most

∑_{αn≤r≤n} \binom{n}{r} exp (−c_{δ}tr + \frac{1}{2}t^{2}\sqrt{n} log n) .  (11)

To state the main result of this section concisely, we need to introduce some notation. Fix δ > 0. Suppose X = (X_{i})_{i=1}^{t} is a family of subsets X_{i} ⊂ V of V, and suppose Π = (Π_{L})_{L∈L} is a fixed family of [t]-indexed partitions of the lines of P = (V, L). Then we let

L(X, δ, Π) = {L ∈ L: L is (X_{i}, δ, Π)-normal for all i ∈ [t]}. (12)

Thus, a line L ∈ L belongs to L(X, δ, Π) if and only if

|X_{i} ∩ L_{j}| ∼_{δ} \frac{|X|}{t\sqrt{n}}  (13)

for all i and j ∈ [t]. Moreover, L(X, δ, Π) = L \ ⋃_{1≤i≤t} B(X_{i}, δ, Π) (cf. (10)). When studying the subgraphs of the graph R = R_{n}(P, H, Π), we shall need to look at families of t sets of vertices X = (X_{i})_{i=1}^{t}, and we shall be interested in the lines that intersect these t sets in the ‘expected way.’ The set L(X, δ, Π) of lines of P defined above is the set of such ‘interesting’ lines.

Given constants 0 < ε < 1/2, δ > 0, and 0 < η < 1, and a family Π = (Π_{L})_{L∈L} of [t]-indexed partitions, we let P(ε, δ, η, Π) denote the following property:

(*) For all X = (X_{i})_{i=1}^{t} with X_{i} ⊂ V such that |X_{i}| ≥ n^{1/2+ε} for all i ∈ [t], we have

|L(X, δ, Π)| ≥ (1 − η)n.

It is probably worth at this point to unfold the definitions to give a more direct formulation of property P(ε, δ, η, Π): the family Π satisfies P(ε, δ, η, Π) if and only if, for all X as in (*), at least (1 − η)n lines L ∈ L are such that (13) holds for all i and j ∈ [t].

Corollary 10 has the following consequence that will be crucial in our study of the random graph R = R_{n}(P, H).

Corollary 11. Let constants 0 < ε ≤ 1/3, δ > 0, and 0 < η < 1 be fixed. Suppose t = t(n) is such that log n ≪ t ≪ n^{ε/2}. Then

ℙ{P(ε, δ, η, Π) holds} → 1

as n → ∞. In particular, if n ≥ n_{0}(ε, δ, η, t), there is a family of [t]-indexed partitions Π = (Π_{L})_{L∈L} for which P(ε, δ, η, Π) holds.

Proof. Let α = α(n) = n^{−1/2+ε} and β = β(n) = n^{−ε/2}. Simple calculations show that

t^{2}\sqrt{n} + βn ≪ n/t,

and that the quantity in (11) tends to 0 as n → ∞. Thus, Corollary 10 says that, with probability tending to 0 as n → ∞, every X ⊂ V with |X| ≥ n^{1/2+ε} is such that

|B(X, δ, Π)| < t^{2}\sqrt{n} + βn ≪ n/t.

In particular, given any X = (X_{i})_{i=1}^{t} as in (*), we have

| ⋃_{1≤i≤t} B(X_{i}, δ, Π)| ≪ n

with probability approaching 1 as n → ∞. Thus Corollary 11 follows.

2.4. The pseudorandomness of R = R_{n}(P, H, Π). Fix a graph H and let P be a projective plane. Consider the graph R = R_{n}(P, H, Π) defined in Section 2.1, where Π = (Π_{L})_{L∈L} is some family of V (H)-indexed partitions of the lines of P.

Let γ denote the edge-density e(H)\binom{t}{2}^{−1} of H, where as customary e(H) stands for the number of edges in H. Later we shall see that, in the proofs of Theorems 3 and 4, we may assume that γ is close to 1/2. Thus, in this section, we assume that

3/7 ≤ γ ≤ 4/7.  (14)

Our aim is to show that if P(ε, δ, η, Π) holds for suitably small parameters ε, δ, and η, any two disjoint and reasonably large sets A and B ⊂ V of vertices of the graph R = R_{n}(P, H, Π) are connected by about γ|A||B| edges. In other words, the graph R is ‘pseudorandom.’ Lemma 12. Let 0 < ε < 1/2 and 0 < δ ≤ 1 be fixed. Suppose Π = (Π_{L})_{L∈L} is a family of V (H)-indexed partitions of the lines of P. Furthermore, suppose that the property P(ε, δ/5, 3δ/40, Π) holds and that t ≥ 40/3δ. Then the graph R = R_{n}(P, H, Π) is such that, for every A, B ⊂ V (R) with A ∩ B = ∅ and |A|, |B| ≥ n^{1/2+ε}, the number of edges e(A, B) between A and B satisfies

e(A, B) ∼_{δ} γ|A||B|.  (15)

Proof. Let L_{AB} be the set of lines L ∈ L that are both (A, δ/5, Π)- and (B, δ/5, Π)-normal. Since property P(ε, δ/5, 3δ/40, Π) holds, we know that

|L_{AB}| ≥ (1 − 3δ/40)n.  (16)

By the definition of L_{AB}, for any line L ∈ L_{AB} we have

|L_{v} ∩ A| ∼_{δ/5} \frac{|A|}{t\sqrt{n}} and |L_{v} ∩ B| ∼_{δ/5} \frac{|B|}{t\sqrt{n}}

for every v ∈ V (H), where L = ⋃_{v∈V (H)} L_{v} is the partition Π_{L} of L. In particular, if uv ∈ E(H), we have

∼_{3δ/5} \frac{|A||B|}{t^{2}n}  (17)

edges joining the sets L_{u} ∩ A and L_{v} ∩ B, and similary for L_{v} ∩ A and L_{u} ∩ B. Furthermore, if uv ∉ E(H), the number of non-edges between L_{u} ∩ A and L_{v} ∩ B, and similarly between L_{v} ∩ A and L_{u} ∩ B, is also given by (17).

Therefore

e(A, B) ≥ ∑_{L∈L_{AB}} ∑_{uv∈E(H)} {|L_{u} ∩ A||L_{v} ∩ B| + |L_{v} ∩ A||L_{u} ∩ B|}

∼_{3δ/5} |L_{AB}|2\frac{|A||B|}{t^{2}n}γ\binom{t}{2} ≥ \frac{1}{1 + 3δ/4}γ|A||B|,

where in the last inequality we used (16) and the fact that t ≥ 40/3δ and δ ≤ 1. Similarly, we infer that the number of non-edges between A and B is at least

\frac{1 − γ}{1 + 3δ/4}|A||B|.

Using that γ ≥ 3/7 (cf. (14)), we may now deduce from straightforward computations that (15) follows.

We observe that the proof above only made use of a weak form of property P(ε, δ/5, 3δ/40, Π). Indeed, this property concerns families X of t elements, but in the proof above we were only concerned about the pair of sets {A, B}.

2.5. Blow-ups of H in R = R_{n}(P, H, Π). In Section 2.4 above, we observed that the graph R = R_{n}(P, H, Π) tends to have all its edges uniformly spread over V (R). The usual binomial random graphs G_{n,p} also have this property, and hence the random graphs R = R_{n}(P, H) and G_{n,p} (with p = γ) may be expected to behave similarly. However, one sees right away a crucial difference between these graphs: R = R_{n}(P, H) is extremely rich in copies of H. Indeed, each line of P is very likely to induce a ‘very fat’ blown-up copy of H. This feature will be crucial in our considerations.

In what follows, if s ≥ 1 is an integer, we shall write H_{s} for the s-fold blow-up of H, namely, the graph on s|V (H)| vertices that we obtain from H by replacing each vertex of H by an independent set of cardinality s and each edge of H by a complete bipartite graph K^{s,s}. The following simple lemma will be needed in the sequel.

Lemma 13. Every red-blue edge colouring of H_{s} that contains no blue copy of H must contain at least s^{2} red edges.

Proof. Let us say that a copy H′ of H in H_{s} is transversal if |V (H′)∩V_{x}| = 1 for all x ∈ V (H), where V_{x} is the independent set of vertices of H_{s} that is naturally associated to x ∈ V (H). Clearly H_{s} has s^{t} transversal copies of H. On the other hand, each edge is contained in s^{t−2} transversal copies of H. Thus, at least s^{t}/s^{t−2} = s^{2} red edges are needed to prevent a transversal blue copy of H. This proves Lemma 13.

3. The General Estimate

Our aim in this section is to give a proof of Theorem 3. Since our proof is fairly long and is based on a few separate ideas, we shall sketch the general approach before we start the proof proper.

Let graphs G and H as in Theorem 3 be given. A simple argument shows that we may assume that the edge-density e(H)\binom{t}{2}^{−1} of H is, say, between 3/7 and 4/7. As mentioned in the introduction, the main idea is to make use of the random graphs R = R_{n}(P, H), defined in Section 2.1.

The two key properties of R for the arguments in this section are the following: (i) R is a pseudorandom graph, in the sense that its edges are uniformly distributed (with density similar to the density of H), and (ii) any collection of t pairwise disjoint sets X_{1}, …, X_{t} of vertices of R induce many ‘fat’ blow-ups of H, as long as the X_{i} are all sufficiently large.

Suppose now that the edges of our graph R have been coloured with red and blue. Property (i) may be used to show that any appropriately large set S of vertices of R that is ‘uniformly rich’ in red edges must induce a red copy of G. Roughly speaking, we shall consider a set S uniformly rich in red edges if S, as well as all large subsets of S, induce sufficiently many red edges. (To be precise, we shall define the term hereditarily ε-red-rich in Section 3.2.1 to formalise this notion of uniform richness.)

On the other hand, property (ii) may be used to show that any collection of t suitably large sets of vertices of R is forced to induce a blue copy of H, as long as the density of the red edges across these sets is small. The proof of the fact that R → (G, H) is then reduced to showing that either R has a set of vertices that is ‘uniformly rich’ in red edges, or else R has t suitably large sets of vertices that induce, across them, very few red edges.

Let us now start the proof of Theorem 3.

3.1. The main lemma. For technical reasons, it will be convenient to prove first the following restricted version of Theorem 3.

Lemma 14. There exist absolute constants t_{0} and C for which the following holds. Let G and H be graphs with |V (G)| = k ≥ 2 and |V (H)| = t ≥ t_{0}, where t ≥ k^{2}. Write γ = e(H)\binom{t}{2}^{−1} for the edge-density of H, and suppose 3/7 ≤ γ ≤ 4/7. Suppose furthermore that H has a proper colouring V (H) = ⋃_{1≤i≤q} V_{i} with all the V_{i} of cardinality w = t/q, where q = χ(H) ≥ 2. Then

r_{ind}(G, H) ≤ t^{Ck log q}.

We now sketch an argument that shows that Lemma 14 implies Theorem 3. Thus, let graphs G and H as in Theorem 3 be given. In particular, we have t ≥ k.

Let us first observe that t may be assumed to be larger than any fixed constant. Indeed, recalling the existence of graphs Γ = Γ(G, H) for which Γ → (G, H) for any given G and H (see [4, 9, 15]), we may exclude from our consideration any bounded number of pairs (G, H), since we may choose the constant C in (4) sufficiently large to cover this bounded number of cases. Moreover, by adding fewer than q = χ(H) isolated vertices to H, we may assume that q divides t.

Now fix a proper vertex colouring V (H) = V_{1}∪⋯∪V_{q} of H. Add t^{2}/q−|V_{i}| isolated vertices to V_{i} for all i to obtain a graph H′. Note that now we have t^{2} vertices. Now, a little thought shows that we may add edges to H′, each of them incident to at least one vertex in V (H′) \ V (H) and all of them respecting the q-colouring we started with, and, furthermore, in such a way that the graph H′′ that we obtain is such that γ = e(H′′)\binom{t^{2}}{2}^{−1} lies between 3/7 and 4/7 (here we also use that t ≥ t_{0} for some large enough constant t_{0}).

Let us outline an easy argument to show that we may indeed obtain the graph H′′ as required. Note that the only thing to check is whether we can accommodate the condition on the density of H′′. If we add to H′ all the edges allowed by the other two conditions, we get at least about

(1 − \frac{1}{q}) \binom{t^{2}}{2} − \binom{t}{2}

new edges. Thus, even if q = 2, we have at least about \frac{1}{2} \binom{t^{2}}{2} edges if t is large. On the other hand, if we do not add any edge to H′, we have at most \binom{t}{2} edges out of \binom{t^{2}}{2}, which gives a density far smaller than 1/2 if t is large. Thus the graph H′′ as required does exist.

It now suffices to apply Lemma 14 to H′′ to deduce that there is a graph Γ such that Γ → (G, H′′) and such that |Γ| ≤ (t + q − 1)^{2Ck log q}, where C is the constant in Lemma 14. Theorem 3 follows, since clearly Γ → (G, H).

In the rest of Section 3, we investigate R = R_{n}(P, H) with the aim of showing that R → (G, H) with positive probability, even if n is not too large with respect to k and t. More precisely, we shall prove the following statement.

(†) There exists an absolute constant t_{0} such that, for any graphs G and H as in Lemma 14, there is an integer n = n(k, t, q) with

n ≤ 4t^{1000k log q},

where q = χ(H), such that

R = R_{n}(P, H) → (G, H)

holds with positive probability.

We shall not try to optimise our constants. In particular, the constant 1000 in (†) is clearly not optimal. We also remark that our proof will in fact show a stronger Ramsey property of R = R_{n}(P, H). Write G^{k} for the family of all graphs on k vertices. Our proof of (†) will in fact give that

R = R_{n}(P, H) → (G^{k}, H),

where the arrow notation above means that, when we colour the edges of R with colours red and blue, either we obtain a blue induced copy of H, or else we obtain a red induced copy of every graph on k vertices.

3.2. Monochromatic subgraphs in R = R_{n}(P, H, Π). Throughout this section, we assume that graphs G and H as in the statement of Lemma 14 are given.

Let us fix a projective plane P = (V, L) with |V | = |L| = n. Let us also fix a family Π = (Π_{L})_{L∈L} of V (H)-indexed partitions of the lines of P. We may thus consider the graph R = R(P, H, Π) defined in Section 2.1. Suppose the edges of R = R(P, H, Π) are coloured with colours red and blue.

In Section 3.2.1 below, we describe a situation in which our red-blue coloured graph R may be guaranteed to contain an induced red copy of G. In Section 3.2.2, we study a condition that forces blue induced copies of H in R.

In both sections that follow, we shall assume that Π is fixed. In particular, our results will be deterministic and not probabilistic. For our arguments to work, we shall impose certain hypotheses on Π. Later on in the proof of (†), we shall invoke Corollary 11 to verify that these conditions imposed on Π are met with positive probability if Π is chosen randomly as specified in the definition of the random graph R = R_{n}(P, H).

3.2.1. Red induced copies of G. Fix 0 < ε < 1/2. A set S ⊂ V (R) is hereditarily ε-red-rich, or ε-HRR for short, if |S| ≥ n^{1/2+ε}t^{10k} and if, for every disjoint pair of sets A, B ⊂ S with |A|, |B| ≥ |S|/kt^{10k}, we have

e_{red}(A, B) ≥ \frac{1}{10t^{2}} |A||B|.  (18)

Here and below, e_{red}(A, B) denotes the number of red edges between A and B. We shall also write E_{red}(A, B) for the set of red edges between A and B. Moreover, N(x) = N_{R}(x) denotes the neighbourhood of the vertex x in R and N_{red}(x) denotes the set of neighbours of x in R that are joined to x by red edges.

In the beginning of Section 3, we mentioned that a notion of ‘uniform richness’ in red edges would appear in our arguments. The property of εred-richness is the precise formulation of this notion. As inequality (18) may suggest, roughly speaking, t^{−2} will be the ‘cut-off’ density in our argument: if we find a (large) set S of vertices in our red-blue edge-coloured graph that has red-edge density Ω(t^{−2}) (in fact, not only S but if all its large subsets has this red-edge density), then we search for a red induced copy of G within S. On the other hand, if no such set exists, we shall seek a blue induced copy of H.

Our next lemma, Lemma 15, states that ε-HRR sets S do indeed contain red induced copies of G, as long as some technical conditions are met. These technical conditions are basically to guarantee that our graph R = R_{n}(P, H, Π) satisfies a suitable pseudorandomness property (cf. Lemma 12). The underlying idea in the proof of Lemma 15 below is a well known one, and the reader is referred to Chvátal, Rödl, Szemerédi, and Trotter [3] and Rödl [16] for former applications of this idea.

Finally, we observe that in later applications of Lemma 15 below, we shall have ε = 1/10.

Lemma 15. Let 0 < ε < 1/2 be fixed, and assume Π = (Π_{L})_{L∈L} is a family of V (H)-indexed partitions of the lines of P for which P(ε, 1/30, 1/80, Π) holds. Moreover, suppose t ≥ 80. Then the graph R = R_{n}(P, H, Π) is such that every ε-HRR set S ⊂ V (R) contains an induced red copy of G.

Proof. Observe first that, since P(ε, 1/30, 1/80, Π) holds, Lemma 12 implies that

e(A, B) ∼_{1/6} γ|A||B|  (19)

holds any pair of disjoint sets A, B ⊂ V (R) with |A|, |B| ≥ n^{1/2+ε}.

Let S_{i} ⊂ S (1 ≤ i ≤ k) be k pairwise disjoint subsets of S, each with cardinality |S_{i}| = ⌊|S|/k⌋. Suppose V (G) = {v_{1}, …, v_{k}}. We shall find s_{i} ∈ S_{i} (1 ≤ i ≤ k) so that {s_{i}, s_{j}} ∈ E(R) if and only if {v_{i}, v_{j}} ∈ E(G) and, moreover, so that all such edges {s_{i}, s_{j}} are coloured red.

Applying (19) to the pairs of sets (S_{1}, S_{j}), where 2 ≤ j ≤ k, we may deduce that there are fewer than (k − 1)n^{1/2+ε} many vertices s ∈ S_{1} such that |N(s) ∩ S_{j}| > (2/3)|S_{j}| for some j = 2, …, k. Furthermore, there are fewer than (k − 1)|S|/kt^{10k} vertices s ∈ S_{1} with |N_{red}(s) ∩ S_{j}| < |S_{j}|/10t^{2} for some j = 2, …, k. This follows since S is ε-HRR. Thus, since

|S_{1}| > \frac{(k − 1)|S|}{kt^{10k}} + (k − 1)n^{1/2+ε},

there exist a vertex s_{1} ∈ S_{1} and sets S_{ℓ}^{(1)} (1 < ℓ ≤ k) with |S_{ℓ}^{(1)}| = ⌈|S_{ℓ}|/10t^{2}⌉ so that, for s ∈ S_{ℓ}^{(1)}, if {v_{1}, v_{ℓ}} ∈ E(G) then {s_{1}, s} ∈ E_{red}(R) and if {v_{1}, v_{ℓ}} ∉ E(G) then {s_{1}, s} ∉ E(R). We repeat this procedure k − 1 times.

On the jth step (2 ≤ j ≤ k) we construct sets S_{ℓ}^{(j)} (j < ℓ ≤ k), each of cardinality ⌈|S_{ℓ}|/(10t^{2})^{j}⌉, and select a vertex s_{j} ∈ S_{j}^{(j−1)} such that for s ∈

S_{ℓ}^{(j)} (j < ℓ ≤ k) we have that if {v_{j}, v_{ℓ}} ∈ E(G) then {s_{j}, s} ∈ E_{red}(R) and if {v_{j}, v_{ℓ}} ∉ E(G) then {s_{j}, s} ∉ E(R). The existence of such a vertex s_{j} follows similarly as before since

|S_{j}^{(j−1)}| = ⌈\frac{|S_{j}|}{(10t^{2})^{j−1}} ⌉ > \frac{(k − j)|S|}{kt^{10k}} + (k − j)n^{1/2+ε}.

The inductive procedure above constructs a red induced copy of G in R, as required.

Note that the proof above in fact shows that, under the conditions given in the lemma, an ε-HRR set of vertices in R is red k-universal, by which we mean that it induces a red copy of any graph on k vertices.

3.2.2. Blue induced copies of H. We may now turn to the lemma that gives a sufficient condition for the existence of a blue induced copy of H in R. Let us recall that q = χ(H) and that w = t/q. In the sequel, if s is a positive integer, we shall write Perm(s) for the set of permutations of the set [s] = {1, …, s}.

Perhaps it is worth observing that, in Lemma 16 below, the hypothesis on the number of edges ‘across’ the sets A_{i} guarantees that the ‘density of red edges’ across these sets is at most 1/5t^{2}. It is this small density of red edges that will allow us to find induced blue copies of H through an application of Lemma 13.

A comparison between Lemmas 15 and 16 suggests that, roughly speaking, t^{−2} should be a good ‘cut-off’ density for our arguments (cf. the remark following inequality (18) concerning this ‘cut-off’ density.)

In the proof of Theorem 3, we shall be concerned with property P(ε, δ, η, Π) with ε = 1/10, δ = 1/30, and η = 1/80. However, Lemma 16 below is stated with a weaker (larger δ and η) and more general (arbitrary ε) hypothesis on Π.

Lemma 16. Let 0 < ε ≤ 1/3 be fixed and suppose Π = (Π_{L})_{L∈L} is a family of V (H)-indexed partitions of the lines of P. If P(ε, 1/3, 1/2, Π) holds, then R = R(P, H, Π) has the following property. Let A_{1}, …, A_{q} be pairwise disjoint subsets of vertices of R with |A_{1}| = ⋯ = |A_{q}| = m, where m ≥ w(n^{1/2+ε} + 1). Assume moreover that

∑_{1≤i<j≤q} e_{red}(A_{i}, A_{j}) ≤ \frac{1}{5t^{2}} ∑_{1≤i<j≤q} |A_{i}||A_{j}| = \frac{1}{5t^{2}} \binom{q}{2}m^{2}.  (20)

Then there exist v_{i} ∈ ⋃_{1≤j≤q} A_{j} (1 ≤ i ≤ t) that induce a blue copy of H in R.

Proof. Recall we have a fixed proper vertex colouring V (H) = ⋃_{1≤i≤q} V_{i} of H with |V_{1}| = ⋯ = |V_{q}| = w = t/q. We write V_{i} = {v_{ij}: 1 ≤ j ≤ w} (1 ≤ i ≤ q). Let L be a line of our projective plane. The labelling v_{ij} of the vertices of H gives a natural labelling of the members L_{v} of the partition L = ⋃_{v} L_{v} of L in Π. Namely, we let the partition classes of L be denoted by L_{ij} (1 ≤ i ≤ q, 1 ≤ j ≤ w) in the natural way. Finally, for each 1 ≤ i ≤ q, choose w pairwise disjoint subsets A_{ij} ⊂ A_{i} (1 ≤ j ≤ w) with |A_{ij}| = ⌊m/w⌋ ≥ n^{1/2+ε} for each j.

Note that a line L is (A_{ij}, δ, Π)-normal if we have

|L_{i′j′} ∩ A_{ij}| ∼_{δ} \frac{|A_{ij}|}{t\sqrt{n}} = \frac{⌊m/w⌋}{qw\sqrt{n}}  (21)

for all 1 ≤ i′ ≤ q, 1 ≤ j′ ≤ w. Let δ = 1/3. In this proof, we shall make use of the lines L that are (A_{ij}, δ, Π)-normal for all the t sets A_{ij} (1 ≤ i ≤ q, 1 ≤ j ≤ w). Write L_{δ} for the set of all such lines. Then, clearly, we have

L_{δ} = L(A, δ, Π),

where A = (A_{ij})_{1≤i≤q,1≤j≤w} (cf. (12)). Since we are assuming that property P(ε, 1/3, 1/2, Π) holds, we know that

|L_{δ}| ≥ n/2.  (22)

We now consider (q + 1)-tuples of permutations σ̄ = (σ_{0}; σ_{1}, …, σ_{q}), where σ_{0} ∈ Perm(q) and σ_{i} ∈ Perm(w) (1 ≤ i ≤ q). In the sequel, if (i, j) ∈ [q] × [w], we write σ̄(i, j) for the pair (a, b) ∈ [q] × [w] where a = σ_{0}(i), and b = σ_{a}(j) = σ_{σ_{0}(i)}(j).

Now suppose L ∈ L_{δ}. Define f(L, σ̄) to be the number of red edges across the sets A_{ij}∩L_{σ̄(i,j)}, where a red edge is counted only if its endvertices belong to two such sets with distinct i.

We now average over L ∈ L_{δ} and σ̄. We have

∑_{L∈L_{δ}} ∑_{σ̄} f(L, σ̄) ≤ ∑_{L∈L} ∑_{σ̄} f(L, σ̄).  (23)

The sum on the right-hand side of (23) above is, however,

(q − 2)!(w − 1)!^{2}w!^{q−2}

times the number of red edges across the A_{i} (i.e., having endvertices in distinct A_{i}). To see this, let us fix one such edge e; say, e = xy and x ∈ A_{ij} and y ∈ A_{i′j′}. Note for later reference that i ≠ i′. The vertices x and y determine a unique line L ∈ L. It now suffices to notice that the values of i ≠ i′, j, and j′ tells us that, out of all the q!w!^{q} possibilities, exactly (q − 2)!(w − 1)!^{2}w!^{q−2} vectors σ̄ = (σ_{0}; σ_{1}, …, σ_{q}) are such that

x ∈ A_{ij} ∩ L_{σ̄(i,j)} and y ∈ A_{i′j′} ∩ L_{σ̄(i′,j′)}.

Therefore, we may indeed deduce that the left-hand side of (23) above is, by (20), at most

(q − 2)!(w − 1)!^{2}w!^{q−2} \frac{1}{5q^{2}w^{2}} ∑_{1≤i<j≤q} |A_{i}||A_{j}|

≤ (q − 2)!\frac{w!^{q}}{5q^{2}w^{4}} \binom{q}{2}m^{2} = \frac{q!w!^{q}}{10q^{2}w^{4}} m^{2}.

Since (22) holds and there are q!w!^{q} many σ̄, there exists a pair (L, σ̄) with L ∈ L_{δ} satisfying

f(L, σ̄) ≤ \frac{m^{2}}{5nq^{2}w^{4}} .  (24)

Fix such a pair (L, σ̄). Recall (21), and pick a set X_{ij} ⊂ A_{ij} ∩ L_{σ̄(i,j)} with |X_{ij}| = s = ⌈(3/4)m/qw^{2}\sqrt{n}⌉ for each 1 ≤ i ≤ q, 1 ≤ j ≤ w. Note that the t sets X_{ij} induce in R a copy of H_{s}, the s-fold blow-up of H. We have m ≤ (4/3)sqw^{2}\sqrt{n}. Hence, we have that the number of red edges in this copy of H_{s} is at most f(L, σ̄) < s^{2}, by (24). It now suffices to apply Lemma 13 to H_{s} to deduce that there is an induced blue copy of H in R, as required.

3.3. The proof of Theorem 3. As observed in Section 3.1, it suffices to prove Lemma 14 to prove Theorem 3. Lemma 14 is, however, a consequence of assertion (†) in Section 3.1, and hence we are left with proving that assertion.

Proof of (†). We fix ε = 1/10 and pick a prime p such that n = p^{2} + p + 1 satisfies

t^{Ck log q} ≤ n ≤ 4t^{Ck log q},

where C = 1000. The existence of such a prime p follows easily from Chebyshev’s theorem. Observe now that

log n ≪ t ≪ n^{ε/2}.  (25)

Indeed, the lower bound on t follows since t ≥ k^{2}, and the upper bound follows by the choice of C. Let us now observe that, quite crudely,

n^{0.4} ≥ t^{1+100k(log_{2} q+1)}.  (26)

Moreover, note that there is an absolute constant t_{0} such that if t ≥ t_{0}, then n ≥ n_{0}(1/10, 1/30, 1/80, t), where n_{0} is as given in Corollary 11. Clearly, we may assume that t_{0} ≥ 80. We shall show that this choice of t_{0} will do in assertion (†).

Suppose graphs G and H as in (†) are given, and suppose that t ≥ t_{0}. Let P = (V, L) be a projective plane of order p. Then |V | = |L| = n = p^{2} + p + 1. Recall (25), and invoke Corollary 11 to see that there is a family of V (H)-indexed partitions Π = (Π_{L})_{L∈L} of the lines of P for which property P(ε, 1/30, 1/80, Π) = P(1/10, 1/30, 1/80, Π) holds. Fix such a Π, and let R = R_{n}(P, H, Π). We claim that R → (G, H). Clearly, this will finish the proof of (†).

To prove our claim, we invoke Lemmas 15 and 16. Since t ≥ t_{0} ≥ 80 and property P(1/10, 1/30, 1/80, Π) holds, according to Lemma 15, we may assume that V (R) contains no ε-HRR subset. Indeed, according to that lemma, if there is an ε-HRR set of vertices in R, we must have a red induced copy of G in R. In the remainder of the proof, we show that the existence of no such ε-HRR subset of vertices implies the existence of sets A_{i} (1 ≤ i ≤ q) as required in Lemma 16. An application of that lemma will then give us a blue induced copy of H, completing the proof of (†).

To carry out the plan above, we shall need the following technical lemma. Let {0, 1}^{ℓ} denote the set of all 0–1 strings of length ℓ. (‡) Let ℓ = ⌈log_{2} q⌉. There are 2^{ℓ} pairwise disjoint sets X_{I} ⊂ V (R) (I ∈ {0, 1}^{ℓ}), each of cardinality m = ⌈n/t^{100ℓk}⌉, satisfying

∑_{I≠J}^{(ℓ)} e_{red}(X_{I}, X_{J}) < (\frac{1}{1 − kt^{−90k}} )^{2(ℓ−1)} \frac{1}{10t^{2}} ∑_{I≠J}^{(ℓ)} |X_{I}||X_{J}|, (27)

where ∑_{I≠J}^{(ℓ)} indicates sum over all I, J ∈ {0, 1}^{ℓ} with I ≠ J.

We postpone the proof of (‡), and carry on with the proof of (†). Assertion (‡) gives us 2^{ℓ} sets X_{I} satisfying (27), where ℓ = ⌈log_{2} q⌉. In particular, we have 2^{ℓ} ≥ q. A simple averaging argument now gives that some q of the sets X_{I}, say A_{i} (1 ≤ i ≤ q), are such that the number of red edges across these q sets is at most the quantity given in (20), as required in Lemma 16. Recall that property P(1/10, 1/30, 1/80, Π) holds. Moreover, note that the sets A_{i} have cardinality m = ⌈n/t^{100ℓk}⌉ ≥ w(n^{0.6} + 1). It follows from Lemma 16 that there must be a blue induced copy in R. This completes the proof of the claim that R → (G, H), and the proof of (†) will be complete once we establish (‡).

Proof of (‡). We prove the existence of the sets X_{I} (ℓ ∈ {0, 1}^{ℓ}) by induction on ℓ. This is simple for ℓ = 1: since V (R) is not ε-HRR, there are sets X′_{0}, X′_{1} ⊂ V (R) with |X′_{i}| ≥ n/kt^{10k} (i ∈ {0, 1}) so that

e_{red}(X′_{0}, X′_{1}) < \frac{1}{10t^{2}} |X′_{0}||X′_{1}|.  (28)

An easy averaging argument shows that there are in fact X_{0} ⊂ X′_{0}, X_{1} ⊂ X′_{1} with |X_{0}| = |X_{1}| = ⌈n/t^{100k}⌉ < n/kt^{10k} such that (28) remains true if X′_{i} is replaced X_{i} (i ∈ {0, 1}). We now turn to the induction step.

Assume that, for some 1 ≤ ℓ < log_{2} q = log_{2} χ(H), we have constructed 2^{ℓ} sets X_{J} (J ∈ {0, 1}^{ℓ}) with |X_{J}| = ⌈n/t^{100ℓk}⌉ such that inequality (27) holds.

We checked above that we do have this situation for ℓ = 1. Our aim now is to show that there exist sets X_{I} (I ∈ {0, 1}^{ℓ+1}) satisfying condition (27) with ℓ replaced by ℓ + 1 and with |X_{I}| = ⌈n/t^{100(ℓ+1)k}⌉ for all I.

Let

u = ⌊\frac{1}{2}(t^{100k} − kt^{10k})⌋ .

We now prove the following assertion.

(‡‡) Each X_{J} (J ∈ {0, 1}^{ℓ}) contains u + 1 pairs of disjoint sets Y_{J,2i}, Y_{J,2i+1} ⊆ X_{J} (0 ≤ i ≤ u) such that

|Y_{J,2i}| = |Y_{J,2i+1}| = ⌈\frac{n}{t^{100(ℓ+1)k}} ⌉  (29)

and

e_{red}(Y_{J,2i}, Y_{J,2i+1}) < \frac{1}{10t^{2}} |Y_{J,2i}||Y_{J,2i+1}|.  (30)

Let us prove (‡‡). We fix J ∈ {0, 1}^{ℓ} and construct the Y_{J,j} (0 ≤ j ≤ 2u + 1) by induction, using the fact that no subset of X_{J} is ε-HRR.

Since each X_{J} has cardinality larger than n^{1/2+ε}t^{10k} but is not ε-HRR, we can find set Y_{J,0}, Y_{J,1} satisfying (29) and such that (30) holds. We now proceed inductively. Suppose the sets Y_{J,2(i−1)}, Y_{J,2(i−1)+1} (1 ≤ i ≤ u) have been found. Put Z_{J} = X_{J} \ ⋃_{0≤j≤2u−1} Y_{J,j}. Observe that

|Z_{J}| = |X_{J}| − ∑_{0≤j≤2u−1} |Y_{J,j}| ≥ kt^{10k} \frac{n}{2t^{100k(ℓ+1)}} ,

where the last inequality is in fact quite crude. Since ℓ < log_{2} q and (26) holds, we have

kt^{10k} \frac{n}{2t^{100k(ℓ+1)}} ≥ kt^{10k} \frac{n}{2t^{100k(log_{2} q+1)}} ≥ n^{0.6}t^{10k} = n^{1/2+ε}t^{10k}.

Hence, the fact that Z_{J} is not ε-HRR implies that there are two sets Y_{J,2i}, Y_{J,2i+1} satisfying (29) and (30). The existence of the sets Y_{J,j} (0 ≤ j ≤ 2u + 1) follows by induction. Since J was arbitrary, assertion (‡‡) is proved.

Let us now proceed with the proof of (‡). For all J ∈ {0, 1}^{ℓ}, set

Y_{J} = ⋃_{i=0}^{2u+1} Y_{J,i}.

Then we have that

|Y_{J}| ≥ 2(u + 1) ⌈\frac{n}{t^{100(ℓ+1)k}} ⌉

≥ (t^{100k} − kt^{10k}) ⌈\frac{n}{t^{100(ℓ+1)k}} ⌉ ≥ (1 − \frac{k}{t^{90k}} ) |X_{J}|.

We may therefore infer from (27) that

∑_{I≠J}^{(ℓ)} e_{red}(Y_{I}, Y_{J}) < ∑_{I≠J}^{(ℓ)} e_{red}(X_{I}, X_{J})

≤ (\frac{1}{1 − kt^{−90k}} )^{2(ℓ−1)} \frac{1}{10t^{2}} (\frac{1}{1 − kt^{−90k}} )^{2} ∑_{I≠J}^{(ℓ)} |Y_{I}||Y_{J}|.

Now note that

e_{red}(Y_{I}, Y_{J}) = ∑_{i,j} e_{red}(Y_{I,2i} ∪ Y_{I,2i+1}, Y_{J,2j} ∪ Y_{J,2j+1}),

where the sum is taken over 0 ≤ i ≤ u and 0 ≤ j ≤ u. It follows from an averaging argument that, for each I ∈ {0, 1}^{ℓ}, there exists r_{I} (0 ≤ r_{I} ≤ u) so that

∑_{I≠J}^{(ℓ)} e_{red}(Y_{I,2r_{I}} ∪ Y_{I,2r_{I}+1}, Y_{J,2r_{J}} ∪ Y_{J,2r_{J} +1})

< (\frac{1}{1 − kt^{−90k}} )^{2ℓ} \frac{1}{10t^{2}} ∑_{I≠J}^{(ℓ)} |Y_{I,2r_{I}} ∪ Y_{I,2r_{I}+1}||Y_{J,2r_{J}} ∪ Y_{J,2r_{J} +1}|.

For each I ∈ {0, 1}^{ℓ}, set X_{I,0} = Y_{I,2r_{I}}, X_{I,1} = Y_{I,2r_{I}+1}. In this way we get a collection of 2^{ℓ+1} sets X_{L} (L ∈ {0, 1}^{ℓ+1}) with |X_{L}| = ⌈n/t^{100(ℓ+1)k}⌉ for all L and such that

∑_{L≠L′}^{(ℓ+1)} e_{red}(X_{L}, X_{L′}) < (\frac{1}{1 − kt^{−90k}} )^{2ℓ} \frac{1}{10t^{2}} ∑_{L≠L′}^{(ℓ+1)} |X_{L}||X_{L′}|.

This finishes the induction step and (‡) is proved.

4. Erdős–Hajnal Simple Graphs

Our aim in this section is to prove Theorem 4. We shall again use the random graphs R = R_{n}(P, H) introduced in Section 2.1.

We start by observing that we may assume that the edge-density γ = e(H)\binom{t}{2}^{−1} of the graph H in the statement of Theorem 4 satisfies 3/7 ≤ γ ≤ 4/7. We shall make use of this assumption towards the end of this section. Furthermore, we may assume that t is larger than some suitably large constant so that the inequalities below hold.

The proof of Theorem 4 will be by induction on the number of vertices of G. However, to make the induction work, we shall need to boost up the claim in that theorem.

4.1. A stronger version of Theorem 4. For graphs Γ, G, and H, and a real number M > 0, let us write Γ →^{M} (G, H) if in any red-blue colouring of the edges of Γ, there are either at least M red induced copies of G, or else there is at least one blue induced copy of H.

Suppose a projective plane P = (V, L) with |L| = |V | = n and a t-vertex graph H are fixed. Consider the graph R = R_{n}(P, H, Π), where, as usual, Π = (Π_{L})_{L∈L} is some family of V (H)-indexed partitions of the lines L of P.

Let a simple graph G on k vertices be fixed. We shall show below that, if n ≥ t^{f} for some large enough f = f(k) and property P(ε, δ, η, Π) holds for small enough ε, δ, and η > 0, then

R →^{M} (G, H),

where M = n^{(1−ϱ)k}, for any constant ϱ > 0 that is fixed in advance. It turns out that the assertion above is still not enough to make the induction work. Indeed, we need a ‘local’ version of the assertion above. In the result below, as customary, if X ⊂ V, we write R[X] for the subgraph of R induced by X.

Lemma 17. Let constants ε and ϱ > 0 and a k-vertex simple graph G be given. Then there exist constants f = f(ε, ϱ, G) and ε̃ = ε̃(ε, ϱ, G) > 0 for which the following holds. Let a t-vertex graph H be given, where t ≥ 80, and suppose P = (V, L) is a projective plane on n ≥ t^{f} points. Consider the graph R = R_{n}(P, H, Π), where Π = (Π_{L})_{L∈L} is such that P(ε̃, 1/30, 1/80, Π) holds. Then, for all X ⊂ V with |X| ≥ n^{1/2+ε}, we have

R[X] →^{M} (G, H),  (31)

where M = |X|^{(1−ϱ)k}.

Proof. The proof will be by induction on k = |V (G)|. If k = 1, there is nothing to do, as (31) holds trivially in this case for any ϱ > 0. Thus, let us assume that k ≥ 2 and that our lemma holds for smaller values of k. Let ε, ϱ > 0, and a k-vertex simple graph G be given. Then G = G_{1} ∪^{·} G_{2} or else G = G_{1} ∨ G_{2} for a pair of graphs (G_{1}, G_{2}) with G_{i} of order k_{i} < k (i = 1, 2). Let us consider the case in which G is the join of the graphs G_{1} and G_{2}. The other case is similar and a little simpler. We shall make a couple of comments about that case later on.

To find the constants f and ε̃ as required in the lemma, we need to make a few numerical considerations. Let η = 1/2 + ε. (††) There exist constants η′, η′′, and ϱ̃ such that 1/2 < η′′ < η′ < η, 0 < ϱ̃ < ϱ, and

(i) η′′ < η′ + η′(1 − ϱ̃)k_{2} − ηk_{2}, (ii) η′′(1 − ϱ̃)k_{1} + η′(1 − ϱ̃)k_{2} + η′ − η > η(1 − ϱ)k. We postpone the proof of (††), and carry on with the proof of Lemma 17.

Fix η′, η′′, and ϱ̃ as in the assertion above. Let η′ = 1/2 + ε′ and η′′ = 1/2 + ε′′. Clearly, ε′, ε′′ > 0. Let us apply the induction hypothesis to the triples (ε′′, ϱ̃, G_{1}) and (ε′, ϱ̃, G_{2}). Let f(ε′′, ϱ̃, G_{1}), f(ε′, ϱ̃, G_{2}), ε̃(ε′′, ϱ̃, G_{1}), and ε̃(ε′, ϱ̃, G_{2}) be the constants whose existence is guaranteed by the induction hypothesis. Put

f = f(ε, ϱ, G) = max \{\frac{2}{ε − ε′} , f(ε′′, ϱ̃, G_{1}), f(ε′, ϱ̃, G_{2})\}  (32)

and

ε̃ = ε̃(ε, ϱ, G) = min{ε, ε̃(ε′′, ϱ̃, G_{1}), ε̃(ε′, ϱ̃, G_{2})}.  (33)

We claim that the above choice for f and ε̃ will do. To prove our claim, let a t-vertex graph H be given, where t ≥ 80, let P = (V, L) be a projective plane on n ≥ t^{f} points, and suppose Π = (Π_{L})_{L∈L} satisfies P(ε̃, 1/30, 1/80, Π). Moreover, fix X ⊂ V with |X| ≥ n^{η} = n^{1/2+ε}. We shall now prove that (31) holds for M = |X|^{(1−ϱ)k}. A simple averaging argument shows that it suffices to consider the case in which |X| = n^{η} = n^{1/2+ε}. (For simplicity, in this proof we ignore ceiling and floor functions.)

Let R[X] have its edges coloured red and blue, and suppose that there is no blue induced of H in R[X]. We must find at least M red induced copies of G in R[X]. Put L(X, 1, Π) = {L ∈ L: L is (X, 1, Π)-normal}. Then, since P(ε, 1, 1/2, Π) clearly holds, we have

|L(X, 1, Π)| ≥ n/2.  (34)

Let s = |X|/2t\sqrt{n}. Each line L in L(X, 1, Π) induces an s-fold blow-up H_{s} of s. Thus, by Lemma 13, each such line must induce at least s^{2} red edges. Using (34), we see that R[X] must contain at least

\frac{1}{2}ns^{2} ≥ \frac{|X|^{2}}{8t^{2}}

red edges. Write d_{red}^{X}(x) for the number of red edges in R[X] that are incident to the vertex x ∈ X. A simple argument shows that the number of vertices x ∈ X such that d_{red}^{X}(x) ≥ |X|/8t^{2} is at least |X|/8t^{2}. Let us fix one such vertex x, and let us look at the set X′ = N_{red}(x) ∩ X of vertices in X that are joined to x by red edges.

Since f ≥ 2/(ε − ε′), we have that |X′| ≥ |X|/8t^{2} ≥ n^{η′}. Since f ≥ f(ε′, ϱ̃, G_{2}) and ε̃ ≥ ε̃(ε′, ϱ̃, G_{2}), we may deduce that R[X′] induces at least n^{(1−ϱ̃)η′k_{2}} red copies of G_{2}. Thus, the total number of red induced copies of K^{1} ∨ G_{2} within R[X] is at least

\frac{|X|}{8t^{2}}n^{(1−ϱ̃)η′k_{2}} ≥ n^{η′+(1−ϱ̃)η′k_{2}}.

Let us say that a red induced copy of G_{2} in R[X] is good if it belongs to at least n^{η′′} red induced copies of K^{1} ∨ G_{2} in R[X]. Again by a simple argument, using inequality (ii) above, we may deduce that we have at least

\frac{1}{2}n^{(1−ϱ̃)η′k_{2}+η′−η}  (35)

good red induced copies of G_{2} in R[X]. Fix one such good copy, and let us look at the set X′′ ⊂ X of vertices x′′ that, together with our good copy of G_{2}, induce a red K^{1} ∨ G_{2}. We have |X′′| ≥ n^{η′′}. Since f ≥ f(ε′′, ϱ̃, G_{1}) and ε̃ ≥ ε̃(ε′′, ϱ̃, G_{1}), we may deduce that R[X′′] contains at least n^{(1−ϱ̃)η′′k_{1}} red induced copies of G_{1}. Thus, our good copy of G_{2} in R[X] belongs to at least n^{(1−ϱ̃)η′′k_{1}} red induced copies of G. Taking into account that the number of such good copies of G_{2} in R[X] is at least as large as the quantity in (35), we deduce that the number of red induced copies of G in R[X] is at least

\frac{1}{2}n^{(1−ϱ̃)η′′k_{1}+(1−ϱ̃)η′k_{2}+η′−η}.

Recalling (i), we see that this quantity is no smaller than n^{(1−ϱ)kη}. This completes the induction step in the case in which G = G_{1} ∨ G_{2}.

Let us now briefly look at the case in which G = G_{1} ∪^{·} G_{2}. The argument here is similar, except that we have to make use of the fact that R[X] contains no pair (A, B) of fairly large disjoint sets with e(A, B) > (2/3)|A||B|. This follows since γ ≤ 4/7, and inequality (15) holds with δ = 1/6 for any A, B ⊂ X with |A|, |B| ≥ n^{1/2+ε}, since P(ε, 1/30, 1/80, Π) holds. We omit the details.

It now remains to prove (††).

Proof of (††). First we choose η′′ such that

η > η′′ > 1/2  (36)

and η′′k_{1} > ηk_{1} − ϱηk. This second inequality is equivalent to

η′′k_{1} + ηk_{2} > ηk(1 − ϱ).  (37)

Inequalities (36) and (37) above imply that it is possible to choose an η′ close enough to η, with η′′ < η′ < η, ensuring that

(η′ − η)k_{2} + η′ > η′′  (38)

and that

η′′k_{1} + η′k_{2} + η′ − η > ηk(1 − ϱ).  (39)

Comparing (38) and (39) with (i) and (ii) in (††), we easily see that it is now possible to choose 0 < ϱ̃ < ϱ close enough to 0 to guarantee (i) and (ii).

Write S^{k} for the family of simple graphs on k points. In fact, the proof of Lemma 17 given above gives that

R = R_{n}(P, H, Π) → (S^{k}, H),

that is, in any red-blue edge colouring of R, we either have a blue induced copy of H, or else we have a red induced copy of every simple graph on k vertices.

Corollary 11 and Lemma 17 imply Theorem 4.

5. Small Trees versus General Graphs

Our aim in this section is to prove Theorem 5. Let a graph H of order t be fixed, and let P = (V, L) be a projective plane with |V | = |L| = n. Let an integer k ≥ 2 be given. In this section, we consider a random graph R′ = R′_{n}(P, H, k) that is better suited for the purposes of this section. Indeed, to be able to prove inequality (5), we must certainly consider graphs that contain large induced trees, and hence we are better off by considering sparser versions of the random graph R = R_{n}(P, H) that we have considered elsewhere in this paper.

5.1. The construction of R′ = R′_{n}(P, H, k). Let b = 200. Put

q = bk \frac{log(kt^{2})}{log log log(kt^{2})}.  (40)

(For simplicity, we shall ignore floor and ceiling functions in this section.) Suppose P = (V, L) is such that n = |V | satisfies

k^{2}t^{4} (\frac{log(kt^{2})}{log log log(kt^{2})})^{2} ≤ n ≤ 4k^{2}t^{4} (\frac{log(kt^{2})}{log log log(kt^{2})})^{2} .  (41)

Let L ∈ L be a line of P. Randomly choose q pairwise disjoint subsets W_{1}, …, W_{q} ⊂ L of L, all of cardinality t. Note that this is possible since tq ≤ r + 1 holds for large enough t. Now, randomly insert q copies of H in L using these W_{i} as the vertex sets of these copies. Repeat this procedure for all the lines L ∈ L of P, making all the random choices independently. The resulting random graph is our R′ = R′_{n}(P, H, k).

Let us remark that the copies of H in R′ = R′_{n}(P, H, k) are in fact pairwise edge-disjoint. This will not, however, prevent us from proving an edge-Ramsey result.

Lemma 18. There exist absolute constants k_{0} and t_{0} for which the following holds. Let H be a graph of order t ≥ t_{0}, and consider R′ = R′_{n}(P, H, k) for k ≥ k_{0}. Then with positive probability we have that

R′ = R′_{n}(P, H, k) → (T, H)  (42)

for any tree T of order k.

Clearly, Lemma 18 above implies Theorem 5. In the rest of Section 5, we give a proof of Lemma 18. Let us mention that, similarly to what happened in previous sections, our proof will in fact give a ‘universal’ version of (42). Namely, one sees from the proof below that T in (42) may be replaced by T^{k}, the family of all trees on k points, i.e., if no blue induced copy of H is found in a red-blue edge-coloured R′, then all trees in T^{k} must be present in R′ as red induced subgraphs.

5.2. A technical lemma on R′ = R′_{n}(P, H, k). Let a graph H and a projective plane P as in the previous section be fixed. The integer k is also fixed throughout this section. Consider the random graph R′ = R′_{n}(P, H, k), and let x, y ∈ V (R′) be two distinct vertices of R′. The common neighbourhood N(x) ∩ N(y) of the vertices x and y in R′ may be ‘unexpectedly large’ (with respect to the edge-density of R′). Indeed, this may happen because x and y may belong to one of the copies of H that we embed in R′. However, our technical lemma below asserts that the number of common neighbours of x and y that do not belong to the line L = L(x, y) ∈ L determined by x and y is fairly small.

Let us say that x and y form a normal pair in R′ if

|(N(x) ∩ N(y)) \ L(x, y)| ≤ \frac{30 log n}{log log log n}.

Lemma 19. Let R′ = R′_{n}(P, H, k) be as above. Then, with probability approaching 1 as n → ∞, all pairs of vertices of R′ are normal.

Proof. We prove a few assertions that together imply our lemma. Below we shall use the term ‘almost surely’ to mean ‘with probability tending to 1 as n → ∞.’ Moreover, we shall tacitly assume that n is large enough whenever needed. (A1) Let x and y be two points of P, and fix a line L ≠ L(x, y) that contains y. Let Y = Y (x, y, L) ⊂ L \ {y} be the set of neighbours of x within L \ {y}. Then the probability that

|Y | < \frac{A log n}{log log n}  (43)

holds is at least 1 − n^{−6A/7}, for any fixed constant A.

To prove assertion (A1), fix a vertex z ∈ L \ {y}. If p is the probability that x and z are adjacent, then, because of (41), we have

p = qe(H)\binom{r + 1}{2}^{−1} ≤ bkt^{2}n^{−1} \frac{log(kt^{2})}{log log log(kt^{2})} ≤ \frac{b}{\sqrt{n}},  (44)

where r is such that n = r^{2} + r + 1, and, as usual, e(H) denotes the number of edges in H. Now, the events xz ∈ E(R′) (z ∈ L\{y}) are all independent. Thus, letting

ℓ = ⌈\frac{A log n}{log log n}⌉ ,

the probability that (43) fails is at most

\binom{r}{ℓ}p^{ℓ} ≤ (\frac{en^{1/2}p}{ℓ})^{ℓ} ≤ (\frac{eb}{ℓ})^{ℓ} ≤ n^{−6A/7},

as required.

Note that, in particular, the following assertion holds. (A2) If A ≥ 3, then, almost surely, for all triples (x, y, L) as in (A1), the set Y = Y (x, y, L) satisfies (43).

(A3) Let two points x, y ∈ V and a constant B be fixed. Assume that Y = Y (x, y, L) satisfies (43) for all lines L ≠ L(x, y) and some fixed A. Then the number of lines L ∈ L \ {L(x, y)} that contain a neighbour of both x and y in R′ = R′_{n}(P, H, k) is less than

\frac{B log n}{log log log n}  (45)

with probability at least 1 − n^{−6B/7}.

To prove assertion (A3), first fix a line L ≠ L(x, y). Since (43) holds, in view of (44) the probability p̃ that L contains a common neighbour of x and y satisfies

p̃ ≤ |Y (x, y, L)|p ≤ \frac{Ab log n}{\sqrt{n} log log n}.  (46)

Now, the events Y (x, y, L) ∩ N(y) ≠ ∅ (L ≠ L(x, y)) are all independent. Hence, the probability that at least

ℓ = ⌈\frac{B log n}{log log log n}⌉

of these events hold is, in view of (46), at most

\binom{r}{ℓ}p^{ℓ} ≤ (\frac{en^{1/2}p̃}{ℓ})^{ℓ} ≤ n^{−6B/7},

as required. (A4) If B ≥ 3, then, almost surely, for all pairs x, y ∈ V of distinct vertices of R′ = R′_{n}(P, H, k), the number of lines different from L(x, y) that contain a common neighbour of x and y is less than the quantity given in (45).

Assertion (A4) follows immediately from (A1) and (A3). (A5) Let y be a point of P, and let L ∈ L contain y. Moreover, suppose that a set Y ⊂ L \ {y} is given, and assume that Y satisfies (43) for some constant A. Then the probability that |Y ∩ N(y)| ≥ 11 is at most n^{−11/4}(log n)^{11}.

The probability that |Y ∩ N(y)| ≥ ℓ happens is at most the probability that a randomly chosen t′-element subset Z of L \ {y} meets Y in at least ℓ elements, where t′ = t − 1. Writing s for the cardinality of Y, we have that this latter probability is at most

\binom{r}{t′}^{−1} ∑_{i≥ℓ} \binom{s}{i}\binom{r − s}{t′ − i} ≤ ∑_{i≥ℓ} \binom{t′}{i} (\frac{s}{r})^{i} ,

which, by (43) and the trivial lower bounds r ≥ \sqrt{n}/2 and n ≥ t^{4}, is seen to be no larger than

2\binom{t}{ℓ} (\frac{2A log n}{\sqrt{n} log log n})^{ℓ} .

Letting ℓ = 11, assertion (A5) follows.

A simple application of assertions (A1)–(A5) with A = B = 3 proves Lemma 19.

5.3. Proof of Lemma 18. We are now ready to prove Lemma 18, which, as remarked above, implies Theorem 5.

Proof of Lemma 18. Let a projective plane P = (V, L) on n points be fixed, and suppose a t-vertex graph H and an integer k are given. Suppose further that (40) and (41) hold. Consider the graph R′ = R′_{n}(P, H, k), and suppose that all pairs of distinct vertices of R′ are normal. We shall show below that, under these conditions, we have

R′ → (T, H)  (47)

for any tree T on k points. Invoking Lemma 19, the proof of Lemma 18 will be complete.

To prove (47), let R′ be red-blue edge-coloured in such a way that no blue induced copy of H is present. Our aim is to show that, then, any tree T on at most k vertices appears as an induced subgraph of R′ with all its edges coloured red. To this end, let us first observe that, since every copy of H in each line of P must contain a red edge, there are at least qn red edges in R′. In fact, we may choose exactly qn red edges in R′ so that, in each line L ∈ L, we have an independent set of q red edges. Let R be such a collection of red edges.

A standard argument now shows that there is a subset V′ of V (R′) such that every vertex v ∈ V′ is incident to at least q red edges in R ∩ E(R′[V′]). In other words, the graph spanned by R ∩ E(R′[V′]) in R′[V′] has minimal degree at least q. In what follows, we restrict our attention to R′[V′].

We shall now prove by induction on |V (T)| that any tree T on at most k vertices is present in R′[V′] as a red induced subgraph. Thus, R′[V′] will be shown to be red k-tree-universal, that is, all trees on k vertices appear in R′[V′] as red induced subgraphs (cf. the remark following the proof of Lemma 15).

There is nothing to do if |V (T)| = 1. So assume that 2 ≤ |V (T)| ≤ k, and that the subtree T′ of T obtained from T by removing a leaf of T appears as a red induced subgraph in R′[V′]. (In the sequel, we identify T′ with this copy of T′ in R′[V′].) Clearly, it suffices to show that an appropriate vertex x′ ∈ V (T′) ⊂ V′ has a neighbour x ∈ V′ such that xx′ is red and, furthermore, x is not adjacent to any vertex in F = T′ − x′. Let such a vertex x′ be fixed.

Let

Z = {z ∈ N_{red}^{R}(x′) ∩ V′: L(x′, z) ∩ V (F) = ∅},  (48)

where N_{red}^{R}(x′) denotes the set of vertices connected to x′ with edges in R, and L(x′, z) is the line of P determined by x′ and z. Since there is at most one red edge in R that is incident to x′ in each line that contains x′, and |V (F)| ≤ k − 2, we have that

|Z| ≥ q − k + 2 ≥ \frac{1}{2}q = \frac{1}{2}bk \frac{log(kt^{2})}{log log log(kt^{2})}.  (49)

Using the normality of the pairs (x′, y) for y ∈ V (F), we have that

| ⋃_{y∈V (F)} N(y) ∩ Z| ≤ \frac{30(k − 2) log n}{log log log n}.  (50)

Comparing (49) and (50) (and recalling that b = 200), we see that there is a vertex x ∈ Z that is not adjacent to any vertex in F in R′. Thus, we have found our red induced copy of T in R′[V′], as required. This completes the induction step, and hence we have proved that R′[V′] is indeed red k-tree-universal.

As remarked earlier, an application of Lemma 19 finishes the proof of Lemma 18.

6. Concluding Remarks

A refinement of Theorem 3 may be proved in the following fashion. As is well known, the technique applied in the proof of Lemma 15 gives better numerical results if the maximum degree of the graph G has smaller order of magnitude than k = |V (G)|. This fact, coupled with slightly more careful calculations, should suffice to improve (4) to

r_{ind}(G, H) ≤ 2^{c_{1}k}t^{c_{2}Δ log q},  (51)

where Δ = Δ(G) is the maximum degree of G, and c_{1} and c_{2} are universal constants.

However, even with (51), Problem 1 and Conjecture 2 remain open.

References

[1] J. Beck, On size Ramsey number of paths, trees, and circuits II, Mathematics of Ramsey Theory, Algorithms and Combinatorics, vol. 5, Springer-Verlag, Berlin, 1990, pp. 34–45.

[2] J.I. Brown and V. Rödl, A Ramsey type problem concerning vertex colourings, Journal of Combinatorial Theory, Series B 52 (1991), no. 1, 45–52, MR92c:05108.

[3] V. Chvátal, V. Rödl, E. Szemerédi, and W.T. Trotter, The Ramsey number of a graph with bounded maximum degree, Journal of Combinatorial Theory, Series B 34 (1983), no. 3, 239–243, MR#85f:05085.

[4] W. Deuber, A generalization of Ramsey’s theorem, Infinite and Finite Sets (Keszthely, 1973) (A. Hajnal, R. Rado, and V.T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, 1975, pp. 323–332.

[5] N. Eaton and V. Rödl, A canonical Ramsey theorem, Random Structures and Algorithms 3 (1992), no. 4, 427–444.

[6] P. Erdős, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), (loose errata) Academia, Prague, 1975, MR52#10500, pp. 183–192.

[7] , On some problems in graph theory, combinatorial analysis and combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983) (London, New York) (B. Bollobás, ed.), Academic Press, 1984, pp. 1–17.

[8] P. Erdős and A. Hajnal, Ramsey-type theorems, Discrete Applied Mathematics 25 (1989), no. 1–2, 37–52, MR90m:05091.

[9] P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs, Infinite and Finite Sets (Keszthely, 1973) (A. Hajnal, R. Rado, and V.T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, 1975, pp. 585– 595.

[10] R.L. Graham and V. Rödl, Numbers in Ramsey theory, Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, Cambridge–New York, 1987, pp. 112–153.

[11] R.L. Graham, B. Rothschild, and J.H. Spencer, Ramsey theory, second ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1990.

[12] T. Łuczak and V. Rödl, On induced Ramsey numbers for graphs with bounded maximum degree, Journal of Combinatorial Theory, Series B 66 (1996), no. 2, 324–333.

[13] J. Nešetřil, Ramsey theory, Handbook of Combinatorics (R.L. Graham, M. Grötschel, and L. Lovász, eds.), North-Holland, Amsterdam, 1995, pp. 1331–1403.

[14] F.P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society 30 (1930), 264–286.

[15] V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973.

[16] , On universality of graphs with uniformly distributed edges, Discrete Mathematics 59 (1986), no. 1-2, 125–134.

[17] V. Rödl and P. Winkler, A Ramsey-type theorem for orderings of a graph, SIAM Journal on Discrete Mathematics 2 (1989), no. 3, 402–406, MR90g:05135.

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: yoshi@ime.usp.br

Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany

   E-mail address: proemel@informatik.hu-berlin.de

Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA

   E-mail address: rodl@mathcs.emory.edu