Ramsey Minimal Graphs

Béla Bollobás^{∗}

Department of Mathematical Sciences

University of Memphis Memphis TN 38152–6429, U.S.A.

and Trinity College

Cambridge CB2 1TQ, U.K.

e-mail: bollobas@msci.memphis.edu

Jair Donadelli^{†} and Yoshiharu Kohayakawa^{‡}

Instituto de Matemática e Estatística

Universidade de São Paulo Rua do Matão 1010

05508–090 São Paulo SP, Brazil

e-mail: {jair, yoshi}@ime.usp.br

Richard H. Schelp

Department of Mathematical Sciences

University of Memphis Memphis TN 38152–6429, U.S.A.

e-mail: schelpr@msci.memphis.edu

Dedicated to Professor Jayme L. Szwarcfiter on the occasion of his 60th birthday

Abstract

As usual, for graphs Γ, G, and H, we write Γ → (G, H) to mean that any red-blue colouring of the edges of Γ contains a red copy of G or a blue copy of H. A pair of graphs (G, H) is said to be Ramsey-infinite if there are infinitely many minimal graphs Γ for which we have Γ → (G, H).

Let ℓ ≥ 4 be an integer. We show that if H is a 2connected graph that does not contain induced cycles of length at least ℓ, then the pair (C^{k}, H) is Ramseyinfinite for any k ≥ ℓ, where C^{k} denotes the cycle of length k.

Keywords: Ramsey critical graphs, Szemerédi’s regularity lemma

1 Introduction

Let us say that a graph Γ is Ramsey for a pair of graphs (G, H) if any red-blue edge-colouring of Γ contains a red copy of G or a blue copy of H. Furthermore, let us say that a Ramsey graph for (G, H) is critical if no proper subgraph of it is Ramsey for (G, H). A pair of graphs (G, H) is said to be Ramsey-infinite if there are arbitrarily large critical Ramsey graphs for (G, H). For example, the pair (P^{3}, P^{3}), consisting of two paths on three vertices, is Ramsey-infinite as is shown by the family of all cycles of odd length. If a pair (G, H) is not Ramsey-infinite, then it is said to be Ramsey-finite.

Let us briefly discuss some results concerning the concepts above. The problem of characterizing those pairs of graphs (G, H) that are Ramsey-infinite was first addressed by Nešetřil and Rödl [10] in 1976. Among other results, those authors proved [12] in 1978 that (G, H) is Ramsey-infinite in the following three cases: (i) both G and H are forests containing a path of length three, (ii) both are 3-connected graphs, and (iii) both have chromatic number at least three. In 1978, Burr et al. [3] proved that if G is a matching then (G, H) is Ramsey-finite for all graphs H. In 1986, Burr [1] proved that if G is a 2-connected graph that remains connected after deleting any two non-adjacent vertices, then the pair (G, G) is Ramsey-infinite.

∗Partially supported by NSF grant DMS-9971788 and DARPA grant F33615-01-C-1900.

†Supported by a CNPq Doctorate Scholarship (Proc. 141633/1998-0).

‡Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997-4) and by CNPq (Proc.

300334/93-1, 468516/2000-0, and 910064/99-7).

In 1991, Faudree [5] basically characterized all Ramsey-finite pairs consisting of two forests. In 1994, Łuczak [9] proved that if G is a forest other than a matching and H contains a cycle, then (G, H) is a Ramsey-infinite pair.

Using Corollary 4 from [14] and Theorem 6 from [13], both results of Rödl and Ruciński, one may deduce that the pair (G, G) is Ramsey-infinite for all G containing a cycle.

Schaefer [15, 16] has recently proved some related, very interesting results concerning the computational complexity of the problem of deciding, given graphs Γ, G, and H, whether the Ramsey property Γ → (G, H) holds.

Burr et al. [2] proposed the following notable conjecture in 1980.

Conjecture 1 The pair (G, H) is Ramsey-infinite unless both G and H are stars with an odd number of edges or at least one of G and H contains a single edge component.

Faudree et al. [6] observe that “an interesting case of the above conjecture is when G is a cycle and H is two-connected. No technique is presently known for showing such a pair is Ramsey-infinite”. Although we are not able to deal with this case completely, we shall show that if we impose further restrictions on H, then such a pair (G, H) is indeed Ramsey-infinite.

This note is organized as follows. In §1.1, we state our main result, Theorem 2. In §2, we introduce the main technical lemmas that we shall need. In §3, we give an informal description of the proof of Theorem 2. Our proof strategy will be based on the probabilistic method; in §4, we give the definition of a random graph Γ that will be crucial, and we prove some lemmas concerning the structure of Γ. Theorem 2 is proved in §5. We close this note with some related observations.

1.1 Terminology and the main result

Let us recall some standard notation and state the main result of this note. A connected graph H is 2connected if it has at least 3 vertices, and the deletion of any vertex does not disconnect H. We call e ∈ E(H) a chord in a cycle C of H if e joins a pair of vertices of C that are not adjacent in C.

We shall use the arrow notation from Ramsey theory: we shall write Γ → (G, H) if the graph Γ is Ramsey for the pair (G, H). Moreover, given an integer t > 0, let us write Γ ↛_{t} (G, H) if for each U ⊂ V (Γ) with |U| ≤ t we have Γ[U] ↛ (G, H), that is, the graph induced by U in Γ is not Ramsey for (G, H).

For any integer ℓ ≥ 4, we denote by C(ℓ) the class of all 2-connected graphs H that have no induced cycle of length ≥ ℓ. Equivalently, C(ℓ) consists of the 2connected graphs H with the property that every cycle of H with ≥ ℓ edges has a chord. For instance, C(4) is the well known family of chordal graphs. Clearly,

C(4) ⊂ C(5) ⊂ C(6) ⊂ …

In this note, we prove the following result.

Theorem 2 Given integers ℓ ≥ 4 and t ≥ 1 and a graph H ∈ C(ℓ), there exists a graph Γ such that Γ → (C^{ℓ}, H) but Γ ↛_{t} (C^{ℓ}, H).

We may immediately deduce the following corollary.

Corollary 3 Let ℓ ≥ 4 be an integer and suppose H ∈ C(ℓ). Then the pair (C^{k}, H) is Ramsey-infinite for any k ≥ ℓ.

Our proof of Theorem 2 is probabilistic. It would be interesting to prove this result by explicit constructions.

Before we proceed, we recall some standard definitions. As usual, we write almost surely to mean ‘with probability tending to 1 as n → ∞’. If f(n) and g(n) are two functions of n, we write f(n) ≍ g(n) to mean that there is a positive constant C for which we have g(n)/C ≤ f(n) ≤ Cg(n) for all large enough n. Our asymptotic notation will always be with respect to n → ∞ and, in fact, we often tacitly assume that n is large enough for our inequalities to hold. All graphs are assumed to be undirected and simple.

