RAMSEY GAMES AGAINST A ONE-ARMED BANDIT

EHUD FRIEDGUT, YOSHIHARU KOHAYAKAWA, VOJTĚCH RÖDL, ANDRZEJ RUCIŃSKI, AND PRASAD TETALI

Abstract. We study the following one-person game against a random graph: the Player’s goal is to 2-colour a random sequence of edges e_{1}, e_{2}, … of a complete graph on n vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge when it comes, before looking at the next edge.

While it is not hard to prove that the expected length of this game is about n^{4/3}, the proof of the upper bound suggests the following relaxation: instead of colouring online, the random graph is generated in only two rounds, and the Player colours the edges of the first round before the edges of the second round are thrown in. Given the size of the first round, how many edges can there be in the second round for the Player to be likely to win? In the extreme case, when the first round consists of a random graph with cn^{3/2} edges, where c is a positive constant, we show that the Player can win with high probability only if constantly many edges are generated in the second round.

1. Introduction

In this paper, we study Ramsey one-person triangle avoidance games against a random graph. In all versions of our game, the goal of the player, called throughout the Painter, is to colour randomly generated edges, using a given number of colours, without creating a monochromatic triangle. The object of this paper is to study how long the Painter can ‘survive’, that is, stay in the game. We distinguish three versions of the game: online, two-round, and offline.

1.1. The three games. Let us discuss the variants of our game separately.

Date: Copy produced on August 9, 2002. 1991 Mathematics Subject Classification. 05C80, 91A43, Secondary: 05C55, 91A60. Key words and phrases. Random graphs, Ramsey games, thresholds. The second author was partially supported by MCT/CNPq through ProNEx

Programme (Proc. CNPq 664107/1997–4) and by CNPq (Proc. 300334/93–1 and 468516/2000–0). The third author was partially supported by NSF Grant 0071261. The fourth author was supported by KBN grant 2 PO3A 015 23. The collaboration between the second and third authors is supported by a CNPq/NSF cooperative grant. The last author was partially supported by the NSF grant DMS-0100298.

1.1.1. The online game. In the online version of our game, the Painter receives a random sequence of edges, and she has to colour each edge as it comes, avoiding monochromatic triangles as long as possible.

It turns out that, when the number of colours available to the Painter is r = 2, this game is quite easy to analyse; indeed, a fairly simple ‘local’ argument shows that this game typically lasts for Θ(n^{4/3}) steps.

We observe that the length of the game is not so sharply determined. When the Painter has seen only o(n^{4/3}) edges, she is essentially certain to be safe; she is most unlikely to survive up to ωn^{4/3} edges, for any ω with ω = ω(n) → ∞ as n → ∞; but, for any c > 0, she has probability bounded away from 0 and 1 of surviving up to cn^{4/3} edges.

1.1.2. The two-round game. What happens if the Painter has a mercy period? That is, suppose she is allowed not to colour the first, say, N_{0} edges online, but may wait to see all of them before committing herself to the colour of those edges. Clearly, she should be able to survive longer, because her initial colouring can be cleverer. Moreover, instead of switching back to the online version after the mercy period of N_{0} edges, let us suppose that another N_{1} random edges are now presented to the Painter. If she is able to extend her initial colouring of the N_{0} edges to the union of the N_{0} and the N_{1} edges still avoiding monochromatic triangles, she wins; otherwise, she loses. This is the two-round version of our game.

We shall analyse the two-round game with N_{0} = cn^{3/2}, for c a small positive constant. (We shall see in a moment why this is the interesting choice for N_{0}.) The result here is that, with such a value of N_{0}, if the Painter has r = 2 colours available, then typically she can win only if N_{1} = O(1): for any N_{1} = N_{1}(n) that tends to infinity, the probability that the Painter wins tends to 0.

We shall also show that, if N_{0} = cn^{3/2} and r = 3 colours are available, then the breakpoint for N_{1} is of order n: if N_{1} = o(n), then the Painter typically wins; if N_{1} = ωn, where ω = ω(n) tends to infinity, then the Painter typically loses. If N_{1} = Θ(n), then she wins with probability bounded away from 0 and 1. Note that, as in the online game, the transition is not sharp.

1.1.3. The offline game. In the offline game, an n-vertex graph G(n, N) with a fixed number of edges N = N(n) is generated uniformly at random and is presented to the Painter; her task is to colour the edges of G(n, N) avoiding monochromatic triangles.

The reader familiar with the theory of random graphs will immediately see that the analysis of this game amounts exactly to determining the threshold for the Ramsey property R_{r}, which consists of all graphs such that every r-colouring of their edges results in a monochromatic triangle.

The threshold for the property R_{r} has been investigated for some time now. In particular, it has been proved that there exist constants c_{r} and C_{r} such that

lim_{n→∞} ℙ[G(n, N) ∈ R_{r}] = \begin{cases}1 & if N > C_{r}n^{3/2} \\ 0 & if N < c_{r}n^{3/2}. \end{cases}  (1)

The above threshold of n^{3/2} was verified for r = 2 in [17] (see also [8]), and then proved for arbitrary r ≥ 2 in [18]. It is interesting to note that the dependence on r is not present in the exponent of n, but only in the constants.

Returning to the case r = 2, the current proofs leave a wide gap between c_{2} and C_{2}. Using a criterion from [10] for the existence of sharp thresholds, that gap was recently annihilated in [9]. In the usual parlance, the Ramsey property R_{2} admits a sharp threshold. We shall come back to this in Section 2. Note that the existence of a sharp threshold for R_{2} means that the offline game for r = 2 colours has a sharply determined value, unlike the online and the two-round games.

1.1.4. Further remarks. It is the result in (1) that suggests the investigation of the two-round game with N_{0} of order n^{3/2}. Note that the game would be trivial if N_{0} > C_{r}n^{3/2}, for in that case the chances of the Painter surviving even the first round are rather slim. On the other hand, if r = 2 and N_{0} = cn^{3/2} with c < c_{r}, then it first seems that the Painter should be happy, because she has a very good chance of being able to colour the edges of the first round. However, our result (Theorem 6 below) shows that, at least for r = 2, her happiness is short-lived: regardless of how small c is, the fact that she has to colour those N_{0} edges before seeing the final graph makes it very unlikely that she will succeed in colouring even as few as, say, N_{1} = log log log n further edges! This is in contrast to the fact that, if N_{0} + N_{1} < c_{r}n^{3/2}, then, typically, G(n, N_{0} + N_{1}) may be 2-edge-coloured avoiding monochromatic triangles (see (1)).

We mention in passing that, in Section 2, we shall attempt to explain how the two-round version of our game naturally arose from a technical part of the proof of the existence of a sharp threshold for R_{2}.

Interestingly enough, both the two-round and online versions of our Ramsey game are much more sensitive to the number of colours available to the Painter than the offline one is. Recall that, for example, in the two-round game, while for r = 2 colours the survival time is O(1), for r = 3 colours the survival time is of order n. For the online, 3-colour game, we have a lower bound of roughly n^{7/5} for its length, which is much larger than for two colours. At this point, we do not have a matching upper bound for the 3-colour game.

1.2. Organization. This paper is organized as follows. In Section 2 we briefly discuss the proof of the existence of a sharp threshold for the property R_{2}, and its relation to this paper. In Section 3, we state and prove our results on Ramsey games. As it turns out, most of the work will go into proving a certain delicate lemma (Lemma 4); Section 4 will be entirely devoted to proving this lemma. In Section 6, we briefly discuss some open problems.

1.3. Notation and terminology. Our notation is fairly standard. We let [n] = {1, …, n}. We write [X]^{k} for the family of k-element subsets of X. Let G = (V (G), E(G)) be a graph. If x is a vertex of G, then N_{G}(x) = N(G; x) denotes the neighbourhood of x in G. We write deg_{G}(x) = |N_{G}(x)| and Δ(G) = max{deg_{G}(x): x ∈ V (G)}. If U ⊆ V (G), we write G[U] for the subgraph of G induced by U. Thus, E(G[U]) = E(G) ∩ [U]^{2}. We put e_{G}(U) for |E(G[U])|, the number of edges induced by U in G, and N_{G}(U) = ⋃_{x∈U} N_{G}(x).

If U, W ⊆ V (G) are disjoint, then G[U, W] stands for the bipartite graph with vertex classes U and W naturally induced by U and W in G. We write E_{G}(U, W) for the set of edges of G with one endvertex in U and the other in W. That is E_{G}(U, W) = E(G[U, W]). We let e_{G}(U, W) = |E_{G}(U, W)|. We sometimes identify a graph with its edge set.

We define, for a graph F, the base graph Base(F) on the vertex set V (F) as follows: a pair e of vertices of F is an edge of Base(F) if it forms a triangle with two edges of F. A colouring of the edges of a graph will be called proper if it does not contain a monochromatic triangle.

We shall consider the three standard models for random graphs: the binomial random graphs G(n, p), the uniform random graphs G(n, N), and the random graph process G_{0} ⊆ ⋯ ⊆ G\binom{n}{2}, which naturally corresponds to random permutations e_{1}, …, e\binom{n}{2} of the edges of the complete graph on [n]. In particular, if we stop a random graph process at time t, we obtain a random graph in the uniform model G(n, t). When convenient, we switch between these models without discussion. A rule of thumb is that most results can be “translated” back and forth between the binomial and uniform models, provided N ∼ p\binom{n}{2}. For more on the (asymptotic) equivalence of these models and on random graphs in general, we refer the reader to [6] and [12]. Another feature we will use is the monotonicity. If a graph property Q is increasing (preserved under edge addition), and p_{1} ≤ p_{2}, then ℙ(G(n, p_{1}) ∈ Q) ≤ ℙ(G(n, p_{2}) ∈ Q).

Most of the time, we have a parameter n and we are interested in the case in which n → ∞. As usual, we use the term ‘asymptotically almost surely’ (a.a.s.) to mean ‘with probability tending to 1 as n → ∞’. Therefore, we often tacitly assume that n is large enough (for instance, for some inequalities to hold). Also, we drop the ⌊ ⌋ and ⌈ ⌉ from our formulae when they are not important. This will simplify the exposition considerably.

Our logarithms are natural logarithms.

Acknowledgements. We thank Svante Janson for his interest and suggestions. Part of this work was done when some of the authors were at the meeting Combinatorics, Probability, and Computing, at the Mathematisches Forschungsinstitut Oberwolfach.

2. Sharp thresholds

