ESSENTIALLY INFINITE COLOURINGS OF GRAPHS

B. BOLLOBÁS, Y. KOHAYAKAWA, AND R. H. SCHELP

Dedicated to the memories of Professors Paul Erdős and Richard Rado

Abstract. The classical Canonical Ramsey Theorem of Erdős and Rado states that, for any integer q ≥ 1, any edge colouring of a large enough complete graph contains one of three canonically coloured complete subgraphs of order q. Of these canonical subgraphs, one is coloured monochromatically while each of the other two have its edge set coloured with many different colours. In this paper, we present a condition on colourings that, roughly speaking, requires them to make effective use of many colours (“essential infiniteness”); this condition is then shown to imply that the colourings in question must contain large refinements of one of two ‘unavoidable’ colourings that are rich in colours. As it turns out, one of these unavoidable colourings is one of the canonical colourings of Erdős and Rado, and the other is a ‘bipartite variant’ of this colouring.

1. Introduction

A seminal result of Erdős and Rado [4] states that if we colour the edges of a large enough complete graph, then a large canonically coloured complete subgraph must occur in our colouring. If our colouring uses only a bounded number of colours, and hence it is ‘poor’ in colours, then the canonically coloured complete subgraph that we are guaranteed to have is in fact a monochromatic complete graph. This is Ramsey’s well known theorem [8]. What, then, is the situation if our colouring is ‘rich’ in colours? In other words, what are the unavoidable substructures in rich colourings?

The main result of this paper, Theorem 2, gives a complete answer to this question. At this early stage, the reader will most probably find more useful the dry but more direct formulation of Theorem 2 given in Remark 13; the only definition that the reader will need is given in Definition 3. We hope that the discussion that follows will put our result in a broader context.

Let us first recall the canonical colourings of Erdős and Rado. There are three canonical colourings of the n-vertex complete graph K^{n}, namely γ_{const},

1991 Mathematics Subject Classification. Primary 05D10; Secondary: 05C35. Key words and phrases. Ramsey theory, canonical colourings, anti-Ramsey type results,

local colourings.

The second author was partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 300334/93–1), and by MCT/FINEP (PRONEX project 107/97). Part of this work was done while the second author was visiting The University of Memphis, whose kind hospitality and support he gratefully acknowledges.

γ_{<}, and γ_{inj}. The colouring γ_{const} assigns the same colour to all the edges of K^{n} and γ_{inj} assigns all different colours. Strictly speaking, γ_{<} is a class of colourings. To describe a member of this class, we assume that the vertex set of K^{n} is linearly ordered by some ordering <. Then, two edges have the same colour under γ_{<} if and only if their <-minimal elements coincide. The theorem of Erdős and Rado states that, for any given integer q ≥ 1, all sufficiently large complete graphs K^{n} with an arbitrary edge-colouring γ: E(K^{n}) → ℤ must contain a complete subgraph K^{q} on q vertices such that γ restricted to E(K^{q}) may be identified with one of the colourings γ_{const}, γ_{<}, and γ_{inj}, if we disregard the names of the colours.

If we require the given colouring γ to use at most a fixed number of colours, the canonical colourings γ_{<} and γ_{inj} will not arise (as long as q is large enough). Thus a monochromatic K^{q} will always be present. Hence, the boundedness of the number of colours to be used in γ “forces” the conclusion in the Erdős–Rado theorem. A slightly weaker condition that forces the same conclusion is that γ should be a locally bounded colouring, that is, only a bounded number of colours should be present at any given vertex. Many Ramsey type results for such colourings are known (see, e.g., Gyárfás et al. [5, 6], Ruciński and Truszczyński [9], Truszczyński [10], Truszczyński and Tuza [11]). On the other hand, a way of forcing the canonical colouring γ_{inj} is to impose the condition that γ should be a proper edge-colouring, i.e., no two edges of the same colour should share an endvertex. Let us mention in passing that surprisingly precise estimates exist for the numerical problems that arise in connection with this observation. See, e.g., Alon, Lefmann, and Rödl [1], Babai [2], and Lefmann, Rödl, Wysocka [7].

Intuitively, the condition that γ should be proper is a local condition that imposes that the colours should be ‘very mixed’. Is there a definition of ‘richness’ for colourings, more global in nature (say, in terms of the number of colours ‘effectively’ used by γ), that forces the conclusion in the Erdős–Rado theorem to be γ_{<} or γ_{inj}? Put simply, what can we say about colourings γ that use many colours?

Consider the following example: let γ_{match} be the colouring that assigns colour 0 to all edges of K^{n}, except for the edges of a fixed matching M ⊂ E(K^{n}) with |M| = ⌊n/2⌋. Furthermore, γ_{match} is injective on M, and colour 0 is not used on any edge from M. Then the number of colours that have been used by γ_{match} is large, but no large γ_{<} or γ_{inj} occurs in γ_{match}. Thus, the naïve condition that γ should use many colours is too weak.