Let h ≥ 2 be an integer. An h-uniform hypergraph on a set of vertices V is a collection E of subsets of V, called hyperedges, each of cardinality h. Thus, in the case in which h = 2, we have ordinary graphs. A hypergraph is linear if any two members of E intersect in at most one vertex. A hypercycle of length 2 is any pair of hyperedges meeting in more than one vertex, whereas a hypercycle of length k (k > 2) is a (linear) hypergraph given by hyperedges E = {E_{1}, …, E_{k}} on ⋃ E such that |E_{i} ∩E_{j}| = 1 if and only if i and j are such that j = i + 1 or i = k and j = 1. We sometimes use the term k-hypercycle to refer to a hypercycle of length k. The girth of a (hyper)graph is the length of a shortest (hyper)cycle in the (hyper)graph. When there is no danger of confusion, we use the simpler terms ‘edge’ and ‘cycle’ even when referring to hypergraphs.

It will be convenient to write G = G^{n} to indicate that the graph G has n vertices. We write e(G) for the number of edges in a graph G.

2 Auxiliary results

2.1 Szemerédi’s regularity lemma

We now describe a version of Szemerédi’s regularity lemma for sparse graphs. Given a graph G = (V, E), for any pair of disjoint sets U, W ⊂ V, we denote the set of edges in the bipartite subgraph induced by U and W in G by E_{G}(U, W), and let

e_{G}(U, W) = |E_{G}(U, W)|

= |{{a, b} ∈ E: a ∈ U and b ∈ W }|.

Suppose 0 < η ≤ 1, D ≥ 1, and 0 < p ≤ 1 are given real numbers. We say that G is (η, D, p)-sparse if, for any pair of disjoint sets U, W ⊂ V with |U|, |W | ≥ η|V |, we have

e_{G}(U, W) ≤ Dp|U||W |.

Strictly speaking, in the definition of (η, D, p)- sparseness above, we could have the product Dp as a single parameter, and would thus have the notion of, say, ‘(η, D′)-sparseness’ (with D′ = Dp). However, as it will become clear in the applications, we shall be dealing with cases in which there is a natural, underlying ‘density’ p in the context.

The p-density of the pair (U, W) in G is

d_{G,p}(U, W) = \frac{e_{G}(U, W)}{p|U||W |}.

For any 0 < ε ≤ 1, the pair of disjoint non-empty sets (U, W), with U, W ⊂ V, is said to be (ε, G, p)- regular if, for all U′ ⊂ U and all W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W |, we have

|d_{G,p}(U, W) − d_{G,p}(U′, W′)| < ε.

We say that a partition Π = (V_{0}, V_{1}, …, V_{k}) of V is (ε, k, G, p)-regular if |V_{0}| ≤ ε|V | and |V_{i}| = |V_{j}| for all i, j ∈ [k] = \{1, …, k\}, and for ≥ (1 − ε)\binom{k}{2} pairs {i, j} ⊂ [k] we have that (V_{i}, V_{j}) is (ε, G, p)- regular.

In this note, we shall use the following lemma, which is a natural variant of Szemerédi’s regularity lemma for sparse graphs observed independently by Kohayakawa and Rödl (see, e.g., [7]).

Lemma 4 For all real numbers ε > 0, D ≥ 1, and integer k_{0} ≥ 1, there exist constants η = η(ε, k_{0}, D) > 0 and K_{0} = K_{0}(ε, k_{0}, D) ≥ k_{0} such that, for any 0 < p = p(n) ≤ 1, any sufficiently large (η, D, p)-sparse graph G = G^{n} admits an (ε, k, G, p)-regular partition for some k_{0} ≤ k ≤ K_{0}.

2.2 A counting lemma

Suppose m > 0 and ℓ ≥ 3 are fixed integers and V^{(m)} = (V_{i})_{i=1}^{ℓ} is a fixed vector of pairwise disjoint sets of vertices, each of cardinality m. Below, the indices of the V_{i}’s will be taken modulo ℓ. Let B > 0, C ≥ 1, D ≥ 1, ε ≤ 1, and ϱ ≤ 1 be positive real numbers and let an integer M ≥ 1 be given. We call a graph F on ⋃_{1≤i≤ℓ} V_{i} an (ε, ϱ, B, C, D; V^{(m)}, M)- graph if

(i) E(F) = ⋃_{i=1}^{ℓ} E_{F} (V_{i}, V_{i+1}) and |E(F)| = M,

(ii) for all 1 ≤ i ≤ ℓ we have that the pairs (V_{i}, V_{i+1}) are (ε, F, \overline{p})-regular, where \overline{p} = Bm^{−1+1/(ℓ−1)}, and their \overline{p}-densities satisfy

ϱ ≤ d_{F,\overline{p}}(V_{i}, V_{i+1}) ≤ D,

(iii) for any 1 ≤ i < ℓ − 1, if U ⊂ V_{i} and W ⊂ V_{i+1} are such that

|U| ≤ |W | ≤ \overline{p}m|U| ≤ (\overline{p}m)^{ℓ−2} ,

then

e_{F} (U, W) ≤ C|W |.  (1)

The main technical result that we shall need is the following ‘counting lemma’, from Kohayakawa and Kreuter [8].

Lemma 5 Let an integer ℓ ≥ 3 be fixed, and let constants 0 < α ≤ 1, 0 < ϱ ≤ 1, C ≥ 1, and D ≥ 1 be given. Then there exist positive constants ε = ε(ℓ, α, ϱ, C, D) ≤ 1, B_{0} = B_{0}(ℓ, α, ϱ, C, D) > 0, and m_{0} = m_{0}(ℓ, α, ϱ, C, D) such that, for all integers m ≥ m_{0} and M ≥ 1, and all real B ≥ B_{0}, the number of (ε, ϱ, B, C, D; V^{(m)}, M)-graphs containing no cycle C^{ℓ} is at most

α^{M} \binom{(ℓ + 2)m^{2}}{M}.

In what follows, V^{(m)} will always denote a vector (V_{i})_{i=1}^{ℓ} of pairwise disjoint sets of vertices, each of cardinality m. If Γ is a graph and U = ⋃_{1≤i≤ℓ} V_{i} ⊂ V (Γ), then Γ[V^{(m)}] will denote the ℓ-partite subgraph of Γ with vertex set U and edge set

⋃_{1≤i≤ℓ} E_{Γ}(V_{i}, V_{i+1}),

where, as usual, the indices are taken modulo ℓ.

2.3 Ramsey’s theorem