The questions considered in this paper arose naturally during the work on [9], which studies the notion of sharp threshold for the property R_{2}. We briefly outline the ideas that arise in that paper in order to explain the background to the present work. However, the remainder of this paper does not depend on this section.

Recall that R_{2} consists of all graphs such that every 2-colouring of their edges results in a monochromatic triangle. Below, we refer to the graphs in R_{2} as Ramsey graphs. The main result in [9] is the following theorem, asserting that property R_{2} admits a sharp threshold.

Theorem 1. There exists a function b = b(n) = Θ(1) such that for all ε > 0 we have

lim_{n→∞} ℙ[G(n, p) ∈ R_{2}] = \begin{cases}1 & if p > (1 + ε)b(n)/\sqrt{n} \\ 0 & if p < (1 − ε)b(n)/\sqrt{n}. \end{cases}

The proof of Theorem 1 is based on a consequence of Friedgut’s criterion from [10], which we now discuss. Let M be an arbitrary, fixed balanced graph with average degree 4, and let M^{∗} be a random copy of M in K_{n}. It follows from [10] that, in order for R_{2} to have a sharp threshold, it is sufficient to prove the following:

(*) For any choice of the constants c, C, α, and ξ > 0, and for any M as above, there is a graph property G such that

(a) if p = p(n) satisfies c/\sqrt{n} ≤ p ≤ C/\sqrt{n}, then G(n, p) ∈ G a.a.s., and, moreover, such that, for all n-vertex graphs G ∈ G with sufficiently large n,

(b) if ℙ[G ∪ M^{∗} ∈ R_{2}] > α, then

ℙ[G ∪ G(n, ξp) ∈ R_{2}] → 1 as n → ∞.

Note that, roughly speaking, the implication in (b) means that every G ∈ G is such that, if G may be turned with positive probability into a Ramsey graph by adding a random copy of M, then G turns a.a.s. into a Ramsey graph when (1 + o(1))ξp\binom{n}{2} edges are sprinkled randomly.

We recall that M is a small graph, and hence the addition of M^{∗} to G is a ‘local’ change, whereas adding G(n, ξp\binom{n}{2}) is ‘global’. Moreover, observe that (b) is non-trivial only when G ∉ R_{2}. Also, because of our conditions on M, it can be proved that M ∉ R_{2} (see [9, 16]).

Let us now say a few words about the verification of Friedgut’s condition (*). One takes for G a certain well-defined pseudorandom property of graphs with n vertices and (1 + o(1))p\binom{n}{2} edges (see [9, Definition 6.1]) and one assumes that the assumption in implication (b) holds. As observed above, one may assume that G ∉ R_{2} and we have M ∉ R_{2}. A fairly complicated and lengthy argument, involving a tailor-cut regularity lemma (see [9]), leads to the conclusion that, for some λ > 0, there exists a ‘small’ family K of ‘large’ subgraphs of G such that there is always a monochromatic copy of a member of K in every proper colouring of the edges of G. More precisely, the family K is such that

(i) |K| = 2^{o(n^{3/2})}, (ii) for all K ∈ K, we have |E(K)| > λ|E(G)|,

and, most importantly,

(iii) for every proper 2-colouring of the edges of G, there is a K ∈ K that is monochromatic.

Now we observe that, in order to prove the conclusion of (b), it is enough to find, for every K ∈ K, a triangle T = T (K) ⊆ G(n, ξp), such that T ⊆ Base(K), i.e., a triangle T such that each of the edges of T forms a triangle together with a path of length two in K. (Indeed, in this case, if K is monochromatic, there is no way to extend the colouring of G to a proper colouring of G ∪ G(n, ξp).)

To establish the existence of T = T (K) above, we first define the following property of a graph G:

(†) Given two real numbers 0 < λ < 1 and 0 < a < 1/6, we say that G has property T (λ, a) if, for any subgraph F of G with at least λ|E(G)| edges, the graph Base(F) contains at least a|V (G)|^{3} triangles.

Since the K ∈ K has at least λ|E(G)| edges (it satisfies (ii) above), if T (λ, a) holds for G ∈ G, then we may conclude that every K ∈ K is such that Base(K) contains at least a|V (G)|^{3} triangles. As it turns out (see the following lemma), we may define G such that (a) holds and T (λ, a) holds for every G ∈ G.

Lemma 2. For any c > 0 and λ > 0, there exists a > 0 such that if p ≥ c/\sqrt{n} then a.a.s. the random graph G(n, p) has property T (λ, a).

Lemma 2 allows us to require that T (λ, a) should hold for all G ∈ G. Now we are ready to establish the existence of T = T (K) for all K ∈ K.

Indeed, for any fixed K ∈ K, the fact that Base(K) contains at least a|V (G)|^{3} triangles implies, via Janson’s inequality [11], that, with probability 1 − 2^{−Θ(n^{3/2})}, there is a triangle T (K) in Base(K) ∩ G(n, ξp). Since (i) holds, we have that a suitable triangle T = T (K) does exist a.a.s. for every K ∈ K. The conclusion of (b) now follows from (iii).

To summarize, the convergence

ℙ[G ∪ G(n, ξp) ∈ R_{2}] → 1

follows indirectly from a statement about the two-round Ramsey game against a random graph: the proof involves extending proper colourings of graphs of size Θ(n^{3/2}). This explains why Lemma 2 and a related result, Lemma 4 given below, are useful tools in studying such games.

3. Ramsey triangle avoidance games

This section contains our main results. In Section 3.1 below, we prove a relatively simple result for the online version of the Ramsey game. In Section 3.2, we state two results on the two-round game, together with their proofs, pending a major technical lemma, Lemma 4, which will be proved in Section 4.

3.1. The online game. Consider the random graph process

e_{1}, …, e\binom{n}{2}

on n vertices (see Section 1.3), revealing its edges one by one, and the following one-person game related to it. The Painter’s task is to 2-colour the edges online, with colours red and blue, say, and not to create a monochromatic triangle for as long as she can. Here online means that the Painter has to decide on the colour of e_{i} before e_{i+1} is generated. The game is over when a monochromatic triangle is created (this does happen eventually if n ≥ 6). For how long can she stay in the game with probability approaching 1 as n → ∞?

More formally, for each strategy π of the Painter, let X_{π} be the length of the game, i.e., X_{π} is the largest index N such that e_{1}, …, e_{N} contains no monochromatic triangle. The goal of the game is to choose a strategy that maximizes the expectation 𝔼(X_{π}). By a strategy we mean a complete set of rules assigning a colour to the next edge.

Since e_{1}, …, e_{N} is exactly the random graph G(n, N), clearly, by (1), an upper bound on the expected duration of the game is C_{2}n^{3/2}. We shall soon show that the threshold for the length of the online game is in fact much smaller.

A crucial tool in our investigation is the base graph Base(F) of a graph F. Recall that a pair e of vertices of F is an edge in Base(F) if it forms a triangle with two edges of F. Now consider an online 2-colouring of the edges e_{1}, …, e\binom{n}{2}. Let R_{i} and B_{i} be the sets of the edges e_{j} (j ≤ i) coloured so far with colours red and blue, respectively. The Painter is stuck if and only if

e_{i+1} ∈ Base(R_{i}) ∩ Base(B_{i}).

Similarly, the game is bound to be over by time j if for some i < j, the intersection of the set of edges {e_{i+1}, …, e_{j}} with Base(R_{i}) (or with Base(B_{i})) contains a triangle.

Let us begin with a trivial lower bound. As long as N = o(n^{6/5}), there is a.a.s. no copy of a diamond in e_{1}, …, e_{N}, that is, a K_{4} with an edge omitted, and the Painter never gets stuck until the Nth edge, since a.a.s.

e_{i+1} ∉ Base(R_{i}) ∩ Base(B_{i})

for each i < N.

But she can do better: as long as N = o(n^{4/3}) a.a.s. neither a copy of K_{4} nor a copy of the pyramid graph (see Figure 1) has emerged, and so Base(G(n, N)) does not contain a triangle. Hence the greedy strategy π_{0} of colouring each edge red, unless such a move would create a red K_{3}, is successful. Indeed, Base(R_{N}), which is a subgraph of Base(G(n, N)), is triangle-free, and no blue triangle will be created. We have just proved that a.a.s. X_{π_{0}} > n^{4/3}/ω for any ω = ω(n) with ω → ∞.

Figure 1. The pyramid, the enhanced pyramid, and the double pyramid

Quite surprisingly, n^{4/3} is the right threshold for the length of the random online triangle avoidance game.

Theorem 3. For every ω with ω = ω(n) → ∞ as n → ∞ and for every strategy π of the Painter, a.a.s. X_{π} < ωn^{4/3}.

Proof. We relax the online regime by allowing a mercy period of N_{0} = n^{4/3} steps; i.e., only after that many edges are generated, do they have to be coloured by the Painter. We shall argue that no matter how they are coloured, the Painter loses a.a.s. after another (ω − 1)n^{4/3} edges. This is nothing else but a two-round exposure technique (see [12]), with a colouring in between.

The aim is to show that a.a.s. every subgraph of G(n, N_{0}) with at least half of the edges (the majority colour) has at least Ω(n^{2}) triangles in its base. Then, by the second moment method, any ωn^{4/3} additional random edges will a.a.s. contain at least one of these triangles and the game will be over.

A.a.s. the number of copies of K_{2,3} in G(n, N_{0}), denoted by X(K_{2,3}), is smaller than, say, n log n. Let R be the majority colour in G(n, N_{0}) and let d_{1}, …, d_{n} be the degree sequence in R. Then the number of triangles in the base of R is at least

∑_{i=1}^{n} \binom{d_{i}}{3} − X(K_{2,3}) ≥ n\binom{N_{0}/n}{3} − X(K_{2,3}) = Ω(n^{2}),

where the last equation holds a.a.s. □

The reader will have no difficulty in verifying that the proofs above show that, for any c > 0, the Painter has probability bounded away from 0 and 1 of surviving up to cn^{4/3} edges.

With three colours at hand the Painter can survive quite a bit longer. The painter may use the natural greedy strategy, say π_{1}, which colours an edge red if possible, otherwise blue if possible, and finally yellow if none of red and blue will do. Using π_{1}, the painter gets stuck only if a copy of the double pyramid, or of the enhanced pyramid (see Figure 1), or of K_{5} with an edge omitted has emerged. Since such subgraphs a.a.s. do not appear in the random graph with o(n^{7/5}) edges, we obtain that ℙ(X_{π_{1}} > n^{7/5}/ω) → 1. However, we do not know whether this is the right threshold.