Let us observe that γ_{match} is just a small perturbation of a bounded colouring: if we disregard a certain vanishing proportion of the edges of K^{n}, we are left with only one colour. Thus, we may say that γ_{match} does not effectively use many colours, and hence it is, essentially, a bounded or finite colouring. To exclude examples such as γ_{match}, we impose the condition that γ should not be ‘close’ to a bounded colouring. More precisely, we impose the condition that the deletion of no vanishing proportion of the edge set of K^{n} should lead to a finite colouring. We call such colourings essentially infinite. The formal definition is given in Section 2.1 (see Definition 7).

In the main result of this paper, we identify the unavoidable substructures in essentially infinite colourings (see Theorem 2). As an application of our result, we completely characterize certain natural local conditions on colourings that imply the essential finiteness of the colourings (see Corollary 3). We believe that this interplay between local and global phenomena is of interest. The problem of giving local conditions to guarantee essential finiteness of colourings was inspired by a conjecture of Clapsadle and Schelp [3].

The organization of this paper is as follows. In Section 2.1, we carefully state and discuss the definitions required in the sequel. The main result is presented in Section 2.2. The above-mentioned application of our main result is given in Section 2.3. The proofs of our results are presented in Section 3. We close with some concluding remarks in Section 4.

2. The main results

2.1. Basic definitions. The basic objects that we shall be dealing with here are edge-colourings of complete graphs, namely, arbitrary functions

γ: E(K) → ℤ,

where K is a complete graph and, for the sake of definiteness, we let the colours to be used be the integers. If K has n vertices, and we wish to emphasise that γ above is an edge-colouring of a complete graph of order n, we write γ^{n} for γ. In the sequel, we use the simpler term colouring to mean edge-colouring of a complete graph.

We say that two colourings γ: E(K^{n}) → ℤ and γ′: E(K^{m}) → ℤ are isomorphic if there are bijections φ: V (K^{n}) → V (K^{m}) and ψ: ℤ → ℤ for which

ψγ = γ′φ^{(2)},

where φ^{(2)} is the map E(K^{n}) → E(K^{m}) naturally induced by φ. In other words, γ and γ′ are isomorphic if n = m and there is a bijection between V (K^{n}) and V (K^{m}) under which the partitions of E(K^{n}) and E(K^{m}) naturally defined by γ and γ′ may be identified. Example 1. If k ≥ 1 is an integer, we let C_{k} be the set of colourings that use at most k colours. Thus, γ ∈ C_{k} if and only if | im γ| ≤ k. Example 2. If k ≥ 1 is an integer, we let C_{local-k} be the set of local kcolourings. Thus, γ: E(K) → ℤ belongs to C_{local-k} if and only if |γ(∂(x))| ≤ k for all vertices x ∈ V (K), where, here and below, we write ∂(x) for the set of edges incident to x.

The following terminology will be convenient for the sequel. Definition 3. Suppose γ = γ^{n}: E(K^{n}) → ℤ is an arbitrary colouring, and let k ≥ 1 and 0 < ε < 1 be given. We shall say that γ is a (k, ε)-bounded colouring if there is a set S ⊂ ℤ with |S| ≤ k and

|γ^{−1}(S)| ≥ (1 − ε)\binom{n}{2}.

Thus, we may say that γ is (k, ε)-bounded if it uses not more than k colours ‘modulo a set of edges of measure ε’. As an example, we mention that γ_{match} defined in the introduction is (1, 1/(n − 1))-bounded. The following quite simple but pleasant result, proved in Section 3.2, shows that a simple local condition can guarantee (k, ε)-boundedness for arbitrarily small ε > 0.

Lemma 1. For any 0 < ε < 1 and k ≥ 1, there is an integer k_{loc} = k_{loc}(ε, k) such that any local k-colouring is (k_{loc}, ε)-bounded.

We may rephrase the lemma above by saying that local k-colourings are ‘essentially finite’. To be precise, we make the following definition. Definition 4. We shall say that the members of a given class C of colourings are essentially finite if, for any 0 < ε < 1, there exists an integer k = k(ε) ≥ 1 for which any member of C is (k, ε)-bounded. Example 5. Trivially, C_{k} is a class of essentially finite colourings for any fixed k ≥ 1. Lemma 1 says that the same holds for C_{local-k}.

Loosely speaking, our aim is to show that families of colourings that are not essentially finite must contain certain unavoidable substructures. As to be expected, such substructures will be ‘rich in colours’. Remark 6. Naturally, the family C_{all} of all colourings is not essentially finite. However, we cannot claim that all members γ ∈ C_{all} (or all members γ = γ^{n} ∈ C_{all} with n sufficiently large) comprise ‘subcolourings’ that are rich in colours, because, for instance, C_{all} contains monochromatic (that is, constant) colourings.

