Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Constructive Lower Bounds on Classical Multicolor Ramsey Numbers"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 P.R. China xxdmaths@sina.com Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 g-exoo@indstate.edu Stanislaw P. Radziszowski Department of Computer Science Rochester Institute of Technology Rochester NY 14623 spr@cs.rit.edu 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