3.2. The two-round game. The proof of Theorem 3 bridges the online and the two-round game, which we now define formally. Given two integers N_{0} and N_{1}, first, N_{0} edges are generated randomly (let G_{0} = G(n, N_{0}) be the graph defined by these edges), and the Painter colours them properly with r colours (if possible), that is, avoiding monochromatic triangles. Then a second round of N_{1} random edges (graph G_{1}) is thrown in and the Painter wins if her colouring of G_{0} has an extension to a proper colouring of G_{0} ∪G_{1} (if G_{0} cannot be properly coloured, the Painter already lost at that stage).

For a given strategy π of the Painter, let P_{π}(r, N_{0}, N_{1}) be the probability that the Painter wins the game when using π. Here, by a strategy, we mean an assignment of an r-edge-colouring to every graph with N_{0} edges. Thus, the goal of the Painter is to find a strategy π that maximizes P_{π}(r, N_{0}, N_{1}). Let

P^{∗}(r, N_{0}, N_{1}) = max_{π} P_{π}(r, N_{0}, N_{1}).

The above proof of Theorem 3 gives that P^{∗}(2, n^{4/3}, ωn^{4/3}) = o(1), because the base of the majority colour in G_{0} = G(n, n^{4/3}) contains Θ(n^{2}) triangles. This simple argument may be extended to a wider range of N_{0} (for r = 2), namely,

n^{7/6} ≤ N_{0} ≤ cn^{3/2},

where here and below c is always assumed to be so small that

ℙ(G(n, cn^{3/2}) ∈ R_{2}) = o(1).

Indeed, along similar lines, one may easily prove that there are Θ(N_{0}^{3}/n^{2}) triangles in the base graph of the majority colour of G_{0} = G(n, N_{0}), and consequently, arguing as in the proof of Theorem 3, we have

P^{∗}(2, N_{0}, ωn^{8/3}/N_{0}) = o(1).

In particular, in the most extreme case, we obtain that the number of triangles in the base graph of the majority colour of G_{0} = G(n, cn^{3/2}) is Θ(n^{5/2}), and thus P^{∗}(2, cn^{3/2}, ωn^{7/6}) = o(1).

Using Lemma 2 with λ = 1/2 and with F consisting of the edges coloured by the majority colour, we can improve the above and conclude that in fact a.a.s., for any 2-edge-colouring of G(n, cn^{3/2}), the number of triangles in the base graph of the majority colour is of maximal possible order Θ(n^{3}). By the second moment method this yields that

P^{∗}(2, cn^{3/2}, ωn) = o(1)

(a triangle is needed in the base of one colour). To improve this any further we need to find a stronger tool.

As we have just seen, Lemma 2, put in the colouring context, says that the base of the majority colour is rich in triangles. A powerful extension of that result, Lemma 4 below, which is the main technical result of this paper, implies that the same is true for the intersection of the bases of two colours, provided the colouring is proper. This result not only settles the two-round game for r = 2, but also for r = 3, the other interesting case.

Lemma 4. For all c > 0, there are constants α and β > 0 such that with p = c/\sqrt{n} the random graph G = G(n, p) a.a.s. satisfies the following property. For every proper 3-colouring E(G) = R ∪ B ∪ Y of the edges of G, there are two colours, say R and B, such that, letting

I = Base(R) ∩ Base(B),  (2)

we have

(i) |E(I)| ≥ αn^{2} and, in fact,

(ii) the graph I contains at least βn^{3} triangles.

Remark 5. Note that Lemma 2 is not a special case of the seemingly stronger Lemma 4. In Lemma 2 the parameter λ may be arbitrarily small, while in Lemma 4 the assumption that the colouring must be proper sets an implicit lower bound on the size of the second largest colour (see (42)). In particular, it seems that Lemma 4 cannot replace Lemma 2 in the proof of Theorem 1 in [9].

Nevertheless, the proof of Lemma 4, besides some new ideas, uses the ideas from the proof of Lemma 2. The relation between the proofs of Lemmas 2 and 4 is briefly discussed in Section 4.2.

Taking Lemma 4 for granted, we are ready to state and prove our results for the two-round game.

Theorem 6. For any ω with ω = ω(n) → ∞ as n → ∞, we have

P^{∗}(2, cn^{3/2}, ω) = o(1).

Proof. This follows immediately from Lemma 4(i) (with Y = ∅), since a.a.s. at least one of the ω new edges will fall into I. □

Finally, let us consider the two-round game for r > 2 and N_{0} = cn^{3/2}. If r ≥ 4, then a trivial conservative strategy is to use only two colours for G_{0} and then another two colours for G_{1}. This, together with the threshold result from [18] settles the game at Θ(n^{3/2}), i.e., there exist constants b and B > 0 for which we have

lim_{n→∞} P^{∗}(r, cn^{3/2}, N_{1}) = \begin{cases}1 & if N_{1} < bn^{3/2} \\ 0 & if N_{1} > Bn^{3/2}. \end{cases}

In the remaining case r = 3, we have the following, complete solution.

Theorem 7. We have

lim_{n→∞} P^{∗}(3, cn^{3/2}, N_{1}) = \begin{cases}1 & if N_{1} ≪ n \\ 0 & if N_{1} ≫ n. \end{cases}

Proof. The ‘1-statement’, that is, the fact that P^{∗}(3, cn^{3/2}, N_{1}) → 1 as n → ∞, follows by using only two colours for G_{0}, and then exclusively the third colour for G_{1}. As long as N_{1} = o(n), a.a.s. there will not be any triangles in G_{1}. The 0-statement follows from the second moment method and Lemma 4(ii). □

We remark that the proof above shows that P^{∗}(3, cn^{3/2}, c′n) is bounded away from 0 and 1 for any c′ > 0.

4. Pairs at distance two in red and blue

Our aim in this section is to prove Lemma 4. On the way we shall come close to proving Lemma 2 (see Section 4.2). However, we refer the reader to [9] for the complete proof of Lemma 2.

Let us introduce a piece of terminology. Let ϱ and d be positive reals. We say that a graph H is (ϱ, τ)-dense if, for all U ⊆ V (H) with |U| ≥ ϱ|V (H)|, we have

e_{H}(U) ≥ τ\binom{|U|}{2}.

We now state a strengthening of Lemma 4, which, together with an easy property of (ϱ, τ)-dense graphs, implies Lemma 4.

Lemma 8. For all c > 0, there is a constant τ > 0 such that, for any ϱ > 0, there is a constant σ > 0 such that for p = c/\sqrt{n} the random graph G = G(n, p) a.a.s. satisfies the following property. For every proper 3-colouring E(G) = R ∪ B ∪ Y of the edges of G, there are two colours, say R and B, for which, letting

I = Base(R) ∩ Base(B),

there exists a set U ⊆ V (G) such that (i) |U| ≥ σn and (ii) I[U] is (ϱ, τ)-dense.

Graphs that are (ϱ, τ)-dense for small ϱ are ‘rich in small subgraphs’; in particular, the following result holds [19].

Lemma 9. For all τ > 0 there exist ϱ, n_{0}, and c_{0} > 0 such that every (ϱ, τ)-dense graph on n ≥ n_{0} vertices contains at least c_{0}n^{3} triangles.

With Lemmas 8 and 9 at hand, it is easy to prove Lemma 4.

Proof of Lemma 4. Given c > 0, Lemma 8 gives us a constant τ > 0. By Lemma 9 we obtain constants ϱ, n_{0}, and c_{0} > 0 such that any u-vertex (ϱ, τ)-dense graph with u ≥ n_{0} contains at least c_{0}u^{3} triangles. We now feed this constant ϱ > 0 to Lemma 8, to get a constant σ > 0.

We claim that the choice of

α = \frac{1}{3}τσ^{2}  (3)

and

β = c_{0}σ^{3},  (4)

will do in Lemma 4.

To prove our claim, suppose we have a proper 3-colouring of the edges of G = G(n, p). By Lemma 8, a.a.s. there are two colours, say R and B, and a set U ⊆ V (G), |U| ≥ σn, for which I[U] = (Base(R) ∩ Base(B))[U] is (ϱ, τ)-dense. Then

|E(I)| ≥ |E(I[U])| ≥ τ\binom{|U|}{2} ≥ \frac{1}{3}τ|U|^{2} ≥ (\frac{1}{3}τσ^{2}) n^{2} = αn^{2}.

Moreover, by the choice of ϱ > 0 and c_{0}, we deduce from Lemma 9 that the number of triangles in the (ϱ, τ)-dense graph I[U] is at least

c_{0}|U|^{3} ≥ c_{0}σ^{3}n^{3} = βn^{3}.

Lemma 4 is proved. □

Let us now briefly comment on the organization of this section. The proof of Lemma 8 fills the remainder of this section, and will require considerable work. This proof is based on some technical, auxiliary results presented in Section 4.1 and proved in Section 5. The actual proof of Lemma 8 is given in Section 4.2.

4.1. Towards the proof of Lemma 8. In this section, we state three lemmas and prove two claims that will be crucial in the proof of Lemma 8.

Throughout this section, we assume that

p = \frac{c}{\sqrt{n}},

where 0 < c ≤ 1/5 is an arbitrary constant that we fix once and for all. We also define once and for all the constants

σ_{0} = (1/200)c^{2},  λ_{0} = (1/30)c^{2}  and  τ_{0} = \frac{1}{800}λ_{0}^{2}c^{2}σ_{0}. (5)

Let H be a graph. A pair of disjoint sets U, V ⊆ V (H) will be called (p, λ; H, ε)-lower semi-regular, or (p, λ; H, ε)-semi-regular for short, if, for all U′ ⊆ U, V′ ⊆ V, with |U′| ≥ ε|U| and |V′| ≥ ε|V |, we have

\frac{e_{H}(U′, V′)}{p|U′||V′|} ≥ λ.

Note that if (U, V) is (p, λ; H, ε)-semi-regular then

e_{H}(U, V) ≥ λp|U||V |.  (6)

Note also that then (U, V) is (p, λ; H, ε′)-semi-regular for any ε′ ≥ ε, and (U^{∗}, V) is (p, λ; H, ε/ϱ)-semi-regular for any U^{∗} ⊆ U with |U^{∗}| ≥ ϱ|U|.

Our first auxiliary lemma, Lemma 10, concerns the existence of a certain substructure in a properly edge-coloured G(n, p). A tripartite graph J on vertex sets Z, U, and W with no edge between Z and W will be called an amalgam (of two bipartite graphs). The amalgam guaranteed by Lemma 10 in a properly edge-coloured G(n, p) satisfies certain properties with respect to its size, colouring and structure (see Figure 2).