The following is an easy consequence of Ramsey’s theorem (see, e.g., [8]).

Lemma 6 Let graphs H_{1}, …, H_{r} (r ≥ 1) be given. Then there exist positive constants c = c(H_{1}, …, H_{r}) > 0 and k_{0} = k_{0}(H_{1}, …, H_{r}) for which the following holds. If k ≥ k_{0} and K^{k} is given an arbitrary r-edge-colouring, then we necessarily have, for some 1 ≤ i ≤ r, at least ck^{|V (H_{i})|} monochromatic copies of H_{i} of colour i.

3 Outline of the proof of Theorem 2

In this section, we describe informally the strategy we employ in the proof of Theorem 2.

Let H be a graph in C(ℓ) on h vertices, where ℓ ≥ 4. We start by fixing a large positive constant A and by setting p_{H} = An^{−(h−1)+1/(ℓ−1)}. We then generate a random h-uniform hypergraph H_{n,p_{H}} on [n] = {1, …, n} according to the binomial model, that is, we independently let each element of

\binom{[n]}{h} = \{E ⊂ [n]: |E| = h\}

be a hyperedge of H_{n,p_{H}} with probability p_{H}. Owing to the choice of p_{H}, almost surely each hyperedge of H_{n,p_{H}} belongs to a large number of hypercycles of length ℓ. Moreover, one may also check that the number of hypercycles of length < ℓ in H_{n,p_{H}} is almost surely o(|E(H_{n,p_{H}})|).

We now obtain a linear hypergraph G of girth ℓ from H_{n,p_{H}} by removing a hyperedge from each of the o(|E(H_{n,p_{H}})|) hypercycles of H_{n,p_{H}} of length < ℓ. We now define a graph Γ = Γ^{n} from G embedding a copy of H in each hyperedge of G arbitrarily. The fact that H belongs to C(ℓ) implies that

(*) the only copies of H that occur in Γ are the ones that we have embedded in the hyperedges of G.

In particular, all the copies of H in Γ are induced copies. Also worth noting is that

(**) if e ∈ E(Γ), then there is a unique copy H′ of H in Γ that contains this edge e of Γ.

We claim that Γ will do in Theorem 2.

First, we wish to show that in every colouring of the edges of Γ with colours red and blue either there is a red copy of C^{ℓ} or else there is a blue copy of H. Let an adversary pick a colouring. We may suppose that our adversary has coloured red exactly one edge from each of the copies of H that we embedded in the hyperedges of G. Indeed, our adversary has to colour red at least one edge from each such copy of H; moreover, because of (*), having one red edge in each such copy of H suffices. We have to show that these red edges must necessarily create a copy of C^{ℓ}.

Let Γ^{(e)} be the spanning subgraph of Γ whose edges are the red edges in the colouring of our adversary. Note that Γ^{(e)} has

|G| = (1 + o(1))|E(H_{n,p_{H}})| ≍ n^{1+1/(ℓ−1)}

edges. Furthermore, as we shall show, there are positive constants A′ and D for which the graph Γ^{(e)} is (η, D, p_{e})-sparse, where

p_{e} = A′n^{−1+1/(ℓ−1)}

and η is an arbitrarily small constant.

Although not directly relevant to this proof, we observe that the random graph G_{n,p_{e}} is such that, almost surely, each of its edges belongs to a large number of ℓcycles, and in fact, by the well known theorem of Rödl and Ruciński [14], we have G_{n,p_{e}} → (C^{ℓ}, C^{ℓ}) if A′ is a large enough constant.

We now go back to the proof of Theorem 2. As the graph Γ^{(e)} is (η, D, p_{e})-sparse, we may apply the regularity lemma (Lemma 4), with some appropriate choices for k_{0} and ε, to obtain an ℓ-tuple (V_{1}, …, V_{ℓ}) of subsets of V (Γ) with (V_{i}, V_{i+1}) (ε; p_{e})-regular and with p_{e}-density bounded away from 0, for all 1 ≤ i ≤ ℓ, where the indices are taken modulo ℓ. By the counting lemma (Lemma 5), it will follow that almost surely Γ is so that such an ℓ-tuple (V_{1}, …, V_{ℓ}) must span an ℓ-cycle C^{ℓ} in Γ^{(e)}. By the definition of Γ^{(e)}, this cycle is monochromatic of colour red. Thus Γ → (C^{ℓ}, H).

In order to show that Γ ↛_{t} (C^{ℓ}, H) for any fixed integer t, we use the fact that almost surely Γ is such that, for any U ⊂ V (Γ) with |U| ≤ t, the graph Γ[U] induced by U in Γ contains a vertex that belongs to at most one copy of H that is completely contained in U. Using this fact, we may inductively colour the edges of Γ[U] red and blue to show that Γ[U] ↛ (C^{ℓ}, H).

4 The construction of Γ = Γ^{n}(ℓ, t, H)

In this section, we introduce the definition of the random graph Γ that is used in the proof of Theorem 2, and state and prove its relevant properties.

4.1 The construction

Suppose we are given an integer ℓ ≥ 4 and a graph H ∈ C(ℓ) of order h ≥ 3. Let V (Γ) = [n] = {1, …, n} and put

p_{H} = p_{H}(n) = An^{−(h−1)+1/(ℓ−1)},  (2)

where A is a positive constant to be defined later. We consider the random h-uniform hypergraph H_{n,p_{H}} on [n], in the standard binomial model. Almost surely, the number of hyperedges e(H_{n,p_{H}}) in H_{n,p_{H}} is

(1 + o(1))(A/h!)n^{1+1/(ℓ−1)}.

Define the hypergraph G from H_{n,p_{H}} deleting one edge from each of the hypercycles of length 2 ≤ k < ℓ. The expected number of such hypercycles in H_{n,p_{H}} is

c(h, k)\binom{n}{k}\binom{n − k}{k(h − 2)}p_{H}^{k} ≍ n^{k/(ℓ−1)}

≤ n = o(e(H_{n,p_{H}})), (3)

where c(h, k) is a constant that depends only on h and k. By Markov’s inequality, the number of hypercycles of length 2 ≤ k < ℓ is almost surely O(nω), for any function ω = ω(n) such that ω → ∞ as n → ∞. In particular, this number is o(e(H_{n,p_{H}})). Therefore, we have

e(G) = (1 + o(1))e(H_{n,p_{H}}).

Now, for each hyperedge F ∈ G we arbitrarily embed a copy of H in F; that is, we consider arbitrary injections

ι_{F} : V (H) ↪ F,

for all F ∈ G.

Finally, define Γ = (V, E) by putting V = [n] and

E = ⋃_{F ∈G} {{ι_{F} (x), ι_{F} (y)}: {x, y} ∈ E(H)}.

