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 generated. Given the size of the first round, how many edges can there be in the second round if the Player is to win with reasonable probability? 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 only if constantly many edges are generated in the second round.

The analysis of the two-round version of the game is based on a delicate lemma concerning edge-coloured random graphs.

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. Informally, the length of the game is the maximum number of edges on which the Painter can win with large probability. We distinguish three versions of the game: online, two-round, and offline.

Date: Copy produced on June 20, 2002. 1991 Mathematics Subject Classification. 05C80, 91A43, Secondary: 05C55, 91A60. Key words and phrases. Random graphs, Ramsey games, thesholds. 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 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. The three games. 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.

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.

Instead of switching back to the online version after the mercy period of N_{0} edges, let us simply 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 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.

We finally turn to the offline version of our 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 first proved for r = 2 in [19] (see also [8]), and then validated for arbitrary r ≥ 2 in [20]. 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 proof in [19] leaves 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 offlline game for r = 2 colours has a sharply determined value, unlike the online and the two-round games.

The result in (1) makes the two-round game with N_{0} of order n^{3/2} quite interesting. 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 N_{0} = cn^{3/2} with c < c_{r}, then the Painter may 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 5, 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 be a graph. If x is a vertex of G, then N_{G}(x) = N(G; x) denotes the neighbourhood of x in 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. 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.

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 processes G_{0} ⊆ ⋯ ⊆ G\binom{n}{2}, which naturally correspond 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].

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 Forschungs Institut Oberwolfach.

2. Sharp thresholds

Recall that R_{2} consists of all graphs such that every 2-colouring of their edges results in a monochromatic triangle. 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) 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}

As the proof of Theorem 1 has some implications with respect to the two-round version of our game, we give a very brief outline of it here. (The remainder of this paper does not depend on this section.)

The proof of Theorem 1 is based on a consequence of Friedgut’s criterion from [10], which says that in order for R_{2} to have a sharp threshold it is sufficient that for any choice of the constants c, α, and ξ > 0, and for any balanced graph M with average degree 4 there is a graph property G such that G(n, p) ∈ G a.a.s., where p = c/\sqrt{n}, and such that, for all n-vertex graphs G ∈ G with sufficiently large n,

(*) if ℙ[G ∪ M^{∗} ∈ R_{2}] > α, then ℙ[G ∪ G(n, ξp) ∈ R_{2}] → 1 as n → ∞,

where M^{∗} is a random copy of M in the complete graph K_{n}. It can be proved in at least two ways that a graph with average degree 4 cannot be a member of R_{2} (see [9, 18]) and hence M ∉ R_{2}. Thus, if G ∉ R_{2} as well, then the assumption of the above implication indicates a very complex structure of G, which in a sense must be close to possessing property R_{2}. This closeness leads, after 50^{+} pages of proof involving a special, tailor-cut regularity lemma, to the conclusion that, for some λ > 0, there exists a family K of subgraphs of G such that

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

and, most importantly,

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

is monochromatic. Now, all we need is for every K to have a triangle T = T (K) in G(n, ξp) such that each of the edges of T connects the endpoints of a path of length two in K. Then, 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 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.

Since G is essentially a pseudorandom graph resembling G(n, c/\sqrt{n}), Lemma 2 below, proved in [9], which we believe is of independent interest, implies that there are plenty of triangles in the base of each K ∈ K. Given two real numbers 0 < λ < 1 and 0 < a < 1/6, we say that a graph 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.

Lemma 2. For any λ > 0, there exists a > 0 such that if np^{2} ≥ λ then, with probability 1 − o(1), the random graph G(n, p) has property T (λ, a).

Finally, a standard application of Janson’s inequality [11] yields for any given K that with probability 1 − 2^{−Θ(n^{3/2})} there is a triangle T (K) in Base(K) ∩ G(n, ξp). This, together with (i) and (iii) above completes the proof of (*).

The convergence

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

