On an Anti-Ramsey Property of Ramanujan Graphs

P.E. Haxell^{1} and Y. Kohayakawa^{1,2}

1Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, England

2Instituto de Matemática e Estatística, Universidade de São Paulo, Caixa Postal 20570, 01452–990 São Paulo, SP, Brazil

Abstract. If G and H are graphs, we write G → H (respectively, G → TH) if for any proper edge-colouring γ of G there is a subgraph H′ ⊂ G of G isomorphic to H (respectively, isomorphic to a subdivision of H) such that γ is injective on E(H′). Let us write C^{ℓ} for the cycle of length ℓ. Spencer (cf. Erdős [10]) asked whether for any g ≥ 3 there is a graph G = G_{g} such that (i) G has girth g(G) at least g, and (ii) G → T C^{3}. Recently, Rödl and Tuza [22] answered this question in the affirmative by proving, using non-constructive methods, a result that implies that for any t ≥ 1 there is a graph G = G_{t} of girth t + 2 such that G → C^{2t+2}. In particular, condition (ii) may be strengthened to (iii) G → C^{ℓ} for some ℓ = ℓ(G). For G = G_{t} above ℓ = ℓ(G) = 2t + 2 = 2g(G) − 2. Here, we show that suitable Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak [18] are explicit examples of graphs G = G_{g} satisfying (i) and (iii) above. For such graphs ℓ = ℓ(G) in (iii) may be taken to be roughly equal to (3/2)g(G), thus considerably improving the value 2g(G)−2 given in the result of Rödl and Tuza. It is not known whether there are graphs G of arbitrarily large girth for which (iii) holds with ℓ = ℓ(G) = g(G).

1. Introduction

In this note we shall consider proper edge-colourings of graphs, and we shall be concerned

with the existence of subgraphs whose edges are all coloured differently. To be more precise,

let a graph G be given, and suppose γ : E(G) → ℕ is a proper edge-colouring of G. We shall say that a subgraph H ⊂ G of G is multicoloured with respect to the colouring γ if γ is injective on E(H). A question raised by Spencer (see [10], p. 29) is as follows: are there graphs G of arbitrarily large girth such that every proper edge-colouring of G admits a multicoloured cycle?

Let G and H be graphs. We write G⟶_{p}^{mc}H if for any proper edge-colouring γ of G there is a subgraph H′ ⊂ G of G isomorphic to H such that γ is injective on E(H′). Recently, Rödl and Tuza [22] settled the above problem of Spencer in the affirmative, by proving the following stronger statement. As customary, we denote the girth of a graph G by g(G), and write C^{ℓ} for a cycle of length ℓ ≥ 3.

Theorem 1. For every positive integer t, every real δ such that 0 < δ < 1/(2t + 1), and every n sufficiently large with respect to t and δ, there is a graph G = G^{n} of order n such that (i) g(G) = t + 2, and (ii) G⟶_{p}^{mc}C^{ℓ} for all 2t + 2 ≤ ℓ ≤ n^{δ}.

Erdős [10] remarked that random methods should be suitable for tackling Spencer’s problem, and indeed in [22] the result above is proved by probabilistic means. In fact, it is shown that if p = n^{ε−1} and ε = ε(t, δ) > 0 is appropriately chosen, then a graph G obtained by suitably altering a random graph G_{p} ∈ G(n, p) almost surely satisfies (i) and (ii). No explicit construction for a graph G as in Theorem 1 is given in [22].

Following [22], for a graph H, let us denote by t(H) the smallest possible girth for a graph G satisfying G⟶_{p}^{mc}H. Formally, let t(H) = inf{g(G) : G⟶_{p}^{mc}H}. In the spirit of the well-known works of Nešetřil and Rödl [20], in [22], Rödl and Tuza raise the following very attractive problem.

Problem 2. Does t(H) = g(H) hold for every graph H?

As pointed out in [22], we do clearly have t(H) = g(H) if H is a forest or if H contains a triangle. The complete bipartite graph K^{4,4} shows that t(C^{4}) = 4. By considering the incidence graph of a projective plane, one may check that t(C^{6}) = 6, and a random construction involving projective planes gives that t(C^{5}) = 5. Thus t(C^{ℓ}) = ℓ for 3 ≤ ℓ ≤ 6. (See Section 5 for details concerning these small cases of ℓ.) More generally, Theorem 1 gives that t(C^{ℓ}) ≥ ⌊ℓ/2⌋ + 1 for all ℓ ≥ 4. Our main results here significantly improve this estimate on t(C^{ℓ}) for large even values of ℓ, and give explicit graphs for Spencer’s original problem. Indeed, Theorems 7 and 11 below show that suitable Ramanujan graphs X of Lubotzky, Phillips, and Sarnak [18] are as required. Roughly speaking, we take a large enough bipartite d-regular X and show that X⟶_{p}^{mc}C^{2s} for all s varying from about (3/4)g(X) up to Ω(d). (See Theorem 7.) Then the asymptotic lower bound for t(C^{ℓ}) (ℓ even) that we obtain is t(C^{2s}) ≥ (4/3 + o(1))s. When deducing this bound, we shall arrive at a simple number-theoretic problem concerning the existence of certain primes. Although this question can be dealt with in a standard manner, for completeness we include a separate section, Section 4, dedicated to it.

The methods used in the proof of Theorem 7 are different from the methods used by Rödl and Tuza; they are based on the eigenvalue method of Alon and Milman (see, e.g. [4], Chapter 9, Section 2) and on the techniques used by Beck [6] to prove that the size-Ramsey number of an ℓ-path is O(ℓ). The fact that Ramanujan graphs are ‘explicit examples’ of extremal or nearly extremal graphs with respect to many problems is well known, and our result gives another example of such a problem. This note was inspired by the results of Alon and Chung [2], and of Friedman and Pippenger [12]. Let us also mention that an extremal problem concerning the relation ⟶_{p}^{mc} is studied in Babai [5], and that the corresponding problem for uniform hypergraphs is considered in Lefmann [17]. Problem 2 is also related to canonical versions of Ramsey’s theorem, in the sense of Erdős and Rado [11].

In the next section we state a few properties of the Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak that we shall use, and we give some lemmas needed in the proof of Theorem 7. Section 3 is devoted to the proof of Theorem 7, and in Section 4 we prove Theorem 11. In Section 5, which is included for completeness, we prove that t(C^{ℓ}) = ℓ for 3 ≤ ℓ ≤ 6. In the last section we give some generalisations of our results, and we mention a related result.

Finally, we remark that appropriate modifications of our results here can be shown to hold for the Ramanujan graphs Y_{m} = Y_{m,p} of Margulis [19]. However we have decided to restrict ourselves to the graphs X^{p,q} because a more detailed analysis of these graphs is available in the literature. Moreover, unfortunately, the use of the Y_{m} does not seem to give significantly better results.

2. Auxiliary lemmas Let p and q be two distinct primes such that p, q ≡ 1 (mod 4), p ≤ q^{2}, and p is not a square in ℤ/qℤ. Throughout this note, except for Section 6, we let G = G_{p,q} = X^{p,q} be the Ramanujan graph of Lubotzky, Phillips, and Sarnak [18]. Thus G is a bipartite graph, with bipartition V = V (G) = V_{0} ∪ V_{1}, say. The order |G| of G is 2n = q(q^{2} − 1), and G is a d-regular graph where d = p + 1. We now recall three important results concerning the graph G. Let us collect three important properties of G in the following lemma.

Lemma 3. Let G = G_{p,q} = X^{p,q} be as above. Then the following hold.