Note that Γ is, roughly speaking, a union of several copies of H. It will be important later to distinguish between two types of copies of H in Γ. For all F ∈ G we call the subgraph ι_{F} (H) ⊂ Γ a non-spontaneous copy of H in Γ. All the other copies of H in Γ we call spontaneous copies.

In the next section, we prove a few properties concerning subgraphs of Γ.

4.2 Subgraphs of Γ

We shall use the following notation below. We shall write Γ^{(e)} for a spanning subgraph of Γ that has the property that each edge of Γ^{(e)} may be extended to a distinct non-spontaneous copy of H in Γ. Recalling the definition of Γ, this means that the graph Γ^{(e)} admits a subhypergraph G(Γ^{(e)}) ⊂ G of G with

G(Γ^{(e)}) = {E_{f}: f ∈ E(Γ^{(e)})}

and with the map f ∈ E(Γ^{(e)}) ↦ E_{f} ∈ G(Γ^{(e)}) ⊂ G injective.

We shall now estimate that probability that Γ should contain a subgraph Γ^{(e)} that has a fixed graph on [n] as a subgraph. Thus, let J be a graph on [n] with edge set \{e_{1}, …, e_{M}\} ⊂ \binom{[n]}{2}. Suppose Γ admits a subgraph Γ^{(e)} with J ⊂ Γ^{(e)}. Then there must exist an M-tuple of hyperedges

(E_{1}, …, E_{M}) ∈ G^{M} = G × ⋯ × G ⊂ H_{n,p_{H}} × ⋯ × H_{n,p_{H}}

with e_{i} ∈ E_{i} for all 1 ≤ i ≤ M and with all the E_{i} distinct. If X = X(H_{n,p_{H}}) is the number of such Mtuples of distinct hyperedges in H_{n,p_{H}}, then

𝔼 X ≤ \binom{n}{h − 2}^{M}p_{H}^{M} < (An^{−1+1/(ℓ−1)})^{M}.

Therefore, by Markov’s inequality, we have

ℙ {∃Γ^{(e)} ⊂ Γ: J ⊂ Γ^{(e)}} ≤ 𝔼 X < p_{e}^{M},

where

p_{e} = An^{−1+1/(ℓ−1)}.

4.2.1 Bipartite subgraphs of Γ

We shall now discuss some results on Γ that assert that no bipartite subgraph of Γ has too high a density. The first result says that large bipartite subgraphs of Γ do not induce an unexpectedly large number of edges in Γ. The second result deals with bipartite subgraphs of Γ on a more local scale.

Proposition 7 For all positive η the graph Γ is almost surely (η, e2e(H), p_{e})-sparse.

Proof. Suppose U, W ⊂ V = V (Γ) = [n] are disjoint subsets of V (Γ) with cardinality |U| = |W | = ⌈ηn⌉ such that e_{Γ}(U, W) > e2e(H)p_{e}|U||W |. Then we have e_{Γ^{(e)}}(U, W) ≥ ⌈e2p_{e}|U||W |⌉, for some Γ^{(e)} ⊂ Γ. The event that there should be Γ^{(e)} ⊂ Γ with e_{Γ^{(e)}}(U, W) ≥ M = ⌈e2p_{e}|U||W |⌉ = Ω(n^{1+1/(ℓ−1)}) has probability at most

\binom{|U||W |}{M}p_{e}^{M} ≤ (e\frac{|U||W |p_{e}}{M} )^{M} ≤ (\frac{1}{2})^{M} .

The number of disjoint subsets U, W ⊂ V with cardinality ⌈ηn⌉ is smaller than 2^{2n}. Therefore, the expected number of pairs of subsets (U, W) spanning > e2e(H)p_{e}|U||W | edges of Γ between them is at most 2^{2n}2^{−M} = o(1). Our proposition follows from Markov’s inequality. □

We shall say that a graph on V = [n] is (p_{e}, C, ℓ)- locally-sparse if, for all disjoint subsets U and W of V with |U| ≤ |W | ≤ (p_{e}n)|U| ≤ (p_{e}n)^{ℓ−2}, we have e(U, W) ≤ C|W |.

Proposition 8 Almost surely the graph Γ is (p_{e}, 4(ℓ− 1)e(H), ℓ)-locally-sparse.

Proof. We proceed as in the previous proof. For convenience, let

C = 4(ℓ − 1)e(H)

and

C′ = C/e(H) = 4(ℓ − 1).

Note that if e_{Γ}(U, W) > C|W |, then there is Γ^{(e)} ⊂ Γ with e_{Γ^{(e)}}(U, W) > C′|W |. If U and W ⊂ V = [n] are fixed, we have

ℙ (∃Γ^{(e)} ⊂ Γ: e_{Γ^{(e)}}(U, W) > C′|W |)

≤ \binom{|U||W |}{⌈C′|W |⌉}p_{e}^{⌈C′|W |⌉} ≤ (\frac{e|U|}{C′}p_{e})^{C′|W |} .

By definition, we are concerned with U and W with |U| ≤ |W | ≤ (p_{e}n)|U| ≤ (p_{e}n)^{ℓ−2}. Notice that p_{e}|U| ≤ (p_{e}n)^{ℓ−2}/n ≤ A^{ℓ−2}n^{−1/(ℓ−1)}. From the fact that |U| ≤ |W | < λn for any λ > 0 for large enough n, we conclude that

\binom{n}{|U|} ≤ \binom{n}{|W |}

and, therefore,

\binom{n}{|U|}\binom{n}{|W |} ≤ \binom{n}{|W |}^{2}.

These inequalities imply that the expected number of pairs (U, W) with U and W of cardinalities u and w such that

u ≤ w ≤ (p_{e}n)u ≤ (p_{e}n)^{ℓ−2}

and such that e_{Γ}(U, W) > Cw is smaller than

∑_{1≤w<λn} ∑_{1≤u≤w} \binom{n}{u}\binom{n}{w} (\frac{e}{C′} · p_{e}u)^{C′w} ,

which is at most

∑_{1≤w<λn} w\binom{n}{w}^{2} (\frac{e}{C′} A^{ℓ−2}n^{−1/(ℓ−1)})^{C′w}

≤ ∑_{1≤w<λn} w (\frac{en}{w})^{2w} (\frac{e}{C′} A^{ℓ−2}n^{−1/(ℓ−1)})^{C′w}

= ∑_{1≤w<λn} \frac{w}{w^{2w}} (\frac{e^{1+2/C′}}{C′} A^{ℓ−2}n^{(2/C′)−(1/(ℓ−1))})^{C′w}

