ON RAMSEY MINIMAL GRAPHS

Tomasz Łuczak

Abstract. An elementary probabilistic argument is presented which shows that for every forest F other than a matching, and every graph G containing a cycle, there exists an infinite number of graphs J such that J → (F, G) but if we delete from J any edge e the graph J − e obtained in this way does not have this property.

Introduction. All graphs in this note are undirected graphs, without loops and multiple edges, containing no isolated points. We use the arrow notation of Rado, writing J → (G, H) whenever each colouring of edges of J with two colours, say, black and white, leads to either black copy of G or white copy of H. We say that J is critical for a pair (G, H) if J → (G, H) but for every edge e of J we have J −e ↛ (G, H). The pair (G, H) is called Ramsey-infinite or Ramsey-finite according to whether the class of all graphs critical for (G, H) is a finite or infinite set.

The problem of characterizing Ramsey-infinite pairs of graphs has been addressed in numerous papers (see [1–7, 9] and [8] for a brief survey of most important facts). In particular, basically all Ramsey-finite pairs consisting of two forests are specified in a theorem of Faudree [7] and a recent result of Rödl and Ruciński [10, Corollary 2] implies that if G contains a cycle then the pair (G, G) is Ramsey-infinite. The main result of this note states that each pair which consists of a non-trivial forest and a non-forest is Ramsey-infinite.

Theorem 1. If F is a forest other than a matching and G is a graph containing at least one cycle then the pair (F, G) is Ramsey-infinite.

Since, as we have already mentioned, minimal Ramsey properties for pairs consisting of two forests have been well studied, Theorem 1 has two immediate consequences.

Corollary 2. Let F be a forest which does not consist solely of stars. Then (F, G) is Ramsey-finite if and only if G is a matching.

Corollary 3. Let K_{1,2m} denote a star with 2m rays. Then (K_{1,2m}, G) is Ramsey-finite if and only if G is a matching.

Proof of Theorem 1. We shall deduce Theorem 1 from the following lemma, a probabilistic proof of which we postpone until the next section. Here and below, we denote by V (G) and E(G) sets of vertices and edges of a graph G, respectively, and set v(G) = |V (G)| and e(G) = |E(G)|.

The Electronic Journal of Combinatorics 1 (1994), #R4

Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322. On leave from Mathematical Institute of the Polish Academy of Sciences, and Adam Mickiewicz University, Poznań, Poland. Research partially supported by KBN grant 2 1087 91 01.

Lemma 4. Let G be a graph with at least one cycle and m, r be natural numbers. Then there exists a subgraph H of G containing a cycle, and a graph J = J(m, r, G) on n vertices, such that:

(a) J contains at least 3mn edge-disjoint copies of G,

(b) every subgraph of J with s vertices, where s ≤ r, contains at most (s − 1)e(H)/(v(H) − 1) edges.

Proof of Theorem 1. Let F be any forest on m vertices, other than a matching, and let G be a graph containing at least one cycle. We shall show that for every r there exists a graph with more than r vertices which is critical for (F, G). Thus, let J = J(m, r, G) be the graph whose existence is guaranteed by Lemma 4, and J̃ be a graph spanned in J by some 3mn edge-disjoint copies of G. Colour edges of J̃ black and white. If there are at least 2mn edges coloured black, then J̃ contains a black copy of F, since Turán’s number for the forest on m vertices is smaller than 2mv(J̃) ≤ 2mn. On the other hand, if the colouring contains less than 2mn black edges, they miss at least mn copies of G, i.e. at least one copy of G is coloured white. Thus, J̃ → (F, G).

Furthermore, for any subgraph K of J̃ on s vertices, s ≤ r, we have K ↛ (F, G). More specifically, we shall show that there is a black and white colouring of edges of K such that black edges form a matching and every proper copy of H, i.e. a copy which is contained in some copy of G, has at least one edge coloured black. Indeed, observe first that the upper bound for the density of subgraphs of J implies that each copy of H in G is induced and each two proper copies have at most one vertex in common (note that since all copies of G are edge-disjoint, proper copies of H can not share an edge). Thus, let H_{1} ⊆ K be a proper copy of H. Then, either no other proper copy of H shares with H_{1} a vertex, and then we may colour one edge of H_{1} black and all other edges of K incident to vertices of H_{1} white, or K contains another proper copy of H, say H_{2}, which has with H_{1} a vertex in common. But then the upper bound given by (b) implies that a subgraph spanned in K by V (H_{1}) ∪ V (H_{2}) contains no other edges but those which belong to E(H_{1}) ∪ E(H_{2}). In such a way one can find a sequence of proper copies of H, say, H_{1}, H_{2}, …, H_{t}, such that