In view of trivial examples such as C_{all} above, we make the following definition. Definition 7. Let C be an infinite class of colourings. Then, we shall say that the members of C are essentially infinite if there exists 0 < ε = ε(C) < 1 such that, for any integer k ≥ 1, there is n_{0} = n_{0}(k) such that all γ^{n} ∈ C with n ≥ n_{0} fail to be (k, ε)-bounded.

In the sequel, if C is a class of essentially infinite colourings, k ≥ 1 is an integer, and ε > 0 is a small enough real, we shall write n_{C}(k, ε) for the least integer with the property that any γ = γ^{n} ∈ C with n ≥ n_{C}(k, ε) is not (k, ε)-bounded. Notice that n_{C}(k, ε) is indeed well-defined as long as ε is small enough.

A simple argument shows that any class C whose members are not essentially finite contains a subset C′ ⊂ C of essentially infinite colourings. A trivial example of a class of essentially infinite colourings is the class of injective colourings

C_{inj} = {γ: γ is injective}.

The following two examples of essentially infinite colourings will be crucial in what follows. Example 8. Let us write γ_{<} = γ_{<}^{n}: E(K^{n}) → ℤ for the colouring under which γ_{<}(ij) = i for all 1 ≤ i < j ≤ n, where we suppose V (K^{n}) = [n] = {1, …, n}. The class C_{<} of colourings consists of all the colourings γ that are isomorphic to some γ_{<}. It is immediate that C_{<} is a class of essentially infinite colourings. One may in fact take any 0 < ε < 1 for ε(C_{<}) in Definition 7. Example 9. Suppose now that K^{2n} (n ≥ 1) has vertex set

V (K^{2n}) = {u_{1}, …, u_{n}, w_{1}, …, w_{n}}.

We write γ_{bip} = γ_{bip}^{2n} for the colouring of E(K^{2n}) under which, for all i and j, we have γ(u_{i}w_{j}) = i and, for all i ≠ j, we have γ(u_{i}u_{j}) = γ(w_{i}w_{j}) = 0. We let C_{bip} consist of all the colourings γ that are isomorphic to some γ_{bip}. It is again immediate that C_{bip} is a class of essentially infinite colourings. In this case, any 0 < ε < 1/2 will do for ε(C_{bip}).

We shall see soon that, in a certain precise sense, the two classes of essentially infinite colourings C_{<} and C_{bip} play a more fundamental rôle than C_{inj}.

2.2. The main result. Roughly speaking, our main result says that any large enough essentially infinite colouring must ‘contain’ arbitrarily large members from C_{<} ∪C_{bip}. We need to define a suitable notion of containment to make this precise. Definition 10. We shall say that a colouring γ̃: E(K^{m}) → ℤ is contained in a colouring γ: E(K^{n}) → ℤ if and only if there is an injection φ: V (K^{m}) ↪ V (K^{n}) such that if e and f ∈ E(K^{m}) and γ̃(e) ≠ γ̃(f), then γ(φ^{(2)}(e)) ≠ γ(φ^{(2)}(f)). As before, φ^{(2)} denotes the map E(K^{m}) → E(K^{n}) naturally induced by φ. We shall write γ̃ ⪯ γ if γ̃ is contained in γ.

It is immediate that, as the notation suggests, the relation of containment defined above is an order relation. Intuitively speaking, if γ contains γ′ then, at least somewhere, the colouring γ is ‘more colourful’ than (or at least as colourful as) the colouring γ′.

Clearly, if γ^{n} is a constant colouring, then γ^{n} ⪯ γ^{m} for any γ^{m} with n ≤ m. Also, if γ^{m} is an injective colouring, then γ^{n} ⪯ γ^{m} for any γ^{n} with n ≤ m. In order to gain further familiarity with the definition above, the reader is invited to show that no γ_{<}^{n} (n ≥ 4) is contained in any γ_{bip} and that no γ_{bip}^{2n} (n ≥ 2) is contained in any γ_{<}. One may thus say that the colourings γ_{<} and γ_{bip} are intrinsically distinct sorts of essentially infinite colourings.

Our main result, Theorem 2, states that γ_{<} and γ_{bip} are unavoidable objects in essentially infinite colourings. Before we state our result, for the sake of convenience, we extend the ⪯ relation to classes of colourings.

Definition 11. Let C_{1} and C_{2} be two classes of colourings. We shall write

C_{1} ⪯ C_{2}

if, for any q_{0} ≥ 1, there is an integer n_{0} = n_{0}(q_{0}) ≥ 1 such that any γ_{2} = γ_{2}^{n} ∈ C_{2} with n ≥ n_{0} contains some member γ_{1} = γ_{1}^{q} of C_{1} with q ≥ q_{0}.

Note that the ⪯ relation, when applied to classes of colourings, is reflexive and transitive (and hence it is a so-called quasi-order). We may now state our result.

Theorem 2. For any class C of essentially infinite colourings, we have

C_{<} ∪ C_{bip} ⪯ C.

Theorem 2 is best possible in the following sense.