≤ ∑_{1≤w<λn} (\frac{e^{1+2/C′}}{C′} A^{ℓ−2}n^{−2/C′})^{C′w}

= o(1).

Our result follows from Markov’s inequality. □

4.2.2 V^{(m)}-subgraphs of Γ

Suppose a constant ϱ > 0 is fixed, and suppose α > 0 is a constant with

α ≤ \frac{ϱℓ}{e^{2}(ℓ + 2)}.

Put

C = 4(ℓ − 1)e(H) and D = e2e(H),

and fix k_{0} ∈ ℕ. Let ε, B_{0}, and m_{0} be the constants whose existence is guaranteed by Lemma 5 for the constants above, and let η and K_{0} be the constants given by Lemma 4 for these values of ε, D, and k_{0}. Recall we write V^{(m)} for a vector (V_{i})_{i=1}^{ℓ} of pairwise disjoint, m-element subsets of V (Γ) = [n]. Recall p_{e} = An^{−1+1/(ℓ−1)}.

Proposition 9 Suppose A ≥ 2B_{0}K_{0}. Then almost surely Γ has the following property. If V^{(m)} and Γ^{(e)} ⊂ Γ are such that

m ≥ \frac{n}{2K_{0}}

and the pairs (V_{i}, V_{i+1}) are (ε, Γ^{(e)}, p_{e})-regular of density at least ϱ for all 1 ≤ i ≤ ℓ, then Γ^{(e)}[V^{(m)}] spans a C^{ℓ}.

Proof. We shall make use of Lemma 5 and Propositions 7 and 8. Let B be such that

p_{e} = Bm^{−1+1/(ℓ−1)}.

Let V^{(m)} and Γ^{(e)} be as in the statement of our proposition.

By the choices of B, C, and D, and by Propositions 7 and 8, we may and shall suppose that Γ^{(e)}[V^{(m)}] is an (ε, ϱ, B, C, D; V^{(m)}, M)-graph, where M is at least ϱp_{e}m^{2}ℓ.

Now notice that

B = p_{e}m^{1−1/(ℓ−1)} = A(m/n)^{1−1/(ℓ−1)}

> B_{0}(2K_{0}m/n)^{1−1/(ℓ−1)} ≥ B_{0},

where the last inequality comes from m ≥ n/2K_{0}. Note that if n is sufficiently large, then m ≥ m_{0}, where m_{0} is as in Lemma 5.

By Lemma 5, the expected number of (ε, ϱ, B, C, D; V^{(m)}, M)-subgraphs in Γ^{(e)} that contains no cycle of length ℓ is, for a fixed V^{(m)}, at most

α^{M} \binom{(ℓ + 2)m^{2}}{M}p_{e}^{M}

≤ (α\frac{e(ℓ + 2)m^{2}}{M} p_{e})^{M} ≤ (\frac{eα(ℓ + 2)}{ℓϱ})^{M}

= (\frac{1}{e})^{M} ≤ exp \{−ϱp_{e}m^{2}ℓ\} .

Summing over all choices for V^{(m)}, we deduce that the expected number of (ε, ϱ, B, C, D; V^{(m)}, M)- subgraphs of Γ^{(e)} with no C^{ℓ}, where V^{(m)} is arbitrary, is

≤ n^{ℓm} exp {−ϱp_{e}m^{2}ℓ}

≤ exp {(log n)mℓ − ϱp_{e}m^{2}ℓ} = o(n^{−3}),

for all integers m and M ≥ ϱp_{e}m^{2}ℓ. Summing over all choices for 1 ≤ m ≤ n and 1 ≤ M ≤ \binom{n}{2}, we have a factor of at most n^{3}. Therefore, our result follows by Markov’s inequality. □

For technical reasons that will become clear only when we prove that Γ → (C^{ℓ}, H) holds almost surely, we shall need to know the number of certain edges that occur in induced h-partite subgraphs of Γ.

We shall write W^{(m)} for h-tuples (W_{i})_{i=1}^{h} of pairwise disjoint sets of vertices of Γ, each of cardinality m.

Proposition 10 Suppose A ≥ (h + 1)/e^{h}. For all W^{(m)} = (W_{j})_{j=1}^{h} with n/ log n ≤ m ≤ n/h, the hpartite subgraph of Γ induced by W^{(m)} almost surely spans at least

\frac{1}{4}e(H)m^{h}p_{H}

edges that may be extended to non-spontaneous copies of H in Γ with all its vertices within

U = ⋃_{1≤j≤h} W_{j}.

Proof. Fix the h-tuple W = W^{(m)} = (W_{j})_{j=1}^{h} of pairwise disjoint subsets of vertices of Γ of cardinality m each and let U = ⋃_{j=1}^{h} W_{j} be as in the statement of our proposition. Define the random variable X_{W} as the number of hyperedges in H_{n,p_{H}} with exactly one vertex from each W_{i}.

The expectation of X_{W} is 𝔼 X_{W} = m^{h}p_{H}. Using Chernoff’s inequality we have

ℙ (X_{W} ≤ \frac{1}{2}𝔼 X_{W})

≤ exp \{−\frac{1}{8}𝔼 X_{W}\}

≤ exp \{−\frac{A}{8}m^{h}n^{−h+1+1/(ℓ−1)}\}

≤ exp \{−\frac{A}{8} (\frac{n}{log n})^{h} n^{−h+1+1/(ℓ−1)}\}

≤ exp \{−\frac{An^{1+1/(ℓ−1)}}{8(log n)^{h}} \} ,

and, as the number of choices for W = W^{(m)} = (W_{j})_{j=1}^{h} is at most 2^{hn}, the probability that there should exist W such that X_{W} ≤ (1/2)𝔼 X_{W} is smaller than

exp \{(h − \frac{An^{1/(ℓ−1)}}{8(log n)^{h}} ) n\} = o(1).

That is, almost surely X_{W} > (1/2)𝔼 X_{W}.

The number of hyperedges deleted from H_{n,p_{H}} to get rid of short hypercycles is O(nω), for any function ω = ω(n) → ∞ as n → ∞. Therefore the number of hyperedges induced by W in G is almost surely ≥ (1/2)𝔼 X_{W} − O(nω) ≥ (1/4)𝔼 X_{W}. Each such hyperedge gives e(H) edges of Γ. Notice that, in fact, all these edges we have just considered are edges that extend to non-spontaneous copies of H in Γ within U, as required in our proposition. This completes the proof of our result. □

4.2.3 Small subgraphs of Γ

Given a vertex v ∈ V = [n], the number of hyperedges of G that contain the vertex v will be called the hyperdegree of v in G, and will be denoted by d_{G}(v). Let us denote by G[U] the sub-hypergraph of G induced by U ⊂ [n]. Thus, G[U] = {E ∈ G: E ⊂ U}.