(i) H_{i} share only one vertex, say v_{i}, with ⋃_{j=1}^{i−1} V (H_{j}), for every i = 2, 3, …, t, (ii) all edges of the subgraph spanned by ⋃_{j=1}^{t} V (H_{j}) are those from ⋃_{j=1}^{t} E(H_{j}), (iii) for each proper copy H′ of H contained in K we have V (H′) ∩ ⋃_{j=1}^{t} V (H_{j}) = ∅.

Now, pick as e_{1} any edge of H_{1} and for i = 2, 3, …, t, choose one edge e_{i} of H_{i} which does not contain vertex v_{i} (since H contains a cycle, such an edge always exists). Clearly, edges e_{i}, i = 1, 2, …, t, form a matching. Colour them black and all other edges adjacent to ⋃_{j=1}^{i−1} V (H_{j}) colour white. Obviously, in such a way we can colour each ‘cluster’ of proper copies of H contained in K, destroying all white copies of G and creating no black copies of F, so K ↛ (F, G).

Thus, we have shown that J̃ → (F, G) but for every subgraph K of J̃ with at most r vertices we have K ↛ (F, G). Consequently, any subgraph contained in J̃ critical for (F, G) must contain more than r vertices and the assertion follows.

Proof of Lemma 4. Let G be a graph with at least one cycle and

m(G) = max \{\frac{e(H)}{v(H) − 1} : H ⊆ G, v(H) ≥ 2\} .

Call a subgraph H of G extremal if m(G) = e(H)/(v(H) − 1). Note that since G contains a cycle, each extremal subgraph of G must contain a cycle as well. Furthermore, denote by G(n, p) a standard binomial model of a random graph on n vertices, in which each pair of vertices appears as an edge independently with probability p.

Lemma 5. Let G be a graph, r be a natural number and p = p(n) = n^{−1/m(G)} log n. Then, with probability tending to 1 as n → ∞, G(n, p) has the following two properties:

(a) G(n, p) contains at least n(log n)^{2} edge-disjoint copies of G,

(b) G(n, p) contains less than n/ log n subgraphs on s vertices, s ≤ r, with more than (s − 1)m(G) edges.

Proof. Let F be a random family of copies of G in G(n, p) such that the probability that a given copy of G in G(n, p) belongs to F is equal to

ρ = 4v(G)!\frac{n(log n)^{2}}{n^{v(G)}p^{e(G)}} ,

independently for each copy. Furthermore, denote by X the size of F. Then, for the expectation of X, we have

3n(log n)^{2} ≤ \binom{n}{v(G)}p^{e(G)}ρ ≤ E X ≤ n^{v(G)}p^{e(G)}ρ = O(n(log n)^{2}) ,

where here and below we assume all inequalities to hold only for n large enough. The second factorial moment of X can be decomposed into two parts: E′_{2} X, which counts the expected number of pairs of edge-disjoint copies from F, and E′′_{2} X related to those pairs of copies which share at least one edge. E′_{2} X can be easily shown to be equal to (E X)^{2}(1 + O(1/n)), whereas for the upper bound for E′′_{2} X we get

(∗)

E′′_{2} X ≤ ∑_{J⊆G} n^{v(J)}p^{e(J)}n^{2(v(G)−v(J))}p^{2(e(G)−e(J))}ρ^{2} ≤ O(n^{2}(log n)^{2}) ∑_{J⊆G} n^{−v(J)}p^{−e(J)}

≤ O(\frac{n}{log n}) ∑_{J⊆G} n^{e(J)(1/m(G)−(v(J)−1)/e(J))} = O(\frac{n}{log n}) .

Thus,