Remark 12. Suppose C̃ is a class of colourings with the property that C̃ ⪯ C for any class C of essentially infinite colourings. Then C̃ ⪯ C_{<} ∪ C_{bip}.

Thus, for any C̃ as in Remark 12 and any class C of essentially infinite colourings, we have

C̃ ⪯ C_{<} ∪ C_{bip} ⪯ C.

Remark 12 is, in fact, almost a tautology, since C_{<} ∪ C_{bip} is a family of essentially infinite colourings. Remark 13. Theorem 2 may be stated in the following direct but somewhat dry way. For any q ≥ 1 and 0 < ε < 1, there exist k_{0} = k_{0}(q, ε) and n_{0} = n_{0}(q, ε) for which the following holds. If γ: E(K^{n}) → ℤ, where n ≥ n_{0}, is not (ε, k_{0})-bounded, then

(i) there exists Z = {z_{1}, …, z_{q}} ⊂ V (K^{n}) such that γ(z_{i}z_{j}) ≠ γ(z_{i′}z_{j′}) whenever i < j, i′ < j′, and i ≠ i′, or

(ii) there exist U = {u_{1}, …, u_{q}} and W = {w_{1}, …, w_{q}} such that γ(u_{i}w_{j}) ≠ γ(u_{i′}w_{j′}) whenever i ≠ i′, and, moreover, no colour that occurs on the U–W edges occurs within U or within W.

It is a pleasant surprise that, in Remark 13 above, we have to allow for case (ii), which describes colourings distinct from the canonical colourings of Erdős and Rado.

2.3. Local versus global colourings. Our main application of Theorem 2 is to do with the following general question: are there purely local conditions on colourings that force ‘essential finiteness’? We have the following type of local condition in mind.

Let H be a graph with at least one edge and let an integer k ≥ 1 be given. We shall say that a colouring γ: E(K^{n}) → ℤ is (H, k)-local if any subgraph H′ of K^{n} isomorphic to H receives at most k colours under γ. For example, if H = K^{1,k+1}, the star with k + 1 rays, then a colouring is (H, k)- local if and only if it is a local k-colouring. For conciseness, write C_{loc}(H, k) for the class of (H, k)-local colourings. Moreover, put

f(H) = max{k: C_{loc}(H, k) is a class of essentially finite colourings}.

Our main result in this section, Corollary 3, determines f(H) exactly. We need to introduce some notation. Let a colouring γ: E(K^{n}) → ℤ be given. Denote by μ(H, γ) the maximal number of colours that the isomorphic copies H′ ⊂ K^{n} of H receive under γ. Furthermore, put

μ(H, C) = max{μ(H, γ): γ ∈ C}

for any class of colourings C. Note that, then, μ(H, C) is the smallest integer μ for which we have C ⊂ C_{loc}(H, μ). We now put

μ(H) = min{μ(H, C_{<}), μ(H, C_{bip})}. (1)

Our main result is then the following.

Corollary 3. We have f(H) = μ(H) − 1 for any graph H with at least one edge.

One may easily check that μ(C^{3}) = 2 and that μ(C^{ℓ}) = ⌈ℓ/2⌉+1 if ℓ ≥ 4, where, as usual, C^{ℓ} denotes the cycle of length ℓ. Moreover, μ(K^{ℓ}) = ℓ − 1. Thus, Corollary 3 implies that f(C^{3}) = f(K^{3}) = 1, f(C^{ℓ}) = ⌈ℓ/2⌉ if ℓ ≥ 4, and f(K^{ℓ}) = ℓ − 2.

3. Proofs

3.1. Proof of Corollary 3. We first prove that f(H) ≤ μ(H) − 1. Suppose μ(H) = μ(H, C_{<}). Then C_{<} ⊂ C_{loc}(H, μ(H)), and C_{loc}(H, μ(H)) cannot be essentially finite, since C_{<} is essentially infinite. The same argument holds if μ(H) = μ(H, C_{bip}). Thus C_{loc}(H, μ(H)) is not essentially finite, which proves that f(H) < μ(H).

Let us now show that f(H) < μ(H) − 1 leads to a contradiction. Put k = μ(H)−1 and suppose k > f(H). Then C_{loc}(H, k) is not essentially finite, by the definition f(H). Let then C ⊂ C_{loc}(H, k) be an infinite class of essentially infinite colourings.

Pick a large enough even integer q_{0} so that μ(H, C_{<}) = μ(H, γ_{<}^{q_{0}}) and μ(H, C_{bip}) = μ(H, γ_{bip}^{q_{0}}). Theorem 2 implies that, then, there must be a colouring γ ∈ C for which there exists γ_{0}^{q_{0}} ∈ C_{<} ∪ C_{bip} with γ_{0}^{q_{0}} ⪯ γ. (Of course, Theorem 2 says that every γ = γ^{n} with n ≥ n_{0}(q_{0}) is such a colouring.) Suppose γ_{0}^{q_{0}} ∈ C_{<}; the case in which γ_{0}^{q_{0}} ∈ C_{bip} is similar. Then