Proposition 11 Let t be any fixed positive integer. Then almost surely every subset U ⊂ V = [n] with |U| ≤ t contains a vertex v whose hyperdegree in H_{n,p_{H}}, and hence in G, is at most 1, that is, d_{G[U]}(v) ≤ d_{H_{n,p_{H}} [U]} ≤ 1.

Proof. Let U ⊂ V be a subset of cardinality u. If U induces m hyperedges and all vertices in U have hyperdegree at least 2, then m ≥ 2u/h. Thus

ℙ (d_{H_{n,p_{H}} [U]}(v) ≥ 2 all v ∈ U)

≤ ℙ (m ≥ \frac{2u}{h})

≤ \binom{\binom{u}{h}}{⌈2u/h⌉}p_{H}^{⌈2u/h⌉}

= O (n^{−2u+(2u/h)(1+1/(ℓ−1))}) .

Therefore, the probability that there should exist a subset U ⊂ V violating our condition is

\binom{n}{u}O (n^{−2u+(2u/h)(1+1/(ℓ−1))})

= O (n^{−u+(2u/h)(1+1/(ℓ−1))}) . (4)

As ℓ ≥ 4, the quantity in (4) is o(1) for all h ≥ 3. Hence such a set U almost surely does not exist, and our result follows. □

5 Proof of Theorem 2

Suppose we are given integers ℓ ≥ 4 and t ≥ 1 and a graph H ∈ C(ℓ) of order h ≥ 3. In our proof, we shall need a number of constants given by Lemmas 4, 5, and 6. First, let

k_{0} = k_{0}(K^{2}, C^{ℓ}, K^{h}) and c = c(K^{2}, C^{ℓ}, K^{h})

be the constants given by Lemma 6. Set

ϱ = \frac{c}{2^{h+2}} , α = \frac{ϱℓ}{e^{2}(ℓ + 2)}, C = 4(ℓ − 1)e(H),

and

D = e2e(H).

Next, let

ε = ε(ℓ, α, ϱ, C, D), B_{0} = B_{0}(ℓ, α, ϱ, C, D),

and

m_{0} = m_{0}(ℓ, α, ϱ, C, D)

be the constants whose existence is guaranteed by Lemma 5, and let

η = η(ε, k_{0}, D) and K_{0} = K_{0}(ε, k_{0}, D)

be the constants given by Lemma 4. We may assume that ε < min{1/2, 2c}. Finally, let

A = max {2B_{0}K_{0}, (h + 1)e^{−h}} .

We now consider a certain family F = F(H) of graphs Γ on V = [n]. First of all, our graphs Γ may be written as a union of M copies of H, say H_{1}, …, H_{M}, with M ≍ \binom{n}{h}p_{H} and with any two distinct H_{i} sharing at most one vertex. In fact, for each Γ in our family, we single out a specific family H_{i} (1 ≤ i ≤ M), and refer to these H_{i} as non-spontaneous copies of H in Γ. All other copies of H in Γ are said to be spontaneous. Furthermore, our graphs Γ = ⋃_{1≤i≤M} H_{i} ∈ F = F(H) satisfy the following properties:

(P1) the hypergraph on V = [n] given by

G = {V (H_{i}): 1 ≤ i ≤ M}

has girth ℓ;

(P2) Γ is (η, D, p_{e})-sparse and (p_{e}, C, ℓ)-locally-sparse;

(P3) for all V^{(m)} = (V_{1}, …, V_{ℓ}), where n/2K_{0} ≤ m ≤ n/k_{0}, if Γ^{(e)} ⊂ Γ[V^{(m)}] is such that the pairs (V_{i}, V_{i+1}) are (ε, Γ^{(e)}, p_{e})-regular of p_{e}- density at least ϱ for all 1 ≤ i ≤ ℓ, then Γ^{(e)} contains C^{ℓ};

(P4) every W^{(m)} = (W_{1}, …, W_{h}) with m ≥ n/ log n

induces

≥ \frac{1}{4}e(H)m^{h}p_{H}

edges of Γ that may be extended to nonspontaneous copies H_{i} of H within

U = ⋃_{1≤j≤h} W_{j};

(P5) all U ⊂ V = [n] with t vertices contains a vertex v_{U} that belongs to at most one nonspontaneous copy H_{i} of H such that V (H_{i}) ⊂ U.

By Propositions 7–11 in §4.2, the family F = F(H) is not empty. The fact that H belongs to C(ℓ) together with (P1) imply the following additional property, whose proof is postponed to §5.3.

(P6) Γ does not contain spontaneous copies of H.

Let us fix a graph Γ in F = F(H). We claim that this choice for Γ will do in Theorem 2. We prove this claim in §§5.1 and 5.2 below.

5.1 Proof of Γ → (C^{ℓ}, H)

Let Γ^{(e)} be the spanning subgraph of Γ defined by colouring red exactly one edge from each nonspontaneous copy H_{i} (1 ≤ i ≤ M) of H in Γ. We shall show that Γ^{(e)} contains a cycle C^{ℓ}. This clearly proves that Γ → (C^{ℓ}, H).

By (P2) we know that Γ^{(e)} is (η, D, p_{e})-sparse. Applying Lemma 4 we get an (ε, k, Γ^{(e)}, p_{e})-regular partition Π = (V_{0}, V_{1}, …, V_{k}) with k_{0} ≤ k ≤ K_{0}. Denote by m the common cardinality of the V_{i} (1 ≤ i ≤ k). We have

\frac{n}{2K_{0}} ≤ \frac{n}{2k} ≤ m ≤ \frac{n}{k} ≤ \frac{n}{k_{0}} .

Let K^{k} be the complete graph on V (K^{k}) = {V_{1}, …, V_{k}}, and consider the following 3-colouring of the edges of K^{k}:

(a) colour {V_{i}, V_{j}} with 1 if (V_{i}, V_{j}) is not ε-regular,

(b) colour {V_{i}, V_{j}} with 2 if (V_{i}, V_{j}) is ε-regular of density ≥ ϱ,

(c) colour {V_{i}, V_{j}} with 3 if (V_{i}, V_{j}) is ε-regular of density < ϱ.

Since k ≥ k_{0}, we have by Lemma 6 that in this colouring of K^{k} there must be

(i) at least ck^{2} copies of K^{2} with all edges of colour 1, or

(ii) at least ck^{ℓ} copies of C^{ℓ} with all edges of colour 2, or

(iii) at least ck^{h} copies of K^{h} with all edges of colour 3.

