SERIE A — MATHEMATIK

Expanding graphs and Ramsey numbers

Stephan Brandt^{†}*

Preprint No. A 96–24 December 1996

Abstract

The generalized Ramsey number r(G, H) is investigated for H being a large order graph of bounded maximum degree. Giving a negative answer to a number of conjectures in generalized Ramsey theory it will be shown that for every nonbipartite graph G there is a function h(G, d) tending to infinity with d, such that the Ramsey number r(G, H) > h(G, d)|H| for almost every d-regular graph H.

†FB Mathematik und Informatik, WE 2, Freie Universität Berlin, Arnimallee 3, 14195 Berlin, Germany

e-mail: brandt@math.fu-berlin.de

*Partly supported by Deutsche Forschungsgemeinschaft, Grant We 1265

Dedication

This paper is dedicated to the memory of Paul Erdős, who died in Warsaw on September 20, 1996 while attending a conference. I communicated with him about these results on the day before his death, where he suggested to estimate the function h, which is performed in Theorem 2 below.

1 Introduction

For two graphs G and H the Ramsey number r(G, H) is the smallest integer r such that every graph F of order p ≥ r contains G as a subgraph or its complement \overline{F} contains H as a subgraph. Chvátal, Rödl, Szemerédi and Trotter [18] proved that the Ramsey number r(H, H) is linear in the order of H for graphs of bounded degree. More precisely, for every Δ there is a constant c(Δ), such that r(H, H) ≤ c(Δ)|H| for every graph H with maximum degree at most Δ. Certainly, c(Δ) is an exponentially growing function of Δ (though the growth might be slower if |H| is required to be much larger than Δ).

Here we investigate the growth of Ramsey numbers r(G, H), where G is a fixed graph and H is a sequence of graphs of bounded maximum degree. It is easy to derive from the result of Chvátal et. al., that r(G, H) ≤ c(Δ(G) + Δ)|H| for every graph H with maximum degree at most Δ. The objective of this paper is to determine lower bounds for r(G, H). Using the expansion properties of random regular graphs, we will show that for every nonbipartite graph G the Ramsey number r(G, H) ≥ h(G, d)|H| for almost every (with probability tending to 1) d-regular graph H, where h(G, d) tends to infinity with d. This contradicts a conjecture of Burr [11, Conj. 4.1], saying that r(G, H) < χ(G)|H| for almost every (all but finitely many) connected graph H of maximum degree at most Δ (χ being the chromatic number), and several other conjectures as well.

This research was motivated by the wealth of experimental data on Ramsey numbers r(K_{3}, H) [6, 7, 8] for (relatively) small order graphs H, where the author first saw well-expanding graphs H having largest Ramsey numbers among undense graphs.

2 History and main results

Let H be a connected graph of order n. Generalizing an observation of Chvátal and Harary [17], Burr [10] established the lower bound of

r(G, H) ≥ (χ(G) − 1)(n − 1) + s(G)  (1)

for any graph G, where χ(G) denotes the chromatic number and s(G) the chromatic surplus of G, i.e. the minimum cardinality of a color class taken over all proper χ(G) colorings of G. Burr [10] defined H to be G-good, if (1) holds with equality.

Which graphs are G-good? Obviously, every graph is K_{2}-good. Furthermore, Burr [10] proved that if H is K_{m}-good then it is also K_{m′}-good whenever 2 ≤ m′ ≤ m.

Two results, dating back to the times before the goodness concept was defined, are saying that the most undense connected graphs are K_{m}-good, namely trees (Chvátal [16]) and cycles of length at least m^{2} − 2 (Bondy and Erdős [5]).

Three conjectures have been posed describing the expected limits for G-goodness (see [11, Section 4]).

Conjecture 1 (Burr [10]) If G is any fixed graph and c is any fixed number, then any connected graph of sufficiently large order with maximum degree Δ ≤ c is Ggood.

Conjecture 2 (Burr and Erdős [12]) If G = K_{m} and c is any fixed number, then any connected graph H of sufficiently large order where every subgraph H′ satisfies |E(H′)|/|H′| < c is G-good.

Conjecture 3 (Burr [11]) If G = K_{3} and c is any fixed number, then any connected graph of sufficiently large order n of size at most cn is G-good.

Two further conjectures by Burr and Faudree [15, Conj. 1.1 and 2.1] generalize Conjecture 2 (for which a reward of 25$ was offered by the authors) to larger classes of graphs than just K_{m}.