μ(H) ≤ μ(H, C_{<}) = μ(H, γ_{0}^{q_{0}}) ≤ μ(H, γ) ≤ k = μ(H) − 1.

The first inequality follows from (1), the equality follows from the choice of q_{0}, the next inequality follows from the fact that γ_{0}^{q_{0}} ⪯ γ, and the last inequality follows from the fact that γ ∈ C ⊂ C_{loc}(H, k). This contradiction proves that f(H) ≥ μ(H) − 1. The proof of Corollary 3 is complete.

3.2. Proof of Lemma 1. We shall show that k_{loc}(ε, k) ≤ ℓ = ⌊2k^{2}/ε^{2}⌋. Suppose for a contradiction that γ is a local k-colouring of K^{n} (n ≥ 2), with e_{i} edges of colour i, where e_{1} ≥ e_{2} ≥ …, and such that

∑_{i>ℓ} e_{i} > ε\binom{n}{2}. (2)

Note that colour i must occur at more than \sqrt{2e_{i}} vertices. Since γ is a local k-colouring, we have

∑_{i≥1} \sqrt{2e_{i}} ≤ kn. (3)

As e_{i} ≤ e_{ℓ+1} ≤ (ℓ + 1)^{−1} ∑_{1≤i≤ℓ+1} e_{i} ≤ (ℓ + 1)^{−1}\binom{n}{2} for every i ≥ ℓ + 1, recalling (2) and (3), we have

\frac{ε\binom{n}{2}}{\{\binom{n}{2}/(ℓ + 1)\}^{1/2}} < \frac{1}{\{\binom{n}{2}/(ℓ + 1)\}^{1/2}} ∑_{i>ℓ} e_{i} ≤ ∑_{i>ℓ} \sqrt{e_{i}} < \frac{kn}{\sqrt{2}}.

But then ℓ + 1 < 2k^{2}/ε^{2}, which is a contradiction. Remark 14. For the purposes of this paper, the rate of growth of the function k_{loc}(ε, k) does not matter. A bound better than the one shown above may be deduced from Corollary 3 of Gyárfás et al. [5].

The proof of Lemma 1 above considers the colours in decreasing order of frequency. N. Alon pointed out to us that if we consider the colours in decreasing order of the number of vertices that they are incident to, then one may prove a better bound. His proof gives that k_{loc}(ε, k) < k^{2}/ε, which is best possible up to a multiplicative constant. To see how his proof goes, suppose we have chosen some set of colours but they still leave out more than ε\binom{n}{2} edges. Considering a vertex of maximum degree in the graph that remains, and recalling that we have a local k-colouring, we see that there is a monochromatic star with more than ε(n − 1)/k rays. Therefore, some yet unused colour touches more than ε(n − 1)/k + 1 ≥ εn/k vertices. Since no vertex may be touched by more than k colours, the number of colours that we will obtain in this process is less than k^{2}/ε. A lower bound of the same order of magnitute follows from a construction based on affine planes.

3.3. Proof of Theorem 2. Let C be a class of essentially infinite colourings. Our aim is to prove that C_{<} ∪ C_{bip} ⪯ C. Thus, let an integer q_{0} ≥ 1 be given. We have to show that a suitable integer n_{0} = n_{0}(q_{0}) = n_{0}(q_{0}, C) as in Definition 11 exists.

Let 0 < ε = ε(C) < 1 be as in Definition 7. We now define a few constants that will be important in the proof. We start by letting

ε_{1} = ε/6  and  δ = ε/12.

Moreover, we pick integers

n_{0},  k_{0} ≫ k_{1}, and  Q ≫ Q_{1} ≫ Q_{2} ≫ Q_{3}

as follows. Let

Q_{3} = R(q_{0}, q_{0}, q_{0}), (4) where we write R for the usual Ramsey function relative to 3 colours. Let Q_{2} be the minimal integer ≥ Q_{3} for which we have

\binom{Q_{2}}{2}\binom{Q_{2} − 3}{Q_{3} − 3} < \binom{Q_{2}}{Q_{3}}. (5)

Put

Q_{1} = \binom{Q_{2}}{2} + Q_{2}, (6)

and set

Q = ⌈\frac{Q_{1}^{4}}{2} ⌉ . (7)

Now put

k_{1} = ⌈\frac{2Q}{δ}⌉  and  k_{0} = k_{loc}(ε_{1}, k_{1} + 1), (8)

where k_{loc} is as in Lemma 1. Finally, let

n_{0} = max \{n_{C}(k_{0}, ε), ⌈\frac{(2k_{1})^{Q}}{ε_{1}(Q − 1)!}⌉\} , (9)

where n_{C}(k_{0}, ε) is as introduced just after Definition 7.

Lemma 4. n_{0} = n_{0}(q) = n_{0}(q, C) defined in (9) will do.

In the remainder of Section 3.3, we prove Lemma 4. Thus, let