may be viewed as a statement about a two-round Ramsey game against a random graph. 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 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 𝔼(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

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, the base of 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 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 λ = min{c^{2}, 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 (44)). 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 2 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 [20] 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 (ϱ, d)-dense if, for all U ⊆ V (H) with |U| ≥ ϱ|V (H)|, we have

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

An easy averaging argument shows that, when verifying this property, it suffices to check only all subsets U of cardinality |U| = ⌈ϱ|V (H)|⌉.

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

Lemma 8. For all c > 0, there is a constant d > 0 such that, for any ϱ > 0, there is a constant σ_{1} > 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| ≥ σ_{1}n and (ii) I[U] is (ϱ, d)-dense.

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

Lemma 9. For all d > 0 there exist ϱ, n_{0}, and c_{0} > 0 such that every (ϱ, d)-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 d > 0. By Lemma 9 we obtain constants ϱ, n_{0}, and c_{0} > 0 such that any u-vertex (ϱ, d)-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 σ_{1} > 0.

We claim that the choice of

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

and

β = c_{0}σ_{1}^{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| ≥ σ_{1}n, for which I[U] = (Base(R) ∩ Base(B))[U] is (ϱ, d)-dense. Then

|E(I)| ≥ |E(I[U])| ≥ d\binom{|U|}{2} ≥ \frac{1}{3}d|U|^{2} ≥ (\frac{1}{3}dσ_{1}^{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 (ϱ, d)-dense graph I[U] is at least

c_{0}|U|^{3} ≥ c_{0}σ_{1}^{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 4.3. The actual proof of Lemma 8 is given in Section 4.2.

4.1. Auxiliary lemmas. In this section, we state three lemmas 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.

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′|} ≥ λ.

Our first auxiliary lemma, Lemma 10, concerns the existence of a certain substructure in a properly edge-coloured G(n, p). A tripartite graph 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| ≥ σ_{1}n (p, λ; J, ε)-semi-regular (p, λ; J, ε)-semi-regular U  J_{0} ⊆ R J_{1} ⊆ B

Figure 2. The amalgam given by Lemma 10

Lemma 10. Let σ_{0} = (1/200)c^{2} and λ = (1/30)c^{2}. For any ε > 0, there is a constant σ_{1} > 0 for which the following assertion holds a.a.s. for G = G(n, p). Suppose

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

is a proper colouring of the edges of G. Then there exist two colours, say R and B, and a subgraph J of G as follows:

(i) the vertex set of J is the union of three pairwise disjoint sets Z, U, and W, with |Z| = |W | = σ_{0}n and |U| ≥ σ_{1}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, λ; J, ε)-semi-regular.

For convenience, let J_{0} = J[Z, U] and J_{1} = J[U, W] be the bipartite graphs induced by the pairs (Z, U) and (U, W) in J. Basically, our second lemma concerns the graph J_{0} in Lemma 10.

Recall that, for a graph F, we write Base(F) for the graph whose edges are the pairs of vertices {x, y} ⊆ V (F) that are joined by a path of length 2 in F. To investigate the ‘density’ of Base(F), we shall concentrate on some suitable bipartite subgraphs of F. Suppose F_{0} is a bipartite subgraph of F, with vertex classes U and W. We shall write B_{U}(F_{0}) for the subgraph Base(F_{0})[U] of Base(F_{0}) induced by the vertex class U. For convenience, we shall often simply write B_{U}(F_{0}) instead of E(B_{U}(F_{0})). Explicitly, we have

B_{U}(F_{0}) = {{u, u′} ⊆ U: ∃w ∈ W with {u, w}, {u′, w} ∈ F_{0}}.

Note that, clearly, B_{U}(F_{0}) ⊆ Base(F).

Lemma 11. For all positive constants σ_{0}, λ, and ϱ, there exists a constant ε > 0 such that a.a.s. G = G(n, p) satisfies the following property. For all bipartite subgraphs J_{0} = (Z, U; E) of G with

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

the graph Base(J_{0})[U] = B_{U}(J_{0}) is (ϱ, d′)-dense, where

d′ = min \{\frac{1}{4}λ^{2}c^{2}σ_{0}, \frac{1}{16}λ^{4}\} .  (6)

As an immediate consequence of Lemmas 10 and 11 we conclude 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] = B_{U}(J_{0}) is (ϱ, d′)-dense. Suppose that I[U] = (Base(R) ∩ Base(B))[U] is not (ϱ, d)-dense for some d to be chosen later (cf. (24)). 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 (ϱ, d)-dense either. This means that there exists a set U^{∗} ⊆ U, with u^{∗} = |U^{∗}| ≥ ϱ|U|, such that

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

The subset U^{∗} generates a subamalgam H of J, which, as our next result shows, is very rare among all amalgams of that size. Consequently, it will follow that a.a.s. G(n, p) does not contain such an amalgam H, contradicting the assumption that I[U] is not (ϱ, d)-dense.

Now come the details. Let Z, U^{∗}, and W be three pairwise disjoint sets of vertices. Suppose we have constants

σ_{0}, λ, τ, and ε′ > 0

and integers

n, T and T′.

Suppose

|Z| = |W | = σ_{0}n and |U^{∗}| ≥ n/ log n.

We now let

B(Z, U^{∗}, W; σ_{0}, λ, τ, ε′; n, T, T′)  (7)

be the family of amalgams H on Z ∪ U^{∗} ∪ W satisfying the following conditions:

(i) E(H) = E_{H}(Z, U^{∗}) ∪ E_{H}(U^{∗}, W), where
|E_{H}(Z, U^{∗})| = T′ and |E_{H}(U^{∗}, W)| = T,

and

Δ(H) ≤ 2c\sqrt{n},  (8)

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

|B_{U^{∗}}(H_{0})| ≥ τ\binom{|U^{∗}|}{2},

and (iv) we have

|B_{U^{∗}}(H_{0}) ∩ B_{U^{∗}}(H_{1})| < d\binom{|U^{∗}|}{2},  (9)

where d is as in (24). We may now state our third and final auxiliary lemma.

Lemma 12. For all positive constants σ_{0}, λ, τ, and α ≤ 1, there exist constants ε′ > 0 and n_{0} such that, with the notation as above, for all n ≥ n_{0} and all T and T′, we have

|B(Z, U^{∗}, W; σ_{0}, λ, τ, ε′; n, T, T′)| ≤ α^{T} \binom{|Z||U^{∗}|}{T′}\binom{|W ||U^{∗}|}{T}.

We observe that Lemma 12 above may be interpreted as a statement concerning the uniform space of amalgams of bipartite graphs on vertex sets Z, U^{∗}, and W and number of edges T′ and T. Indeed, Lemma 12 tells us that the probability that a random element from this space should be an element of the family in (7) is at most α^{T} for any given α > 0, if n is sufficiently large and ε′ is sufficiently small.

Hence, one may say that the members H in the family in (7) are extremely rare, as long as T is large (which will turn out to be our case). We now use this fact to show that the random graph G(n, p) is quite unlikely to contain such rare graphs H.

Given σ_{0}, λ, τ, ε′ > 0, and n, let us call an amalgam

H = (Z, U^{∗}, W; E_{H}(Z, U^{∗}), E_{H}(U^{∗}, W))

rare if |Z| = |W | = σ_{0}n,

u^{∗} = |U^{∗}| ≥ n/ log n,  (10)
Δ(H) ≤ 2c\sqrt{n},  (11)

and (ii)–(iv) from the definition of the family in (7) hold. Note that if H is rare, then, setting |E_{H}(Z, U^{∗})| = T′ and |E_{H}(U^{∗}, W)| = T, we have

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

and hence, as (10) holds, we have

T, T′ ≫ n log n.  (13)

On the other hand, we observe that, by (11), we have T′ ≤ 2c\sqrt{n}|U^{∗}|, and hence, using (12), we have

\frac{T}{T′} ≥ \frac{λp|U^{∗}||W |}{2c\sqrt{n}|U^{∗}|} = \frac{λ(c/\sqrt{n})σ_{0}n}{2c\sqrt{n}} = \frac{1}{2}λσ_{0}.  (14)

in every rare amalgam. Finally, we invoke Lemma 12 with the constants σ_{0}, λ, and τ above and

α = (\frac{λ}{2e})^{4/λσ_{0}} .  (15)

Lemma 12 then gives us a constant ε′ = ε′(L12) > 0.

After having done this preliminary work, we state and prove the following crucial claim.

Claim 13. A.a.s., G = G(n, p) contains no rare amalgam with parameters σ_{0}, λ, τ, and ε′.

Proof. We shall deduce this claim from Lemma 12. We start by setting

ϑ_{0} = α^{λσ_{0}/4}  and  ϑ_{1} = α^{1/2}.  (16)

Note that (16) gives that

ϑ_{1} < ϑ_{0} = \frac{λ}{2e}.  (17)

Since T ≥ (λσ_{0}/2)T′ (see (14)), we have

α^{T} = α^{T/2}α^{T/2} = ϑ_{0}^{(2/λσ_{0})T} ϑ_{1}^{T} ≤ ϑ_{0}^{T′}ϑ_{1}^{T} .  (18)

We are now ready to show that a.a.s. no rare amalgam occurs as a subgraph in G = G(n, p). We shall use the first moment method. The expected number of such subgraphs is

∑ |B(Z, U^{∗}, W; σ_{0}, λ, τ, ε′; n, T, T′)|p^{T +T′},  (19)

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

∑_{u^{∗}} ∑_{T, T′} n^{u^{∗}}n^{2σ_{0}n}α^{T} \binom{σ_{0}nu^{∗}}{T′}\binom{σ_{0}nu^{∗}}{T}p^{T′+T}

≤ ∑_{u^{∗}} ∑_{T, T′} n^{3n}ϑ_{0}^{T′}ϑ_{1}^{T} (\frac{eσ_{0}nu^{∗}}{T′} )^{T′} (\frac{eσ_{0}nu^{∗}}{T} )^{T} p^{T′+T}

= ∑_{u^{∗}} ∑_{T, T′} n^{3n} (ϑ_{0} \frac{eσ_{0}pnu^{∗}}{T′} )^{T′} (ϑ_{1} \frac{eσ_{0}pnu^{∗}}{T} )^{T}

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

≤ n^{4n} ∑_{T, T′} (\frac{1}{2})^{T +T′}

≤ n^{4n}(n^{2})^{2}2^{−ωn log n}

for some ω = ω(n) with ω → ∞ as n → ∞ (see (13)). We conclude that the expectation in (19) is o(1), and Claim 13 follows by Markov’s inequality. □

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

Let c > 0 be given. A moment’s thought shows that the almost sure property asserted 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]). To define the constant d whose existence is guaranteed in Lemma 8, we proceed as follows. Let