Conjecture 1 was shown to hold if G is bipartite by Burr, Erdős, Faudree, Rousseau and Schelp [14]. Here we will show that it is false in every other case. Even more, if G is not bipartite then Conjecture 1 is false for almost every d-regular graph H, if d is sufficiently large with respect to G. In fact, the Ramsey number r(G, H) exceeds γn for any constant γ, if d is sufficiently large with respect to G and γ for almost every d-regular graph. So, in particular, all the other conjectures are false as well. The term almost every means “with probability 1 − o(1)” unless otherwise stated.

Theorem 1 For every nonbipartite graph G there is a function h(G, d) tending to infinity as d → ∞, such that r(G, H) > h(G, d)n for almost every d-regular graph H of order n.

In order to prove Theorem 1 it suffices to prove the statement for odd cycles C_{2k+1} (k ≥ 1), since every nonbipartite graph contains an odd cycle, and r(G, H) ≥ r(G′, H) for every subgraph G′ of G. We can give explicit lower bounds for h(C_{2k+1}, d). In fact, it turns out that we can choose h to be a reasonably fast growing function of d.

Theorem 2 For odd cycles, Theorem 1 holds with h(C_{3}, d) = Ω(\sqrt{d}/ log d) and h(C_{2k+1}, d) = Ω((d/ log d)^{1/(4k+2)}) for every k ≥ 2.

Moreover, Burr, Erdős, Faudree, Rousseau and Schelp [13] asked for the functions f(n, m) and g(n, m), where f(n, m) is the largest integer such that every connected graph of order n and size at most f(n, m) is K_{m}-good, and g(n, m) is the largest integer such that some connected graph of order n and size f(n, m) is K_{m}-good.

While g(n, m) is for every fixed m a superlinear function in n [13], the situation is different for f(n, m). For m ≥ 4, Burr et.al. [13] proved that f(n, m) = n+o(n). For m = 3 they proved that f(n, 3)/n > 17/15. We will show that f(n, 3)/n < 84, and, in fact, with a different approach and a more refined analysis which is not presented here we can show that f(n, 3)/n < 11.75. However, this is likely to be still far from the optimum. The author would expect 2 < f(n, 3)/n < 6, say, if n is sufficiently large. Computer experiments [7] seem to indicate that at least f(n, 3)/n > 3/2 holds for larger n.

The method that we use is as follows: We employ the expansion properties of random regular graphs to justify that these graphs cannot be contained in the complement of lexicographic products F [\overline{K_{s}}], where F is a certain graph with larger odd girth than G and small independence number.

3 Concepts and notation

The graph theoretical notation is standard as far as possible; for notation and concepts not defined here the reader is referred to introductory literature, e.g. [24].

The lexicographic product (composition) G[H] of two graphs G and H has vertex set V (G) × V (H) and two vertices (v_{i}, w_{i}) and (v_{j}, w_{j}) are joined by an edge if and only if (1) v_{i}v_{j} ∈ E(G) or (2) v_{i} = v_{j} and w_{i}w_{j} ∈ E(H). In our case we will consider only the case where H is a complete graph or its complement.

The girth of a graph is the length of a shortest cycle and the odd girth is the length of a shortest odd cycle. Note that the odd girth of a graph G is inherited by the lexicographic product G[\overline{K}_{r}].

The clique number ω(G) of a graph G is the maximum number of vertices which are pairwise joined by an edge and the independence number α(G) is the maximum number of vertices which are pairwise not joined by an edge. The independence ratio is α(G)/|G|, where |G| denotes the order of G.

A subgraph of a graph G is a graph G′ with V (G′) ⊆ V (G) and E(G′) ⊆ E(G) ∩ \binom{V (G′)}{2}, where the edges of the undirected, simple graph are considered as two-

element subsets of the vertex set, and \binom{V}{2} denotes the set of all two-element subsets

of V. An induced subgraph is a subgraph G′ satisfying E(G′) = E(G) ∩ \binom{V (G′)}{2}.

4 Expanding graphs

Typical graphs tend to have the property that the edges are homogeneously distributed over the graph (even though most infinite sequences of graphs that we know do not have this property). This means, in particular, that for any two reasonably large disjoint subsets U, W of vertices the number of edges joining them does not deviate a lot from the expected number of edges (which is |U||W ||E(H)|/\binom{|V (H)|}{2}). A necessary condition for H being a subgraph of a graph F is the following:

F has an induced subgraph F′ of order |V (H)|, such that for every pair u, w the minimum number of edges joining two sets of cardinalities u and w is at least as large in F′ as in H.

This is the key obstruction that will be used to prove that the Ramsey number r(C_{2k+1}, H) is large for well-expanding graphs H.

Which families of graphs with linearly many edges will be suitable for having a large Ramsey number (vs. C_{2k+1}), due to this reason? A random regular graph will almost surely do. Moreover, as shown by Robinson and Wormald [23], for d ≥ 3 a random d-regular graph is almost surely hamiltonian, so, in particular, it is connected.

A suitable model for random regular graphs was introduced by Bollobás [2] (see also [3]). To construct a d-regular graph with n vertices (d times n even) take a set {1, 2, …, n} of vertices with d half-edges sticking out of each vertex. Choose a random pairing of the half-edges to edges. Such a pairing will be called a configuration. The result will be a d-regular multigraph, possibly containing loops or multiple edges. However, for fixed d, a positive fraction of the graphs will be simple graphs [2]. So any statement, which holds for almost every d-regular multigraph, will hold for almost every d-regular simple graph as well. Note that every labelled d-regular simple graph appears with the same probability in this model. Moreover, the number of configurations with 2x half edges is

N(2x) = \frac{(2x)!}{x!2^{x}}.

From Stirling’s formula, we get (1 − o(1))\sqrt{2} (\frac{2x}{e})^{x} < N(2x) < \sqrt{2} (\frac{2x}{e})^{x}.

Bollobás [4] proved that almost every d-regular graph for d ≥ 3 has large isoperimetric number. The next result shows that such graphs are good expanders in a stronger sense. To avoid tedious case analysis we concentrate on the range of c that we will need in our proofs and we make no attempt to optimize the bound for d.

Theorem 3 Suppose 0 < c ≤ 1/15 and d is an integer satisfying d > 2(1 − ln c)/c(1 − 5c). Let H be a random d-regular multigraph of order n (dn even). Then almost surely (as n → ∞) there is an edge between any pair of disjoint vertex sets U, W satisfying |U| = |W | ≥ cn.

Proof. Suppose |U| = |W | = m = ⌈cn⌉ = ηn, so η → c as n → ∞. Consider the configurations where exactly k edges join vertices of U. Suppose that no edge joins U to W. Then all ends of the remaining dm − 2k half-edges emanating from U have the other end in V (H) \ (U ∪ W), and for a chosen subset of dm − 2k half-edges emanating from V (H) \ (U ∪ W) we have (dm − 2k)! possibilities to pair them with the half-edges of U. Finally, we can pair the remaining half-edges in any fashion. Set 2k/d = γn and let X_{U,W} denote the number of edges joining U to W. Then the probability

P [X_{U,W} = 0] = ∑_{0≤k≤dm/2} \frac{\binom{dm}{2k}N(2k)\binom{d(n−2m)}{dm−2k}(dm − 2k)!N(d(n − 2m) + 2k)}{N(dn)}.

We can estimate \binom{dm}{2k} ≤ (\frac{eη}{γ})^{γdn}, N(2k) ≤ \sqrt{2}(\frac{γdn}{e})^{γdn/2}, \binom{d(n−2m)}{dm−2k}(dm − 2k)! ≤ n(dn(1 − 5η/2 + γ/2))^{(η−γ)dn} by pairing the terms around the middle, and

\frac{N(d(n − 2m) + 2k)}{N(dn)} < (1 + o(1)) (\frac{dn(1 − 2η + γ)}{e})^{dn(1−2η+γ)/2} (\frac{e}{dn})^{dn/2}

= (1 + o(1))(1 − 2η + γ)^{dn/2} (\frac{e}{dn(1 − 2η + γ)})^{(η−γ/2)dn}
≤ (1 + o(1)) (e^{−(2η−γ)^{2}/4}(dn(1 − 2η + γ))^{−(η−γ/2)})^{dn} ,

where the last term follows from the inequality 1 − x ≤ e^{−x−x^{2}/2} for 0 ≤ x < 1. Writing

Ψ(η, γ) = (\frac{eη^{2}}{γ(1 − 2η)})^{γ}

we get that \sqrt{2}(Ψ(η, γ))^{dn/2} > \binom{dm}{2k}N(2k)/((1 − 2η + γ)dn)^{γdn/2}, so