(i) The girth g(G) of G satisfies 4 log_{p}(q/√2) ≤ g(G) < 4 log_{p}(q√(2p)). In particular, setting t = ⌈(2/3) log_{p}(n/√2)⌉, we have d > p ≥ 2^{−1/3t}n^{2/3t} and g(G) ≥ 2t.

(ii) The eigenvalues of the adjacency matrix of G are ±λ_{0}, …, ±λ_{n−1}, where 0 ≤ λ_{n−1} ≤

⋯ ≤ λ_{0} = d, and |λ_{i}| ≤ 2p^{1/2} = 2(d − 1)^{1/2} for all i ≠ 0. (iii) For any U ⊂ V_{0} and any W ⊂ V_{1}, the number of edges e(U, W) between U and W

satisfies |e(U, W) − (d/n)|U||W || ≤ 2{(d − 1)|U||W |}^{1/2}.

Property (ii), often called the Ramanujan property, is proved in [18], together with the lower bound for g(G) in (i). The upper bound in (i) is a result of Biggs and Boshier [7]. Finally, we remark that the technique given in Alon and Spencer [4], Chapter 9, Section 2, is enough to prove (iii).

For the rest of this note, we let ε = 2 × 10^{−6}, and set ℓ = ⌈3t/2⌉ where t is as in Lemma 3(i). Our aim is to show that if p and q are larger than a certain absolute constant,

t ≥ 2, and d ≥ 16ε^{−2ℓ}, then G = G_{p,q} = X^{p,q}⟶_{p}^{mc}C^{2s} for all ℓ + 1 ≤ s ≤ (ε^{ℓ}/6)n^{1/ℓ} + 1.

In what follows, several of the inequalities are claimed to hold for large enough values of p and q only. We also assume that p and q are so that t ≥ 2. (For instance, we may require that q ≥ 3p/2 to guarantee that t ≥ 2.) Note that, in particular, we have d ≥ d_{0} = 2^{−1/6}n^{2/3t}. Below, our indices will be taken modulo 2 so that, e.g. V_{0} = V_{2} = …, etc.

For convenience, we introduce the following simple definition. Let J be a bipartite graph with a fixed bipartition, say V (J) = X ∪Y, and let b and f be positive real numbers. Then we shall say that J is a (b, f)-expander if for all U ⊂ X and U ⊂ Y such that |U| ≤ b we have |Γ_{J}(U)| ≥ f|U|. Note that for a (b, f)-expander J if V (J) ≠ ∅ and f > 1, then |X|, |Y | > b.

If H is a graph and U, W ⊂ V (H) are disjoint sets of vertices, we write H[U, W] for the bipartite subgraph of H with vertex set U ∪W and edge set E_{H}(U, W) = {uw ∈ E(H) : u ∈ U, w ∈ W }. Also, if A, B ⊂ V (H), then e(A, B) = e_{H}(A, B) denotes the number of edges in H that have one endvertex in A and the other in B. As usual, we denote the minimal degree min_{x∈H} d_{H}(x) of the graph H by δ(H). Recall G = G_{p,q} = X^{p,q} has order 2n = q(q^{2} − 1). Throughout this note, we let r = n/2. Note that clearly n = q(q^{2} − 1)/2 is even, and hence r is an integer. We are now ready to state and prove our first lemma.

Lemma 4. Suppose d ≥ 360^{2}. Let S_{σ} ⊂ V_{σ} with |S_{σ}| = r = n/2 (σ = 0, 1) be given. Let H ⊂ G′ = G[S_{0}, S_{1}] be a spanning subgraph of G′ such that e(H) ≥ (1/3)e(G′). Then there are sets S̄_{σ} ⊂ S_{σ} (σ = 0, 1) such that if J = H[S̄_{0}, S̄_{1}], then (i) δ(J) ≥ d/18, and (ii) J is an (r/10f, f)-expander for any 0 < f ≤ 360^{−2}d. In particular, we have |S̄_{σ}| ≥ n/20 (σ = 0, 1).

Proof. Let d′ = e(G′)/r be the average degree of G′ = G[S_{0}, S_{1}]. Note that as d ≥ 144, we have d′ ≥ d/3. Let Z ⊂ S_{0} ∪ S_{1} be a minimal non-empty set satisfying e(H[Z]) ≥ (1/6)d′|Z|. Let S̄_{σ} = Z ∩ S_{σ} (σ = 0, 1), and let J = H[S̄_{0}, S̄_{1}]. Then, for any X ⊂ Z, we have e_{J}(X, Z) ≥ (1/6)d′|X|. Indeed, we have e_{J}(X, Z) = e(H[Z]) − e(H[Z \ X]) ≥ (d′/6)|Z| − (d′/6)|Z \ X| = (d′/6)|X|. Noting that for x ∈ Z = V (J) we have d_{J}(x) = e_{J}({x}, Z), we see that δ(J) = min_{x∈J} d_{J}(x) ≥ d′/6 ≥ d/18, which proves (i).

Now assume 0 < f ≤ 360^{−2}d. We shall show that J is an (r/10f, f)-expander. Suppose U ⊂ S̄_{σ}, where σ = 0 or 1, and u = |U| ≤ r/10f. Let W = Γ_{J}(U) ⊂ S̄_{σ+1}, and set w = |W |. We claim that w ≥ fu. Suppose for a contradiction that w < fu. Then du/18 ≤ d′u/6 ≤ e_{J}(U, Z) = e_{J}(U, W) ≤ e_{G}(U, W) ≤ (d/n)uw + 2(duw)^{1/2} < du/20 + 2(duw)^{1/2}, and hence w ≥ 360^{−2}du ≥ fu, which is a contradiction.

To see that |S̄_{σ}| ≥ n/20 (σ = 0, 1), it suffices to note that f_{0} = 360^{−2}d > 1. Indeed, as J is an (r/10f, f)-expander for all 0 < f ≤ f_{0}, we have |S̄_{σ}| > r/10f (σ = 0, 1) for all 1 < f ≤ f_{0}. Letting f tend to 1, we conclude that |S̄_{σ}| ≥ r/10 (σ = 0, 1).

We now let γ : E(G) → ℕ be an arbitrary fixed proper edge-colouring of G = G_{p,q}. Let S_{σ} ⊂ V_{σ} such that |S_{σ}| = r = n/2 (σ = 0, 1) be given. Also, let H ⊂ G′ = G[S_{0}, S_{1}] be a spanning subgraph of G′ such that e(H) ≥ (1/3)e(G′). Suppose S̄_{σ} ⊂ S_{σ} (σ = 0, 1) are as in Lemma 4, and again let J = H[S̄_{0}, S̄_{1}].

For tidiness, if P ⊂ G is a path, we write γ(P) for γ(E(P)), and say that γ is injective on P if it is injective on E(P). We may now state and prove the key lemma needed in the proof of our main result.

Lemma 5. Suppose ℓ ≤ ℓ′ ≤ εn^{1/ℓ}. Let c_{0} ∈ ℕ, and x ∈ S̄_{σ} (σ = 0 or 1) be given. Then there is a set T ⊂ S̄_{σ+ℓ′} such that (i) |T | ≥ ε^{ℓ}n, and (ii) for all y ∈ T there is an x–y path P_{y} of length ℓ′ in J with (a) c_{0} ∉ γ(P_{y}), and (b) γ injective on P_{y}.

Proof. First recall that the minimal degree δ(J) of J satisfies δ(J) ≥ d/18 ≥ 3ℓ′. Thus clearly there is a path P_{0} ⊂ J in J, starting at x, of length ℓ′ − ℓ, such that (a) c_{0} ∉ γ(P_{0}), and (b) γ is injective on P_{0}. Suppose P_{0} is an x–x′ path, and note that x′ ∈ S_{σ′}, where σ′ = σ + ℓ′ − ℓ. We now let d′_{0} = d_{0} if t is even, and let d′_{0} = 2^{−1/6}n^{1/ℓ} if t is odd. Note that clearly d′_{0} ≤ d_{0} ≤ d.