σ_{0} = \frac{1}{200}c^{2},  (20)
λ = \frac{1}{30}c^{2},  (21)

(22)

and

τ = min \{\frac{1}{4}λ^{2}c^{2}σ_{0}, \frac{1}{16}λ^{4}\} .  (23)

We then set

d = \frac{1}{800}λ^{2}c^{2}σ_{0}τ^{2},  (24)

and claim that this choice for d will do.

To prove our claim above, let an arbitrary 0 < ϱ ≤ 1 be given. We have to prove the existence of a suitable constant σ_{1} > 0. To this end, we first invoke Lemma 11 with the constants σ_{0}, λ, and ϱ above, to obtain a constant ε(L11) > 0. Moreover, we invoke Lemma 12 with the constants σ_{0}, λ, and τ above and

α = (\frac{λ}{2e})^{4/λσ_{0}} .  (25)

Lemma 12 then gives us a constant ε′(L12) > 0.

We now let

ε = min{ε(L11), ϱε′(L12)}.  (26)

Finally, we invoke Lemma 10 for the value of ε in (26) to obtain

σ_{1} = σ_{1}(L10) > 0.  (27)

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

For later convenience, let

ε′ = \frac{ε}{ϱ}.  (28)

Observe that, by the choice of ε′ in (28), Lemma 12 tells us that the family

B(Z, U^{∗}, W; σ_{0}, λ, τ, ε′; n, T, T′)  (29)

is ‘small’. In fact, we have already proved that, with this choice of ε′ ≤ ε′(L12), a.a.s. G(n, p) contains no rare amalgam with parameters σ_{0}, λ, τ, and ε′ (see Claim 13).

We now proceed to prove that the value of σ_{1} given in (27) will do in Lemma 8. To that end, suppose that we have a colouring E(G) = R ∪B ∪Y of G = G(n, p) with no monochromatic triangles.

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

Δ(G) ≤ 2c\sqrt{n},  (30)

and hence we shall assume that (30) holds for G. By Claim 13, we may also suppose that G contains no rare amalgam with parameters σ_{0}, λ, τ, and ε′. Finally, we may suppose that G satisfies the almost sure properties given in Lemmas 10 and 11. We shall now 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).

Clearly, we have |U| ≥ σ_{1}n, and hence condition (i) in Lemma 8 holds. Hence, the proof of Lemma 8 will be finished if we prove the following fact.

Fact 14. The graph I[U] is (ϱ, d)-dense.

Proof. Our proof strategy has already been unveiled just after the statement of Lemma 11. Here we give all 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] = B_{U}(J_{0}) is (ϱ, τ)-dense.

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

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

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

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

and

|(B_{U}(J_{0}) ∩ B_{U}(J_{1})) ∩ [U^{∗}]^{2}| < d\binom{|U^{∗}|}{2}.  (32)

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})|.

Since (Z, U) and (U, W) are (p, λ; J, ε)-semi-regular, by the choice of ε′ (see (28)) and (31), we have that (Z, U^{∗}) and (U^{∗}, W) are (p, λ; H, ε′)-semi-regular.

We already know that B_{U}(J_{0}) is (ϱ, τ)-dense, so that

|B_{U^{∗}}(H_{0})| = |B_{U}(J_{0}) ∩ [U^{∗}]^{2}| ≥ τ\binom{|U^{∗}|}{2}.  (33)

However, we may deduce from (32) that

|B_{U^{∗}}(H_{0}) ∩ B_{U^{∗}}(H_{1})| = |(B_{U}(J_{0}) ∩ B_{U}(J_{1})) ∩ [U^{∗}]^{2}| < d\binom{|U^{∗}|}{2}.

The crucial observation now is that the graph H is a rare amalgam with parameters σ_{0}, λ, τ, and ε′. Indeed, it only remains to check (10) and (11). Both are clear: we have |U^{∗}| = ϱ|U| ≥ ϱσ_{1}n ≫ n/ log n, and hence (10) does hold. Inequality (11) follows trivially, as Δ(H) ≤ Δ(G) ≤ 2c\sqrt{n} (see (30)).

We have reached a contradiction, for we supposed that G contains no rare amalgam with the parameters above. This contradiction completes the proof of Fact 14. □

As observed before, Fact 14 completes 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 λ|E(G)| for some fixed λ > 0. We wish to show that Base(F) contains cn^{3} triangles, for some constant c > 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 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 (ϱ, d)-dense, induced subgraph with at least σn vertices, where ϱ, d, and σ are certain positive constants. It now follows from Lemma 9 that Base(F) must contain cn^{3} triangles, for some constant c, as required in Lemma 2.

4.3. Proof of the auxiliary lemmas. The three auxiliary lemmas stated in Section 4.1 are proved in the first three subsections of this section. However, the hardest of the lemmas to prove, Lemma 12, will be deduced from a new auxiliary lemma (Lemma 23), which is proved in the last subsection of this section.

4.3.1. Proof of Lemma 10. We start with two basic lemmas.

Lemma 15. Let G be a graph on k ≥ 1 vertices and at least γ\binom{k}{2} edges, where 0 < γ ≤ 1. Then there is a set of vertices Y ⊆ V (G) with

|Y | ≥ \frac{1}{2}γk + 1  (34)

and so that the graph G[Y] induced by Y in G has minimum degree

δ(G[Y]) ≥ \frac{1}{2}γk.  (35)

In particular, the number of vertices of degree at least γk/2 in G is at least γk/2 + 1.

Proof. The result holds if k ≤ 2/γ, and hence we suppose k > 2/γ. Pick a subset Y ⊆ V (G) with |Y | ≥ 2 that maximizes the ratio |E(G[Y])|/(|Y |−1). Put ℓ = |E(G[Y])| and y = |Y |. By the choice of Y, we have

\frac{ℓ}{y − 1} ≥ \frac{γ}{k − 1}\binom{k}{2} = \frac{1}{2}γk.  (36)

This implies that ℓ ≥ (γ/2)k > 1, and hence y > 2. Let v be a vertex in Y, and write d for its degree in G[Y]. Then, by the choice of Y, considering the subgraph G[Y \ {y}] (recall |Y | = y > 2 and hence |Y \ {y}| ≥ 2), we see that

\frac{ℓ}{y − 1} ≥ \frac{|E(G[Y \ \{y\}])|}{y − 2} = \frac{ℓ − d}{y − 2}.

This implies that d ≥ ℓ/(y − 1) ≥ γk/2 (recall (36)). Therefore, (35) holds. Clearly, inequality (35) implies (34). □

Lemma 16. Suppose k ≥ 1 and

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

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

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

and

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

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 our colouring (37). For C = R and B, let

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