Z W  |W | = σ^{0}n |Z| = σ_{0}n |U| ≥ σn (p, λ_{0}; J, ε)-semi-regular (p, λ_{0}; J, ε)-semi-regular U  J_{0} ⊆ R J_{1} ⊆ B

Figure 2. The amalgam given by Lemma 10

Lemma 10. For all ε > 0, there is σ > 0 for which the following assertion holds a.a.s. for G = G(n, p). Suppose

E(G) = R ∪ B ∪ Y  (7)

is a proper colouring of the edges of G. Then there exist two colours, say R and B, and a subgraph J of G which is an amalgam with vertex sets Z, U, and W, as follows:

(i) |Z| = |W | = σ_{0}n and |U| ≥ σn,

(ii) we have E_{J}(Z, U) ⊆ R and E_{J}(U, W) ⊆ B, (iii) the pairs (Z, U) and (U, W) are (p, λ_{0}; J, ε)-semi-regular.

Basically, our second lemma concerns the base of the subgraph J_{0} = J[Z, U] of an amalgam J as in Lemma 10 (as well as, by symmetry, the base of J_{1} = J[U, W]).

Lemma 11. For all ϱ > 0, there is ε > 0 such that a.a.s. G = G(n, p) satisfies the following property. For all bipartite subgraphs J_{0} of G with bipartition (Z, U) and such that

(i) z = |Z| = σ_{0}n and u = |U| ≥ n/ log n, and (ii) (Z, U) is (p, λ_{0}; J_{0}, ε)-semi-regular,

the graph Base(J_{0})[U] is (ϱ, τ_{0})-dense.

Lemma 11 follows immediately from the next claim. Let J_{0}^{∗} be a bipartite graph with bipartition (Z, U^{∗}). Recall that we have the constants σ_{0}, λ_{0} and τ_{0}, defined in (5). Given ε′ > 0, we shall say that J_{0}^{∗} is ε′-rare if (i^{∗}) z = |Z| = σ_{0}n and u^{∗} = |U^{∗}| ≥ n/ log n, (ii^{∗}) (Z, U^{∗}) is (p, λ_{0}; J_{0}^{∗}, ε′)-semi-regular, and (iii^{∗}) | Base(J_{0}^{∗})[U^{∗}]| < τ_{0}\binom{u^{∗}}{2}.

Claim 12. If ε′ > 0 is small enough, then a.a.s. G = G(n, p) contains no ε′-rare bipartite subgraph.

To deduce Lemma 11 from Claim 12 take ε = ε′ϱ. In turn, Claim 12 follows easily from a special case of Lemma 14 below.

Proof of Claim 12. Put F = K_{u^{∗}}, τ′ = 1, and α = λ_{0}/2e into Lemma 14 obtaining the desired value of ε′. We will apply the first moment method. By Lemma 14, the expected number of ε′-rare bipartite subgraphs of G(n, p) is at most

∑_{u^{∗}} ∑_{T} \binom{n}{u^{∗}}α^{T} \binom{u^{∗}z}{T}p^{T} ≤ ∑_{u^{∗}} ∑_{T} n^{u^{∗}} (\frac{αe}{λ_{0}})^{T}

< n^{n}2^{−Ω(n^{3/2}/(log n)^{2})} = o(1).

The summation above extends over all integers n/(log n)^{2} ≤ u^{∗} ≤ n and λ_{0}pzu^{∗} ≤ T ≤ \binom{n}{2}. Note that λ_{0}pzu^{∗} ≥ λ_{0}σ_{0}cn^{3/2}/(log n)^{2}. □

As an immediate consequence of Lemmas 10 and 11 we conclude that for all ϱ > 0 there exists σ > 0 such that a.a.s. G = G(n, p) contains an amalgam J that satisfies (i)–(iii) of Lemma 10 and such that Base(J_{0})[U] is (ϱ, τ_{0})-dense. Suppose that I[U] = (Base(R) ∩ Base(B))[U] is not (ϱ, τ)- dense for some τ. Then, because

I[U] = (Base(R) ∩ Base(B))[U] ⊇ (Base(J_{0}) ∩ Base(J_{1}))[U],

the graph (Base(J_{0}) ∩ Base(J_{1}))[U] is not (ϱ, τ)-dense either. This means that there exists a set U^{∗} ⊆ U, with u^{∗} = |U^{∗}| ≥ ϱ|U|, such that

|(Base(J_{0}) ∩ Base(J_{1}))[U^{∗}]| < τ\binom{u^{∗}}{2}.

The subset U^{∗} generates a subamalgam H of J, which, as our next result shows, is very unlikely to appear in G(n, p).

Now come the details. Let Z, U^{∗}, and W be three pairwise disjoint sets of vertices. Given ε′ and n, let us call an amalgam H with tripartition (Z, U^{∗}, W) ε′-rare if

(i) we have

|Z| = |W | = σ_{0}n,  (8)
u^{∗} = |U^{∗}| ≥ n/(log n)^{2},  (9)
Δ(H) ≤ 2c\sqrt{n},  (10)

(ii) the pairs (Z, U^{∗}) and (U^{∗}, W) are (p, λ_{0}; H, ε′)-semi-regular, (iii) letting H_{0} = H[Z, U^{∗}] and H_{1} = H[U^{∗}, W],

| Base(H_{0})[U^{∗}]| ≥ τ_{0}\binom{|U^{∗}|}{2},

and (iv) we have

|(Base(H_{0}) ∩ Base(H_{1}))[U^{∗}]| < τ_{0}^{3}\binom{|U^{∗}|}{2}.  (11)

Note the symmetry of the roles of H_{0} and H_{1} in the above definition. We will make use of it later in the proof.

Claim 13. If ε′ > 0 is small enough, then a.a.s. G = G(n, p) contains no ε′-rare amalgam.

Claim 13 follows from Lemma 14, a delicate result indicating that some bipartite graphs are rare. In order to state Lemma 14, we need to introduce more definitions and notation.

Let U^{∗} and W be two disjoint sets of vertices. Suppose F ⊆ [U^{∗}]^{2} is a graph with vertex set U^{∗}. Suppose now that we have a constant ε′ > 0 and integers n and T. Suppose further that w = |W | = σ_{0}n, u^{∗} = |U^{∗}| ≥ n/(log n)^{2}, and |F | = τ′\binom{u^{∗}}{2}. We call a bipartite graph H with bipartition (U^{∗}, W) (F, ε′)-rare if

(i) |E| = T and Δ(H) ≤ 2c\sqrt{n}, (ii) (U^{∗}, W) is (p, λ_{0}; H, ε′)-semi-regular, and (iii) we have

|F ∩ Base(H)[U^{∗}]| < τ_{0}τ′|F |.  (12)

Finally, let

B_{1} = B_{1}(U^{∗}, W; F; τ′, ε′; n, T)  (13)

be the family of all (F, ε′)-rare, bipartite graphs H. We are now ready to state our third auxiliary lemma, the formulation of which is based on the notation and definitions introduced above.

Lemma 14. Let any constants τ′ > 0 and 0 < α ≤ 1 be given. Then there exist constants ε′ > 0 and n_{0} such that, with the notation as above, for all n ≥ n_{0}, all F as above, and all 0 ≤ T ≤ u^{∗}w, we have

|B_{1}(U^{∗}, W; F; τ′, ε′; n, T)| ≤ α^{T} \binom{u^{∗}w}{T}.

Lemma 14 is a statement concerning the uniform space of the bipartite graphs with vertex classes U^{∗} and W, and T edges. Indeed, this lemma asserts that a random element of this space is extremely unlikely to be a member of the family B_{1} defined in (13), as the probability that this happens can be made subexponentially small.

The proof of Lemma 14 is postponed to Section 5.3.

Proof of Claim 13. We first show that, for a suitable ε′, ε′-rare amalgams really are rare among all amalgams of that size. We feed τ′ = τ_{0} and

α = \frac{1}{2} (\frac{λ_{0}}{e} )^{2}  (14)

into Lemma 14, and obtain a constant ε′ > 0. Let

B_{2} = B_{2}(Z, U^{∗}, W; ε′; n, T, T′)  (15)

be the family of ε′-rare amalgams H on Z ∪ U^{∗} ∪ W, with T edges with endpoints in W and T′ edges with endpoints in Z.

Fact 15. For all T and T′, we have

|B_{2}(Z, U^{∗}, W; ε′; n, T, T′)| ≤ α^{T} \binom{zu^{∗}}{T′}\binom{wu^{∗}}{T}.  (16)

Proof. For any graph H ∈ B_{2}, we let H_{0} = H[Z, U^{∗}] and H_{1} = H[U^{∗}, W]. To show (15), we may count the graphs in B_{2} by estimating the number of H_{0} crudely by

\binom{zu^{∗}}{T′},  (17)

and, for each fixed H_{0}, estimating the number of H_{1} that we may ‘put together with H_{0}’ to form a graph H in B_{2}.

Let us now fix a bipartite graph H_{0} with bipartition (Z, U^{∗}) satisfying conditions (i)–(iii) in the definition of ε′-rare amalgams. Moreover, let a subgraph

F ⊆ Base(H_{0})[U^{∗}]

with |F | = τ_{0}\binom{|U^{∗}|}{2} be fixed. If for some H_{1} with bipartition (U^{∗}, W) the amalgam H = H_{0} ∪ H_{1} ∈ B_{2}, then

H_{1} ∈ B_{1} = B_{1}(U^{∗}, W; F; τ′, ε′; n, T),  (18)

that is, H_{1} is (F, ε′)-rare. Indeed, conditions (i) and (ii) in the definition of B_{1} clearly hold for H_{1}. To check condition (iii), we observe that, in view of (11), we have

|F ∩ Base(H_{1})[U^{∗}]| ≤ |(Base(H_{0}) ∩ Base(H_{1}))[U^{∗}]| < τ_{0}^{3}\binom{|U^{∗}|}{2} = τ_{0}^{2}|F |.

Therefore (12) holds (with τ′ = τ_{0}), and so does condition (iii) in the definition of B_{1}. We conclude that (18) is true.

To verify (16), it now suffices to put together the bounds in (17) and in Lemma 14 (with τ′ = τ_{0}). □

We now use Fact 15 to show that the random graph G(n, p) is quite unlikely to contain ε′-rare amalgams H.

Note that if H is an ε′-rare amalgam with T + T′ edges, then,