Let N_{0} = {x′}. Let 1 ≤ i ≤ ℓ, and suppose that pairwise disjoint sets N_{j} ⊂ S̄_{0} ∪ S̄_{1} (0 ≤ j < i) have been defined so that, for every 0 ≤ j < i, we have

(i) N_{j} ⊂ S_{σ′+j}, (ii) |N_{j}| = ⌈(d′_{0}/3 × 360^{2})^{j}⌉, (iii) for all z ∈ N_{j}, there is an x′–z path P_{z} in J such that (a) V (P_{0}) ∩ V (P_{z}) = {x′},

(b) |V (P_{z}) ∩ N_{k}| = 1 (0 ≤ k ≤ j), and (c) P′_{z} = P_{0}P_{z} is an x–z path in J with c_{0} ∉ γ(P′_{z}) and γ injective on P′_{z}.

We shall now extend the sequence N_{j} (0 ≤ j < i) by defining N_{i} ⊂ S̄_{0} ∪ S̄_{1} suitably. Let U = N_{i−1}, W = Γ_{J}(U), and f = d′_{0}/360^{2}. Note that |U| = ⌈(d′_{0}/3 × 360^{2})^{i−1}⌉ ≤ r/10f, and hence |W | ≥ f|U|. Let W′ = W ∩ (V (P_{0}) ∪ ⋃_{j=0}^{i−1} N_{j}). Then we have

|W′| ≤ ⌈\frac{1}{2} (ℓ′ − ℓ + 1)⌉ + ∑_{j=0}^{i−2} |N_{j}| ≤ ℓ′ − 1 + 2|N_{i−2}|.

For each z ∈ N_{i−1}, fix an x′–z path P_{z} ⊂ J as in (iii) above, and let P′_{z} = P_{0}P_{z}. Now let

W′′ = ⋃_{z∈N_{i−1}} {w ∈ Γ_{J}(z) : γ(zw) ∈ {c_{0}} ∪ γ(P′_{z})}.

Then |W′′| ≤ ∑_{z∈N_{i−1}}(1 + |γ(P′_{z})|) ≤ ℓ′|N_{i−1}|. Let N′_{i} = W \ (W′ ∪ W′′). Then

\begin{aligned}|N′_{i}| & ≥ |W | − (|W′| + |W′′|) ≥ |W | − (ℓ′ − 1 + 2|N_{i−2}| + ℓ′|N_{i−1}|) \\ & ≥ f|N_{i−1}| − 2ℓ′|N_{i−1}| ≥ \frac{d′_{0}}{3 × 360^{2}} |N_{i−1}| ≥ (\frac{d′_{0}}{3 × 360^{2}} )^{i} . \end{aligned}

Let N_{i} ⊂ N′_{i} be such that |N_{i}| = ⌈(d′_{0}/3 × 360^{2})^{i}⌉. Note that then (i), (ii), and (iii) hold for j = i. Thus by induction there are sets N_{j} (0 ≤ j ≤ ℓ) satisfying (i), (ii), and (iii) for all 0 ≤ j ≤ ℓ. To finish the proof, let T = N_{ℓ}.

3. The main result

As in the previous section, we let a proper edge-colouring γ : E(G) → ℕ be fixed. Let the partition of E = E(G) naturally induced by γ be E = E_{1} ∪ ⋯ ∪ E_{k}, where, say, E_{i} = γ^{−1}({i}) ≠ ∅ (1 ≤ i ≤ k). For the rest of this section, let V_{σ} = S_{σ}^{(0)} ∪ S_{σ}^{(1)}, with |S_{σ}^{(0)}| = |S_{σ}^{(1)}| = r = n/2, be a fixed partition of V_{σ} (σ = 0, 1). Let G^{(i)} = G[S_{0}^{(i)}, S_{1}^{(i)}] (i = 0, 1).

We shall use the following slightly non-standard notation. If H is a graph and F ⊂ E(H), we write H[F] for the spanning subgraph of H with edge set F. The following result is a simple technical lemma.

Lemma 6. Suppose d ≥ 108 log 3. Then there exists a partition [k] = C_{0} ∪ C_{1} of [k] = {1, …, k} such that if we let H^{(i)} = G^{(i)} [E(G^{(i)}) ∩ ⋃_{j∈C_{i}} E_{j}] (i = 0, 1), then e(H^{(i)}) ≥ (1/3)e(G^{(i)}) (i = 0, 1).

Proof. Set a_{i}^{(j)} = |E_{i} ∩E(G^{(j)})| for 1 ≤ i ≤ k and j = 0, 1. Note that 0 ≤ a_{i}^{(j)} ≤ r. Put i ∈ [k] in C_{0} with probability 1/2, independently from all other j ∈ [k]. Let X_{i} = 1 if i ∈ C_{0} and X_{i} = 0 if i ∈ C_{1}. Let H^{(i)} (i = 0, 1) be as in the statement of our lemma. Then clearly e(H^{(0)}) = ∑_{1≤i≤k} a_{i}^{(0)}X_{i}. Let Y_{i} = a_{i}^{(0)}X_{i}/r (1 ≤ i ≤ k), and set Y = ∑_{1≤i≤k} Y_{i}. Then, for any 0 ≤ δ ≤ 1, by Hoeffding’s inequality we have that ℙ{Y ≤ (1 − δ)𝔼(Y)} ≤ exp{−δ^{2}𝔼(Y)/2}. Note that 𝔼(Y) = e(G^{(0)})/2r ≥ d/6 ≥ 18 log 3, and therefore we have that ℙ{e(H^{(0)}) ≤ (1/3)e(G^{(0)})} ≤ 1/3. Similarly ℙ{e(H^{(1)}) ≤ (1/3)e(G^{(1)})} ≤ 1/3, and thus a partition as required does exist.

We are now ready to prove our main result.

Theorem 7. Let p and q be distinct primes such that p, q ≡ 1 (mod 4), q^{2} ≥ p, and p is not a square in ℤ/qℤ. Let n = q(q^{2} − 1)/2, t = ⌈(2/3) log_{p}(n/√2)⌉, ℓ = ⌈3t/2⌉, and ε = 2 × 10^{−6}. Suppose t ≥ 2, d = p + 1 ≥ 16ε^{−2ℓ}, and let G = G^{2n} = X^{p,q}. Then, if ℓ + 1 ≤ s ≤ (ε^{ℓ}/6)n^{1/ℓ} + 1, we have G⟶_{p}^{mc}C^{2s}.

Proof. Recall that a partition V_{σ} = S_{σ}^{(0)} ∪ S_{σ}^{(1)} with |S_{σ}^{(0)}| = |S_{σ}^{(1)}| = r = n/2 of V_{σ} (σ = 0, 1) has been fixed. Let us now fix C_{i} and H^{(i)} (i = 0, 1) as in Lemma 6. For both i = 0, 1, we apply Lemma 4 to obtain S̄_{σ}^{(i)} ⊂ S_{σ}^{(i)} with |S̄_{σ}^{(i)}| ≥ n/20 (σ = 0, 1) such that J^{(i)} = H^{(i)}[S̄_{0}^{(i)}, S̄_{1}^{(i)}] is an (r/10f, f)-expander for all 0 < f ≤ d/360^{2}. Since |S̄_{0}^{(0)}|, |S̄_{1}^{(1)}| ≥ n/20, we have e_{G}(S̄_{0}^{(0)}, S̄_{1}^{(1)}) > 0. Let x_{0}x_{1} ∈ E(G) be such that x_{0} ∈ S̄_{0}^{(0)} and x_{1} ∈ S̄_{1}^{(1)}. Let c_{0} = γ(x_{0}x_{1}), and suppose ℓ ≤ ℓ′ ≤ (ε^{ℓ}/6)n^{1/ℓ} ≤ εn^{1/ℓ}. We shall now proceed to find a multicoloured 2s-cycle C^{2s} ⊂ G where s = ℓ′ + 1.