By Lemma 15, we have |U_{R}|, |U_{B}| ≥ γk/2 + 1 ≥ γ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}| − |T |) .

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{|T |}{|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 now recall Szemerédi’s well-known regularity lemma [23] (see also [12, Section 8.3]). Since we are dealing with sparse graphs (that is, graphs with a subquadratic number of edges), we shall make use of a suitable 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 we have been dealing with a ‘one-sided’ version of regularity, namely, ‘semi-regularity’. Note 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 | − ε.

When dealing with regular pairs, the following simple observation is often useful.

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

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, ⌊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, 15, 16]).

Lemma 18. 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.

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}.  (40)

Put

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

Let

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

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

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

and claim that this choice for σ_{1} 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 number of triangles in G is a.a.s. (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 show that, by Chebyshev’s inequality, the number of diamonds as above 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 (5) 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}.  (44)

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,  (45)

and

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

Moreover, we may suppose that G and all its subgraphs are (p; 2, β)-bounded.

Let us now apply Lemma 18 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 19. Suppose F ⊆ E(G) is a subset of edges of G = G(n, p), with |F | ≥ λ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}λp (\frac{n}{k})^{2} .  (47)

Then

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

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

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

and so

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

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

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

pairs (V_{i}, V_{j}) are (p; F, δ)-regular, each satisfying (47); that is, the set Φ satisfies (48), 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} .  (49)

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

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

Since

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

the fact that (45) 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 (41)) 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}.  (51)

We now apply Lemma 16 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 (50) and (51), we may apply Lemma 16 with γ = c^{2}/25. We then obtain i_{0} ∈ [k] = V (K_{k}) and two disjoint sets J′_{C} ⊆ [k] (C = R and B, say) with

|J′_{C}| ≥ \frac{1}{8} (\frac{1}{25}c^{2}) k = \frac{1}{200}c^{2}k,  (52)

such that, for all j ∈ J′_{C}, we have that

(V_{i_{0}}, V_{j}) is (p; C, δ)-regular  (53)

and

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

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

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

and let

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

Claim 20. 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)} = σ_{1}n.

Property (ii) asserted in Lemma 10 is clear from the definition of J (see (55)). We are now left with proving (iii), that is, that (Z, U) and (U, W) are (p, λ; 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} = λ.  (56)

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

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

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

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

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

Indeed,

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

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

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

as δ ≤ ε^{2} (see (41)). It follows from (59) that (58) does indeed hold.

We now go back to (57). Clearly, the right-hand side of (57) is, by (53), (54), and (58), at least

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

≥ (\frac{1}{28}c^{2} − δ) (1 − ε) ≥ \frac{1}{30}c^{2}.

We have thus concluded that (56) does indeed hold, as required. This concludes the proof that (Z, U) is (p, λ; J, ε)-semi-regular, and the proof of Claim 20 is complete. □

Claim 20 completes the proof of Lemma 10. □

4.3.2. Proof of Lemma 11. We start by stating the following upper tail estimate from [21]. We give this result in a very general form. Given a finite set Γ and 0 < p < 1, we denote by Γ_{p} a random binomial subset of Γ. Note that ([n]^{2})_{p} is nothing else but the random graph G(n, p). Let S ⊆ [Γ]^{s} and set μ = 𝔼|{S ∈ S: S ⊆ Γ_{p}}|.

Lemma 21. For all q and t > 0, with probability at least

1 − exp \{−\frac{qt}{s(μ + t)}\}

there is E_{0} ⊆ Γ_{p} with |E_{0}| = q such that Γ_{p} \ E_{0} contains fewer than μ + t sets from S.

The above lemma implies the following result.

Corollary 22. For every c > 0, a.a.s., for each pair U, W ⊆ [n] with U ∩W = ∅, there exists E_{0} = E_{0}(U, W) ⊆ E(G(n, c/\sqrt{n})) with |E_{0}| = n log n such that the bipartite subgraph of G(n, c/\sqrt{n}) \ E_{0} spanned between the sets U and W contains no more than

2\binom{|U|}{2}\binom{|W |}{2}\frac{c^{4}}{n^{2}}

copies of the 4-cycle C_{4}.

Proof. Apply Lemma 21 to Γ = U × W and S, the family of the edge sets of all 4-cycles in Γ, with s = 4, p = c/\sqrt{n}, q = n log n, and

t = μ = \binom{|U|}{2}\binom{|W |}{2}\frac{c^{4}}{n^{2}} .

We omit the easy calculations. □

For more about upper tail estimates, see [14], and for further developments of the above deletion technique, see [13].

We are now ready to plunge into the proof of Lemma 11.

Proof of Lemma 11. Let σ_{0}, λ, and ϱ be given. We claim that ε = min{1/18, ϱ} will do. Let U′ ⊆ U be an arbitrary subset of U with

|U′| = ϱ|U| ≥ ε|U|.

We shall show that B_{U}(J_{0}) induces at least d′\binom{|U′|}{2} edges within U′ (see (6)), and this will prove Lemma 11.

We first observe that, by the (p, λ; J_{0}, ε)-semi-regularity of (Z, U), at least (1 − ε)|Z| = (1 − ε)σ_{0}n vertices in Z send at least λp|U′| = λpϱ|U| edges into U′.

By Corollary 22, we may suppose that we may drop a set of edges E_{0} from J_{0}, with |E_{0}| ≤ n log n, so as to guarantee that the number of 4-cycles left within Z ∪ U′ is at most

\binom{|Z|}{2}\binom{|U′|}{2}\frac{c^{4}}{n^{2}} ≤ \frac{1}{2}c^{4}σ_{0}^{2}ϱ^{2}u^{2},  (60)

where u = |U|. In what follows, we work with the graph J′_{0} = J_{0} \ E_{0}. Note that the number of vertices in Z that are incident to at least n^{1/3} log n edges in E_{0} is at most n^{2/3}. Therefore, for large enough n, at least (1−3ε/2)|Z| = (1 − 3ε/2)σ_{0}n vertices in Z send at least (3/4)λpϱu edges into U′ in J′_{0}.

Suppose the \binom{|U′|}{2} pairs within U′ are e_{1}, …, e\binom{|U′|}{2}. Let x_{i} be the number

of vertices in Z that send edges to both endvertices of e_{i} in J′_{0} for all 1 ≤ i ≤ \binom{|U′|}{2}. Clearly, the graph B_{U}(J′_{0}) ⊆ B_{U}(J_{0}) induces as many edges within U′ as there are indices i for which x_{i} > 0. Adjust the notation so that x_{i} > 0 for 1 ≤ i ≤ N and x_{i} = 0 for i > N. It will suffice to show that

N ≥ d′\binom{|U′|}{2}.  (61)

For large enough n, we have

∑_{1≤i≤N} x_{i} = ∑_{z∈Z} \binom{deg_{J′_{0}}(z)}{2}

≥ \frac{1}{2}(1 − 2ε)σ_{0}n (\frac{3}{4})^{2} λ^{2}p^{2}ϱ^{2}u^{2} ≥ \frac{1}{4}λ^{2}c^{2}σ_{0}ϱ^{2}u^{2}. (62)

Let us now observe that the number of C_{4} in J′_{0}[Z, U′] is