P [X_{U,W} = 0] <

O(n^{2}) max_{0≤γ≤η} [(Ψ(η, γ))^{dn/2} (\frac{1 − 5η/2 + γ/2}{1 − 2η + γ})^{(η−γ)dn} e^{−dn(2η−γ)^{2}/4}]

< O(n^{2}) max_{0≤γ≤η} (Ψ(η, γ)(1 − η/2 − γ/2)^{2(η−γ)}e^{−(2η−γ)^{2}/2})^{dn/2}
< O(n^{2}) max_{0≤γ≤η} (Ψ(η, γ)e^{−(η^{2}−γ^{2})−(2η−γ)^{2}/2})^{dn/2} .

The function Ψ(η, γ) is maximal if γ = η^{2}/(1 − 2η), whence Ψ(η, γ) ≤ e^{η^{2}/(1−2η)}. Now suppose that n is sufficiently large. If γ ≤ 7η^{2}/2 then using η < (1 + o(1))/15 we get

P [X_{U,W} = 0] < e^{((1−2η)^{−1}−(3−7η−49η/120))η^{2}dn/2} < e^{−(1−5η)η^{2}dn}.

If γ > 7η^{2}/2 then Ψ(η, γ) has a negative contribution in the exponent and P [X_{U,W} = 0] < e^{−(1−5η)η^{2}dn} holds as well. On the other hand, there are

\frac{\binom{n}{m}\binom{n−m}{m}}{2} = \frac{\binom{n}{2m}\binom{2m}{m}}{2} < (\frac{e}{2η} )^{2ηn} 2^{2ηn} = e^{(1−ln η)2ηn}

pairs of disjoint sets of cardinalities m. So the probability that there is a pair of disjoint sets of cardinalities m, which are not joined by an edge is at most

(e^{2(1−ln η)−d(1−5η)η})^{ηn} .

Hence, if d > 2(1 − ln c)/c(1 − 5c) then in a random d-regular multigraph almost surely every pair of disjoint subsets of cardinalities at least cn is joined by an edge. □

This is only an existence proof, and given a random regular graph it may be difficult to decide, whether the graph has this property. Anyway, we can at least justify that a regular graph has this property based on the eigenvalues of the adjacency matrix (see [1, p. 122]). Broder and Shamir [9] (cf. the improvement of Friedman [20]) proved in a slightly different and more restricted model of random regular graphs, that the justification via eigenvalues is possible for almost all d-regular graphs if d is sufficiently large and even. Moreover, explicit constructions of infinite families of regular graphs with constant degree are known which are well-expanding in the sense of Theorem 3, e.g. the non-bipartite Ramanujan graphs constructed by Lubotzky, Phillips and Sarnak [22]. Note that the bounds for d obtained via eigenvalue estimates are weaker than those computed directly in Theorem 3.

5 Lexicographic products as Ramsey graphs

In the previous section we analyzed properties of well-expanding graphs with regard to our needs. In order to show that for such a graph H the Ramsey number r(C_{2k+1}, H) is large, one has to find a graph of large order compared to H, which does not contain C_{2k+1} and whose complement does not contain H. This graph will be the lexicographic product of a graph with small independence number and odd girth exceeding 2k + 1 with an edgeless graph. Note that F [\overline{K}_{r}] has the same odd girth as F, while for r ≥ 2 it has many short even cycles. Moreover, the independence ratio α(F [\overline{K}_{r}])/|F [\overline{K}_{r}]| = α(F)/|F |.

Certainly, C_{2k+1} is not a subgraph of F [\overline{K}_{r}]. Turning to the complement, we will see that \overline{F [\overline{K}_{r}]} = \overline{F} [K_{r}] is not a well expanding graph in the required sense, since every subgraph of order n = |F [\overline{K}_{r}]|/h contains two disjoint vertex sets of cardinalities ⌈cn⌉ which are not joined by an edge, c being a constant only depending on F. So any sufficiently well-expanding graph H of order n cannot be a subgraph of \overline{F} [K_{r}]. We simulate subgraphs of lexicographic products \overline{F} [K_{r}] by assigning weights to the vertices v_{i} of F, representing the ratio of the vertices in V_{i} belonging to the subgraph.

Lemma 1 Let F be a graph of order p with clique number ω. Assign to every vertex v of F a weight w_{v} with 0 ≤ w_{v} ≤ 1. If t = ∑_{v∈V} w_{v} > ω, then F contains two non-adjacent vertices x_{1}, x_{2} with w_{x_{i}} ≥ (t − ω)/(p − ω).