T, T′ ≥ λ_{0}p|Z||U^{∗}| = λ_{0}p|W ||U^{∗}| = λ_{0}σ_{0}pnu^{∗},  (19)

and hence, as (9) holds, we have

T, T′ = Ω(n^{3/2}/ log n) ≫ n log n.  (20)

Without loss of generality we may assume that T ≥ T′. We are now ready to show that a.a.s. no ε′-rare amalgam occurs as a subgraph in G = G(n, p). Similar to the proof of Claim 12, we shall use the first moment method. The expected number of such subgraphs is

∑ |B_{2}(Z, U^{∗}, W; ε′; n, T, T′)| p^{T +T′},  (21)

where the sum is over all choices of Z, U^{∗}, W ⊆ V (G) and over all choices of T and T′. We use (16), (19), and (20) to estimate (21). Below, we write ∑_{u^{∗}} for the sum over n/ log n ≤ u^{∗} ≤ n and ∑_{T, T′} for the sum over T, T′ ≥ λ_{0}σ_{0}pnu^{∗} (see (19)). The quantity in (21) is at most

∑_{u^{∗}} ∑_{T, T′} \binom{n}{u^{∗}}\binom{n}{w}\binom{n}{z}α^{T} \binom{wu^{∗}}{T′}\binom{zu^{∗}}{T}p^{T′+T}

≤ ∑_{u^{∗}} ∑_{T, T′} n^{3n}α^{T} (\frac{e}{λ_{0}} )^{2T} ≤ n^{4n} ∑_{T} (\frac{1}{2})^{T}

≤ n^{4n}(n^{2})2^{−Ω(n^{3/2}/ log n)} = o(1).

Claim 13 follows by Markov’s inequality. □

4.2. Proof of Lemma 8. We shall use Lemmas 10, 11, and Claim 13 to prove Lemma 8.

Let c > 0 be given. A moment’s thought shows that the property asserted a.a.s. for G = G(n, p) is increasing, and therefore we may suppose that c ≤ 1/5 (for details concerning this argument, for instance see [12, Lemma 1.10]). We set

τ = τ_{0}^{3},  (22)

and claim that this choice for τ will do.

To prove our claim above, let an arbitrary 0 < ϱ ≤ 1 be given. We have to prove the existence of a suitable constant σ > 0. To this end, we first invoke Lemma 11 with this ϱ, to obtain a constant ε(L11) > 0. Moreover, Claim 13 gives us a constant

ε′(C13) > 0.  (23)

We now let

ε′ = min{ε(L11)/ϱ, ε′(C13)}.  (24)

and, finally, invoke Lemma 10 with ε = ε′ϱ to obtain

σ = σ(L10) > 0.  (25)

We claim that σ chosen above will do in Lemma 8. In the remainder of this proof we verify this claim.

It follows easily from the Chernoff bound that a.a.s.

Δ(G(n, p)) ≤ 2c\sqrt{n}.  (26)

Let G = G(n, p) satisfy the conclusions of Lemmas 10 and 11 and Claim 13 with the above parameters, as well as Δ(G) ≤ 2c\sqrt{n}. (Note that all these properties hold a.a.s. for G(n, p).)

Suppose that we have a colouring E(G) = R ∪ B ∪ Y with no monochromatic triangles. We shall show that G must then contain the required set U.

Since G satisfies the conclusion of Lemma 10, there is an amalgam J ⊆ G as in the statement of that lemma. We follow the notation of Lemma 10, so that, e.g., V (J) = Z ∪ U ∪ W (see Figure 2 as well).

As we have |U| ≥ σn, condition (i) in Lemma 8 holds. Hence, the proof of Lemma 8 will be finished if we show the following fact.

Fact 16. The graph I[U] is (ϱ, τ)-dense.

Proof. Our proof strategy has already been unveiled just after the proof of Claim 12. Here we give the details.

Let J_{0} = J[Z, U] and J_{1} = J[U, W]. Since G satisfies the conclusion of Lemma 11, the graph Base(J_{0})[U] is (ϱ, τ_{0})-dense.

We now claim that (Base(J_{0}) ∩ Base(J_{1}))[U] is (ϱ, τ)-dense. Note that, then, I[U] must be (ϱ, τ)-dense, because

I[U] = (Base(R) ∩ Base(B))[U] ⊇ (Base(J_{0}) ∩ Base(J_{1}))[U].

Suppose for a contradiction that (Base(J_{0})∩Base(J_{1}))[U] is not (ϱ, τ)-dense, and let U^{∗} ⊆ U be a witness to this fact, that is, suppose that

|U^{∗}| ≥ ϱ|U|  (27)

and

|(Base(J_{0}) ∩ Base(J_{1}))[U^{∗}]| < τ\binom{|U^{∗}|}{2}.  (28)

We let H be the subgraph of J induced by Z ∪ U^{∗} ∪ W. Also, let H_{0} = H[Z, U^{∗}] and H_{1} = H[U^{∗}, W], and let T′ = |E(H_{0})| and T = |E(H_{1})|. We claim that H is an ε′-rare amalgam. Condition (i) of the definition of an ε′-rare amalgam clearly holds (note that Δ(H) ≤ Δ(G)).

Since (Z, U) and (U, W) are (p, λ_{0}; J, ε)-semi-regular, by the choice of ε′ (see (24)) and (27), we have that (Z, U^{∗}) and (U^{∗}, W) are (p, λ_{0}; H, ε′)-semi-regular, so condition (ii) holds too.

We already know that Base(J_{0})[U] is (ϱ, τ_{0})-dense, so that

| Base(H_{0})[U^{∗}]| = | Base(H_{0})[U^{∗}]| ≥ τ_{0}\binom{|U^{∗}|}{2},  (29)

which verifies condition (iii). Finally note that (28) yields (iv), since

Base(H_{0}) ∩ Base(H_{1}))[U^{∗}] = Base(J_{0}) ∩ Base(J_{1}))[U^{∗}].

We have reached a contradiction, for we supposed that G contains no ε′-rare amalgam. This contradiction completes the proof of Fact 16, and consequently the proof of Lemma 8. □

Comments on the proof of Lemma 2. We observed in the beginning of Section 4 that we would come close to proving Lemma 2. We may now expand on this remark a little (we shall be sketchy).

Suppose p = c/\sqrt{n}, where c > 0 is an arbitrary constant, and consider G = G(n, p). Furthermore, suppose F ⊆ E(G) has cardinality at least λ_{0}|E(G)| for some fixed λ_{0} > 0. We wish to show that Base(F) contains an^{3} triangles, for some constant a > 0.

Recall that Lemma 10 asserts the existence of a certain substructure in a G(n, p) (an ‘amalgam’ of two bipartite graphs) whose edges have been properly 3 coloured (see Figure 2). In the case in which we have a subset of edges F of G = G(n, p) as above, one may prove the existence, within F, of, say, the ‘upper half’ of the amalgam in Figure 2. In fact, using the notation introduced immediately after the statement of Lemma 10, one may prove the existence of the graph J_{0}. (The proof is roughly speaking ‘contained’ in the proof of Lemma 10.)

With a suitable graph J_{0} at hand, one may apply Lemma 11, and deduce that Base(F) contains a (ϱ, τ)-dense, induced subgraph with at least σn vertices, where ϱ, τ, and σ are certain positive constants. It now follows from Lemma 9 that Base(F) must contain an^{3} triangles, for some constant a, as required in Lemma 2.

5. Proofs of the auxiliary lemmas

Out of the three auxiliary lemmas stated in Section 4.1, only two remain to be proved, namely, Lemmas 10 and 14. The proofs of both results involve regular and semi-regular pairs, and hence we shall start with a section devoted to these concepts.

5.1. Semi-regularity. The notion of a (p, λ; H, ε)-semi-regular pair has been already defined on page 12. When dealing with semi-regular pairs, the following simple observation is often useful.

Lemma 17. If (U, W) is (p, λ; H, ε)-semi-regular and U_{0} ⊆ U satisfies |U_{0}| ≥ ε|U|, then more than (1 − ε)|W | vertices of W have each at least λp|U_{0}| neighbours in U_{0}.

The following powerful generalization of Lemma 17, is, in fact, its corollary. Recall that for V ⊆ V (H), N_{H}(V) = ⋃_{v∈V} N_{H}(v) is the union of the neighbourhoods in H of all vertices v ∈ V.

Corollary 18. Let (U, W) be a (p, λ; H, ε)-semi-regular pair, let d < |W | be an integer, and fix U_{0} ⊆ U with |U_{0}| > (ε/μ)|U|, where μ = exp{−λpd/2}. Then the number of d-element subsets W_{0} of W such that

|U_{0} \ N_{H}(W_{0})| > μ|U_{0}|  (30)

is less than

ε^{d/2}\binom{d}{d/2}|W |^{d}/d!.

Proof. Let W_{0} ⊆ W be a d-element subset of W with a fixed ordering w_{1}, …, w_{d} of its elements. We define a sequence

U_{0} ⊇ ⋯ ⊇ U_{d} = U_{0} \ ⋃_{w∈W_{0}} N(H_{0}; w) = U_{0} \ N_{H}(W_{0})  (31)

of descending subsets of W, putting

U_{j} = U_{j−1} \ N(H_{0}; w_{j}) = U_{0} \ ⋃_{1≤k≤j} N(H_{0}; w_{k}),  (32)

for all 1 ≤ j ≤ d. Let us call the ratio

|U_{j}|/|U_{j−1}|  (33)

the shrinking factor at j (1 ≤ j ≤ d). Observe that this factor depends only on the sequence w_{1}, …, w_{j}. Observe that for a set W_{0} satisfying (30), at least d/2 shrinking factors are greater than 1 − λp. Indeed, otherwise we would have

|U_{d}| ≤ (1 − λp)^{d/2}|U_{0}| ≤ μ|U_{0}|.

Note also that for each 1 ≤ j ≤ d, we have

U_{j−1} ≥ μ|U_{0}| > ε|U|

and hence, by Lemma 17 there are fewer than ε|W | vertices w ∈ W with less than λp|U_{j−1}| neighbours in U_{j−1}.

Let W^{×} ⊆ W^{d} = W × ⋯ × W be the collection of ordered d-tuples (w_{1}, …, w_{d}) that have at least d/2 indices j with shrinking factor greater than 1 − λp. It follows that

|W^{×}| ≤ \binom{d}{d/2}ε^{d/2}|W |^{d}.  (34)