∑_{1≤i≤N} \binom{x_{i}}{2}.

By (60), we have that

∑_{1≤i≤N} \binom{x_{i}}{2} ≤ \frac{1}{2}c^{4}σ_{0}^{2}ϱ^{2}u^{2}.  (63)

On the other hand, by the Cauchy–Schwarz inequality, we have that

∑_{1≤i≤N} \binom{x_{i}}{2} ≥ N\binom{N^{−1} ∑_{1≤i≤N} x_{i}}{2}

= \frac{1}{2}( ∑_{1≤i≤N} x_{i})(\frac{1}{N} ∑_{1≤i≤N} x_{i} − 1). (64)

We now analyse two cases. Suppose first that ∑_{1≤i≤N} x_{i} ≤ 2N. Then, by (62), we have

N ≥ \frac{1}{2} ∑_{1≤i≤N} x_{i} ≥ \frac{1}{8}λ^{2}c^{2}σ_{0}ϱ^{2}u^{2} ≥ \frac{1}{4}λ^{2}c^{2}σ_{0}\binom{|U′|}{2}.  (65)

Suppose now that, on the contrary, we have ∑_{1≤i≤N} x_{i} > 2N. Then, by (62) and (64), we have

∑_{1≤i≤N} \binom{x_{i}}{2} ≥ \frac{1}{4N} ( ∑_{1≤i≤N} x_{i})^{2} ≥ \frac{1}{64N} λ^{4}c^{4}σ_{0}^{2}ϱ^{4}u^{4}.  (66)

Comparing (63) and (66), we deduce that

\frac{1}{64N} λ^{4}c^{4}σ_{0}^{2}ϱ^{4}u^{4} ≤ \frac{1}{2}c^{4}σ_{0}^{2}ϱ^{2}u^{2},

whence

N ≥ \frac{1}{32}λ^{4}ϱ^{2}u^{2} ≥ \frac{1}{16}λ^{4}\binom{|U′|}{2}.  (67)

Lemma 11 follows from (65) and (67). □

4.3.3. Proof of Lemma 12. In order to prove Lemma 12, we shall make use of a further auxiliary lemma, Lemma 23 below. Let us introduce some notation to state this lemma.

Let U^{∗} and W be two disjoint sets of vertices. Suppose F ⊆ [U^{∗}]^{2} is a collection of pairs of vertices in U^{∗}. For convenience, we shall often refer to the graph with vertex set U^{∗} and edge set F as F as well. Suppose now that we have constants

σ_{0}, λ, τ, and ε′ > 0

and integers

n and T .

Suppose further that (i) |W | = σ_{0}n and u^{∗} = |U^{∗}| ≥ n/ log n, (ii) |F | = τ\binom{|U^{∗}|}{2} = τ\binom{u^{∗}}{2}.

We now let

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

be the family of bipartite graphs H = (U^{∗}, W; E) satisfying the following conditions:

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

|F ∩ B_{U^{∗}}(H)| < \frac{1}{800}λ^{2}σ_{0}c^{2}τ|F |.  (69)

We are finally ready to state our auxiliary lemma, the formulation of which is based on the notation and definitions introduced above.

Lemma 23. Let any positive constants σ_{0}, λ, τ, and α ≤ 1 be given. Then there exist constants ε′ > 0 and n_{0} such that, with the notation as above, for all n ≥ n_{0} and all T, we have

|B(U^{∗}, W; F; σ_{0}, λ, τ, ε′; n, T)| ≤ α^{T} \binom{|U^{∗}||W |}{T}.

As observed immediately after its statement, Lemma 12 may be thought of as an assertion concerning the uniform space of certain amalgams. Lemma 23 is a statement concerning the uniform space of the bipartite graphs with vertex classes U^{∗} and W. Indeed, this lemma asserts that a random element of this space is extremely unlikely to be member of the family in (68).

The proof of Lemma 23 is postponed to Section 4.3.4. We shall now see that Lemma 12 follows from Lemma 23 almost immediately.

Proof of Lemma 12. Let σ_{0}, λ, τ, and α as in the statement of Lemma 12 be given. We feed these constants to Lemma 23, and obtain a constant ε′ > 0; we claim that this ε′ will do in Lemma 12. We prove this claim as follows.

For any graph

H ∈ B_{1} = B(Z, U^{∗}, W; σ_{0}, λ, τ, ε′; n, T, T′),  (70)

we let H_{0} = H[Z, U^{∗}] and H_{1} = H[U^{∗}, W]. We may count the graphs as in (70) by estimating the number of H_{0} that we have, 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_{1}.

We estimate the number of graphs H_{0} trivially, by saying that there are at most

\binom{|Z||U^{∗}|}{T′}  (71)

such graphs. Let us now fix a graph H_{0} = (Z, U^{∗}; E_{0}) satisfying the conditions (i)–(iv) in the definition of the family B_{1}. Moreover, let

F ⊆ B_{U^{∗}}(H_{0})

with |F | = τ\binom{|U^{∗}|}{2} be fixed. We now make the following claim.

Claim 24. If H_{1} = (U^{∗}, W; E_{1}) is so that H = H_{0} ∪ H_{1} is a member of B_{1}, then

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

Proof. We have |W | = σ_{0}n and |F | = τ\binom{|U^{∗}|}{2}. Conditions (i) and (ii) in the definition of B_{0} clearly hold for H_{1}. To check condition (iii), we observe that, in view of (9), we have

|F ∩ B_{U^{∗}}(H_{1})| ≤ |B_{U^{∗}}(H_{0}) ∩ B_{U^{∗}}(H_{1})|

< \frac{1}{800}λ^{2}σ_{0}c^{2}τ^{2}\binom{|U^{∗}|}{2} = \frac{1}{800}λ^{2}σ_{0}c^{2}τ|F |.

Therefore (69) holds and so does condition (iii) in the definition of B_{0}. We conclude that (72) holds. □

It now suffices to put together the bound in (71), Lemma 23, and Claim 24 to deduce that the number of graphs H as in (70) is at most

α^{T} \binom{|Z||U^{∗}|}{T′}\binom{|W ||U^{∗}|}{T},

as required. □

4.3.4. Proof of Lemma 23. In this somewhat long section, we shall prove Lemma 23, the crucial lemma in the proof of Lemma 12. We warn the reader that this will be a fairly technical proof. The basic underlying idea in this proof comes from a lemma in [17, Lemma 11] (see also [12, Lemma 8.30]).

We start by letting arbitrary positive constants σ_{0}, λ, τ, and α as in the statement of Lemma 23 be given. To prove Lemma 23, we need to define an appropriate constant ε′ > 0. Put

α_{0} = \frac{1}{2}α^{48/λτσ_{0}},  (73)
ε^{∗∗} = min \{\frac{1}{2}τ exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\} , \frac{1}{4}α_{0}^{2}e^{−8c^{2}/σ_{0}}\} ,  (74)

and let

ε′ = \frac{1}{2}τε^{∗∗}.  (75)

We claim that this choice for ε′ will do in Lemma 23. Our task for the remainder of this section is to justify this claim.

For later reference, we observe that the following inequalities hold:

ε^{∗∗} = 2\frac{ε′}{τ} ≤ \frac{1}{2},  (76)
ε^{∗∗} ≤ \frac{1}{2}τ exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\} ,  (77)
2e^{4c^{2}/σ_{0}} \sqrt{ε^{∗∗}} ≤ α_{0},  (78)

and

(2α_{0})^{λτσ_{0}/48} ≤ α.  (79)

Recall that we wish to estimate the number of bipartite graphs H = (U^{∗}, W; E) in

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

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

Lemma 25. Suppose H ∈ B_{0}. Then H contains two edge-disjoint subgraphs H_{0} = (U^{∗}, W; E_{0}) and H_{1} = (U^{∗}, W; E_{1}) such that

H = H_{0} ∪ H_{1},  (80)

and so that the pair (U^{∗}, W) is (p, λ/3; H_{i}, ε′)-semi-regular for both i = 0 and i = 1. Moreover, we have |E(H_{0})| = |E(H_{1})| = T/2.

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_{0}, we fix a decomposition as in (80). We shall now invoke Lemma 15, which tells us that, roughly speaking, any dense graph contains a large subgraph with large minimum degree. We explicitly state the result of an application of Lemma 15 to F as a fact.

Fact 26. There exists a set U^{∗∗} ⊆ U^{∗} for which we have

(i) δ(F [U^{∗∗}]) ≥ τu^{∗}/2, that is, the minimum degree of the graph F [U^{∗∗}] induced by U^{∗∗} in F is at least τu^{∗}/2,

(ii) u^{∗∗} = |U^{∗∗}| ≥ τu^{∗}/2 + 1.

Proof. This follows immediately from Lemma 15 applied to the graph F. □

For the remainder of our proof, we fix U^{∗∗} as in Fact 26. The following observation is clear.

Fact 27. Let H_{i}^{∗∗} = H_{i}[U^{∗∗}, W] (i ∈ {0, 1}) be the subgraph of H_{i} induced by U^{∗∗} ∪ W. Recall ε^{∗∗} = 2ε′/τ. Then (U^{∗∗}, W) is (p, λ/3; H_{i}^{∗∗}, ε^{∗∗})-semi-regular for both i = 0 and i = 1.

Proof. It suffices to recall that |U^{∗∗}| ≥ τu^{∗}/2 and that the pair (U^{∗}, W) is (p, λ/3; H_{i}, ε′)-semi-regular (i ∈ {0, 1}). □

Recall that if J is a graph and x is a vertex of J, then we write

N(J; x) = N_{J}(x)

for the neighbourhood of x in J.

Remark 28. We observe that N(H_{i}^{∗∗}; v) = N(H_{i}; v) for any v ∈ U^{∗∗} and i ∈ {0, 1}. Also, clearly, we have N(H_{i}^{∗∗}; w) ⊆ N(H_{i}; w) for any w ∈ W and i ∈ {0, 1}.

We now need to fix some notation. We let

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

Moreover, we let

F_{i} = N(F; v_{i}) ∩ U^{∗∗} ⊆ U^{∗∗}  (82)

be the neighbourhood of v_{i} in the graph F [U^{∗∗}]. Because of our choice of U^{∗∗} in Fact 26, we have

|F_{i}| ≥ δ(F [U^{∗∗}]) ≥ f = \frac{1}{2}τu^{∗}  (83)

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

We now define a concept that will be important in the proof that follows. Let sets F^{∗} ⊆ U^{∗∗} and W_{0} ⊆ W be given. We put

F̃^{∗} = F^{∗} \ ⋃_{w∈W_{0}} N(H_{0}; w).  (84)

We shall say that W_{0} is bad with respect to F^{∗} if

|F̃^{∗}| ≥ |F^{∗}| exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\} .  (85)

Roughly speaking, W_{0} is bad with respect to F^{∗} if the H_{0}-neighbourhood of W_{0} ‘bites out’ too little from F^{∗}. (We remark in passing that we shall be applying this definition for ‘large’ sets W_{0}, namely, sets W_{0} with |W_{0}| ≥ λp|W |/3.)

Next, we let d_{i} (1 ≤ i ≤ u^{∗∗}) be the degree of v_{i} in the graph H_{1}^{∗∗} = H_{1}[U^{∗∗}, W], or, equivalently, in H_{1}. Recalling that (U^{∗∗}, W) is (p, λ/3; H_{1}^{∗∗}, ε^{∗∗})- semi-regular and that

ε^{∗∗} ≤ \frac{1}{2}

(cf. (76)), we may suppose that

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

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

W^{(i)} = N(H_{1}^{∗∗}; v_{i}) = N(H_{1}; v_{i}) = {w_{1}^{(i)}, …, w_{d_{i}}^{(i)}}  (87)

for all 1 ≤ i ≤ u^{∗∗}/2. We shall say that v_{i} (1 ≤ i ≤ u^{∗∗}/2) is bad if W^{(i)} is bad with respect to F_{i} = N(F; v_{i}) ∩ U^{∗∗}.

Proof strategy, main claims, and the proof. We now briefly discuss what we are aiming at. Recall that we are considering

H ∈ B_{0} = B(U^{∗}, W; F; σ_{0}, λ, τ, ε′; n, T).  (88)

We shall use the fact that Base(H) does not contain too many edges from F. Explicitly, we shall use that not too many edges {a, b} ∈ F are such that there is a vertex w ∈ W with both {a, w} and {w, b} edges in H (see (69)). Note that if w ∈ N(H_{1}^{∗∗}; a) and b ∈ N(H_{0}^{∗∗}; w), then {a, b} belongs to Base(H) = Base(H_{0} ∪ H_{1}). The neighbourhood W_{0} = N(H_{1}^{∗∗}; a) = N(H_{1}; a) of a in H_{1} is bad with respect to F^{∗} if

F̃^{∗} = F^{∗} \ ⋃_{w∈W_{0}} N(H_{0}; w).

is large or, equivalently, the neighbourhood

F^{∗} ∩ ⋃_{w∈W_{0}} N(H_{0}; w)

of W_{0} within F^{∗} = N(F; a) ∩ U^{∗∗} in H_{0} is small. The vertex a is bad if its neighbourhood W_{0} is bad. Roughly speaking, these definitions make it so that a is bad if too few edges from F incident to a belong to Base(H).

Since globally H is such that only a small number of edges from F belong to Base(H), it must be that many vertices a are incident to too few edges from F ∩ Base(H), and hence there are many bad vertices a.

We shall estimate from above the number of graphs H as in (88) by proving that, if H_{0} is fixed, then the great majority of sets W_{0} ⊆ W are good, and hence it is very atypical for a vertex a ∈ U^{∗∗} to be bad. However, since many vertices a must be bad in H, this will tell us that H_{1}^{∗∗} must be quite a peculiar graph. This will imply a strong bound on the number of graphs H_{1}^{∗∗}. Summing over all choices for H_{0}, we shall still have a strong bound on the number of graphs H as in (88).

The following two claims make precise the ideas sketched above. Recall that H as in (88) is fixed, and our notation is so that (86) holds.