Proof. Let V′ be the set of vertices v with w_{v} ≥ (t − ω)/(p − ω). Since ω + (p − ω)(t − ω)/(p − ω) = t we obtain |V′| > ω. So V′ contains two non-adjacent vertices. □

Before treating the general case, we first prove that f(n, 3)/n < 84 by showing that r(K_{3}, H) > 2|H| for almost every d-regular graph with d ≥ 168. Let r = ⌈2n/5⌉ and take F = C_{5}. Setting t = |H|/r = 5(1 − o(1))/2 and assigning weights of total weight t to the vertices of C_{5}, we get from Lemma 1 that C_{5} contains two nonadjacent vertices of weight w_{x_{i}} ≥ (1 − o(1))/6. So every subgraph F′ of \overline{C_{5}[\overline{K}_{r}]} = C_{5}[K_{r}] of order |F′| = tr = n contains two disjoint subsets, each of cardinality |F′|w_{x_{i}}/t = (1 − o(1))n/15, which are not joined by an edge. Employing Theorem 3 with c = (1 − o(1))/15 we get that, as n → ∞, for almost every d-regular graph H with d ≥ 168 and order n every pair of disjoint subsets of cardinalities (1−o(1))n/15 is joined by an edge. So H cannot be a subgraph of any subgraph of C_{5}[K_{r}] with the same order as H, and hence not be a subgraph of C_{5}[K_{r}]. So the Ramsey number r(K_{3}, H) > 2n and hence f(n, 3)/n < 84.

It should be mentioned that C_{5}[\overline{K}_{r}] is, in fact, Ramsey graph for the Ramsey number r(K_{3}, H) of certain undense graphs H which are well-expanding. E.g. let H be the (unique) r(K_{3}, K_{5})-Ramsey graph itself which is 4-regular of order 13 and well expanding. Using the program mtf due to Brandt, Brinkmann and Harmuth [6] we can compute that r(K_{3}, H) = 26, and C_{5}[\overline{K}_{5}] is a Ramsey graph. This shows, by the way, that f(13, 3)/13 < 2.

The same approach can be used to show that r(C_{2k+1}, H) > h(C_{2k+1}, d)|H|, where h(C_{2k+1}, d) → ∞ as d → ∞. We will make use of the existence of families of graphs F_{i} with the following properties: α(F_{i})/|F_{i}| tends to 0 and F_{i}[\overline{K}_{r}] does not contain C_{2k+1} for any r ≥ 1. We can simply choose F_{i} to be a family of graphs with girth exceeding 2k + 1, since the odd girth of F_{i}[\overline{K}_{r}] remains unchanged. The existence of families with arbitrarily large girth and arbitrarily small independence ratio was proven by Erdős [19] by probabilistic means, in order to show that there are graphs with arbitrarily large girth and chromatic number. Proof of Theorem 2. Let β(k, p) be the minimum independence number taken over all graphs of order p with odd girth more than 2k + 1. By Kim’s result [21, Theorem 1.1] we have β(3, p) = O(\sqrt{p log p}) (note that the inequality in [21, Theorem 1.1] is misprinted) and by Erdős’ result [19] we have β(k, p) = O(p^{1−1/(4k+2)}).

Let d be an integer which is sufficiently large with respect to k and set c = 3 ln d/d. By Theorem 3 in a d′-regular graph H of order n with d′ ≥ d almost surely every pair of disjoint vertex sets U, W of cardinality |U|, |W | ≥ cn are joined by an edge since d′ ≥ d > 2(1 − ln c)/(1 − 5c)c.

For p = ⌈1/2c⌉ there exists a graph F of odd girth larger than 2k + 1 and order p which has independence number β(k, p). Now set r = ⌈n/2β(k, p)⌉ and choose 0 < ε < β(k, p)/2p. If n is sufficiently large then n/r ≥ 2(1 − ε)β(k, p). Assume that H is a subgraph of \overline{F} [K_{r}], i.e. there is an injection σ : V (H) → V (\overline{F} [K_{r}]) such that xy ∈ E(H) implies σ(x)σ(y) ∈ E(\overline{F} [K_{r}]). Let k_{i} be the number of vertices from H with σ(x) = (v_{i}, ·). Assign to every vertex v_{i} of \overline{G} weight w_{v_{i}} = k_{i}/r. So the total weight is n/r ≥ 2(1 − ε)β(k, p). By Lemma 1 the graph \overline{F} contains two non-adjacent vertices x_{1}, x_{2} of weight

