tailieunhanh - Báo cáo toán học: "A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K3"

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: A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K3. | A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K3 Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 ge@judy. Submitted September 13 1994 Accepted September 18 1994 Abstract For k 5 we establish new lower bounds on the Schur numbers S k and on the k-color Ramsey numbers of K3. For integers m and n let m n denote the set i I m i n . A set S of integers is called sum-free if i j 2 S implies i j 2 S where we allow i j. The Schur function S k is defined for all positive integers as the maximum n such that 1 n can be partitioned into k sum-free sets. The k-color Ramsey number of the complete graph Kn often denoted Rk n is defined to be the smallest integer t such that in any k-coloring of the edges of Kt there is a complete subgraph Kn all of whose edges have the same color. A sum-free partition of 1 s gives rise to a K3-free edge k-coloring of Ks. by identifying the vertex set of Ks. with 0 s and by coloring the edge uv according to the set membership of u v . Hence Rk 3 S k 2. It is known that S 1 1 S 2 4 S 3 13 and S 4 44. The first three values are easy to verify the last one is due to L. D. Baumert 1 . The best previously published bounds for S 5 are 157 S 5 321 the lower bound was proved in 4 and the upper bound in 6 . For Ramsey numbers we know R2 3 6 and R3 3 17 the current bounds on R4 3 are 51 and 65 5 . Below we list the five sets of a sum-free partition of 1 160 Since the partition is symmetric i and 161 i always belong to the same set only the integers from 1 to 80 are listed. 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 1 1994 R8 2 Set 1 4 5 15 16 22 28 29 39 40 41 42 48 49 59 Set 2 2 3 8 14 19 20 24 25 36 46 47 51 62 73 Set 3 7 9 11 12 13 17 27 31 32 33 35 37 53 56 57 61 79 Set 4 1 6 10 18 21 23 26 30 34 38 43 45 50 54 65 74 Set 5 44 52 55 58 60 63 64 66 67 68 69 70 71 72 75 76 77 78 80 This proves that S 5 160. It follows that R5 3 162. From 1 and 2 we have S k c 321 k 5