Note that (i) cannot hold, because the number of pairs that are not ε-regular is ≤ ε\binom{k}{2} ≤ 2c\binom{k}{2} < ck^{2}. If (ii) holds, any C^{ℓ} ⊂ K^{k} of colour 2 determines a vector, say V^{(m)} = (V_{i})_{i=1}^{ℓ}, of pairwise disjoint subsets of vertices of Γ such that, according to (P3), will happily give us a C^{ℓ} ⊂ Γ^{(e)}. Let us suppose that (iii) holds and let us derive a contradiction. This will then force (ii) to hold, completing our proof.

The number of edges in Γ^{(e)} that belong to the E_{Γ^{(e)}}(V_{i}, V_{j}) that correspond to colour 3 edges from K^{k} is

∑ {e_{Γ^{(e)}}(V_{i}, V_{j}): {V_{i}, V_{j}} ∈ E(K^{k}) of colour 3}

< \binom{k}{2}ϱp_{e}m^{2} ≤ \binom{k}{2}ϱp_{e} (\frac{n}{k})^{2}

< \frac{1}{2}ϱAn^{1+1/(ℓ−1)} < \frac{c}{2^{h+3}} An^{1+1/(ℓ−1)}. (5)

On the other hand, by (iii), we have at least ck^{h} copies of K^{h} that are monochromatic of colour 3 in K^{k}. Fix one such K^{h}, and let J be the h-partite subgraph of Γ naturally associated with this K^{h}. Each vertex class of J has m ≥ n/2K_{0} ≥ n/ log n vertices.

By Property (P4), we know that J spans ≥ (1/4)e(H)m^{h}p_{H} edges that may be extended to nonspontaneous copies of H within V (J). Therefore, we have ≥ (1/4)m^{h}p_{H} non-spontaneous copies of H within J, and hence we have ≥ (1/4)m^{h}p_{H} edges from Γ^{(e)} within J. Finally, note that if we have two distinct K^{h} monochromatic of colour 3 in K^{k}, then each ‘contributes’ with ≥ (1/4)m^{h}p_{H} distinct edges in our edge count for Γ^{(e)}. Indeed, this comes from our somewhat peculiar definition of the edges that are counted in (P4), and the fact that any two nonspontaneous copies H_{i} of H in Γ have no common edges.

Since we have ≥ ck^{h} copies of K^{h} that are monochromatic of colour 3 in K^{k}, we have at least

ck^{h} \frac{1}{4}m^{h}p_{H} ≥ ck^{h} \frac{1}{4} (\frac{n}{2k} )^{h} An^{−h+1+1/(ℓ−1)}

≥ \frac{c}{2^{h+2}} An^{1+1/(ℓ−1)} (6)

edges that belong to the E_{Γ^{(e)}}(V_{i}, V_{j}) that correspond to colour 3 edges from K^{k}. However, inequalities (5) and (6) contradict each other, and hence we may conclude that (iii) cannot hold. This completes our proof of the fact that Γ → (C^{ℓ}, H).

5.2 Proof of Γ ↛_{t} (C^{ℓ}, H)

In this section we prove, by induction in |U|, that any induced subgraph Γ[U] on at most t vertices is not Ramsey for the pair (C^{ℓ}, H). Let U ⊂ V = [n]. If |U| < max{ℓ, h} then, clearly, Γ[U] ↛ (C^{ℓ}, H).

Let us suppose that max{ℓ, h} ≤ |U| ≤ t and that in any subset U′ ⊂ V of smaller cardinality the induced subgraph is not Ramsey for the pair (C^{ℓ}, H). By (P5) there exists a vertex v_{U} that belongs to at most one non-spontaneous copy H_{i} of H in Γ such that V (H_{i}) ⊂ U; for convenience, let H_{i_{0}} be this H_{i} if it exists. Now, fix a red-blue edge-colouring of Γ[U\{v_{U}}] with neither a red copy of C^{ℓ} nor a blue copy of H. Such a colouring exists by the induction hypothesis.

Colouring red only one edge e incident to v_{U} does not create a red C^{ℓ} in Γ[U]. The other edges incident to v_{U} we colour blue. Note that we may choose the edge e in such a way that we do not create a blue copy of H: it suffices to pick e from H_{i_{0}} (if it exists; otherwise the choice is arbitrary). With this choice, if we do create a blue copy of H in Γ[U], then we must have a spontaneous copy of H in Γ[U] ⊂ Γ. However, spontaneous copies of H do not exist by (P6) and hence we have indeed found a colouring of Γ[U] without a red C^{ℓ} and without a blue H. This completes the induction step and the proof is complete.

5.3 On the property (P6)

Let us consider a graph Γ = ⋃_{1≤i≤M} H_{i} in the family F = F(H), with H ∈ C(ℓ). We wish to show that Γ does not contain spontaneous copies of H. We shall deduce this from (P1) in the definition of the family F = F(H). The reader will see that this is not particularly difficult to prove, but we shall present a detailed proof.

The proof is by contradiction. Suppose H̃ is a spontaneous copy of H in Γ. Let Ẽ = V (H̃) and E_{i} = V (H_{i}) (1 ≤ i ≤ M). Recall that (P1) states that the hypergraph G = {E_{i}: 1 ≤ i ≤ M} has girth ℓ. Note that this implies that all the H_{i} are induced subgraphs of Γ, as ℓ > 2. Since H̃ is spontaneous, it follows that Ẽ ∉ G.

Below, we shall often use the following fact: if e is an edge of Γ = ⋃_{1≤i≤M} H_{i}, then e ∈ E(H_{i}) for a uniquely determined index 1 ≤ i = i(e) ≤ M. Clearly, the uniqueness of i = i(e) follows from the fact that G is a linear hypergraph.

We shall call a cycle C in H̃ useful if it has edges in at least two distinct H_{i} (1 ≤ i ≤ M).

Claim 12 The graph H̃ contains a useful cycle.

Proof. Let x ∈ Ẽ be an arbitrary vertex in Ẽ = V (H̃), and let e = {x, x′} be an edge of H̃ incident to x. Let 1 ≤ i_{0} = i_{0}(e) ≤ M be such that e ∈ E(H_{i_{0}}). We cannot have Ẽ ⊂ E_{i_{0}} = V (H_{i_{0}}) ∈ G. Let y ∈ Ẽ \ E_{i_{0}}, and let f = {y, y′} be an edge of H̃ incident to y. There is a unique 1 ≤ j_{0} = j_{0}(f) ≤ M with f ∈ E(H_{j_{0}}). Clearly, j_{0} ≠ i_{0}.

As H is 2-connected, the edges e = {x, x′} ∈ E(H_{i_{0}}) and f = {y, y′} ∈ E(H_{j_{0}}) lie on a cycle of H̃. Thus H̃ contains a cycle that has edges in distinct H_{i}, as claimed. □

