The Size-Ramsey Number of Trees

P.E. Haxell^{1∗} and Y. Kohayakawa^{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, let us write G → (H)_{2} if G contains a monochromatic copy of H in any 2-colouring of the edges of G. The size-Ramsey number r_{e}(H) of a graph H is the smallest possible number of edges a graph G may have if G → (H)_{2}. Suppose T is a tree of order |T | ≥ 2, and let t_{0}, t_{1} be the cardinalities of the vertex classes of T as a bipartite graph, and let Δ(T) be the maximal degree of T. Moreover, let Δ_{0}, Δ_{1} be the maxima of the degrees of the vertices in the respective vertex classes, and let β(T) = t_{0}Δ_{0}+t_{1}Δ_{1}. Beck [7] proved that β(T)/4 ≤ r_{e}(T) = O{β(T)(log |T |)^{12}}, improving on a previous result of his [6] stating that r_{e}(T) ≤ Δ(T)|T |(log |T |)^{12}. In [6], Beck conjectures that r_{e}(T) = O{Δ(T)|T |}, and in [7] he puts forward the stronger conjecture that r_{e}(T) = O{β(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing that r_{e}(T) = O{β(T) log Δ(T)}.

1991 Mathematics Subject Classification 05 C 55, 05 C 05, 05 C 80

∗Current address: Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNPq (Proc. 300334/93–1).

1. Introduction

In this note we are concerned with a numerical problem in Ramsey theory: we shall study the size-Ramsey number of trees. Before we proceed, let us introduce some notation and definitions. For a graph G, we write |G| for the order |V (G)| of G, and e(G) for its size e(G). Let a real 0 ≤ γ ≤ 1 and an integer r ≥ 2 be fixed, and suppose G and H are graphs. We write G →_{γ} H if any subgraph J ⊂ G of G with size e(J) ≥ γe(G) contains an isomorphic copy of H as a subgraph, and we write G → (H)_{r} if G contains a monochromatic copy of H in any edgecolouring of G with r colours.

Settling a one-hundred-dollar problem of Erdős, ten years ago Beck [6] proved the following striking result. Let P^{t} be the path of order t. If 0 < γ ≤ 1 and p = C_{γ}/n, where C_{γ} > 0 is a constant that depends only on γ, then the random graph G_{p} = G_{n,p} ∈ G(n, p) is almost surely such that G →_{γ} P^{t} for t = ⌊C_{γ}^{−1}n⌋. As an immediate corollary, one has that for any fixed r ≥ 2 the r-size-Ramsey number

r_{e}(H, r) = min{e(G): G → (H)_{r}}  (1)

of the path H = P^{t} is O(c_{r}t) for some constant c_{r} that depends only on r. Also in [6], Beck shows by non-constructive means that the size-Ramsey number r_{e}(T) = r_{e}(T, 2) of a tree T = T^{t} of order t and maximal degree Δ = Δ(T) is not greater than Δt(log t)^{12}. (The proof of this result is complex and it is heavily based on the probabilistic method: besides random graphs, the Erdős–Lovász sieve is used.) Thus, for trees of bounded maximal degree, the size-Ramsey number is nearly linear in |T |. Indeed, Beck conjectures in [6] that r_{e}(T) = O{Δ(T)|T |}.

More recently, Friedman and Pippenger [11] improved on Beck’s result by showing that, for trees T of bounded maximal degree, it does indeed hold that the size-Ramsey number r_{e}(T) is linear in |T |. The proof in [11] is based on a new, beautiful tree-universality result for expanding graphs. With this result in hand, basically following Alon and Chung [3] and Beck [6], Friedman and Pippenger [11] prove the following result. Let 0 < γ ≤ 1, and 1 ≤ Δ < t be given. Then, for suitable primes p and q, the Ramanujan graph X = X^{p,q} constructed by Lubotzky, Phillips, and Sarnak [16] is such that (i) e(X) ≤ cΔ^{4}γ^{−3}t, where c is an absolute constant, and (ii) X →_{γ} T for any tree T of order |T | ≤ t and maximal degree Δ(T) ≤ Δ. Note that this is a ‘density’ type result rather than a Ramsey-theoretical one, by which we mean that it concerns the property G →_{γ} T rather than G → (T)_{r}. Clearly, the Friedman–Pippenger result above implies that r_{e}(T) = O{Δ(T)^{4}|T |} for any tree T. This bound has very recently been improved by Ke [14], who proved a density type result implying that r_{e}(T) = O{Δ(T)^{2}|T |}. Our first main result in this note, Theorem 9 (see also Corollary 10), improves this to r_{e}(T) = O{Δ(T)|T |}, thus verifying the conjecture of Beck [6].

Now, note that if T is the (t − 1)-star K^{1,t−1} (t ≥ 2), then clearly r_{e}(T) = 2t − 3, whereas Δ(T)|T | = t(t − 1). Thus the bound r_{e}(T) = O{Δ(T)|T |} may be far from sharp for some trees T. Beck [7] has identified what seems to be the ‘correct’ parameter of a tree T that determines the order of r_{e}(T). If T has bipartition V (T) = V_{0}(T) ∪ V_{1}(T) and t_{σ} = |V_{σ}(T)|, Δ_{σ} = Δ_{σ}(T) = max{d(v): v ∈ V_{σ}(T)} (σ ∈ {0, 1}), let β(T) = t_{0}Δ_{0} + t_{1}Δ_{1}. Note that for instance β(K^{1,t−1}) = 2(t − 1) and moreover β(T) ≤ Δ(T)|T | for any tree T. Improving his previous result, Beck [7] proved that

β(T)/4 ≤ r_{e}(T) ≤ Cβ(T)(log |T |)^{12}  (2)

for any tree T and some absolute constant C, and thus determined r_{e}(T) up to a (log |T |)^{12} factor. Beck conjectures in [7] that the lower bound in (2) gives the correct order of r_{e}(T), i.e. that r_{e}(T) = O{β(T)}. We are unable to prove this conjecture, but here we considerably improve the upper bound in (2) by showing that r_{e}(T) ≤ Cβ(T) log Δ(T) for some absolute constant C. Furthermore, the result of Beck that gives the upper bound in (2) is intrinsically Ramsey-theoretical, whereas ours is a density type result.

Our method is based on the Friedman–Pippenger tree-universality result. We in fact obtain a variant of that result using the same argument, and then we show how our bounds follow from this variant and a simple result concerning random bipartite graphs. Our methods are non-constructive owing to the use of random graphs, but we remark that, for most trees T, there are explicit constructions of graphs G that give r_{e}(T) = O{Δ(T)|T |}. These constructions are based on the Ramanujan graphs X^{p,q} of Lubotzky, Phillips, and Sarnak [16], and certain Cayley graphs of Abelian groups due to Alon [2]. For trees T with Δ(T) about |T |^{1−1/d} for some integer d ≥ 2, we may prove that r_{e}(T) = O{Δ(T)|T |} constructively by considering projective geometries. (See Section 5).

This note is organised as follows. Our variant of Friedman and Pippenger’s tree-universality result is stated and proved in Section 2, and in the following section we give the results concerning random bipartite graphs that we need. For the inequalities used in Section 3 as well as for definitions not given here in detail, we refer the reader to [8]. In Section 4 we prove our main results. Comments concerning explicitly constructed graphs that may replace the random graphs used in our proofs are given in Section 5.

2. A tree-universality result

We shall assume throughout that all our bipartite graphs have been given a fixed bipartition. More specifically, if G is a bipartite graph, its associated bipartition will be V (G) = V_{0}(G) ∪ V_{1}(G). In particular, if T is a tree of order t = |T | ≥ 2, we assume fixed one of the canonical bipartitions V (T) = V_{0}(T) ∪ V_{1}(T) of T. Also, if G is a bipartite graph with associated bipartition V (G) = V_{0}(G)∪V_{1}(G), we let Δ_{σ}(G) = max{d_{G}(v): v ∈ V_{σ}(G)} and put n_{σ}(G) = |V_{σ}(G)| (σ ∈ {0, 1}). We sometimes write G = G^{n_{0},n_{1}} if n_{σ}(G) = n_{σ} (σ ∈ {0, 1}). If T is a tree, and Δ_{σ}(T) ≤ Δ_{σ}, n_{σ}(T) ≤ t_{σ} (σ ∈ {0, 1}), we say that T is a (t_{0}, Δ_{0}; t_{1}, Δ_{1})- tree.

Now let J be a bipartite graph with associated bipartition V (J) = V_{0}(J) ∪ V_{1}(J). If for every X ⊂ V_{σ}(J) with |X| ≤ b_{σ} (σ ∈ {0, 1}) we have |Γ_{J}(X)| ≥ f_{σ}|X|, we say that J is a (b_{0}, f_{0}; b_{1}, f_{1})-expanding bipartite graph. The main result in this section is the following.

Theorem 1. Suppose 1 ≤ Δ_{0} ≤ t_{1} and 1 ≤ Δ_{1} ≤ t_{0} are fixed integers. Then every non-empty (2t_{1}/Δ_{0}, 2Δ_{0}; 2t_{0}/Δ_{1}, 2Δ_{1})-expanding bipartite graph contains as a subgraph every (t_{0}, Δ_{0}; t_{1}, Δ_{1})-tree.

The rest of this section is devoted to the proof of the above result. Thus, suppose t_{σ}, Δ_{σ} (σ ∈ {0, 1}) are as in Theorem 1, let T be a fixed (t_{0}, Δ_{0}; t_{1}, Δ_{1})- tree, and let J be a (2t_{1}/Δ_{0}, 2Δ_{0}; 2t_{0}/Δ_{1}, 2Δ_{1})-expanding bipartite graph. We shall show that J contains a copy of T as a subgraph.

Let S ⊂ T be a subtree of T. A function f: V (S) → V (J) is an embedding of S in J if f is injective, it preserves the adjacency relation, and moreover it preserves the vertex classes, i.e. f(V_{σ}(T) ∩ V (S)) ⊂ V_{σ}(J) for σ ∈ {0, 1}. In what follows the indices will be reduced modulo 2, so that, for instance, V_{0}(J) = V_{2}(J) = · · ·. Let us now suppose that an embedding f: S → J is given, and suppose X ⊂ V_{σ}(J) (σ ∈ {0, 1}). Then we let A_{f}(X) = |Γ_{J}(X) \ f(V (S))|. Also, for x ∈ J we let D_{f}(x) = d_{S}(f^{−1}(x)) if x ∈ f(V (S)) and D_{f}(x) = 0 otherwise, and put B_{f}(X) = ∑_{x∈X}(Δ_{σ} −D_{f}(x)). Finally, we set C_{f}(X) = A_{f}(X)−B_{f}(X).

Let us say that X is f-solvent if C_{f}(X) ≥ 0, and f-bankrupt otherwise. If C_{f}(X) = 0, we shall say that X is f-critical. A central definition is the following. We shall say that f is good if every X ⊂ V (J) with X ⊂ V_{σ}(J) (σ ∈ {0, 1}) is f-solvent whenever |X| ≤ 2t_{σ+1}/Δ_{σ}. We have now arrived at the main claim in the proof of Theorem 1.

Claim. (i) If S ⊂ T is a subtree of T with |S| = 1, then there is a good embedding f: S → J of S in J. (ii) Let S ⊂ T be a subtree of T, and suppose f: S → J is a good embedding of S in J. If S ⊂ S′ ⊂ T, where S′ is a tree with |S′| = |S|+1, then there is a good embedding g: S′ → J of S′ in J that extends f.

As Theorem 1 immediately follows from (i) and (ii) above, we proceed to prove this claim. Let us first consider (i). Suppose V (S) = {x} ⊂ V_{σ}(T) (σ ∈ {0, 1}). Then let f: V (S) → V (J) be any function such that f(x) ∈ V_{σ}(J). We claim that f is a good embedding. To check this, let X ⊂ V_{ρ}(J) (ρ ∈ {0, 1}) be such that |X| ≤ 2t_{ρ+1}/Δ_{ρ}. Let us check that C_{f}(X) ≥ 0. If X = ∅, then clearly C_{f}(X) = A_{f}(X) = B_{f}(X) = 0, and so we assume that X ≠ ∅. Note that then A_{f}(X) = |Γ_{J}(X)\{f(x)}| ≥ 2Δ_{ρ}|X|−1 ≥ Δ_{ρ}|X| ≥ B_{f}(X). Thus C_{f}(X) ≥ 0, and f is indeed good. We now turn to (ii).

Suppose f: S → J and S ⊂ S′ ⊂ T are as in the statement of (ii). Then clearly there is a leaf v of S′ such that V (S′) \ V (S) = {v}. Let w ∈ S be the unique neighbour of v in S′. Suppose v ∈ V_{σ′}(T) (σ′ ∈ {0, 1}). Now let us consider all embeddings g: S′ → J of S′ in J that extend f, and let G be the set of such extensions. Our claim is that G contains a good extension. Although strictly speaking this is not necessary, let us first check that G ≠ ∅ as a warm-up. Since {f(w)} is f-solvent, we have that |Γ_{J}(f(w)) \ f(V (S))| = A_{f}({f(w)}) ≥ B_{f}({f(w)}) = Δ_{σ′+1} − d_{S}(w) ≥ 1, which implies that indeed f has at least one extension g ∈ G. We now check that G contains a good extension.

Suppose for a contradiction that every g ∈ G admits a g-bankrupt set X_{g} ⊂ V (J) such that X_{g} ⊂ V_{ρ}(J), where ρ = ρ(g) ∈ {0, 1} and |X_{g}| ≤ 2t_{ρ+1}/Δ_{ρ}. Since f is good, the sets X_{g} (g ∈ G) are all f-solvent.

We now do a little simple calculation. For brevity, if P is a statement we set [P] = 0 if P is false and [P] = 1 if P is true. Fix X ⊂ V_{ρ}(J) (ρ ∈ {0, 1}) and let g ∈ G. Note that then A_{g}(X) = |Γ_{J}(X) \ g(V (S′))| = |Γ_{J}(X) \ f(V (S))| − [g(v) ∈ Γ_{J}(X)]. Moreover B_{g}(X) = ∑_{x∈X}(Δ_{ρ} − D_{g}(x)) = B_{f}(X) − [f(w) ∈ X] − [g(v) ∈ X]. Thus we have that

C_{g}(X) = C_{f}(X) − [g(v) ∈ Γ_{J}(X)] + [f(w) ∈ X] + [g(v) ∈ X].

From this, and the fact that X_{g} is g-bankrupt but f-solvent, we conclude that

X_{g} is f-critical, g(v) ∈ Γ_{J}(X_{g}) \ X_{g}, and f(w) ∉ X_{g}  (3)

for every g ∈ G. Note in particular that ρ(g) = σ′ + 1 for all g ∈ G; that is, we have X_{g} ⊂ V_{σ′+1}(J) for all g ∈ G.

Lemma 2. Suppose X ⊂ V_{ρ}(J), where ρ ∈ {0, 1}, is f-critical and satisfies |X| ≤ 2t_{ρ+1}/Δ_{ρ}. Then |X| ≤ t_{ρ+1}/Δ_{ρ}.

Proof. We have A_{f}(X) = |Γ_{J}(X) \ f(V (S))| ≥ 2Δ_{ρ}|X| − t_{ρ+1}, and B_{f}(X) = ∑_{x∈X}(Δ_{ρ} − D_{f}(x)) ≤ Δ_{ρ}|X|. Since A_{f}(X) − B_{f}(X) = C_{f}(X) = 0, the lemma follows.

We now check that C_{f} is a submodular function when restricted to each of the power sets P(V_{ρ}(J)) of V_{ρ}(J) (ρ ∈ {0, 1}).

Lemma 3. Suppose X, Y ⊂ V_{ρ}(J), where ρ ∈ {0, 1}. Then

C_{f}(X ∩ Y) + C_{f}(X ∪ Y) ≤ C_{f}(X) + C_{f}(Y).  (4)

Proof. Note first that B_{f} is a modular function on P(V_{ρ}(J)) (ρ ∈ {0, 1}). Now (4) follows from the observation that Γ_{J}(X ∩ Y) ⊂ Γ_{J}(X) ∩ Γ_{J}(Y) and Γ_{J}(X ∪ Y) = Γ_{J}(X) ∪ Γ_{J}(Y).

An easy consequence of the above two lemmas is the following.

Corollary 4. Suppose X, Y ⊂ V_{ρ}(J), where ρ ∈ {0, 1}, are f-critical and moreover |X|, |Y | ≤ t_{ρ+1}/Δ_{ρ}. Then X ∪ Y is f-critical and |X ∪ Y | ≤ t_{ρ+1}/Δ_{ρ}.

Proof. Since |X ∪ Y | ≤ 2t_{ρ+1}/Δ_{ρ} and f is good, the set X ∪ Y is f-solvent. Similarly X ∩ Y is f-solvent. Now (4) and the fact that X and Y are f-critical imply that X ∩ Y and X ∪ Y are f-critical as well. Lemma 2 now gives that |X ∪ Y | ≤ t_{ρ+1}/Δ_{ρ}, as required.

We are now ready to finish the proof of (ii) of our claim. Let X^{∗} = ⋃_{g∈G} X_{g} ⊂ V_{σ′+1}(J). By Corollary 4, we have that X^{∗} is f-critical and |X^{∗}| ≤ t_{σ′}/Δ_{σ′+1}. Recall that f(w) ∉ X_{g} for any g ∈ G (cf. (3)), and so f(w) ∉ X^{∗}. Let X′ = X^{∗} ∪ {f(w)} ⊂ V_{σ′+1}(J). We now claim that

Γ_{J}(X′) \ f(V (S)) = Γ_{J}(X^{∗}) \ f(V (S)).  (5)

It suffices to check that if y ∈ Γ_{J}(f(w)) \ f(V (S)), then y ∈ Γ_{J}(X^{∗}). So suppose y ∈ Γ_{J}(f(w)) \ f(V (S)) is fixed. Then note that there is an extension g ∈ G of f for which g(v) = y. But then by (3) we conclude that y = g(v) ∈ Γ_{J}(X_{g}) ⊂ Γ_{J}(X^{∗}). Thus (5) does indeed hold, and we have A_{f}(X′) = A_{f}(X^{∗}). Now note that B_{f}(X′) = B_{f}(X^{∗})+(Δ_{σ′+1} −d_{S}(w)) > B_{f}(X^{∗}). Thus C_{f}(X′) < C_{f}(X^{∗}) = 0. However, |X′| = |X^{∗}| + 1 ≤ t_{σ′}/Δ_{σ′+1} + 1 ≤ 2t_{σ′}/Δ_{σ′+1}, and hence, as f is good, we have that C_{f}(X′) ≥ 0. This contradiction completes the proof of Theorem 1.

3. Bipartite graphs with uniformly distributed edges

Let integers n_{0}, n_{1} ≥ 1 and r_{0}, r_{1} ≥ 1 be such that n_{0}r_{0} = n_{1}r_{1}. Set r = max{r_{0}, r_{1}}, and let p = (r_{0}/n_{1}) log r = (r_{1}/n_{0}) log r. We shall assume throughout that r ≥ 3 and p ≤ 1. Consider the space G(n_{0}, n_{1}; p) of random bipartite graphs G = G_{n_{0},n_{1},p} with vertex classes V_{0}(G) and V_{1}(G) satisfying |V_{σ}(G)| = n_{σ} (σ ∈ {0, 1}), and where each edge is independently present with probability p. Our aim in this section is to show the following technical lemma, which we shall do with the aid of the random graphs G_{n_{0},n_{1},p}. If G is a graph and U, W ⊂ V (G), we let e_{G}(U, W) denote the number of edges that have one endvertex in U and the other in W.

Lemma 5. There is an absolute constant r^{∗} ≥ 1 for which the following holds. Let n_{0}, n_{1}, r_{0}, r_{1} ≥ 1 be integers with n_{0}r_{0} = n_{1}r_{1}, and set p = (r_{0}/n_{1}) log r = (r_{1}/n_{0}) log r where r = max{r_{0}, r_{1}}. Suppose 0 < α ≤ 1 satisfies αr_{0}, αr_{1} ≥ 1. Then if r ≥ r^{∗} there is a bipartite graph G = G^{n_{0},n_{1}} such that (i) 1/2 ≤ e(G)/n_{0}r_{0} log r ≤ 2, and (ii) if σ ∈ {0, 1}, for any U ⊂ V_{σ}(G), W ⊂ V_{σ+1}(G) with 1 ≤ u = |U| ≤ u_{σ} = ⌊n_{σ+1}/er_{σ}⌋ = ⌊n_{σ}/er_{σ+1}⌋ and w = |W | = ⌊αr_{σ}u⌋, we have

e(U, W) = e_{G}(U, W) < puw + 12e(r_{σ}uw)^{1/2} log r.  (6)

Proof. Note that if p ≥ 1, we may take for G a complete bipartite graph with vertex classes of order n_{0} and n_{1}. Thus we assume that p < 1. We shall show that then, provided r is large enough, the probability that G = G_{p} = G_{n_{0},n_{1},p} ∈ G(n_{0}, n_{1}; p) satisfies (i) and (ii) is positive. For σ ∈ {0, 1}, let Q_{σ} be the property given in assertion (ii). We shall in fact show that, as r → ∞, we have (iii) ℙ(Q_{σ}) = 1 − o(1) (σ ∈ {0, 1}) and (iv) ℙ(1/2 ≤ e(G)/r_{0}n_{0} log r ≤ 2) = 1 − o(1).

Let us check (iii) first, and notice that by symmetry we may assume σ = 0. Let 1 ≤ u ≤ u_{0} and w = w(u) = ⌊αr_{0}u⌋. Set A = 12e, μ = puw, and b = A(r_{0}uw)^{1/2} log r. Let U ⊂ V_{0}(G) and W ⊂ V_{1}(G) be such that |U| = u and |W | = w. Let P_{u} = ℙ(e(U, W) ≥ μ + b), and set E_{0} = ∑_{1≤u≤u_{0}} \binom{n_{0}}{u}\binom{n_{1}}{w}P_{u}. Our aim is to show that E_{0} = o(1) as r → ∞. Let

η = \frac{b}{μ} = \frac{A(r_{0}uw)^{1/2} log r}{(r_{0}/n_{1})uw log r} = An_{1}(r_{0}uw)^{−1/2}.  (7)

We estimate E_{0} = ∑_{u} \binom{n_{0}}{u}\binom{n_{1}}{w}P_{u} by breaking the sum into two parts. Let E_{0}^{(1)} = ∑^{∗} \binom{n_{0}}{u}\binom{n_{1}}{w}P_{u}, where ∑^{∗} denotes sum over all 1 ≤ u ≤ u_{0} with η ≤ e^{2}, and let E_{0}^{(2)} = E_{0} − E_{0}^{(1)}. Note that below we may assume that r is large enough for our inequalities to hold.

(1) We have E_{0}^{(1)} = o(1) as r → ∞. Here we assume throughout that η ≤ e^{2}. We start by claiming that P_{u} = ℙ(e(U, W) ≥ μ + b) ≤ exp { − (A^{2}/3e^{4})n_{1} log r}. To check this claim, let us first consider the case in which η ≤ 1. Note that from (7) we have that η^{2}μ = A^{2}n_{1} log r. Then Hoeffding’s inequality [13] (see also [17]) gives that P_{u} ≤ exp {− (A^{2}/3)n_{1} log r}, and the claim follows in this case. Now consider the case 1 ≤ η ≤ e^{2}. Here P_{u} ≤ ℙ(e(U, W) ≥ 2μ) ≤ exp{−μ/3}, again by Hoeffding’s inequality. Note that b/μ = η ≤ e^{2} gives that μ ≥ b/e^{2} = (A/e^{2})(r_{0}uw)^{1/2} log r. Also, we have An_{1}(r_{0}uw)^{−1/2} = η ≤ e^{2}, and therefore μ ≥ (A^{2}/e^{4})n_{1} log r. Thus our claimed upper bound for P_{u} follows.

We now estimate E_{0}^{(1)}. If n_{0} ≤ n_{1} this is very quick: note that

E_{0}^{(1)} = ∑^{∗} \binom{n_{0}}{u}\binom{n_{1}}{w}P_{u} ≤ 2^{n_{0}+n_{1}} exp \{−\frac{A^{2}}{3e^{4}} n_{1} log r\} ≤ (4r^{−6})^{n_{1}} = o(1)

as r → ∞. Thus let us assume that n_{0} > n_{1}. Then

E_{0}^{(1)} ≤ 2^{n_{1}} ∑^{∗} \binom{n_{0}}{u}P_{u} ≤ 3 × 2^{n_{1}} exp \{−\frac{A^{2}}{3e^{4}} n_{1} log r\} (\frac{en_{0}}{u_{0}} )^{u_{0}}

≤ 3 × 2^{n_{1}}(e^{2}r_{1})^{n_{1}/er_{0}} exp \{−\frac{A^{2}}{3e^{4}} n_{1} log r\}

≤ 3 × 2^{n_{1}} exp \{\frac{2n_{1}}{er_{0}} + \frac{n_{1}}{er_{0}} log r − \frac{A^{2}}{3e^{4}} n_{1} log r\} ,

which tends to 0 as r → ∞.

(2) We have E_{0}^{(2)} = o(1) as r → ∞. We now assume that η ≥ e^{2}. Let v be such that b = evμ/ log v. Then ev/ log v = b/μ = η ≥ e^{2}, and hence we may suppose v ≥ e. Also, we have evμ/ log v = b ≥ 1 ≥ e/v, and so v^{2}μ ≥ log v. Thus P_{u} ≤ ℙ(e(U, W) ≥ b) ≤ exp{−vμ} (see Theorem 7(ii) in Chapter I of [8]). Now, we have vμ = (b/e) log v ≥ 12(r_{0}uw)^{1/2}(log r)(log v) ≥ 12(r_{0}uw)^{1/2}(log r). Thus v ≥ 12(r_{0}uw)^{−1/2}n_{1}, and hence

P_{u} ≤ exp\{−vμ\} ≤ (\frac{(r_{0}uw)^{1/2}}{12n_{1}} )^{12(r_{0}uw)^{1/2} log r} .  (8)

Note that if w ≤ 1 then u ≤ 1, and hence (6) holds trivially; that is, we have P_{u} = 0 in this case. Thus we assume αr_{0}u ≥ ⌊αr_{0}u⌋ = w ≥ 2. Hence w ≥ αr_{0}u/2, and we have from (8) that

P_{u} ≤ (\frac{α^{1/2}r_{0}u}{12n_{1}})^{6αr_{0}u log r} .

Thus E_{0}^{(2)} = ∑^{†} \binom{n_{0}}{u}\binom{n_{1}}{w}P_{u}, where ∑^{†} indicates sum over all 2 ≤ u ≤ u_{0} with η ≥ e^{2}, is at most

∑^{†} (\frac{en_{0}}{u} )^{u} (\frac{en_{1}}{αr_{0}u})^{αr_{0}u} P_{u} ≤ ∑_{u=2}^{u_{0}} (\frac{en_{0}}{u} )^{u} \{\frac{en_{1}}{αr_{0}u} (\frac{ur_{0}}{n_{1}} )^{6 log r}\}^{αr_{0}u}

≤ ∑_{u=2}^{u_{0}} (\frac{en_{0}}{u} )^{u} (\frac{1}{α})^{αr_{0}u} (\frac{ur_{0}}{n_{1}} )^{4αr_{0}u log r}

≤ ∑_{u=2}^{u_{0}} (er_{1} (\frac{1}{α})^{αr_{0}} (\frac{ur_{0}}{n_{1}} )^{3αr_{0} log r})^{u} ,

which is at most ∑_{2≤u≤u_{0}} e^{u}{αr^{2}}^{−αr_{0}u} ≤ ∑_{u≥2}(e/r)^{u} = o(1) as r → ∞.

Thus we have shown that E_{0} = E_{0}^{(1)} + E_{0}^{(2)} = o(1) as r → ∞, and hence that (iii) above does indeed hold. To see (iv), it suffices to note that e(G) has binomial distribution Bi(n_{0}n_{1}, p) with parameters n_{0}n_{1} and p and that 𝔼(e(G)) = pn_{0}n_{1} = n_{0}r_{0} log r → ∞ as r → ∞.

When n_{0} = n_{1} in Lemma 5, we may require a more restrictive condition on G = G^{n,n}, as shows Lemma 6 below. One may prove this lemma by suitably altering the proof of Lemma 5 and hence we omit its proof.

Lemma 6. There is an absolute constant r^{∗} ≥ 1 for which the following holds. Let r^{∗} ≤ r ≤ n, set p = r/n, and suppose 0 < α ≤ 1 satisfies αr ≥ 1. Then there is a bipartite graph G = G^{n,n} such that (i) 1/2 ≤ e(G)/nr ≤ 2, and (ii) if σ ∈ {0, 1}, for any U ⊂ V_{σ}(G), W ⊂ V_{σ+1}(G) with 1 ≤ u = |U| ≤ n/2r and w = |W | = ⌊αru⌋, we have e_{G}(U, W) < puw + 12e(ruw)^{1/2}.

4. The main results Let H be a bipartite graph with bipartition V (H) = V_{0}(H) ∪ V_{1}(H), and suppose V_{0}(H), V_{1}(H) ≠ ∅. Let d̄_{σ}(H) = |V_{σ}(H)|^{−1} ∑{d_{H}(v): v ∈ V_{σ}(H)} be the average degree of the vertices in V_{σ}(H) (σ ∈ {0, 1}). The following simple but useful lemma was observed by Beck [7]. We include Beck’s proof of this lemma for completeness.

Lemma 7. Let H be as above. Then there is a non-empty induced subgraph J ⊂ H of H such that (*) for any U ⊂ V_{σ}(J) = V_{σ}(H) ∩ V (J) (σ ∈ {0, 1}), we have e_{J}(U, V (J)) ≥ (1/2)d̄_{σ}(H)|U|.

Proof. We define a sequence H = H_{0} ⊃ H_{1} ⊃ ⋯ of induced subgraphs of H as follows. Let H_{0} = H, and suppose H_{0} ⊃ ⋯ ⊃ H_{i−1} (i ≥ 1) have been defined. If |H_{i−1}| = 0, or else |H_{i−1}| > 0 and condition (*) in our lemma holds, we terminate the sequence. Suppose |H_{i−1}| > 0 but (*) fails. Then let U ⊂ V (H_{i−1}) be such that U ⊂ V_{σ}(H_{i−1}) for some σ ∈ {0, 1}, and moreover e_{H_{i−1}}(U, V (H_{i−1})) < (1/2)d̄_{σ}(H)|U|. We now let H_{i} = H_{i−1} − U. This defines a sequence H = H_{0} ⊃ ⋯ ⊃ H_{t} of induced subgraphs of H. If J = H_{t} is as required, we are done. Thus suppose |H_{t}| = 0. But then

e(H) = ∑_{1≤i≤t} (e(H_{i−1}) − e(H_{i})) < \frac{1}{2}d̄_{0}(H)|V_{σ}(H)| + \frac{1}{2}d̄_{1}(H)|V_{σ}(H)| = e(H),

which is a contradiction, and hence we necessarily have |H_{t}| > 0.

We may now prove our first main result.

Theorem 8. Let 0 < γ ≤ 1 be given. Then there is a constant c_{γ} > 0 depending only on γ for which the following holds. For all integers 1 ≤ Δ_{0} ≤ t_{1} and 1 ≤ Δ_{1} ≤ t_{0}, there is a bipartite graph G such that (i) e(G) ≤ c_{γ}(Δ_{0}t_{0} +Δ_{1}t_{1}) log Δ, where Δ = max{Δ_{0}, Δ_{1}}, and (ii) G →_{γ} T for any (t_{0}, Δ_{0}, t_{1}, Δ_{1})-tree T.

Proof. Let γ, t_{σ}, Δ_{σ} (σ ∈ {0, 1}) be as above. In proving our result, we may assume that Δ ≥ e^{2}r^{∗}, where r^{∗} is as given in Lemma 5. Moreover, we may further assume that Δ_{0}t_{0} ≥ Δ_{1}t_{1}. We now start the proof proper.

Let 0 < α = α(γ) ≤ min{eγ/4, 4/e^{2}} be the largest real number such that (1/12e)^{2}(γ/4 − α/e)^{2} ≥ α. For σ ∈ {0, 1}, let r_{σ} be the smallest integer power of 2 such that αr_{σ} ≥ 2Δ_{σ}. Clearly r_{σ} ≤ (4/α)Δ_{σ} (σ ∈ {0, 1}). Now let n_{0} be the smallest power of 2 such that n_{0} ≥ 2et_{0}r_{1}/Δ_{1}. Then we have n_{0} ≤ (16e/α)t_{0}. Finally, let n_{1} = r_{0}n_{0}/r_{1}. Then note that n_{1}/er_{0} ≥ n_{0}/er_{1} ≥ 2t_{0}/Δ_{1} ≥ 2t_{1}/Δ_{0}. Now let G = G^{n_{0},n_{1}} be the bipartite graph whose existence is guaranteed in Lemma 5. Then

e(G) ≤ 2n_{0}r_{0} log r ≤ 2 (\frac{16et_{0}}{α} ) (\frac{4Δ_{0}}{α} ) log (\frac{4Δ}{α}) ≤ c′_{γ}(t_{0}Δ_{0} + t_{1}Δ_{1}) log Δ,

where c′_{γ} = 128eα^{−2} log(4/α), since log(4Δ/α) ≤ (log(4/α)) log Δ as α ≤ 4e^{−2} and Δ ≥ e^{2}. Thus (i) in our result holds for G if c_{γ} ≥ c′_{γ}. We now check (ii). Thus let H ⊂ G be a fixed subgraph of G with e(H) ≥ γe(G). Let J ⊂ H be the subgraph of H given by Lemma 7. We claim that then the graph J is (2t_{1}/Δ_{0}, 2Δ_{0}; 2t_{0}/Δ_{1}, 2Δ_{1})-expanding.

Suppose for a contradiction that U ⊂ V_{σ}(J) is such that u = |U| ≤ 2t_{σ+1}/Δ_{σ} and |Γ_{J}(U)| < 2Δ_{σ}|U|, where σ ∈ {0, 1}. Then, let W ⊂ V_{σ+1}(J) be such that w = |W | = ⌊αr_{σ}u⌋ and Γ_{J}(U) ⊂ W. Now observe that

\frac{γ}{4} r_{σ}(log r)u ≤ \frac{γ}{2} d̄_{σ}(G)u ≤ \frac{1}{2}d̄_{σ}(H)u ≤ e_{J}(U, V (J)) ≤ e_{G}(U, W)

< puw + 12e(r_{σ}uw)^{1/2} log r ≤ \frac{α}{e}r_{σ}(log r)u + 12e(r_{σ}uw)^{1/2} log r.

Thus (γ/4 − α/e)r_{σ}(log r)u < 12e(r_{σ}uw)^{1/2} log r, and hence we have αr_{σ}u ≤ (1/12e)^{2}(γ/4 − α/e)^{2}r_{σ}u < w = ⌊αr_{σ}u⌋, which is a contradiction. Therefore we conclude that indeed J is (2t_{1}/Δ_{0}, 2Δ_{0}; 2t_{0}/Δ_{1}, 2Δ_{1})-expanding. Now (ii) above follows from Theorem 1.

Our second main result is as follows.

Theorem 9. Let 0 < γ ≤ 1 be given. Then there is a constant c_{γ} > 0 depending only on γ for which the following holds. For any 1 ≤ Δ < t, there is a bipartite graph G such that (i) e(G) ≤ c_{γ}Δt, and (ii) G →_{γ} T for any tree T of order |T | ≤ t and maximal degree Δ(T) ≤ Δ.

Proof. Let γ, Δ, t be as in the statement of our result. We may assume that Δ ≥ r^{∗}, where r^{∗} is as in Lemma 6. Let 0 < α = α(γ) ≤ γ/2 be the largest real such that (1/12e)^{2}(γ/4 − α/2)^{2} ≥ α. Now let r = ⌈2Δ/α⌉ ≤ 4Δ/α, and n = ⌈4tr/Δ⌉ ≤ 32t/α. Note that then r^{∗} ≤ r ≤ n, 0 < α ≤ 1, and let G = G^{n,n} be the corresponding bipartite graph given by Lemma 6. Then e(G) ≤ 2rn ≤ 2(4Δ/α)(32t/α) ≤ 256α^{−2}Δt. We now check that G →_{γ} T for any tree T with |T | ≤ t and Δ(T) ≤ Δ. Let H ⊂ G be a subgraph of G with e(H) ≥ γe(G). Let J ⊂ H be the subgraph of H given by Lemma 7. It now suffices to check that J is a (2t/Δ, 2Δ; 2t/Δ, 2Δ)-expanding bipartite graph.

Suppose for a contradiction that U ⊂ V_{σ}(J) is such that |Γ_{J}(U)| < 2Δ|U| although u = |U| ≤ 2t/Δ, where σ ∈ {0, 1}. Then, let W ⊂ V_{σ+1}(J) be such that w = |W | = ⌊αru⌋ and Γ_{J}(U) ⊂ W. Now observe that

\begin{matrix}\frac{γ}{4} ru ≤ \frac{γ}{2} d̄_{σ}(G)u ≤ \frac{1}{2}d̄_{σ}(H)u ≤ e_{J}(U, V (J)) ≤ e_{G}(U, W) \\ < puw + 12e(ruw)^{1/2} ≤ \frac{α}{2}ru + 12e(ruw)^{1/2}. \end{matrix}

Thus αru ≤ (1/12e)^{2}(γ/4 − α/2)^{2}ru < w = ⌊αru⌋, which is a contradiction.

An immediate corollary to Theorems 8 and 9 is the upper bound for the size-Ramsey number of trees given in Corollary 10 below. The lower bound in this corollary is due to Beck [7], and its very short proof is included for convenience.

Corollary 10. For any r ≥ 2, there is a constant c_{r} depending only on r such that

β(T)/4 ≤ r_{e}(T, r) ≤ c_{r} min{β(T) log Δ(T), |T |Δ(T)}

for all trees T.

Proof. Let an integer r ≥ 2 and a tree T be fixed. Let T have bipartition V (T) = V_{0}(T) ∪ V_{1}(T), and let t_{σ} = |V_{σ}(T)|, Δ_{σ} = Δ_{σ}(T) (σ ∈ {0, 1}). We may assume that t_{0}Δ_{0} ≥ t_{1}Δ_{1}. Let us prove that r_{e}(T, 2) ≥ β(T)/4. Suppose G → (T)_{2}.

Let U = {v ∈ G: d_{G}(v) ≥ Δ_{0}} and set W = V (G) \ U. Colour the edges of G between U and W red, and the rest of the edges of G blue. Suppose T′ ⊂ G is a monochromatic copy of T in G, and let φ: T → T′ be an isomorphism. Let v_{0} ∈ V_{0}(T) have degree d_{T} (v) = Δ_{0}. Clearly φ(v_{0}) ∈ U, and hence regardless of the colour of T′, we have φ(V_{0}(T)) ⊂ U. Thus e(G) ≥ |U|Δ_{0}/2 ≥ |V_{0}(T)|Δ_{0}/2 = t_{0}Δ_{0}/2 ≥ β(T)/4. The upper bound for r_{e}(T, r) follows immediately from Theorems 8 and 9.

5. Concluding remarks

The existence of the graph G in Theorem 9 is proved by non-constructive means. For some values of γ, Δ, and t we may however take for G a suitable Ramanujan graph X = X^{p,q}. More precisely, there is an absolute constant ε > 0 with the following property. For any given 0 < γ ≤ 1, there exist constants c_{γ} > 0, Δ_{γ}, t_{γ} ≥ 1 depending only on γ such that, for any integers 1 ≤ Δ < t with Δ ≥ Δ_{γ}, t ≥ t_{γ}, and Δ ≤ t^{ε}, there are primes p and q such that a bipartite Ramanujan graph X = X^{p,q} constructed by Lubotzky, Phillips, and Sarnak [16] is such that (i) e(X) ≤ c_{γ}Δt, and (ii) X →_{γ} T for any tree T of order |T | ≤ t and maximal degree Δ(T) ≤ Δ. The only extra work involved in proving the statement above has to do with the existence of the primes p and q. We refer the reader to Section 4 of [12], where a similar number-theoretic problem is treated. The key result there is a beautiful theorem of Bombieri [9] (see also Davenport [10], §28) on the distribution of primes in arithmetic progressions. With this result in hand, our task there is quite straightforward, and in fact the same method applies here, proving the above assertion. Let us also remark that the techniques presented in this note also show that the incidence graphs of certain projective geometries are explicit examples that prove Theorem 9 for Δ and t with Δ about t^{1−1/d} for some integer d ≥ 2. (See Theorem 2.3 in Alon [1].)

Finally, we should like to mention that Professor Noga Alon [2] has kindly pointed out to us that one may improve the observations above as follows. One of the methods that is given for the construction of almost k-wise independent random variables in Alon, Goldreich, Håstad, and Peralta [4], namely, Construction 3, can be suitably modified to give an elementary construction of an rregular n-vertex graph whose second largest eigenvalue in absolute value μ_{1} is such that |μ_{1}| ≤ ur^{1/2}, where n = 2^{uk} and r = 2^{2k}, and u and k are any fixed integers with u ≥ 3 and k ≥ 1. Here one considers a suitable Cayley graph of a certain Abelian group, and uses the result given in Problem 11.8 of Lovász [15] (see Section 3.2 of Alon and Roichman [5]). These graphs, the Ramanujan graphs of Lubotzky, Phillips, and Sarnak and, as pointed out by Professor Alon, their powers may be used to prove appropriate variants of Lemma 6 constructively, thus allowing one to give a constructive proof of Theorem 9 for a wide range of values of γ, Δ, and t.

References

[1] Alon, N., Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6 (1986), 207–219.

[2] Alon, N., Personal communication, August 1993.

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

[4] Alon, N., Goldreich, O., Håstad, J., Peralta, R., Simple constructions of almost kwise independent random variables, Random Structures and Algorithms 3 (1992), 289–304.

[5] Alon, N., Roichman, Y., Random Cayley graphs and expanders, to appear.

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

[7] Beck, J., On size Ramsey number of paths, trees, and circuits II, in Mathematics of Ramsey Theory (Nešetřil, J., Rödl, V., eds), Algorithms and Combinatorics 5, Springer-Verlag, Berlin 1990, pp. 34–45.

[8] Bollobás, B., Random Graphs, Academic Press, London, 1985, xvi + 447pp.

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

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

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

[12] Haxell, P.E., Kohayakawa, Y., On an anti-Ramsey property of Ramanujan graphs, to appear.

[13] Hoeffding, W., Probability inequalities for sums of bounded random variables, Jour. Amer. Statistical Assoc. 58 (1963), 13–30.

[14] Ke, X., The size Ramsey number of trees with bounded degree, Random Structures and Algorithms 4 (1993), 85–97.

[15] Lovász, L., Combinatorial Problems and Exercises, North Holland, Amsterdam 1979.

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

[17] McDiarmid, C.J.H., On the method of bounded differences, in Surveys in Combinatorics 1989 (Siemons, J., ed.), London Mathematical Society Lecture Notes Series 141, Cambridge University Press, Cambridge 1989, pp. 148–188.