tailieunhanh - Báo cáo toán học: "A Bound for Size Ramsey Numbers of Multi-partite Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Bound for Size Ramsey Numbers of Multi-partite Graphs. | A Bound for Size Ramsey Numbers of Multi-partite Graphs Yuqin Sun and Yusheng Li Department of Mathematics Tongji University Shanghai 200092 P. R. China xxteachersyq@ li_yusheng@ Submitted Sep 28 2006 Accepted Jun 8 2007 Published Jun 14 2007 Mathematics Subject Classification 05C55 Abstract It is shown that the diagonal size Ramsey numbers of complete m-partite graphs Km n can be bounded from below by cn22 m-1 ra where c is a positive constant. Key words Size Ramsey number Complete multi-partite graph 1 Introduction Let G G1 and G2 be simple graphs with at least two vertices and let G G1 G2 signify that in any edge-coloring of edge set E G of G in red and blue there is either a monochromatic red G1 or a monochromatic blue G2. With this notation the Ramsey number r G1 G2 can be defined as r G1 G min N Kn Ơ1 Ơ2 min V G I G G1 G2 . As the number of edges of a graph is often called the size of the graph Erdos Faudree Rousseau and Schelp 2 introduced an idea of measuring minimality with respect to size rather than order of the graphs G with G Gp G2 . Let e G be the number of edges of G. Then the size Ramsey number r G1 G2 is defined as r G1 G2 min e G G G1 G2 . Supported in part by National Natural Science Foundation of China. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N11 1 As usual we write f G G as f G . Erdos and Rousseau in 3 showed r Kn n -1 n22n 1 60 Gorgol 4 gave f Km n cn22mn 2 2 where and henceforth Km n is a complete m-partite graph with n vertices in each part and c 0 is a constant. Bielak 1 gave f Kn n n cn n2 22n 3 where cn 413 as n 1. We shall generalize 1 and 3 by improving 2 as f Km n cn22 m-1 n where c cm 0 that has a positive limit as n 1. 2 Main results We need an upper bound for the number of subgraphs isomorphic to Km n in a graph of given size. The following counting lemma generalizes a result of Erdos and Rousseau 3 and we made a minor improvement for the case m 2. Lemma 1 Let n 2 be an integer. A graph with q edges