γ = γ^{n}: E(K^{n}) → ℤ

be a colouring in C with n ≥ n_{0}. As n_{0} ≥ n_{C}(k_{0}, ε), we know that

(10) γ is not (k_{0}, ε)-bounded.

For any x ∈ V (K^{n}), let

c_{δ}(x) = min{|γ(∂(x) \ F_{x})|: F_{x} ⊂ ∂(x) and |F_{x}| ≤ δ(n − 1)}. (11)

Put

W = {x ∈ V (K^{n}): c_{δ}(x) > k_{1}}.

Case 1. |W | < ε_{1}n. Let K′ be the complete graph obtained from K^{n} by the removal of the vertices in W. Suppose K′ has n′ vertices. Also, write γ̃ for the colouring induced by γ on E(K′). We now wish to define a new colouring γ′ for K′, taking into account that, for all x ∈ V (K′), we have c_{δ}(x) ≤ k_{1}. Let

F = ⋃{F_{x} ∩ E(K′): x ∈ V (K′)}, (12)

where F_{x} denotes, for all x ∈ V (K′), a set of edges incident to x for which the minimum in (11) is attained. It is clear that

|F | ≤ δn^{2}. (13)

Suppose γ̃ uses colours 1, 2, 3, …, and recolour all the edges in F with colour 0. Let γ′ be this new colouring of K′. Observe that γ′ is in fact a local (k_{1} + 1)-colouring. Recalling the definition of k_{0} in (8), we see that there exists S ⊂ ℤ with |S| ≤ k_{0} for which we have

|(γ′)^{−1}(S)| ≥ (1 − ε_{1})\binom{n′}{2},

and hence, by (13), we have

|(γ′)^{−1}(S \ \{0\})| ≥ \binom{n′}{2} − \{ε_{1}\binom{n′}{2} + δn^{2}\} .

Thus, noticing that there are at most |W |n ≤ ε_{1}n^{2} edges that touch the vertices in W, we see that the set S \ {0}, of at most k_{0} colours, fails to ‘cover’ at most

(\frac{1}{2}ε_{1} + δ + ε_{1}) n^{2} < ε\binom{n}{2}

of the edges of our original complete graph K^{n}. In other words, we have proved that γ is (k_{0}, ε)-bounded, which is a contradiction to (10).

Case 2. |W | ≥ ε_{1}n. We start by stating a simple auxiliary result, which may be proved by a straightforward greedy argument. (The easy proof of this result uses the fact that k_{1} is at least as large as 2Q/δ; see (8).)

Lemma 5. Let Q, k_{1}, and δ be as above. Let α_{1} ≥ α_{2} ≥ ⋯ ≥ 0 be reals such that

∑_{i≥1} α_{i} = 1, (14)

but

∑_{1≤i≤k_{1}} α_{i} < 1 − δ. (15)

Then there exist indices 0 = i_{−1} < i_{0} < ⋯ < i_{Q} such that, putting

β_{j} = ∑_{i_{j−1}<i≤i_{j}} α_{i} (0 ≤ j ≤ Q),

we have

\frac{1}{k_{1}} ≤ β_{j} < \frac{2}{k_{1}}

for all j = 1, …, Q.

The lemma above and a Zarankiewicz type argument leads us to our next claim. In what follows, we write E(A, B) for the set of edges that join vertices in A to vertices in B. Moreover, if, e.g., A = {a}, we write E(a, B) for E({a}, B).

Lemma 6. There exist disjoint sets S and T ⊂ V (K^{n}) with |S| = |T | = Q such that, for any s ∈ S, the colouring γ restricted to E(s, T) is injective.

Proof. For x ∈ V (K^{n}) and i ∈ ℤ, let

d(x, i) = |∂(x) ∩ γ^{−1}(i)|.

Thus, d(x, i) is the number of edges of colour i incident to x. Fix x ∈ W, and put

α_{i} = \frac{d(x, i)}{n − 1}

for all i ∈ ℤ. Without loss of generality, we may assume that only strictly positive colours i occur at x, and that d(x, 1) ≥ d(x, 2) ≥ · · ·. Then α_{1} ≥ α_{2} ≥ ⋯, identity (14) holds, and, since x ∈ W, inequality (15) holds as well. Thus, Lemma 5 gives us a sequence J_{1}^{(x)}, …, J_{Q}^{(x)} ⊂ ℤ of pairwise disjoint sets of colours for which

d(x, J_{i}^{(x)}) = ∑_{j∈J_{i}^{(x)}} d(x, j) ≥ \frac{n − 1}{k_{1}}

for all i = 1, …, Q.

We conclude that the number of stars K^{1,Q} with Q rays and centre x ∈ W, each with all its Q edges coloured differently, is at least

∑_{x∈W} ∏_{1≤i≤Q} d(x, J_{i}^{(x)}) ≥ |W | (\frac{n − 1}{k_{1}})^{Q} ≥ ε_{1}n (\frac{n}{2k_{1}} )^{Q} .