Let us now observe that any useful cycle C ⊂ H̃ may be written as a concatenation of q = q(C) ≥ 2 paths P_{1}, …, P_{q} such that

(i) each P_{i} (1 ≤ i ≤ q) has at least one edge,

(ii) each P_{i} (1 ≤ i ≤ q) is contained in an H_{j}, where j = j(i) is uniquely determined,

(iii) we have j(i − 1) ≠ j(i) for all 1 ≤ i ≤ q, where the indices i are taken modulo q.

Let C_{0} ⊂ H̃ be a useful cycle of minimal length, and put q_{0} = q(C_{0}).

Recall that we write E_{j} for V (H_{j}) ∈ G (1 ≤ j ≤ M). Consider the cyclic sequence E_{j(1)}, …, E_{j(q_{0})} of hyperedges of G determined by C_{0} (see (ii) above). A moment’s thought now shows that there must be a segment of this sequence with q′ elements (2 ≤ q′ ≤ q_{0}) that forms a hypercycle in G. Since G has girth ℓ, we have q_{0} ≥ q′ ≥ ℓ. Because of (i) above, we have that C_{0} has length ≥ q_{0} ≥ ℓ.

We now use the definition of the family C(ℓ) and the fact that H̃ ∈ C(ℓ) to deduce that the cycle C_{0} ⊂ H̃ must have a chord, say c ∈ E(H̃). This chord c belongs to some H_{i} (1 ≤ i ≤ M), say H_{i(c)}. Recall C_{0} is a useful cycle, and let i(1) ≠ i(2) be such that C_{0} contains edges from both H_{i(1)} and H_{i(2)}. Adjusting the notation, we may further assume that i(c) ≠ i(1).

Let C_{1} and C_{2} be the two cycles sharing the chord c that together form C_{0} + c. By adjusting the notation again, we may assume that there is an edge of H_{i(1)} in C_{1}. Since c ∈ E(C_{1}) ∩ E(H_{i(c)}) and i(c) ≠ i(1), the cycle C_{1} ⊂ H̃ is useful. As C_{1} is shorter than C_{0}, we have a contradiction to the choice of C_{0}. This contradiction shows that no spontaneous copy of H may occur in Γ, and our proof is complete.

6 Concluding remarks

Our proof of the fact that the Ramsey property Γ → (C^{ℓ}, H) holds almost surely follows [8] closely, although the random graph Γ presents some different technical difficulties (in [8], Ramsey properties of the usual binomial random graph G_{n,p} are investigated). The construction of Γ has already been used to prove Ramsey type results for orderings and vertex colourings (see, e.g., Nešetřil and Rödl [11]).

The strong assumption given by property (P6) was crucial in our proof of the fact that Γ ↛_{t} (C^{ℓ}, H) holds almost surely. It was in fact (P6) that led us to restrict H to 2-connected graphs without long induced cycles. It would be very interesting to drop this hypothesis on long cycles, or at least find further natural, weaker conditions that ensures (P6) given that (P1) holds.

Going in another direction, we mention that Burr, Faudree, and Schelp [4] proved that (G, H) is Ramseyinfinite if all the pairs (G_{i}, H_{j}) are Ramsey-infinite, where the G_{i} are the blocks of G and the H_{j} are the blocks of H.

We close by mentioning that we have in fact proved a stronger Ramsey property for Γ. Indeed, we proved that, almost surely, Γ is such that, in any colouring of its edges with red and blue, either there is an induced C^{ℓ} all the edges of which are coloured red, or else there is an induced copy of H all the edges of which are coloured blue. Therefore, we have proved that the pair (C^{ℓ}, H) is what is called strong-Ramsey-infinite. This concept has been investigated in Burr [1], Burr, Faudree, and Schelp [4], and Nešetřil and Rödl [12], among others.

7 Acknowledgements

The authors are grateful to the referee for his or her comments.

References

[1] Stefan A. Burr, Some Ramsey-infinite graphs in the diagonal case, Ars Combin. 21 (1986), 173– 178. MR 87m:05126 1, 6

[2] Stefan A. Burr, Paul Erdős, Ralph J. Faudree, Cecil C. Rousseau, and Richard H. Schelp, Ramsey-minimal graphs for matchings, The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, 1981, pp. 159– 168. MR 83c:05092 1

[3] Stefan A. Burr, Paul Erdős, Ralph J. Faudree, and Richard H. Schelp, A class of Ramsey-finite graphs, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (Winnipeg, Man.), Utilitas Math., 1978, pp. 171–180. MR 80m:05081 1

[4] Stefan A. Burr, Ralph J. Faudree, and Richard H. Schelp, On graphs with Ramsey-infinite blocks, European J. Combin. 6 (1985), no. 2, 129–132. MR 87f:05118 6

[5] Ralph Faudree, Ramsey minimal graphs for forests, Ars Combin. 31 (1991), 117–124. MR 92i:05151 1

[6] Ralph J. Faudree, Cecil C. Rousseau, and Richard H. Schelp, Problems in graph theory from Memphis, The mathematics of Paul Erdős, II, Springer, Berlin, 1997, pp. 7–26. MR 97m:05134 1

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

[8] Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms 11 (1997), no. 3, 245–276. MR 99g:05159 2.2, 2.3, 6

[9] Tomasz Łuczak, On Ramsey minimal graphs, Electron. J. Combin. 1 (1994), Research Paper 4, approx. 4 pp. (electronic). MR 95b:05149 1

[10] Jaroslav Nešetřil and Vojtěch Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976), no. 1, 85–95. MR 54 #173 1

[11] , On a probabilistic graph-theoretical method, Proc. Amer. Math. Soc. 72 (1978), no. 2, 417–421. MR 80a:05158 6

[12] , The structure of critical Ramsey graphs, Acta Math. Acad. Sci. Hungar. 32 (1978), no. 3-4, 295–300. MR 80c:05102 1, 6

[13] Vojtěch Rödl and Andrzej Ruciński, Lower bounds on probability thresholds for Ramsey properties, Combinatorics, Paul Erdős is eighty, Vol. 1, János Bolyai Math. Soc., Budapest, 1993, pp. 317–346. MR 95b:05150 1

[14] , Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942. MR 96h:05141 1, 3

[15] Marcus Schaefer, Graph Ramsey theory and the polynomial hierarchy (extended abstract), Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM, New York, 1999, pp. 592–601 (electronic). MR 1 798 082 1

[16] , Graph Ramsey theory and the polynomial hierarchy, J. Comput. System Sci. 62 (2001), no. 2, 290–322, Special issue on the Fourteenth Annual IEEE Conference on Computational Complexity (Atlanta, GA, 1999). MR 2002a:68049 1