We first apply Lemma 5 to J^{(i)} (i = 0, 1) and obtain T^{(i)} ⊂ S̄_{i+ℓ′} such that (i) |T^{(i)}| = a = ⌈ε^{ℓ}n⌉, and (ii) for all y_{i} ∈ T^{(i)}, there is an x_{i}–y_{i} path P_{y_{i}} ⊂ J^{(i)} in J^{(i)} of length ℓ′ with γ injective on P_{y_{i}} and c_{0} ∉ γ(P_{y_{i}}).

For each y_{i} ∈ T^{(i)} (i = 0, 1), fix an x_{i}–y_{i} path P_{y_{i}} ⊂ J^{(i)} as given in (ii) above. We now notice that, since d ≥ 16ε^{−2ℓ}, we have e_{G}(T^{(0)}, T^{(1)}) ≥ (d/n)a^{2} − 2d^{1/2}a ≥ (d/2n)a^{2}. For i = 0, 1, let

F_{i} = ⋃_{y_{i}∈T^{(i)}} {y_{i}z ∈ E(G) : z ∈ T^{(i+1)}, and γ(y_{i}z) ∈ {c_{0}} ∪ γ(P_{y_{i}})},

and set F = F_{0} ∪ F_{1}. Then |F | ≤ (ℓ′ + 1)|T^{(0)} ∪ T^{(1)}| ≤ 2(ℓ′ + 1)a. Note that since ℓ ≥ 3 and d ≥ 16ε^{−2ℓ}, we have ε^{ℓ}d ≥ 2 × 10^{18}. Thus ℓ′ + 1 ≤ (ε^{ℓ}/6)n^{1/ℓ} + 1 ≤ (ε^{ℓ}/6)2^{1/6}d + 1 < (ε^{ℓ}/4)d, and therefore |E_{G}(T^{(0)}, T^{(1)})\F | ≥ (d/2n)a^{2}−2(ℓ′+1)a = a (ε^{ℓ}d/2 − 2(ℓ′ + 1)) > 0. Finally, suppose y_{0}y_{1} ∈ E_{G}(T^{(0)}, T^{(1)}) \ F. Then, if P_{y_{0}} = x_{0}z_{1}z_{2} … y_{0}, P_{y_{1}} = x_{1}z′_{1}z′_{2} … y_{1}, we have that C = x_{0}z_{1}z_{1} … y_{0}y_{1} … z′_{2}z′_{1}x_{1}x_{0} is a 2s-cycle in G and γ is injective on E(C). This finishes the proof of the theorem.

Recall that for G as in Theorem 7 we have g(G) ≥ 2t, and in fact g(G) is roughly equal to 2t (cf. Lemma 3(i)). Thus in the above result we have G⟶_{p}^{mc}C^{2s} for 2s about (3/2)g(G). Notice, in fact, that this means that the short multicoloured cycles guaranteed by Theorem 7 are necessarily induced. Moreover, note that if ℓ is not too large, then the upper bound for s in Theorem 7 is nearly of the same order as d = p + 1. Thus, since the chromatic index of G is d, the restriction that s should not exceed (ε^{ℓ}/6)n^{1/ℓ} + 1 cannot be essentially weakened.

4. The existence of suitable primes

Theorem 7 states that X = X^{p,q}⟶_{p}^{mc}C^{2s} provided p, q, and s satisfy certain conditions. For brevity, let us say that a pair (p, q) of primes is good if p, q ≡ 1 (mod 4), q ≥ 2p, and p is a quadratic non-residue modulo q. Note that a priori it is not clear that there is any good pair (p, q) of primes that admits an integer s satisfying the conditions in Theorem 7. Our first aim in this section is to present a simple result, Lemma 9, that implies that for any even ℓ ≥ 18 there is a good pair (p, q) such that X = X^{p,q}⟶_{p}^{mc}C^{ℓ} (see Theorem 11). Moreover, we shall see that we may further require the girth g(X) of X to be roughly as large as (2/3)ℓ.

As usual, for an integer n ≥ 1, let φ(n) denote the number of integers 1 ≤ m ≤ n coprime to n. Also, let Λ(n) = log p if n is a positive integer power of a prime p, and let Λ(n) = 0 otherwise. Let a real x > 0 and integers h ≥ 2, a ≥ 1 be given. We put

ψ(x; h, a) = ∑{Λ(n) : 2 ≤ n ≤ x, n ≡ a (mod h)}.

A well-known number-theoretic result states that ψ(x; h, a) = (1 + o(1))x/φ(h) as x → ∞, provided h and a are fixed and (a, h) = 1. In fact, the following refinement of Dirichlet’s celebrated theorem on primes in arithmetic progressions is an easy consequence of the above result. For fixed h and a with (a, h) = 1, we have π(x; h, a) = (1 + o(1))x/φ(h) log x (x → ∞), where π(x; h, a) is the number of primes 2 ≤ p ≤ x with p ≡ a (mod h). We refer the reader to Davenport [9] for this and other related results from analytic number theory.

Below, we shall be interested in the error term in the above asymptotic estimate for ψ(x; h, a). Let us introduce some notation. We put E(x; h, a) = |ψ(x; h, a) − x/φ(h)|, E(x, h) = max{E(x; h, a) : (a, h) = 1}, and E^{∗}(x, h) = max{E(y, h) : 0 < y ≤ x}. The following beautiful and far-reaching result was proved by Bombieri [8] (see also Davenport [9], §28).

Theorem 8. Let A > 0 be fixed. Then there is a constant C = C(A) such that, for x^{1/2}(log x)^{−A} ≤ Q ≤ x^{1/2}, we have ∑_{2≤h≤Q} E^{∗}(x, h) ≤ Cx^{1/2}Q(log x)^{5}.

In particular, the above result implies that E^{∗}(x, h) is a great deal smaller than x/φ(h) for most h ≤ x^{1/2}(log x)^{−A}. Furthermore, clearly, Theorem 8 states that under the given conditions the average error Ave_{2≤h≤Q} E^{∗}(x, h) is O{x^{1/2}(log x)^{5}}. We remark in passing that assuming the generalised Riemann hypothesis, one may prove that E(x, h) = O{x^{1/2}(log x)^{2}} for x ≥ h (cf. §20 in [9]). Such a bound for E(x, h) would allow us to give a more direct proof of the existence of appropriate good pairs of primes.

The main lemma of this section is Lemma 9. For its proof we shall need the following simple result. For x > 0 put ψ_{2}(x) = ∑ Λ(n), where the sum is extended over all 2 ≤ n = p^{k} ≤ x with p a prime and k ≥ 2 an integer. Then, by the prime number theorem, we have that ψ_{2}(x) ≤ (2 + o(1))x^{1/2} as x → ∞. Let us now turn to Lemma 9. Suppose a set H = {h_{i} ∈ ℕ : i ≥ 1} of integers is fixed, and assume 2 ≤ h_{1} < h_{2} < · · · . Moreover, let integers 1 ≤ a_{i} < h_{i} (i ≥ 1) be given.