Let us call the stars counted above special stars. Averaging over all subsets of V (K^{n}) of size Q, we see that there is

T = \{t_{1}, …, t_{Q}\} ∈ \binom{V (K^{n})}{Q} (16)

such that t_{1}, …, t_{Q} are the Q endvertices of at least

\frac{ε_{1}Q!}{(2k_{1})^{Q}} n (17)

special stars. Recalling (9) and that n ≥ n_{0}, we obtain that (17) is at least Q. Hence, there are Q centres that form a set S that, together with T in (16) above, is as required in Lemma 6.

For A ⊂ S and B ⊂ T, let us say that property D(A, B) holds if

for any distinct b, b′ ∈ B, γ(E(A, b)) ∩ γ(E(A, b′)) = ∅.

Lemma 7. There exist S_{1} ⊂ S and T_{1} ⊂ T with |S_{1}| = |T_{1}| = Q_{1} for which D(S_{1}, T_{1}) holds.

Proof. Observe that property D(S_{1}, T_{1}) holds if S_{1} ∪ T_{1} does not induce a pair of independent S_{1}–T_{1} edges of the same colour. Let M_{i} be the set of edges of colour i. Then m_{i} = |M_{i}| ≤ Q, and ∑_{i} m_{i} = Q^{2}. The number of pairs of independent edges of the same colour is at most

∑_{i} \binom{m_{i}}{2} ≤ Q\binom{Q}{2}.

Hence, the probability that a random pair of sets (S_{1}, T_{1}) with |S_{1}| = |T_{1}| = Q_{1} violates D(S_{1}, T_{1}) is at most

Q\binom{Q}{2}\binom{Q − 2}{Q_{1} − 2}^{2}/\binom{Q}{Q_{1}}^{2} = \frac{Q_{1}^{2}(Q_{1} − 1)^{2}}{2(Q − 1)} < 1,

where in the last inequality we used (7). Consequently, some pair (S_{1}, T_{1}) will do.

Lemma 7 and (6) give the following.

Lemma 8. There exist S_{2} ⊂ S_{1} and T_{2} ⊂ T_{1} with |S_{2}| = |T_{2}| = Q_{2} such that, for any s, s′ ∈ S_{2}, we have γ(ss′) ∉ γ(E(S_{2}, T_{2})).

Proof. Pick for S_{2} an arbitrary Q_{2}-subset of S_{1}. Since D(S_{1}, T_{1}) holds, a colour that occurs on \binom{S_{2}}{2} occurs in γ(E(S_{1}, t)) for at most one t ∈ T_{1}. Thus (6) ensures that a suitable set T_{2} ⊂ T_{1} exists.

For our next step in the proof, we need the following lemma.

Lemma 9. Let Q_{2} and Q_{3} be as above, and suppose we have a function

σ : E(K^{Q_{2}}) → {0} ∪ [Q_{2}] = {0, 1, …, Q_{2}},

where we assume that V (K^{Q_{2}}) = [Q_{2}]. Then there exists a set T′ ⊂ V (K^{Q_{2}}) with |T′| ≥ Q_{3} such that, for all i ∈ T′, we have

σ^{−1}(i) ∩ \binom{T′}{2} ⊂ ∂(i) ∩ \binom{T′}{2}. (18)

Proof. Suppose that, for any T′ ⊂ [Q_{2}] with |T′| = Q_{3}, there is i ∈ T′ violating (18). Let us call an edge e induced by T′ that witnesses the fact that (18) fails a T′-witness. Let us count the number of pairs (T′, e), where T′ ⊂ [Q_{2}] has cardinality Q_{3} and e is a T′-witness. By hypothesis, this number is at least \binom{Q_{2}}{Q_{3}}. On the other hand, any edge e in K^{Q_{2}} is a T′-witness for none, or for

\binom{Q_{2} − 3}{Q_{3} − 3}

Q_{3}-sets T′. Hence the total number of pairs (T′, e) as above is at most

\binom{Q_{2}}{2}\binom{Q_{2} − 3}{Q_{3} − 3}.

In view of (5), this is a contradiction.

We apply Lemma 9 to the complete graph induced by T_{2}, and the colouring σ defined by