Claim 29. For all 1 ≤ i ≤ u^{∗∗}/2, the number of subsets W_{0} of W with cardinality d_{i} = |N(H_{1}; v_{i})| that are bad with respect to F_{i} is at most

α_{0}^{d_{i}} \binom{|W |}{d_{i}}.  (89)

Claim 30. More than u^{∗∗}/4 vertices v_{i} with 1 ≤ i ≤ u^{∗∗}/2 are bad.

We complete the proof of Lemma 23 assuming Claims 29 and 30 above.

Completion of the proof of Lemma 23. Suppose H as in (88) is given.

(a) In view of Lemma 25, we may decompose H as a union H_{0} ∪ H_{1}, where both H_{i} (i ∈ {0, 1}) are such that (U^{∗}, W) is (p, λ/3; H_{i}, ε′)- semi-regular, and |E(H_{0})| = |E(H_{1})| = T/2.

(b) In view of Facts 26 and 27, we know that there is a set U^{∗∗} ⊆ U^{∗} satisfying (i) and (ii) of Fact 26, and such that (U^{∗∗}, W) is (p, λ/3; H_{i}^{∗∗}, ε^{∗∗})-semi-regular for H_{i}^{∗∗} = H_{i}[U^{∗∗}, W] for both i ∈ {0, 1}.

Using (a) and (b) above, we may estimate the cardinality of

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

as follows. We ‘generate’ the members H ∈ B_{0} in steps, as outlined below. (1) We first fix H_{0}, as in (a).

(2) We then define U^{∗∗} using F (see Fact 26).

(3) We generate H_{1} in two stages:

(a) We first fix a partition T/2 = T^{∗∗} + (T/2 − T^{∗∗}) of the number of edges T/2 that we want in our graph H_{1}.

(b) We then generate H_{1}^{∗∗} = H_{1}[U^{∗∗}, W] = (U^{∗∗}, W; E^{∗∗}), with

|E^{∗∗}| = T^{∗∗}.
(c) We finally generate H_{1} − E^{∗∗}.

In order to estimate |B_{0}| from above, we estimate the number of ways the steps above may be carried out. (Note that we did not require that H_{0} and H_{1} above be disjoint. Since we are after an upper bound for |B_{0}|, this is justified.)

Let us focus on Step 3b in the procedure above. We start by fixing a degree sequence d = {d(v): v ∈ U^{∗∗}} for the vertices in U^{∗∗} in the graph H_{1}^{∗∗}. To generate H^{∗∗}, it suffices to pick a member of the product

∏ {[W]^{d(v)} : v ∈ U^{∗∗}}.  (90)

We shall use Claims 29 and 30 to estimate how many members from (90) are ‘valid’ choices (i.e., choices that correspond to graphs H_{1}^{∗∗} that may be completed to graphs H_{1} with H = H_{0} ∪ H_{1} ∈ B_{0}).

Fact 31. The number of elements of (90) that correspond to valid graphs H_{1}^{∗∗} is at most

2^{u^{∗∗}}α_{0}^{D} ∏ \{\binom{|W |}{d(v)}: v ∈ U^{∗∗}\} ,  (91)

where D = (1/12)λpu^{∗∗}|W |.

Proof. The factor 2^{u^{∗∗}} takes care of all the possibilities for which vertices in U^{∗∗} are bad. We ‘gain’ the factor α^{D} in the estimate (91) because Claim 30 tells us that at least u^{∗∗}/4 vertices in U^{∗∗} are bad, and each bad vertex v must have a neighbourhood that is chosen from at most

α_{0}^{d(v)}\binom{|W |}{d(v)}

many possibilities (cf. (89) in Claim 29). Therefore we ‘gain’ a factor of

∏{α_{0}^{d(v)} : v is a bad vertex} ≤ α_{0}^{D},

where D = (u^{∗∗}/4)(λ/3)p|W | = (1/12)λpu^{∗∗}|W | (cf. (86)), and Fact 31 is proved. □

To estimate the quantity in (91), 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)λpu^{∗∗}|W |}{2c\sqrt{n}u^{∗}} ≥ \frac{1}{48}λτσ_{0}.

Therefore (91) is at most

2^{u^{∗∗}}α_{0}^{(λτσ_{0}/48)T} ∏ \{\binom{|W |}{d(v)}: v ∈ U^{∗∗}\} .  (92)

We now sum (92) over all choices for d = {d(v): v ∈ U^{∗∗}} and over all choices for U^{∗∗} ⊆ U^{∗}. Recalling that d is a partition of T^{∗∗}, we see that this sum is at most

2^{u^{∗}+u^{∗∗}}α_{0}^{(λτσ_{0}/48)T} \binom{|W ||U^{∗∗}|}{T^{∗∗}}.  (93)

We now sum (93) over all choices for T^{∗∗} and over all choices for H_{1} − E^{∗∗} (see Step 3c). This gives us at most

2^{u^{∗}+u^{∗∗}}α_{0}^{(λτσ_{0}/48)T} \binom{|W ||U^{∗}|}{T} ≤ 2^{2u^{∗}}α_{0}^{(λτσ_{0}/48)T} \binom{|W ||U^{∗}|}{T}.  (94)

Also (cf. (12) and (13)), we have

T ≥ λpu^{∗}|W | = λcσ_{0}u^{∗}\sqrt{n} ≫ u^{∗} log u^{∗}.  (95)

Inequality (95) gives us that (94) is at most

(2α_{0})^{(λτσ_{0}/48)T} \binom{|W ||U^{∗}|}{T} ≤ α^{T} \binom{|W ||U^{∗}|}{T},  (96)

where the inequality above follows from (79). Lemma 23 follows from (96).

□

Proof of the claims. We are now left with proving Claims 29 and 30.

Proof of Claim 29. Fix 1 ≤ i ≤ u^{∗∗}/2. For simplicity, put F^{∗} = F_{i} = N(F; v_{i}) ∩ U^{∗∗} and let d = d_{i} = |N(H_{1}; v_{i})|. Let W_{0} ⊆ W be a d-element subset of W and fix and ordering w_{1}, …, w_{d} of the elements of W_{0}. We define a sequence

F^{∗} = F^{(0)} ⊇ ⋯ ⊇ F^{(d)} = F̃^{∗} = F^{∗} \ ⋃_{w∈W_{0}} N(H_{0}; w)  (97)

of decreasing subsets of W, putting

F^{(j)} = F^{(j−1)} \ N(H_{0}; w_{j}) = F^{∗} \ ⋃_{1≤k≤j} N(H_{0}; w_{k}),  (98)

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

|F^{(j)}|/|F^{(j−1)}|  (99)

the shrinking factor at j (1 ≤ j ≤ d). Observe that this factor depends only on the sequence w_{1}, …, w_{j}. Moreover, note that we like small shrinking factors; if we have many indices j with small shrinking factors, then W_{0} is likely to be a good set, because F̃^{∗} is likely to be a small set. We make this remark precise in what follows.

Suppose W_{0} is a bad set with respect to F^{∗} = F_{i} = N(F; v_{i}) ∩ U^{∗∗}.

Fact 32. The number of indices j with shrinking factor less than 1 − λp/3 at j is smaller than d/2.