Lemma 9. Suppose that for a constant ρ > 0 we have |H ∩ [n]| = (ρ + o(1))n/ log n as n → ∞. Let 0 < η < 1/2 and b > 0 be fixed. Then there is h_{i} ∈ H and a prime q such that h_{i} ≥ b, q ≡ a_{i} (mod h_{i}), and (h_{i}/4)^{1/η}/4 ≤ q ≤ (h_{i}/4)^{1/η}.

Proof. Let A = 7 in Theorem 8, and set C = C(7). Pick Q ≥ 2, and let x_{0} = x_{0}(Q) be such that Q = x_{0}^{1/2}(log x_{0})^{−7}. Assume that Q is sufficiently large so that (i) 4x_{0}^{η} ≥ b, (ii) log x_{0} ≥ (80C/ρ)2^{η}, (iii) x_{0}^{1/2−η} ≥ 60 × 2^{η}, and (iv) ψ_{2}(x_{0}) ≤ 3x_{0}^{1/2}. Now note that, as x → ∞,

\begin{aligned}N(x) & = |\{h ∈ H : 4x^{η} < h ≤ 4(2x)^{η}\}| \\ & = (4ρ + o(1))\frac{(2x)^{η}}{η log(2x)} − (4ρ + o(1))\frac{x^{η}}{η log x}, \end{aligned}

which is, for large enough x, at least

\frac{4ρx^{η}}{η log x} (2^{3η/4} − 2^{η/4}) ≥ 2ρ(log 2)x^{η}(log x)^{−1} ≥ ρx^{η}(log x)^{−1}.

Thus we may further assume that Q is sufficiently large to guarantee that N(x_{0}) ≥ ρx_{0}^{η}(log x_{0})^{−1}. Now, by Theorem 8, we clearly have that E^{∗}(x_{0}, h) ≥ (2C/ρ)x_{0}^{1−η}(log x_{0})^{−1} holds for at most (ρ/2)x_{0}^{η}(log x_{0})^{−1} values of 2 ≤ h ≤ Q. Thus there is h_{i} ∈ H such that b ≤ 4x_{0}^{η} < h_{i} ≤ 4(2x_{0})^{η}, and E^{∗}(x_{0}, h_{i}) ≤ (2C/ρ)x_{0}^{1−η}(log x_{0})^{−1}. Hence we have E(x_{0}; h_{i}, a_{i}), E(x_{0}/2; h_{i}, a_{i}) ≤ (2C/ρ)x_{0}^{1−η}(log x_{0})^{−1}. Therefore

\begin{aligned}ψ(x_{0}; h_{i}, a_{i}) − ψ(x_{0}/2; h_{i}, a_{i}) & ≥ \frac{x_{0}}{2φ(h_{i})} − \frac{4C}{ρ} · \frac{x_{0}^{1−η}}{log x_{0}} \\ & ≥ \frac{x_{0}}{10φ(h_{i})} + ψ_{2}(x_{0}) > ψ_{2}(x_{0}), \end{aligned}

where for the second inequality we use (ii) and (iii) above. Thus there is a prime q such that x_{0}/2 < q ≤ x_{0} and q ≡ a_{i} (mod h_{i}). Finally, note that (h_{i}/4)^{1/η}/4 ≤ x_{0}/2 < q ≤ x_{0} ≤ (h_{i}/4)^{1/η}.

We now apply the above lemma to our particular set-up. For a, b ≥ 2, let ℓ(a, b) = ⌈(3/2)⌈(2/3) log_{a}(n(b)/√2)⌉⌉, where n(b) = b(b^{2} − 1)/2. Note that in Theorem 7, we have ℓ = ℓ(p, q).

Lemma 10. Let P ≥ 2 and ℓ_{0} ≥ 8 be given. Then (i) if ℓ_{0} ≡ 0 or 2 (mod 3), there is a good pair (p, q) of primes with p ≥ P and ℓ(p, q) = ℓ_{0}, and (ii) if ℓ_{0} ≡ 1 (mod 3), then there is a good pair (p, q) of primes with p ≥ P and ℓ(p, q) = ℓ_{0} + 1.

Proof. (i) We may clearly assume that P ≥ 53. Let p_{i} (i ≥ 1) be the ith prime congruent to 1 modulo 4. Let h_{i} = 4p_{i}, and set H = {h_{i} : i ≥ 1}. Note that H ∩ [n] = {h_{i} = 4p_{i} : p_{i} ≤ n/4}, and so |H ∩ [n]| = π(n/4; 4, 1). Thus |H ∩ [n]| = (1/8 + o(1))n/ log n as n → ∞. Now let 1 ≤ s_{i} < p_{i} (i ≥ 1) be such that 4s_{i} ≡ 1 (mod p_{i}), and let 1 ≤ r_{i} < p_{i} (i ≥ 1) be a quadratic non-residue modulo p_{i}. Let 1 ≤ a_{i} < h_{i} (i ≥ 1) be such that a_{i} ≡ 4s_{i}r_{i} + p_{i} (mod h_{i}). We now define 0 < η < 1/2 as follows. If ℓ_{0} ≡ 0 (mod 3), we let η = 3/ℓ_{0}, and if ℓ_{0} ≡ 2 (mod 3), we let η = 6/(2ℓ_{0} − 1). Set b = 4P. Lemma 9 then gives that, for some i ≥ 1 and some prime q, we have p_{i} ≥ P, q ≡ 4s_{i}r_{i} + p_{i} (mod 4p_{i}), and (1/4)p_{i}^{1/η} ≤ q ≤ p_{i}^{1/η}. But then q ≡ 1 (mod 4) and q is a quadratic non-residue modulo p_{i}. By the law of quadratic reciprocity, we have that p_{i} is a quadratic non-residue modulo q. Since η < 1/2, we may deduce from q ≥ (1/4)p_{i}^{1/η} that q ≥ 2p_{i}. Thus (p_{i}, q) is good. Moreover, a simple but a little tedious calculation shows that indeed ℓ(p_{i}, q) = ℓ_{0} (the assumption P ≥ 53 is used here). This finishes the proof of (i). Assertion (ii) follows immediately from (i).

With Lemma 10 in hand, we may easily show that for any even L ≥ 18 there is a good pair (p, q) such that X^{p,q}⟶_{p}^{mc}C^{L}.

Theorem 11. Suppose s ≥ 9 and L = 2s. Then there is a good pair (p, q) of primes such that (i) X = X^{p,q}⟶_{p}^{mc}C^{L}, and (ii) g(X) ≥ (2/3)(L − 4) if s ≡ 0 or 1 (mod 3) and g(X) ≥ (2/3)(L − 2) otherwise.

5. Very short multicoloured cycles In the introduction we remarked that we have t(C^{ℓ}) = ℓ for all 3 ≤ ℓ ≤ 6. For ℓ ∈ {3, 4} this statement can be verified by considering the complete graph K^{14} and the complete bipartite graph K^{4,4}. Now, for ℓ = 6 we take a projective plane P of large order, and consider its incidence bipartite graph, namely, the bipartite graph I = I(P) with vertex classes V_{0}, V_{1}, where V_{0} = V_{0}(P) is the set of points of P and V_{1} = V_{1}(P) is the set of lines of P, and with xy ∈ E(I) (x ∈ V_{0}, y ∈ V_{1}) if and only if x and y are incident in P. By estimating the maximal possible number of non-multicoloured 6-cycles in a properly edge-coloured I = I(P), we may verify that I⟶_{p}^{mc}C^{6} for a large enough P. Since g(I) = 6, we conclude that t(C^{6}) = 6.

For completeness, we check here that t(C^{5}) = 5: using probabilistic methods we shall ‘construct’ a suitable graph G to verify this fact. Our method of proof might be of some use to prove upper bounds for t(C^{ℓ}) for large odd ℓ. Our random construction of G is based again on large projective planes P.

