tailieunhanh - Báo cáo toán học: " New Lower Bounds for Some Multicolored 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: New Lower Bounds for Some Multicolored Ramsey Numbers. | New Lower Bounds for Some Multicolored Ramsey Numbers Aaron Robertson1 Department of Mathematics Temple University Philadelphia PA 19122 email aaron@ Submitted October 26 1998 Accepted November 15 1998 Classihcation 05D10 05D05 Abstract In this article we use two different methods to find new lower bounds for some multicolored Ramsey numbers. In the first part we use the finite field method used by Greenwood and Gleason GG to show that R 5 5 5 242 and R 6 6 6 692. In the second part we extend Fan Chung s result in C to show that R 3 3 3 k1 k2 . kr 3R 3 3 k1 k2 . kr R k1 k2 . kr 3 holds for any natural number r and for any ki 3 i 1 2 . r. This general result along with known results imply the following nontrivial bounds R 3 3 3 4 91 R 3 3 3 5 137 R 3 3 3 6 165 R 3 3 3 7 220 R 3 3 3 9 336 and R 3 3 3 11 422. Introduction This paper is presented in two part which can be read independently of each other. Part one uses finite fields and Part two extends an argument by Fan Chung. Part one of this article is accompanied by the Maple package RES available for download at the author s website. Recall that N R k1 k2 . kr is the minimal integer with the following property Ramsey Property If we r-color the edges of the complete graph on N vertices then there exists j 1 j r such that a monochromatic j-colored complete graph on kj vertices is a subgraph of the r-colored KN. 1 webpage aaron This paper is part of the author s . thesis under the direction of Doron Zeilberger. This paper was supported in part by the NSF under the PI-ship of Doron Zeilberger. THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R3 2 Part One The Finite Field Method In this first part we add two more lower bounds to Radziszowski s Dynamic Survey R on the subject. We show by using the finite field technique in GG that R 5 5 5 242 and R 6 6 6 692. The previous best lower bound for R 5 5 5 was 169 given by Song S who more generally shows that R 5 5 . 5 4 r-1 1 r .