Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: ON RAMSEY MINIMAL GRAPHS. | ON RAMSEY MINIMAL GRAPHS Tomasz LuCZAK 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-inhnite or Ramsey-hnite according to whether the class of all graphs critical for G H is a hnite or inhnite set. The problem of characterizing Ramsey-inhnite 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-hnite pairs consisting of two forests are specihed in a theorem of Faudree 7 and a recent result of Rodl and Rucinski 10 Corollary 2 implies that if G contains a cycle then the pair G G is Ramsey-inhnite. The main result of this note states that each pair which consists of a non-trivial forest and a non-forest is Ramsey-inhnite. 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-inhnite. 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-hnite if and only if G is a matching. COROLLARy 3. Let K1 2m denote a star with 2m rays. Then K1 2m G is Ramsey-hnite if and only if G is a matching. Proof of Theorem 1. We shall deduce Theorem 1 .