The construction of G. Let P be a projective plane of order q, and let n = q^{2} + q + 1. Thus I is a (q+1)-regular bipartite graph and we have |V_{0}| = |V_{0}(P)| = |V_{1}| = |V_{1}(P)| = n. By considering random partitions, we may assume that V_{0} = A_{0} ∪ A_{1} ∪ A_{2}, V_{1} = B_{1} ∪ B_{2} are partitions of V_{0} and V_{1} such that, for all i ∈ {0, 1, 2} and j ∈ {1, 2}, we have (i) n/6 ≤ |A_{i}| ≤ n/2, n/3 ≤ |B_{j}| ≤ 2n/3, and (ii) |Γ_{I}(x) ∩ B_{j}| ≥ (q + 1)/3 for all x ∈ V_{0}, and |Γ_{I}(y) ∩ A_{i}| ≥ (q + 1)/4 for all y ∈ V_{1}.

We next define H ⊂ I by deleting the edges in E_{I}(A_{1}, B_{2}) ∪ E_{I}(A_{2}, B_{1}) from I. Now let p = ω/n, where ω = ω(n) = 4 log n. For all pairs (a_{1}, a_{2}) ∈ A_{1} × A_{2}, add the edge a_{1}a_{2} to H independently with probability p, and let J be the resulting random graph. Our aim now is to verify that, almost surely, we may delete some edges from E_{J}(A_{1}, B_{1}) ∪ E_{J}(A_{2}, B_{2}) ∪ E_{J}(A_{1}, A_{2}) from J in such a way that the resulting graph G is such that (iii) |Γ_{G}(y) ∩ A_{i}| ≥ (q + 1)/5 for all y ∈ V_{1}, i ∈ {1, 2}, (iv) for any U ⊂ A_{1}, W ⊂ A_{2} with |U|, |W | ≥ n/15, we have e_{G}(U, W) ≥ p|U||W |/2, and (v) all vertices z ∈ A_{1} ∪ A_{2} have degree d_{G[A_{1},A_{2}]}(z) = O(ω) in G[A_{1}, A_{2}].

Let us choose which edges from E_{J}(A_{1}, B_{1}) we shall delete. To this end, we first concentrate our attention on a vertex y ∈ B_{1}. Choose a maximum collection of edgedisjoint quadrilaterals C^{4} ⊂ J[A_{1}, A_{2} ∪ {y}] that contain y, and let E_{y} be the edges incident to y present in this collection. The edges we delete from E_{J}(A_{1}, B_{1}) are the ones in E_{1} = ⋃_{y∈B_{1}} E_{y}. In exactly the same way, we define a set E_{2} ⊂ E_{J}(A_{2}, B_{2}) of edges of J to be deleted from J.

Finally, let E_{12} ⊂ E_{J}(A_{1}, A_{2}) be the set of all the edges present in 4-cycles C^{4} ⊂ J[A_{1}, A_{2}]. Define now G to be the subgraph G = J − (E_{1} ∪ E_{2} ∪ E_{12}) of J. It is quite easy to check that (iii), (iv), and (v) above hold in G almost surely. Let us fix G satisfying such conditions. This completes the ‘construction’ of G. Claim. We have g(G) = 5 and G⟶_{p}^{mc}C^{5}. Proof of the Claim. It is immediate that g(G) ≥ 5. To verify the second assertion in our claim, we use the counting argument of Rödl and Tuza [22], which applies very easily here owing to our definition of G. It is easily seen that any vertex a_{0} ∈ A_{0} belongs to Ω(ωn) cycles C^{5} ⊂ G, and hence the total number of copies of C^{5} in G is Ω(ωn^{2}). Let now γ : E(G) → ℕ be a fixed proper edge-colouring of G, and let us count the number of non-multicoloured C^{5} contained in G. Let us write a_{0}b_{1}a_{1}a_{2}b_{2} for a 5-cycle of G, where naturally a_{i} ∈ A_{i} and b_{j} ∈ B_{j} (i ∈ {0, 1, 2}, j ∈ {1, 2}). How many such C^{5} have the edges a_{0}b_{1} and a_{2}b_{2} of the same colour? For such cycles, the number of possibilities for a_{0}b_{1} is O(n^{3/2}) and for a_{0}b_{2}, given a_{0}b_{1}, is O(n^{1/2}). Also, given a_{0}b_{1} and a_{0}b_{2}, there is at most one possibility for a_{2}b_{2} as this edge must be incident to b_{2} and must have the same colour as a_{0}b_{1}. Finally, there is at most one vertex a_{1} ∈ A_{1} with a_{1}a_{2}, a_{1}b_{1} ∈ E(G). Thus the total number of 5-cycles a_{0}b_{1}a_{1}a_{2}b_{2} in G with the edges a_{0}b_{1}, a_{2}b_{2} of the same colour is O(n^{2}). Analysing a few more cases, one checks that the number of non-multicoloured 5-cycles in G is O(n^{2}). Since the total number of 5-cycles in G is Ω(ωn^{2}), we are done.

In view of our results for t(C^{ℓ}) for ℓ even, the method above might apply to give improved lower estimates for t(C^{ℓ}) for large odd ℓ. This would be an interesting problem to consider.

6. Some generalisations The technique used in [22] to prove Theorem 1 gives two results of a more general nature. Roughly speaking, these results assert the existence of graphs G of large girth satisfying G⟶_{p}^{mc}H for any very sparse graph H. Given a graph H, let m(H) = max{e(H′)/|H′|}, where the maximum is taken over all subgraphs H′ ⊂ H of positive order. Using a simple ‘decomposition’ result given in [22] (cf. the proof of Theorem 2 in [22]), and the methods of Sections 2 and 3 above applied to the non-bipartite Ramanujan graphs X^{p,q} of Lubotzky, Phillips, and Sarnak [18] (so here p is a quadratic residue modulo q), one may prove the following result.

Theorem 12. Let t, h ≥ 3 be given. Then there exist primes p and q, a real μ > 0, and an integer g ≥ 3 such that if G = G_{t,h} = X^{p,q}, then (i) g(G) ≥ t and (ii) G⟶_{p}^{mc}H for every graph H with m(H) ≤ 1 + μ, g(H) ≥ g, and |H| ≤ h.

Theorem 12 above has as an immediate corollary Theorem 13 below. For two graphs G and H, let us write G⟶_{p}^{mc}TH if for any proper edge-colouring γ of G, there is a subgraph H′ ⊂ G of G that is a subdivision of H and such that γ is injective on E(H′).

Theorem 13. Let t, k ≥ 3 be given. Then there exist primes p and q such that if G = G_{t,k} = X^{p,q}, then (i) g(G) ≥ t and (ii) G⟶_{p}^{mc}TK^{k}.

Note that this result settles a generalised version of Spencer’s original question. Indeed, when k = 3 this theorem asserts the existence of graphs of arbitrarily large girth that have the property that however they are properly edge-coloured, we may always find a multicoloured cycle in them. Moreover, Theorem 13 tells us that suitable Ramanujan graphs have this property. The existence of the graphs G_{t,h} and G_{t,k} as above was proved in [22] by non-constructive means, and no explicit examples of such graphs were given. Our aim in this section is to give a sketch of proof for Theorem 12.