Now let W ⊆ [W]^{d} be the set of d-element subsets W_{0} of W that satisfy (30). Clearly, if W_{0} ∈ W, then any ordered d-tuple (w_{1}, …, w_{d}) with W_{0} = {w_{1}, …, w_{d}} belongs to W^{×} (that is, any ordering of a member of W is in W^{×}). This and (34) give that

d!|W| ≤ |W^{×}| ≤ \binom{d}{d/2}ε^{d/2}|W |^{d},

which completes the proof. □

The reader may have observed that the concepts of (ϱ, τ)-denseness and ε-semi-regularity are related (the latter is a ‘bipartite version’ of the former). Furthermore, the reader acquainted with the celebrated regularity lemma of Szemerédi [21] has certainly observed that the notion of ε-semi-regularity is a weaker form of ε-regularity. As it turns out, it is more convenient for us to work with this weaker notion.

However, to be able to assert the existence of suitable semi-regular pairs in our graphs, we shall invoke the regularity lemma, which we now recall. Since we are dealing with sparse graphs (that is, graphs with a subquadratic number of edges), we shall make use of an appropriate variant. We need to introduce some definitions.

A graph H is called (p; b, β)-bounded if for all pairs of disjoint subsets U, V ⊆ V (H) with |U|, |V | > β|V (H)| we have e_{H}(U, V) ≤ bp|U||V |. A pair U, V ⊆ V (H), U ∩ V = ∅, is called (p; H, ε)-regular if for all U′ ⊆ U and V′ ⊆ V, with |U′| ≥ ε|U| and |V′| ≥ ε|V |, we have

|\frac{e_{H}(U′, V′)}{p|U′||V′|} − \frac{e_{H}(U, V)}{p|U||V |}| ≤ ε.

Observe that, clearly, if a pair is (p; H, ε)-regular, then it is also (p, λ; H, ε)- semi-regular for λ = e_{H}(U, V)/p|U||V | − ε.

Let |V (H)| = n. A partition V (H) = V_{1} ∪ ⋯ ∪ V_{k} is (p; H, ε, k)-regular if all but at most ε\binom{k}{2} pairs (V_{i}, V_{j}) are (p; H, ε)-regular, and, for all i = 1, …, k, we have ⌊n/k⌋ ≤ |V_{i}| ≤ ⌈n/k⌉. The following sparse version of Szemerédi’s regularity lemma will be important in what follows (for general discussions on this lemma, see, e.g., [12, 13, 14]).

Lemma 19. For all ε > 0, b ≥ 1, and all integers m and r ≥ 1, there exist β > 0 and K ≥ m for which the following holds. For all p and all rtuples of (p; b, β)-bounded graphs (H_{1}, …, H_{r}), with all the H_{i} on the same vertex set V with |V | ≥ m, there exists a partition V = V_{1} ∪ ⋯ ∪ V_{k} of V with m ≤ k ≤ K that is (p; H_{i}, ε, k)-regular for all 1 ≤ i ≤ r.

5.2. Proof of Lemma 10. We start with two basic facts.

Fact 20. Let G be a graph on k ≥ 1 vertices and with at least γ\binom{k}{2} edges, where 0 < γ ≤ 1. Then the number of vertices of degree at least γk/2 in G is at least γk/2. □

Fact 21. Suppose k ≥ 1 and

E(K_{k}) = R ∪ B ∪ Y ∪ S  (35)

is a colouring of the edges of the complete graph K_{k} with colours red, blue, yellow, and sienna, where

|R|, |B| ≥ γ\binom{k}{2}

and

|S| ≤ \frac{1}{8}γ^{2}\binom{k}{2}.  (36)

Then there is a vertex x in K_{k} and distinct colours C_{1}, C_{2} ∈ {R, B, Y } such that x is incident to at least γk/8 edges of colour C_{1} and at least γk/8 edges of colour C_{2}.

Proof. For a colour C and vertex x, let d(C, x) be the number of edges of colour C incident to x in colouring (35). For C = R and B, let

U_{C} = \{u ∈ V (K_{k}): d(C, x) ≥ \frac{1}{2}γk\} .  (37)

By Fact 20, we have |U_{R}|, |U_{B}| ≥ γk/2. Clearly, we are done if U_{R} ∩ U_{B} ≠ ∅. Hence we suppose that U_{R} ∩ U_{B} = ∅. Consider the |U_{R}||U_{B}| edges in E(U_{R}, U_{B}) = E_{K_{k}}(U_{R}, U_{B}). There is a colour C ∈ {R, B, Y } for which we have

|E(U_{R}, U_{B}) ∩ C| ≥ \frac{1}{3} (|U_{R}||U_{B}| − |S|) .

Without loss of generality, we may assume that C ≠ R. By averaging, we may deduce that there is a vertex x ∈ U_{R} for which we have

d(C, x) ≥ \frac{|E(U_{R}, U_{B}) ∩ C|}{|U_{R}|} ≥ \frac{1}{3} (|U_{B}| − \frac{|S|}{|U_{R}|})

≥ \frac{1}{3} (\frac{1}{2}γk − \frac{(1/16)γ^{2}k^{2}}{γk/2} ) = \frac{1}{8}γk,

and we are again done: x is incident to at least γk/2 ≥ γk/8 edges of colour R and to at least γk/8 edges of colour C ≠ R. □

We are now ready to prove Lemma 10.

Proof of Lemma 10. Let ε > 0 be given. Since the smaller ε is, the stronger is the conclusion in Lemma 10, we may suppose that

ε ≤ \frac{1}{30}.  (38)

Put

δ = min \{ε^{2}, \frac{1}{10^{2}} λ_{0}, \frac{1}{2 × 10^{4}} c^{4}\} and m = \frac{16}{3λ_{0}^{2}} .  (39)

Let

β = β(δ, m) and K = K(δ, m)  (40)

be the constants given by Lemma 19, for the constants ε = δ, b = 2, m, and r = 3 as above. We now let

σ = \frac{1}{K(δ, m)},  (41)

and claim that this choice for σ will do. We now proceed to prove this claim. Thus, let the graph G and the edge-colouring E(G) = R ∪ B ∪ Y be as in the statement of Lemma 10.

The expected number of triangles in G is (1/6 + o(1))(np)^{3} = (1/6 + o(1))c^{3}n^{3/2}. Also, the expected number of edges e = {a, b} together with two further vertices x and y (x ≠ y) with x, y ∈ N(G; a) ∩ N(G; b) (that is, the number of diamonds) is

\binom{n}{2}\binom{n − 2}{2}p^{5} ∼ (\frac{1}{4} + o(1)) c^{5}n^{3/2}.

Standard variance calculations, combined with Chebyshev’s inequality, show that both quantities above are concentrated around their means, i.e., a.a.s. the number of triangles is (1/6 + o(1))c^{3}n^{3/2}, and the number of diamonds is a.a.s. (1/4 + o(1))c^{5}n^{3/2}. Therefore, the number of triangles in G that are ‘solitary’, that is, that share no edge with any other triangle, is a.a.s.

\frac{1}{6}c^{3}n^{3/2} − \frac{1}{4}c^{5}n^{3/2} ≥ \frac{1}{7}c^{3}n^{3/2},

where we used that c ≤ 1/5. We may hence suppose that G contains at least c^{3}n^{3/2}/7 solitary triangles.

By adjusting the notation, we may suppose that

|R| ≥ |B| ≥ |Y |.

Since we are supposing that the colouring (7) contains no monochromatic triangle, we may deduce that |B ∪ Y | ≥ c^{3}n^{3/2}/7; indeed, each solitary triangle must contain either a blue edge or a yellow edge, for otherwise it would be entirely red. In particular, we have

|R|, |B| ≥ \frac{1}{14}c^{3}n^{3/2}.  (42)

By Chernoff’s inequality, we may also suppose that, for each pair U, W ⊆ V (G) with U ∩ W = ∅ and |U|, |W | ≥ n/ log n, we have

\frac{1}{2}|U||W |p ≤ e_{G}(U, W) = |E_{G}(U, W)| ≤ 2|U||W |p,  (43)

and

e_{G}(U) = |E(G[U])| ≤ |U|^{2}p.  (44)

Note that it follows from (43) that G is a.a.s. (p; 2, β)-bounded for all β > 0.

Let us now apply Lemma 19 to obtain a partition V (G) = V_{1} ∪ ⋯ ∪ V_{k} of V (G) with m ≤ k ≤ K that is (p; F, δ, k)-regular for F = R, F = B, and F = Y. We now state and prove a claim that will be used in what follows.

Claim 22. Suppose F ⊆ E(G) is a subset of edges of G = G(n, p), with |F | ≥ λ_{0}cn^{3/2}. Let V_{1}, …, V_{k} be a (p; F, δ, k)-regular partition of V (G), where m ≤ k ≤ K. Suppose for simplicity that |V_{1}| = ⋯ = |V_{k}|. Let Φ be the set of pairs {i, j} (1 ≤ i < j ≤ k) for which (V_{i}, V_{j}) is (p; F, δ)-regular and

e_{F} (V_{i}, V_{j}) ≥ \frac{1}{2}λ_{0}p (\frac{n}{k})^{2} .  (45)

Then

|Φ| ≥ \frac{5}{8}λ_{0}\binom{k}{2}.  (46)

Proof. Let ℓ = x\binom{k}{2} = |Φ| and recall that we are assuming that |V_{i}| = n/k (1 ≤ i ≤ k). Using that G satisfies (43) and (44) for all ‘large’ U and W ⊆ V (G), we deduce that

λ_{0}cn^{3/2} ≤ |F | ≤ 2ℓ (\frac{n}{k})^{2} p + (\binom{k}{2} − ℓ) \frac{λ_{0}p}{2} (\frac{n}{k})^{2} + k (\frac{n}{k})^{2} p,

and so

λ_{0} ≤ x + \frac{1}{4}(1 − x)λ_{0} + \frac{1}{k} .

Solving the last inequality for x, we obtain x ≥ 3λ_{0}/4, because 1/k ≤ 1/m = 3λ_{0}^{2}/16. Hence, at least

\frac{3}{4}λ_{0}\binom{k}{2} − δ\binom{k}{2} ≥ \frac{5}{8}λ_{0}\binom{k}{2}

pairs (V_{i}, V_{j}) are (p; F, δ)-regular, each satisfying (45); that is, the set Φ satisfies (46), as required. □

For F = R, B, and Y, let Φ_{F} be the set of pairs {i, j} (1 ≤ i < j ≤ k) such that (V_{i}, V_{j}) is (p; F, δ)-regular and