Proof. Suppose for a contradiction that we have at least d/2 indices j with shrinking factor less than 1 − λp/3. Then

|F̃^{∗}| = |F^{(d)}| < |F^{∗}| (1 − \frac{1}{3}λp)^{d/2} ≤ |F^{∗}| exp \{−\frac{1}{6}λpd\} .  (100)

Recall that p = cn^{−1/2} and d = d_{i} ≥ (λ/3)p|W | = (λ/3)pσ_{0}n (see (86)). We may deduce from (100) that

|F̃^{∗}| < |F^{∗}| exp \{−\frac{1}{6}λ^{2}p^{2}σ_{0}n\} = |F^{∗}| exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\} ,  (101)

contradicting the assumption that W_{0} is bad with respect to F^{∗} (cf. (85) and (101)). □

Let us now fix 1 ≤ j ≤ d. When is the shrinking factor at j poor? More precisely, when is this shrinking factor at least 1 − λp/3? This is the case if and only if

|N(H_{0}; w_{j}) ∩ F^{(j−1)}| ≤ \frac{1}{3}λp|F^{(j−1)}|.  (102)

We shall now argue that (102) is atypical; that is, if (102) holds, then w_{j} is an ‘atypical vertex’.

Since W_{0} is a bad set with respect to F^{∗} = F_{i} and (77) and (83) hold, we have

|F^{(j−1)}| ≥ |F̃^{∗}| ≥ |F^{∗}| exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\} ≥ f exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\}

≥ (\frac{1}{2}τ exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\}) u^{∗} ≥ ε^{∗∗}|U^{∗∗}|. (103)

Recalling that (U^{∗∗}, W) is (p, λ/3; H_{0}^{∗∗}, ε^{∗∗})-semi-regular, we see that (103) implies that the number of vertices w ∈ W with

|N(H_{0}; w) ∩ F^{(j−1)}| < \frac{1}{3}λp|F^{(j−1)}|

is smaller than ε^{∗∗}|W |. We have proved the following fact.

Fact 33. For every w_{1}, …, w_{j−1} ∈ W, there is a set W^{(j)} ⊆ W of cardinality less than ε^{∗∗}|W | such that if the shrinking factor at j for the sequence

w_{1}, …, w_{j−1}, w_{j}

is at least 1 − λp/3, then w_{j} ∈ W^{(j)}.

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 poor shrinking factor, that is, with shrinking factor at least 1 − λp/3. Fact 33 implies that

|W^{×}| ≤ 2^{d}(ε^{∗∗})^{d/2}|W |^{d}.  (104)

Now let W ⊆ [W]^{d} be the set of d-element subsets of W that are bad with respect to F^{∗}. We wish to show that |W| satisfies (89).

Fact 32 implies that, 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 (104) give that

d!|W| ≤ |W^{×}| ≤ 2^{d}(ε^{∗∗})^{d/2}|W |^{d},  (105)

and hence, using that d ≤ 2c\sqrt{n} (see (86)), for large enough n we have

|W| ≤ 2^{d}(ε^{∗∗})^{d/2} \frac{|W |^{d}}{d!} ≤ 2^{d}(ε^{∗∗})^{d/2}e^{d^{2}/|W |}\binom{|W |}{d}

≤ 2^{d}(ε^{∗∗})^{d/2}e^{4c^{2}/σ_{0}} \binom{|W |}{d} ≤ α_{0}^{d}\binom{|W |}{d}, (106)

where in the last inequality we used (78). Clearly, Claim 29 follows from (106). □

Proof of Claim 30. Suppose for a contradiction that the number of vertices v_{i} (1 ≤ i ≤ u^{∗∗}/2) that are bad is at most u^{∗∗}/4. Therefore,

(*) the number of vertices v_{i} (1 ≤ i ≤ u^{∗∗}/2) that are not bad is at

least u^{∗∗}/4. Suppose v_{i} is a vertex that is not bad, where 1 ≤ i ≤ u^{∗∗}/2. This means that W_{0} = N(H_{1}^{∗∗}; v_{i}) = N(H_{1}; v_{i}) is not bad, that is, the neighbourhood

F_{i} ∩ ⋃_{w∈W_{0}} N(H_{0}; w)

of W_{0} within F_{i} = N(F; v_{i}) ∩ U^{∗∗} in H_{0} has cardinality greater than

(1 − exp \{−\frac{1}{18}λ^{2}c^{2}σ_{0}\}) |F_{i}| ≥ \frac{1}{50}λ^{2}c^{2}σ_{0}f,  (107)

where we used that |F_{i}| ≥ f and that x = (1/18)λ^{2}c^{2}σ_{0} ≤ 1/2, and hence 1 − e^{−x} ≥ x/2, say. However, this means that v_{i} contributes to F ∩ B_{U^{∗}}(H) at least as many pairs as in (107) (with some pairs counted twice, when we consider all the vertices v_{i}). Recalling (*) and Fact 26(ii), we see that

|F ∩ B_{U^{∗}}(H)| ≥ \frac{1}{4}u^{∗∗} × \frac{1}{2} (\frac{1}{50}λ^{2}c^{2}σ_{0}f)

≥ \frac{1}{400} × \frac{1}{2}τu^{∗} × λ^{2}c^{2}σ_{0}f = \frac{1}{800}λ^{2}c^{2}σ_{0}τu^{∗}f. (108)

Recall now that f = τu^{∗}/2; we may then deduce from (108) that

|F ∩ B_{U^{∗}}(H)| ≥ \frac{1}{1600}λ^{2}c^{2}σ_{0}τ^{2}(u^{∗})^{2}

≥ \frac{1}{800}λ^{2}c^{2}σ_{0}τ^{2}\binom{u^{∗}}{2} = \frac{1}{800}λ^{2}c^{2}σ_{0}τ|F |. (109)

Note that (109) is in contradiction to the fact that H ∈ B_{0} (see (69) and (88)). We conclude that (*) must fail, and hence that the number of vertices v_{i} (1 ≤ i ≤ u^{∗∗}/2) that are bad exceeds u^{∗∗}/4. Claim 30 is proved. □

5. 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 graph H, the interesting range for N_{0} is around the classical 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} (see [21]).

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 most interesting question is if 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 [18]. 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 [22].

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 5

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

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 5 4. , Deterministic graph games and a probabilistic intuition, Combin. Probab.

Comput. 3 (1994), no. 1, 13–26. MR 95h:90191 5

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 5

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 5

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

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, 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, 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, 4.3.1, 4.3.1, 4.3.4

13. Svante Janson and Andrzej Ruciński, The deletion method for upper tail estimates, 30pp, submitted, 2000. 4.3.2

14. , The infamous upper tail, Random Structures Algorithms 20 (2002), no. 3, 317–342. 4.3.2

15. Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216–230. MR 99g:05145 4.3.1

16. 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. 4.3.1

17. 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 4.3.4

18. Andrzej Kurek and Andrzej Ruciński, The sparsest Ramsey graphs are complete graphs, submitted, 2002. 2, 5

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

20. 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.2

21. , Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942. MR 96h:05141 4, 4.3.2, 5

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

23. 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 4.3.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