We start with some preparation concerning the decomposition result given in [22]. Let an integer s ≥ 1 be given. A sequence of graphs (F_{k})_{0}^{m} is an s-decomposition series for a graph H if K^{1} = F_{0} ⊂ ⋯ ⊂ F_{m} = H and, for all 1 ≤ k ≤ m, the graph F_{k} is obtained from F_{k−1} either by the addition of an isolated vertex or of a vertex of degree one, or else by the addition of an x′–y′ path of order at least s, by joining x′ (respectively y′) to a vertex x ∈ F_{k−1} (respectively y ∈ F_{k−1}), where x and y are not necessarily distinct. Thus, more precisely, we either have |F_{k}| = |F_{k−1}| + 1, V (F_{k}) = V (F_{k−1}) ∪ {x}, and d_{F_{k}}(x) ≤ 1, or else we have |F_{k}| ≥ |F_{k−1}| + s, for all w ∈ W = V (F_{k}) \ V (F_{k−1}) we have d_{F_{k}}(w) = 2, and W induces a path in F_{k}.

For sparse graphs of large girth, as shown by Rödl and Tuza [22], we have the following simple result on the existence of decomposition series.

Lemma 14. If a graph H is such that m(H) < 1 + 1/(3s − 1) and g(H) ≥ s + 1, then H admits an s-decomposition series.

To prove Theorem 12, in addition to Lemma 14 we need a somewhat cumbersome technical lemma, namely Lemma 15 below. Before we can state that result, we need to introduce a few definitions and some notation. Let us fix a non-bipartite Ramanujan graph G = G^{n} = X^{p,q}, and recall that (†) the inequality in Lemma 3(iii) holds for any two disjoint sets U, W ⊂ V (G) (cf. Alon and Spencer [4], Chapter 9, Section 2). Suppose γ : E(G) → ℕ is a fixed proper edge-colouring of G. Let m ≥ 1 be fixed, and let V = V (G) = V_{0} ∪ ⋯ ∪ V_{m} be a partition of V such that n′ = |V_{1}| = … = |V_{m}| is even and ⌊n/2m⌋ ≤ n′ ≤ ⌊n/2m⌋ + 1. Also, for 1 ≤ k ≤ m, let V_{k} = S_{k} ∪ T_{k} be a partition of V_{k} with |S_{k}| = |T_{k}|, and let G′_{k} = G[S_{k}, T_{k}] be the bipartite graph induced by the vertex classes S_{k} and T_{k} in G. Now let ℕ = C_{1} ∪ ⋯ ∪ C_{m} be a partition of ℕ, and let G_{k} = G′_{k}[γ^{−1}(C_{k})] (1 ≤ k ≤ m). Now, the argument used in the proof of Lemma 6 gives that there is a partition (C_{k})_{1}^{m} of ℕ such that e(G_{k}) ≥ (1/2m)e(G′_{k}) (1 ≤ k ≤ m), provided d = p + 1 is at least as large as a constant d_{0} = d_{0}(m) depending only on m. In the sequel, we assume that our partition (C_{k})_{1}^{m} is as above. Moreover, from now on we tacitly assume that d = p + 1 is large enough with respect to m.

Lemma 15. Let m ≥ 1 be fixed. Then there are constants c_{i} > 0 (0 ≤ i ≤ 3) depending only on m satisfying the following property. For each i ∈ {0, 1} and 1 ≤ k ≤ m, there are sets S_{k}^{(i)} ⊂ S_{k}, T_{k}^{(i)} ⊂ T_{k}, and a vertex x_{0} ∈ V_{0} such that S_{k}^{(0)} ∩S_{k}^{(1)} = ∅ and T_{k}^{(0)} ∩T_{k}^{(1)} = ∅ (1 ≤ k ≤ m) and such that the following holds. Let J_{k}^{(i)} = G_{k}[S_{k}^{(i)}, T_{k}^{(i)}] (i ∈ {0, 1}, 1 ≤ k ≤ m). Then, for all 1 ≤ k ≤ m and i ∈ {0, 1}, we have

(i) |S_{k}^{(i)}|, |T_{k}^{(i)}| ≥ r_{k} = c_{1}^{m−k}r, where r ≥ c_{0}n, (ii) |Γ_{G}(x_{0}) ∩ S_{k}^{(i)}| ≥ d|S_{k}^{(i)}|/2n and |Γ_{G}(x_{0}) ∩ T_{k}^{(i)}| ≥ d|T_{k}^{(i)}|/2n, (iii) for all k < ℓ ≤ m, and i_{k}, i_{ℓ} ∈ {0, 1}, if x ∈ J_{k}^{(i_{k})} then |Γ_{G}(x) ∩ S_{ℓ}^{(i_{ℓ})}| ≥ d|S_{ℓ}^{(i_{ℓ})}|/2n

and |Γ_{G}(x) ∩ T_{ℓ}^{(i_{ℓ})}| ≥ d|T_{ℓ}^{(i_{ℓ})}|/2n, (iv) J_{k}^{(i)} is (c_{2}r_{k}/f, f)-expanding for all 0 < f ≤ c_{3}d.

We only briefly describe a proof of Lemma 15. We start by applying the ‘bipartite version’ of Szemerédi’s lemma for subgraphs of pseudo-random graphs (see [16]) to the graphs G_{k} ⊂ G′_{k}, with an appropriately small ε = ε(m) > 0. This gives us sets S′_{k} ⊂ S_{k}, T′_{k} ⊂ T_{k} (1 ≤ k ≤ m) with |S′_{k}| = |T′_{k}| = Ω(n) for all k and such that G_{k}[S′_{k}, T′_{k}] is (ε, G_{k}, G′_{k})-regular and e(G_{k}[S′_{k}, T′_{k}]) ≥ (1/3m)e(G′_{k}[S′_{k}, T′_{k}]). (For the definition of these terms, the reader is referred to [16].) We now define the sets S_{k}^{(i)}, T_{k}^{(i)} as required in the lemma by reverse induction on k, and we define the vertex x_{0} last.

Let us first split S′_{m} and T′_{m} into pairs of sets of cardinality as equal as possible, say S′_{m} = S_{m,0} ∪ S_{m,1} and T′_{m} = T_{m,0} ∪ T_{m,1}. Applying the argument we used in the proof of Lemma 4, we may find suitable sets S_{m}^{(i)} ⊂ S_{m,i}, T_{m}^{(i)} ⊂ T_{m,i} (i ∈ {0, 1}) as required. Now we alter the sets S′_{k}, T′_{k} (1 ≤ k < m) to guarantee (iii) in our lemma: we delete from S′_{k}∪T′_{k} any vertex x for which |Γ_{G}(x)∩S_{m}^{(i)}| < d|S_{m}^{(i)}|/2n or |Γ_{G}(x)∩T_{m}^{(i)}| < d|T_{m}^{(i)}|/2n for some i ∈ {0, 1}. Let S′′_{k} ⊂ S′_{k}, T′′_{k} ⊂ T′_{k} be the sets we obtain in this way, and then note that by (†) we have |S′′_{k}| ≥ |S′_{k}|/2, |T′′_{k}| ≥ |T′_{k}|/2 (1 ≤ k < m). Moreover, by the (ε, G_{k}, G′_{k})-regularity of G_{k}[S′_{k}, T′_{k}] ⊂ G′_{k}[S′_{k}, T′_{k}], we have e(G_{k}[S′′_{k}, T′′_{k}]) ≥ (1/6m)e(G′_{k}[S′′_{k}, T′′_{k}]) (1 ≤ k < m).

We now consider S′′_{k}, T′′_{k} (1 ≤ k < m), and by induction find sets S_{k}^{(i)}, T_{k}^{(i)} (i ∈ {0, 1}, 1 ≤ i < k) satisfying (i), (iii), and (iv) in Lemma 15. This completes the definition of the sets S_{k}^{(i)}, T_{k}^{(i)}. The existence of a suitable vertex x_{0} ∈ V_{0} satisfying Lemma 15(ii) follows from (†). Finally, we note that Theorem 12 follows from Lemmas 14 and 15.