w_{x_{i}} ≥ \frac{2(1 − ε)β(k, p) − ω}{p − ω} ≥ \frac{(1 − 2ε)β(k, p)}{p − β(k, p)} > \frac{β(k, p)}{p}.

So H contains two vertex sets U, W with |U|, |W | ≥ β(k, p)r/p ≥ n/2p ≥ cn which are not joined by an edge.

Hence a random d′-regular graph H is almost surely not a subgraph of \overline{F} [K_{r}], so, in particular r(C_{2k+1}, H) > h(C_{2k+1}, d)|H|, where h(C_{2k+1}, d) = pr/|H| ≥ p/2β(k, p). Since p = Θ(d/ log d) we get h(C_{3}, d) = Ω(\sqrt{d}/ log d) and h(C_{2k+1}, d) = Ω((d/ log d)^{1/(4k+2)}) for k ≥ 2. □

The property that every pair of small disjoint subsets is joined by an edge is a strong expansion property, which is not satisfied e.g. by well-expanding bipartite graphs. It would be interesting to know whether weaker expansion properties can already force a sequence of undense graphs H to have large Ramsey number r(G, H), perhaps restricted to graphs G in a subclass of nonbipartite graphs.

Acknowledgement

I thank Alan Frieze and Jean-Pierre Tillich for their helpful remarks, and Hans Mielke for pointing out a mistake in an earlier version.

References

[1] N. Alon and J. H. Spencer, The probabilistic method, Wiley, New York, 1992.

[2] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Europ. J. Comb. 1 (1980), 34–38.

[3] B. Bollobás, Random Graphs, Academic Press, London, 1985.

[4] B. Bollobás, The isoperimetric number of random regular graphs, Europ. J. Comb. 9 (1988), 241–244.

[5] J. A. Bondy and P. Erdős, Ramsey numbers for cycles in graphs, J. Comb. Theory Ser. B 14 (1974), 46–54.

[6] S. Brandt, G. Brinkmann, T. Harmuth, The generation of maximal triangle-free graphs, in preparation.

[7] S. Brandt, G. Brinkmann, T. Harmuth, All Ramsey numbers r(K_{3}, G) for connected graphs of order 9, in preparation.

[8] G. Brinkmann, All Ramsey numbers r(K_{3}, G) for connected graphs of order 7 and 8, submitted.

[9] A. Broder and E. Shamir, On the second eigenvalue of random regular graphs, In: 28th Symp. on Foundations of Comp. Sci., IEEE (1987), pp. 286– 294.

[10] S. A. Burr, Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. (2) 24 (1981), 11–20.

[11] S. A. Burr, What can we hope to accomplish in generalized Ramsey theory?, Discrete Math. 67 (1987), 215–225.

[12] S. A. Burr and P. Erdős, Generalizations of a Ramsey-theoretic result of Chvátal, J. Graph Theory 7 (1983), 39-51.

[13] S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, An extremal problem in generalized Ramsey theory, Ars Comb. 10 (1980), 193–203.

[14] S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The Ramsey number for the pair complete bipartite graph—graph of limited degree, in: Graph Theory with Applications to Algorithms and Computer Science (Alavi et. al., eds.) Wiley, 1985, 163–174.

[15] S. A. Burr and R. J. Faudree, On graphs G for which all large trees are G-good, Graphs & Comb. 9 (1993), 305–313.

[16] V. Chvátal, Tree—complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.

[17] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III, Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345.

[18] V. Chvátal, V. Rödl, E. Szemerédi and W. T. Trotter, The Ramsey number of graphs with bounded degree, J. Comb. Theory Ser. B 34 (1983), 239–243.

[19] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38.

[20] J. Friedman, On the second eigenvalue and random walks in random d-regular graphs, Combinatorica 11 (1991), 331–362.

[21] J. H. Kim, The Ramsey number R(3, t) has order of magnitude t^{2}/ log t, Random Structures & Algorithms 7 (1995), 173–207.

[22] A. Lubotsky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.

[23] R. W. Robinson and N. C. Wormald, Almost all regular graphs are Hamiltonian, Random Structures and Algorithms 5 (1994), 363–374.

[24] D. B. West, Introduction to graph theory, Prentice Hall, 1996.