Var X = E_{2} X + E X − (E X)^{2} = E′_{2} X + E′′_{2} X + E X − (E X)^{2} = O(E X(log n)^{2}) ,

and, from Chebyshev’s inequality, X ≥ 2 E X/3 ≥ 2n(log n)^{2} with probability tending to 1 as n → ∞. Furthermore, note that (∗) implies that the expected number of copies of G in F which share an edge with another member of F is O(n/ log n), so, from Markov’s inequality, with probability at least 1 − O(1/ log n), the number of such copies in F is smaller than n. Thus, with probability tending to 1 as n → ∞, family F contains at least n(log n)^{2} edge-disjoint copies of G and the first part of the assertion follows.

In order to verify (b) let Y denote the number of subgraphs of G(n, p) of size s, s ≤ r, with more than (s − 1)m(G) edges, and define ϵ > 0 as

ϵ = min{⌊(s − 1)m(G)⌋ + 1 − (s − 1)m(G) : 1 ≤ s ≤ r} .

Then

E Y ≤ ∑_{s=1}^{r} \begin{matrix}( & {s \atop 2} & ) \\ ∑ \\ t=⌊(s−1)m(G)⌋+1 \end{matrix} n^{s}2^{\binom{s}{2}}p^{t} ≤ O(n^{1−ϵ/m(G)}(log n)^{\binom{r}{2}}) = O(n/(log n)^{2}) .

Hence, from Markov’s inequality, with probability tending to 1 as n → ∞ the number of such subgraphs is smaller than n/ log n.

Proof of Lemma 4. From Lemma 5 it follows that for every graph G which is not a forest, and for every natural number r, one can find N such that for each n ≥ N there exists a graph Ĵ_{n} on n vertices such that Ĵ_{n} contains at least n(log n)^{2} disjoint copies of G and the number of subgraphs of Ĵ_{n} with s vertices, s ≤ r, and more than (s − 1)m(G) edges, is smaller than n/ log n. Let n = max{N, e^{r^{2}}, e^{2m}}. Then, Ĵ_{n} contains at least 4m^{2}n edge-disjoint copies of G and not more than r^{2}n/ log n ≤ n edges which belong to ‘dense’ small subgraphs. Thus, removing these edges from Ĵ_{n} results in a graph J(m, r, G) without dense small subgraphs which contains at least 4m^{2}n − n ≥ 3mn edge-disjoint copies of G.

References

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

[2] S.A.Burr, P.Erdős, R.J.Faudree, C.C.Rousseau and R.H.Schelp, Ramsey minimal graphs for the pair star-connected graph, Studia Scient.Math.Hungar. 15 (1980), 265–273.

[3] S.A.Burr, P.Erdős, R.J.Faudree, C.C.Rousseau and R.H.Schelp, Ramsey minimal graphs for star forests, Discrete Math. 33 (1981), 227–237.

[4] S.A.Burr, P.Erdős, R.J.Faudree, C.C.Rousseau and R.H.Schelp, Ramsey minimal graphs for matchings, in The Theory and Applications of Graphs (G.Chartrand, ed.) Wiley (1981) pp.159–168.

[5] S.A.Burr, P.Erdős, R.J.Faudree, C.C.Rousseau and R.H.Schelp, Ramsey minimal graphs for forests, Discrete Math. 38 (1982), 23–32.

[6] S.A.Burr, P.Erdős, R.J.Faudree and R.H.Schelp, A class of Ramsey-finite graphs, in Proc.9th S.E.Conf. on Combinatorics, Graph Theory and Computing (1978) pp.171–178.

[7] R.J.Faudree, Ramsey minimal graphs for forests, Ars Combin. 31 (1991), 117–124.

[8] R.J.Faudree, C.C.Rousseau and R.H.Schelp, Problems in graph theory from Memphis, preprint.

[9] J.Nešetřil and V.Rödl, The structure of critical graphs, Acta Math.Acad.Sci.Hungar. 32 (1978), 295–300.

[10] V.Rödl and A.Ruciński, Threshold functions for Ramsey properties, submitted.

Key words and phrases: critical graphs, Ramsey theory 1991 Mathematics Subject Classifications: 05D10, 05C80