σ(tt′) = \{ \begin{matrix}i & if γ(tt′) ∈ γ(E(S_{2}, i)) and i ∈ T_{2}, \\ 0 & if γ(tt′) ∉ ⋃_{i∈T_{2}} γ(E(S_{2}, i)) = γ(E(S_{2}, T_{2})). \end{matrix}

(If we wish to follow the notation in Lemma 9 exactly, we may assume without loss of generality that T_{2} = [Q_{2}].) Recalling that property D(S_{1}, T_{1}) holds, we notice that the fact that S_{2} ⊂ S_{1} and T_{2} ⊂ T_{1} implies that σ is well-defined. Since (5) holds, Lemma 9 gives the following.

Lemma 10. There exist S_{3} ⊂ S_{2} and T_{3} ⊂ T_{2} with |S_{3}| = |T_{3}| = Q_{3} such that, for any distinct t, t′ ∈ T_{3}, we have

γ(tt′) ∉ ⋃_{t′′} γ(E(S_{3}, t′′)),

where the union is taken over all t′′ ∈ T_{3} \ {t, t′}.

We are now able to finish the proof of Lemma 4, and hence of Theorem 2. Consider the following {±1, 0}-colouring ρ of the edges of the complete graph on T_{3}. First, equip T_{3} with some arbitrary linear order <. Then, colour tt′ (t ≠ t′ ∈ T_{3}) with colour 0 if

γ(tt′) ∉ ⋃_{t′′∈T_{3}} γ(E(S_{3}, t′′)).

We colour tt′ with colour 1 if t < t′ and γ(tt′) ∈ γ(E(S_{3}, t)), and, finally, we colour tt′ with colour −1 if t < t′ and γ(tt′) ∈ γ(E(S_{3}, t′)). Because of (4), we know that there is T_{ρ} ⊂ T_{3} with |T_{ρ}| = q_{0} such that ρ is constant on \binom{T_{ρ}}{2}.

If ρ has value 0 on \binom{T_{ρ}}{2}, then it is easily seen that we have found an isomorphic copy of a ‘refinement’ of γ_{bip}^{2q_{0}} ∈ C_{bip} in our original colouring γ. (As the terminology suggests, a refinement of a given colouring of a complete graph K is a colouring of E(K) that induces a partition of E(K) that is finer than the partition induced by the given colouring.) Therefore, we have γ_{bip}^{2q_{0}} ⪯ γ. If, on the other hand, ρ is −1 or 1 on \binom{T_{ρ}}{2}, then, since property D(S_{3}, T_{3}) holds, it follows that γ restricted to T_{ρ} is isomorphic to a refinement of γ_{<}^{q_{0}} ∈ C_{<}, and hence γ_{<}^{q_{0}} ⪯ γ. Thus, in either case, we have found γ_{1} = γ_{1}^{q} ∈ C_{<} ∪ C_{bip} with q ≥ q_{0} contained in γ, as required. Lemma 4 is proved.

4. Concluding remarks

The reader has undoubtedly noticed that we were quite generous in the estimates in our proofs. Indeed, we have not attempted to obtain particularly good bounds for the natural extremal functions that arise in connection with Theorem 2.

We have only considered colourings of finite graphs. Clearly, similar investigations may be pursued for other combinatorial structures. In the infinite case, the questions may be formulated in measure-theoretic or topological terms. We shall come back to such topics in a future note.

Acknowledgements. The second author thanks S. Hougardy, H. J. Prömel, and A. Taraz for interesting discussions. It is also a pleasure for us to thank N. Alon for his comments and to acknowledge the careful work of an anonymous referee, whose many suggestions improved the presentation of this paper.

References

[1] N. Alon, H. Lefmann, and V. Rödl, On an anti-Ramsey type result, Sets, Graphs and Numbers, vol. 60, Colloquia Mathematica Societatis János Bolyai, North-Holland, 1991, pp. 9–22.

[2] L. Babai, An anti-Ramsey theorem, Graphs and Combinatorics 1 (1985), no. 1, 23–28.

[3] R. A. Clapsadle and R. H. Schelp, Local edge colorings that are global, Journal of Graph Theory 18 (1994), no. 4, 389–399.

[4] P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proceedings of the London Mathematical Society 2 (1952), no. 3, 417–439.

[5] A. Gyárfás, J. Lehel, J. Nešetřil, V. Rödl, R. H. Schelp, and Zs. Tuza, Local kcolorings of graphs and hypergraphs, Journal of Combinatorial Theory, Series B 43 (1987), no. 2, 127–139.

[6] A. Gyárfás, J. Lehel, R. H. Schelp, and Zs. Tuza, Ramsey numbers for local colorings, Graphs and Combinatorics 3 (1987), no. 3, 267–277.

[7] H. Lefmann, V. Rödl, and B. Wysocka, Multicolored subsets in colored hypergraphs, Journal of Combinatorial Theory, Series A 74 (1996), no. 2, 209–248.

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

[9] A. Ruciński and M. Truszczyński, A note on local colorings of graphs, Discrete Mathematics 164 (1997), no. 1-3, 251–255, The Second Krakow Conference on Graph Theory (Zgorzelisko, 1994).

[10] M. Truszczyński, Generalized local colorings of graphs, Journal of Combinatorial Theory, Series B 54 (1992), no. 2, 178–188.

[11] M. Truszczyński and Zs. Tuza, Linear upper bounds for local Ramsey numbers, Graphs and Combinatorics 3 (1987), no. 1, 67–73.

Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA, and Trinity College, Cambridge CB2 1TQ, UK

E-mail address: bollobas@msci.memphis.edu

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 Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA

E-mail address: schelpr@msci.memphis.edu