e_{F} (V_{i}, V_{j}) ≥ \frac{1}{2} (\frac{1}{14}c^{2}) p (\frac{n}{k})^{2} = \frac{1}{28}c^{2}p (\frac{n}{k})^{2} .  (47)

We apply Claim 22 with F = R and B and λ_{0} = c^{2}/14 (see (42)). That claim tells us that

|Φ_{R}|, |Φ_{B}| ≥ \frac{1}{25}c^{2}\binom{k}{2}.  (48)

Since

3 × \frac{1}{28}c^{2}p (\frac{n}{k})^{2} ≤ \frac{1}{2}p (\frac{n}{k})^{2} ,

the fact that (43) holds for all ‘large’ U and W ⊆ V (G) implies that if a pair {i, j} (1 ≤ i < j ≤ k) is not a member of Φ_{R} ∪ Φ_{B} ∪ Φ_{Y}, then (V_{i}, V_{j}) is not (p; F, δ)-regular for some F ∈ {R, B, Y }. Put

Φ_{S} = [k]^{2} \ (Φ_{R} ∪ Φ_{B} ∪ Φ_{Y}).

The observations above, the fact that V_{1}, …, V_{k} is a (p; F, δ, k)-regular partition of V (G) for F ∈ {R, B, Y }, and our choice of δ (see (39)) imply that

|Φ_{S}| ≤ 3δ\binom{k}{2} ≤ \frac{3}{2 × 10^{4}} c^{4}\binom{k}{2} < \frac{1}{8} (\frac{1}{25}c^{2})^{2} \binom{k}{2}.  (49)

We now apply Fact 21 to the following colouring of the edges of the complete graph K_{k} on [k] = {1, …, k}:

E(K_{k}) = Φ_{R} ∪ Φ_{B} ∪ Φ_{Y} ∪ Φ_{S}.

In view of (48) and (49), we may apply Fact 21 with γ = c^{2}/25. We then obtain i_{0} ∈ [k] = V (K_{k}) and two disjoint sets Γ′_{F} ⊆ [k] (F = R and B, say) with

|Γ′_{F} | ≥ \frac{1}{8} (\frac{1}{25}c^{2}) k = \frac{1}{200}c^{2}k,  (50)

such that, for all j ∈ Γ′_{F}, we have that

(V_{i_{0}}, V_{j}) is (p; F, δ)-regular  (51)

and

e_{F} (V_{i_{0}}, V_{j}) ≥ \frac{1}{28}c^{2}p (\frac{n}{k})^{2} .  (52)

We let Γ_{F} ⊆ Γ′_{F} (F = R and B) be an arbitrary subset of Γ′_{F} with |Γ_{F} | = (c^{2}/200)k. Moreover, let

U = V_{i_{0}}, Z = ⋃_{j∈Γ_{R}} V_{j}, and W = ⋃_{j∈Γ_{B}} V_{j},

and let

J = R[Z, U] ∪ B[U, W].  (53)

Claim 23. We claim that J, Z, U, and W satisfy (i), (ii), and (iii) of Lemma 10.

Proof. We start by noticing that

|Z| = |W | = \frac{1}{200}c^{2}k × \frac{n}{k} = \frac{1}{200}c^{2}n = σ_{0}n.

Moreover,

|U| = \frac{n}{k} ≥ \frac{n}{K(δ, m)} = σn.

Property (ii) asserted in Lemma 10 is clear from the definition of J (see (53)). We are now left with proving (iii), that is, that (Z, U) and (U, W) are (p, λ_{0}; J, ε)-semi-regular. We deal with (Z, U), as the other case is analogous.

Let U′ ⊆ U and Z′ ⊆ Z be such that |U′| ≥ ε|U| and |Z′| ≥ ε|Z|. We have to show that

\frac{e_{J}(U′, Z′)}{p|U′||Z′|} ≥ \frac{1}{30}c^{2} = λ_{0}.  (54)

Put Z′_{j} = Z′ ∩ V_{j} (j ∈ Γ_{R}). Clearly, we have e_{J}(U′, Z′) = ∑_{j∈Γ_{R}} e_{J}(U′, Z′_{j}). Therefore, we have

\frac{e_{J}(U′, Z′)}{p|U′||Z′|} = ∑_{j∈Γ_{R}} \frac{e_{J}(U′, Z′_{j})}{p|U′||Z′_{j}|} × \frac{|U′||Z′_{j}|}{|U′||Z′|}

= ( ∑_{j∈Γ′_{R}} + ∑_{j∈Γ′′_{R}} )\frac{e_{J}(U′, Z′_{j})}{p|U′||Z′_{j}|} × \frac{|Z′_{j}|}{|Z′|}, (55)

where Γ′_{R} = {j ∈ Γ_{R}: |Z′_{j}|/|V_{j}| < δ}, and Γ′′_{R} = Γ_{R} \ Γ′_{R}. We now claim that

∑_{j∈Γ′′_{R}} \frac{|Z′_{j}|}{|Z′|} ≥ 1 − ε.  (56)

Indeed,

∑_{j∈Γ′_{R}} |Z′_{j}| ≤ δ ∑_{j∈Γ′_{R}} |V_{j}| ≤ δ|Z|.

Moreover, |Z′| ≥ ε|Z|, and hence

∑_{j∈Γ′_{R}} |Z′_{j}| ≤ δ (\frac{1}{ε}|Z′|) ≤ ε|Z′|,  (57)

as δ ≤ ε^{2} (see (39)). It follows from (57) that (56) does indeed hold.

We now go back to (55). Clearly, the right-hand side of (55) is, by (51), (52), and (56), at least

∑_{j∈Γ′′_{R}} \frac{e_{J}(U′, Z′_{j})}{p|U′||Z′_{j}|} × \frac{|Z′_{j}|}{|Z′|} ≥ (\frac{1}{28}c^{2} − δ) ∑_{j∈Γ′′_{R}} \frac{|Z′_{j}|}{|Z′|}

≥ (\frac{1}{28}c^{2} − δ) (1 − ε) ≥ \frac{1}{30}c^{2} = λ_{0}

We have thus shown that (54) does indeed hold, and so (Z, U) is (p, λ_{0}; J, ε)- semi-regular. This concludes the proof of Claim 23. □

Claim 23 completes the proof of Lemma 10. □

5.3. Proof of Lemma 14. The basic underlying idea in this proof comes from [15, Lemma 11] (see also [12, Lemma 8.30]).

We start by letting arbitrary positive constants τ′, and α be given. To prove Lemma 14, we need to define an appropriate constant ε′ > 0. Put

ε′ = min \{\frac{1}{16}(α/3)^{96/λ_{0}τ′σ_{0}}, \frac{1}{4}τ′ exp\{−λ_{0}c^{2}/3\}\} .  (58)

We claim that this choice for ε′ will do.

Recall that we wish to estimate the number of bipartite graphs H with bipartition (U^{∗}, W), where |W | = w = σ_{0}n and |U^{∗}| = u^{∗} ≥ n/(log n)^{2}, belonging to the family

B_{1} = B_{1}(U^{∗}, W; F; τ′, ε′; n, T),

where

F ⊆ [U^{∗}]^{2},  |F | = τ′\binom{u^{∗}}{2}.  (59)

In order to obtain this estimate, let us make the following observation about the graphs H ∈ B_{1}.

Lemma 24. Suppose H ∈ B_{1}. Then H is a union of two edge-disjoint subgraphs H′ and H′′ with |E(H′)| = |E(H′′)| = T/2, and such that the pair (U^{∗}, W) is both, (p, λ_{0}/3; H′, ε′)-semi-regular and (p, λ_{0}/3; H′′, ε′)-semi-regular.

Proof. It suffices to use the ‘probabilistic method’, taking a random partition. The result follows from standard exponential estimates for the tail of the hypergeometric distribution. We omit the details. □

For each graph H ∈ B_{1}, we fix a decomposition H = H′ ∪ H′′. By Lemma 20, there exists a set U^{∗∗} ⊆ U^{∗} such that

u^{∗∗} = |U^{∗∗}| ≥ τ′u^{∗}/2  (60)

and for all v ∈ U^{∗∗} we have deg_{F} (v) ≥ τ′u^{∗}/2. We now need to fix some notation. Let

U^{∗∗} = {v_{i}: 1 ≤ i ≤ u^{∗∗} = |U^{∗∗}|}.

and let

F_{i} = N(F; v_{i}), W^{(i)} = N(H′′; v_{i}) (61)

be the neighbourhoods of v_{i} in the graph F and H′′, respectively. Because of our choice of U^{∗∗}, we have

|F_{i}| = deg_{F} (v_{i}) ≥ \frac{1}{2}τ′u^{∗}  (62)

for all 1 ≤ i ≤ u^{∗∗}.

Let d_{i} = |W^{(i)}|. Then, by the (p, λ_{0}/3; H′′, ε′)-semi-regularity of (U^{∗}, W), it follows from Lemma 17 that for at least u^{∗∗} − ε′u^{∗} > u^{∗∗}/2 indices i, we have d_{i} ≥ (λ_{0}/3)p|W | (note that ε′ < τ′/4). Thus, we may suppose that

\frac{1}{3}λ_{0}p|W | ≤ d_{i} ≤ 2c\sqrt{n} for all 1 ≤ i ≤ u^{∗∗}/2  (63)

(recall that Δ(H) ≤ 2c\sqrt{n}). It will be convenient to set

W^{(i)} = {w_{1}^{(i)}, …, w_{d_{i}}^{(i)}}  (64)

for all 1 ≤ i ≤ u^{∗∗}/2.

Let

μ_{0} = exp{−λ_{0}^{2}c^{2}σ_{0}/18}.  (65)

We shall say that v_{i} (1 ≤ i ≤ u^{∗∗}/2) is bad if

|F_{i} \ N(H′; W^{(i)})| ≥ μ_{0}|F_{i}|.

We claim that more than u^{∗∗}/4 vertices are bad. Suppose for a contradiction that the number of vertices v_{i} (1 ≤ i ≤ u^{∗∗}/2) that are not bad is at least u^{∗∗}/4. Let v_{i} be one of them. Clearly, the number of edges of F ∩ Base(H)[U^{∗}] adjacent to v_{i} is precisely |F_{i} ∩ N(H′; W^{(i)})| (this is the set of H′-neighbours of the H′′-neighbours of v_{i} which are also F -neighbours of v_{i}). Since v_{i} is not bad, we have

|F_{i} ∩ N(H′; W^{(i)})| ≥ (1 − μ_{0})|F_{i}| ≥ \frac{1}{50}λ_{0}^{2}c^{2}σ_{0}|F_{i}|,  (66)

