Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Some New Ramsey Colorings"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Some New Ramsey Colorings. | Some New Ramsey Colorings Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 ge@fred.indstate.edu Submitted April 19 1998 Accepted May 14 1998. Abstract New lower bounds for 15 classical Ramsey numbers are established. Several of the colorings are found using a new variation of local search heuristics. Several others are found using known colorings as building blocks. AMS Subject Classifications 05D10 05D04 Introduction In this note several lower bounds for classical Ramsey numbers are improved using two different methods. First we use a new synthesis of simulated annealing and tabu search to establish several new bounds. Then some constructions that use smaller constructions as building blocks are described. In total we improve 13 entries in Radziszowski s table of two-color classical Ramsey numbers 5 and also add two entries to his list of classical multicolor bounds. A Simple Search Algorithm The algorithm is outlined in the context of minimizing an integer function of binary boolean variables. Let f f x1 . xk be such a function. Three important data structures are required a current solution vector a history list and a temperature. The current solution vector is denoted by V x1 . xk . In addition V will denote to the vector obtained from V by changing bit i i.e. Vi x1 . xi-1 1 xi xi 1 . xk . As the algorithm proceeds the current solution vector is repeatedly changed. Each time it is changed the old vector is saved in a history list H of previous solution vectors. This is an essential idea from tabu search 1 . The algorithm also has a notion of temperature as in simulated annealing. In this case the temperature T is a positive integer which restricts the range of choices the algorithm has for changing V . During each iteration we compute di f Vi f V for 1 i k. From the set di the T smallest values are collected and from these one is chosen randomly. The corresponding change is then incorporated into the new