tailieunhanh - Báo cáo toán học: "Constructive Lower Bounds on Classical Multicolor Ramsey Numbers"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài:Constructive Lower Bounds on Classical Multicolor Ramsey Numbers. | Constructive Lower Bounds on Classical Multicolor Ramsey Numbers Xu Xiaodong and Xie Zheng Department of Mathematics and System Science National University of Defense Technology Changsha 410073 . China xxdmaths@ Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 g-exoo@ Stanislaw P. Radziszowski Department of Computer Science Rochester Institute of Technology Rochester NY 14623 spr@ Submitted Apr 5 2004 Accepted May 19 2004 Published Jun 4 2004 MR Subject Classification 05C55 Abstract This paper studies lower bounds for classical multicolor Ramsey numbers first by giving a short overview of past results and then by presenting several general constructions establishing new lower bounds for many diagonal and off-diagonal multicolor Ramsey numbers. In particular we improve several lower bounds for Rk 4 and Rk 5 for some small k including 415 R3 5 634 R4 4 2721 R4 5 3416 R5 4 and 26082 R5 5 . Most of the new lower bounds are consequences of general constructions. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R35 1 1 Introduction and Notation In this paper we study undirected loopless graphs and edge-colorings where technically an edge joining u and v is a set u v . Often however we will denote the same edge by u v or equivalently by v u . A k1 k2 . kr -coloring r kị 1 is an assignment of one of r colors to each edge in a complete graph such that it does not contain any monochromatic complete subgraph Kki in color i for 1 i r. Similarly a k1 k2 . kr n -coloring is a k1 . kr -coloring of the complete graph on n vertices Kn. Let R k1 . kr and R k1 . kr n denote the set of all k1 . kr - and k1 . kr n -colorings respectively. The Ramsey number R k1 . kr is defined to be the least n 0 such that R k1 . kr n is empty. In the diagonal case k1 . kr m we will use simpler notation Rr m and Rr m n for sets of colorings and Rr m for the Ramsey numbers. In the case of 2 colors r 2 we deal with