where we used that x = (1/18)λ_{0}^{2}c^{2}σ_{0} ≤ 1/2, and hence 1 − e^{−x} ≥ x/2, say. However, this means that v_{i} contributes to F ∩Base(H)[U^{∗}] at least as many pairs as in (66) (with some pairs counted twice, when all v_{i} are considered). Consequently, by (5), (59), (60) and (62)

|F ∩ Base(H)[U^{∗}]| ≥ \frac{1}{4}u^{∗∗} × \frac{1}{2} (\frac{1}{50}λ_{0}^{2}c^{2}σ_{0} \frac{1}{2}τ′u^{∗})

≥ τ_{0}(τ′)^{2}\binom{u^{∗}}{2} = τ_{0}τ′|F |, (67)

which is in contradiction to the fact that H ∈ B_{1} (see (12)).

Completion of the proof of Lemma 14. Suppose H ∈ B_{1} is given. In view of Lemma 24, we may decompose H as a union H′ ∪ H′′, so that |E(H′)| = |E(H′′)| = T/2 and (U^{∗}, W) is both, (p, λ_{0}/3; H′, ε′)-semi-regular, and (p, λ_{0}/3; H′′, ε′)-semi-regular.

We estimate the cardinality of

B_{1} = B_{1}(U^{∗}, W; F; σ_{0}, λ_{0}, τ′, ε′; n, T)

as follows. We ‘generate’ the members H ∈ B_{1} in two rounds: first H′, then H′′. We do not require that H′ and H′′ above be disjoint. Since we are after an upper bound for |B_{1}|, this is justified.

The number of choices of H′ is bounded crudely by \binom{wu^{∗}}{T/2}. With fixed H′, for every H′′ such that H′ ∪ H′′ ∈ B_{1}, there exist u^{∗∗}/4 bad vertices v_{i} ∈ U^{∗} with d_{i} = |N(H′; v_{i})| ≥ (λ_{0}/3)pw. For each one of them we apply Corollary 18 to H′ with d = d_{i}, U_{0} = F_{i}, W_{0} = W^{(i)}, ε = ε′, λ = λ_{0}/3 and μ = exp{−λ_{0}pd/6}.

We have |F_{i} \N(H′; W^{(i)})| > μ_{0}|F_{i}| ≥ μ|F_{i}|, and thus (30) holds. We also have

|F_{i}| ≥ τ′u^{∗}/2 > ε′ exp{λ_{0}c^{2}/3}u^{∗} ≥ (ε′/μ)u^{∗}.

Hence, by Corollary 18 the number of choices of the neighbourhood N(H′′; v_{i}) is at most

(ε′)^{d/2}\binom{d}{d/2}w^{d}/d! < (ε′)^{d/2}2^{d}\binom{w}{d}.  (68)

Thus, an upper bound on the number of choices of H′′ may be obtained by bounding first the number of choices of the u^{∗∗}/4 bad vertices by 2^{u^{∗}}, and then summing the products

(2\sqrt{ε′})^{D} ∏ \{\binom{w}{d(v)}: v ∈ U^{∗}\}  (69)

over all degree sequences d = {d(v): v ∈ U^{∗}}, where D = (1/12)λ_{0}pu^{∗∗}w is a lower bound on the sum of the degrees of all bad vertices (cf. (63)). Indeed, with a fixed set of bad vertices U^{∗∗∗}, and fixed degree sequence d, by (68) there are at most

∏_{v∈U^{∗∗∗}}(ε′)^{d(v)/2}2^{d(v)}\binom{w}{d(v)} × ∏_{v∈U^{∗}\U^{∗∗∗}} \binom{w}{d(v)}

choices of the neighbourhoods which together create H′′. To estimate the quantity in (69), we observe that, because Δ(H) ≤ 2c\sqrt{n}, we have T ≤ 2c\sqrt{n}|U^{∗}| = 2cu^{∗}\sqrt{n}. Moreover, we recall that u^{∗∗} ≥ τ′u^{∗}/2, p = c/\sqrt{n}, and w = σ_{0}n, and hence we have

\frac{D}{T} ≥ \frac{(1/12)λ_{0}pu^{∗∗}w}{2c\sqrt{n}u^{∗}} ≥ \frac{1}{48}λ_{0}τ′σ_{0}.

Therefore, given H′, there are at most

2^{u^{∗}}(2\sqrt{ε′})^{(λ_{0}τ′σ_{0}/48)T} ∏ \{\binom{w}{d(v)}: v ∈ U^{∗}\}  (70)

choices for H′′. We now sum (70) over all choices of d = {d(v): v ∈ U^{∗}}. Recalling that d is a partition of T/2, and that

T ≥ λ_{0}pu^{∗}w = λ_{0}cσ_{0}u^{∗}\sqrt{n} ≫ u^{∗}  (71)

(cf. (19) and (20)), we see that this sum is at most

(4\sqrt{ε′})^{(λ_{0}τ′σ_{0}/48)T} \binom{wu^{∗}}{T/2}.  (72)

To obtain the desired bound on B_{1} we have to multiply the above by \binom{wu^{∗}}{T/2}, the number of choices for H′. As, crudely,

\binom{wu^{∗}}{T/2}^{2} < 3^{T} \binom{wu^{∗}}{T},

Lemma 14 is proved by our choice of ε′. □

6. Concluding remarks

We close by mentioning a few remarks and open problems.

The online game for more colours. We hope to address the online game when the Painter has r > 2 colours in the near future.

General graphs. It would be most interesting to generalize our results for general graphs H, that is, for avoidance games in which the Painter has to avoid monochromatic copies of a given graph H. However, our methods are deeply based on the simple structure of the triangles and hence a completely new approach may be needed.

Our results above suggest that, in the two-round game for arbitrary graphs H, the first interesting case is the one in which r = 2 and N_{0} is around the threshold for the corresponding Ramsey property, that is, N_{0} = Θ(n^{2−1/d_{2}(H)}), where d_{2}(H) = max{(|E(F)| − 1)/(|V (F)| − 2): F ⊆ H, |V (F)| > 2} (see [19]).

Deterministic games. In the deterministic version of our online game, say for r = 2 and H = K_{k}, the edges are generated not randomly, but by an adversary. Hence, this is a two-person game with the payoff to the Painter equal to the number of coloured edges until she is forced to form a monochromatic clique K_{k}.

Define the online Ramsey number R̄(k) as the value of this game. The question is whether it is true that R̄(k) = o(R(k)^{2}) as k → ∞, where R(k) is the classical Ramsey number. Some preliminary results in this direction have been proved by Kurek and Ruciński [16]. In particular, R̄(3) = 8 and R̄(k, l) = o(R(k, l)^{2}) as k → ∞ while l ≥ 3 is fixed, where R(k, l) and R̄(k, l) are the corresponding off-diagonal numbers.

Finally, we mention that other games inspired by Ramsey’s theorem have been investigated in several forms. The reader is referred to, for instance, Beck [2, 3, 4, 5], Beck and Csirmaz [1], Erdős and Selfridge [7], and Seress [20].

References

[1] J. Beck and L. Csirmaz, Variations on a game, J. Combin. Theory Ser. A 33 (1982), no. 3, 297–315. MR 84a:90092 6

[2] József Beck, van der Waerden and Ramsey type games, Combinatorica 1 (1981), no. 2, 103–116. MR 84a:90093 6

[3] , Random graphs and positional games on the complete graph, Random graphs ’83 (Poznań, 1983), North-Holland, Amsterdam, 1985, pp. 7–13. MR 87j:05130 6

[4] , Deterministic graph games and a probabilistic intuition, Combin. Probab. Comput. 3 (1994), no. 1, 13–26. MR 95h:90191 6

[5] , Foundations of positional games, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), vol. 9, 1996, pp. 15–47. MR 99h:90128 6

[6] Béla Bollobás, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. MR 87f:05152 1.3

[7] P. Erdős and J. L. Selfridge, On a combinatorial game, J. Combinatorial Theory Ser. A 14 (1973), 298–301. MR 48 #5655 6

[8] P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without K_{4}, Graphs Combin. 2 (1986), no. 2, 135–144. MR 89b:05124 1.1.3

[9] E. Friedgut, V. Rödl, A. Ruciński, and P. Tetali, A sharp threshold for random graphs with monochromatic triangle in every edge coloring, in preparation, 2002. 1.1.3, 2, 2, 5, 4

[10] Ehud Friedgut, Sharp thresholds of graph properties, and the k-sat problem, J. Amer. Math. Soc. 12 (1999), no. 4, 1017–1054, With an appendix by Jean Bourgain. MR 2000a:05183 1.1.3, 2

[11] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph, Random graphs ’87 (Poznań, 1987), Wiley, Chichester, 1990, pp. 73–87. MR 91m:05168 2

[12] , Random graphs, Wiley-Interscience, New York, 2000. MR 2001k:05180 1.3, 3.1, 4.2, 5.1, 5.3 [13] Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of com-

putational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216–230. MR 99g:05145 5.1

[14] Y. Kohayakawa and V. Rödl, Szemerédi’s regularity lemma and quasi-randomness, Recent advances in algorithms and combinatorics, Springer, Berlin, 63pp., to appear, 2002. 5.1

[15] Yoshiharu Kohayakawa, Tomasz Łuczak, and Vojtěch Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133–163. MR 97b:11011 5.3

[16] Andrzej Kurek and Andrzej Ruciński, The sparsest Ramsey graphs are complete graphs, submitted, 2002. 2, 6

[17] Tomasz Łuczak, Andrzej Ruciński, and Bernd Voigt, Ramsey properties of random graphs, J. Combin. Theory Ser. B 56 (1992), no. 1, 55–68. MR 94b:05172 1.1.3

[18] Vojtěch Rödl and Andrzej Ruciński, Random graphs with monochromatic triangles in every edge coloring, Random Structures Algorithms 5 (1994), no. 2, 253–270. MR 95a:05102 1.1.3, 3.2

[19] , Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942. MR 96h:05141 4, 6

[20] Ákos Seress, On Hajnal’s triangle-free game, Graphs Combin. 8 (1992), no. 1, 75–79. MR 93a:05095 6

[21] Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401. MR 81i:05095 5.1

Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, 91904, Israel

   E-mail address: ehudf@math.huji.ac.il

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

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

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

Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland, and Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA

   E-mail address: rucinski@amu.edu.pl

School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA

   E-mail address: tetali@math.gatech.edu