Proof of Theorem 12 . Let t, h ≥ 3 be fixed, and note that we may clearly assume that t ≥ 4. Let g = 4 + 3t and suppose μ < 1/(9t + 8) is a fixed real. Moreover, let p, q be primes congruent to 1 modulo 4 with p a quadratic residue modulo q. Arguing in the same way as in Section 4, we see that there are arbitrarily large primes p and q as above satisfying the additional property that p^{t/2} ≤ q ≤ 2p^{t/2}. Let us fix such a pair (p, q) with p large enough with respect to h. From the properties of p and q above, we see that the Ramanujan graph G = G^{n} = X^{p,q} of Lubotzky, Philips, and Sarnak [18] is non-bipartite, has order n = q(q^{2} −1)/2, has girth g(G) ≥ t, and is d-regular with d = p+1 ≥ 2^{−4/9}n^{2/3t}. We claim that G will do in Theorem 12 for the given values of t and h.

Let H be a graph of order h with m(H) ≤ 1+μ and girth g(H) ≥ g. Let γ : E(G) → ℕ be a proper edge-colouring of G. We shall show that G admits a multicoloured copy of H with respect to γ. To do so, let (F_{k})_{0}^{m} be an s-decomposition series for H with s = 3t + 3. Also, fix partitions (V_{k})_{0}^{m} and (C_{k})_{1}^{m} as in the paragraph before Lemma 15, and apply that lemma. Now, the argument used in the proof of Lemma 5 and Theorem 7, coupled with a simple induction, successively gives that multicoloured copies of the graphs K^{1} = F_{0} ⊂ F_{1} ⊂ ⋯ are present in G, and hence a multicoloured copy of H does appear in G, as required. We omit the details.

We close with a Ramsey type result. As customary, for graphs G and H and an integer r ≥ 2, write G → (H)_{r} if in any (not necessarily proper) edge-colouring of G with r-colours we may find a monochromatic copy of H. By making use of Szemerédi’s regularity lemma for subgraphs of pseudo-random graphs [16], one may prove the following result (cf. [15]).

Theorem 16. Let r ≥ 2 be given. Then there are constants c_{0} = c_{0}(r) > 0 and p_{0} = p_{0}(r) such that the following holds. Let p and q be two unequal primes such that p, q ≡ 1 (mod 4), p ≤ q^{2}, and p is a square in ℤ/qℤ. Let t ≥ 3 be given. If p ≥ p_{0} and q ≥ q_{0} = q_{0}(r, p, t), where q_{0} = q_{0}(r, p, t) depends only on r, p, and t, then G = G^{n} = X^{p,q} is such that (i) e(G) = (p + 1)n/2, (ii) g(G) ≥ t, and (iii) G → (C^{s})_{r} for any integer s with 4 log_{2} n + 1 ≤ s ≤ c_{0}n.

This result has a simple consequence concerning multicoloured cycles in edge-coloured graphs. Let r ≥ 1 be given. Let us say that a (not necessarily proper) edge-colouring γ : E(G) → ℕ of a graph G is r-bounded if |γ^{−1}({i})| ≤ r for all i ∈ ℕ. Let us write G⟶_{r}^{mc}H if, for any r-bounded edge-colouring of G, there is a multicoloured copy of H in G. Clearly, if for two graphs G and H we have G → (H)_{r}, then G⟶_{r}^{mc}H. Thus, Theorem 16 implies that in r-bounded edge-colourings of Ramanujan graphs, we can always find very long multicoloured cycles. This is of some interest in view of the remark in the last paragraph of Section 3. For a related result, the reader is referred to Frieze and Reed [13], where it is proved that, for some large constant A, any r-bounded edge-colouring of the complete graph K^{n} admits a multicoloured Hamilton cycle, where r = r(n) = n/A log n. Hahn and Thomassen [14] conjecture that the statement above holds for some r = r(n) = Ω(n).

Acknowledgements. This work is part of the PhD thesis of the first author, who worked under the supervision of Dr B. Bollobás at the University of Cambridge, and was supported by an NSERC Canada 1967 Science and Engineering Scholarship. The second author was supported by Churchill College, Cambridge, where he was a Junior Research Fellow while this work was being done. The authors are indebted to Drs B. Bollobás and L. Babai for their insightful comments on previous versions of this note.

References

[1] Alon, N., Eigenvalues and expanders, Combinatorica 6 (1986), 83–96.

[2] Alon, N., Chung, F.R.K., Explicit construction of linear sized tolerant networks, Discrete Math. 72 (1988), 15–19.

[3] Alon, N., Milman, V.D., λ_{1}, isoperimetric inequalities for graphs and superconcentrators, J. Combinatorial Theory (B) 38 (1985), 73–88.

[4] Alon, N., Spencer, J.H., The Probabilistic Method, John Wiley and Sons, Inc., New York 1992, xiii + 254pp.

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

[6] Beck, J., On size Ramsey number of paths, trees, and circuits I, J. Graph Theory 7 (1983), 115–129.

[7] Biggs, N.L., Boshier, A.G., Note on the girth of Ramanujan graphs, J. Combinatorial Theory (B) 49 (1990), 190–194.

[8] Bombieri, E., On the large sieve, Mathematika 12 (1965), 201–225.

[9] Davenport, H., Multiplicative Number Theory, Second edition, Graduate Texts in Mathematics 74, Springer–Verlag, New York 1980, xiv + 177pp.

[10] Erdős, P., Some old and new problems in various branches of combinatorics, Cong. Numerantium 23 (1979), 19–37.

[11] Erdős, P., Rado, R., A combinatorial theorem, J. London Math. Soc. 25 (1950), 249–255.

[12] Friedman, J., Pippenger, N., Expanding graphs contain all small trees, Combinatorica 7 (1987), 71–76.

[13] Frieze, A., Reed, B., Polychromatic Hamilton cycles, to appear.

[14] Hahn, G., Thomassen, C., Path and cycle sub-Ramsey numbers and an edge-colouring conjecture, Discrete Math. 62 (1986), 29–33.

[15] Haxell, P.E., Extremal and Ramsey Type Results for Graphs and Hypergraphs, PhD thesis, University of Cambridge, March 1993.

[16] Kohayakawa, Y., A version of Szemerédi’s regularity lemma for sparse pseudo-random graphs, manuscript.

[17] Lefmann, H., On an anti-Ramsey type result, Pre-print 91–023, Universität Bielefeld, 1991.

[18] Lubotzky, A., Phillips, R., Sarnak, P., Ramanujan graphs, Combinatorica 8 (1988), 261–277.

[19] Margulis, G.A., Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators, Problemy Peredachi Informatsii 24 (1988), 51–60 (in Russian), English translation in Problems of Information Transmission 24 (1988), 39–46.

[20] Nešetřil, J., Rödl, V., Partite construction and Ramsey space systems, in Mathematics of Ramsey Theory, Algorithms and Combinatorics 5 (Nešetřil, J., Rödl, V., eds), Springer-Verlag, Berlin 1990, pp. 98–112.

[21] Prömel, H.J., Voigt, B., Canonizing Ramsey theorems for finite graphs and hypergraphs, Discrete Math. 54 (1985), 49–59.

[22] Rödl, V., Tuza, Zs., Rainbow subgraphs in properly edge-coloured graphs, Random Structures and Algorithms 3 (1992), 175–182.

[23] Szemerédi, E., Regular partitions of graphs, in Problèmes en Combinatoire et Théorie des Graphes, Proc. Colloque Inter. CNRS (Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., Sotteau, D., eds), CNRS, Paris 1978, pp. 399–401.