Construction And Computation On Graphs In Ramsey Theory

Ramsey theory is an important branch of combinatorics mathematics which is widely applied in various areas such as mathematics and computer science.Recently,Ramsey theory has been developed rapidly.Ramsey number,Ramsey multiplicity and Folkman number are the key subjects in Ramsey theory,where edge Folkman number is a natural generalization of classic Ramsey number.Until now,there are few exact values of Ramsey numbers, Ramsey multiplicities and Folkman number are determined.Combining the computer constructive proof with mathematical proof,three subject as the small classic Ramsey numbers, Ramsey multiplicities,and Folkman numbers are researched,and the detailed contents are as follows(1) The properties of the Ramsey graphs are helpful to give the lower bounds for Ramsey numbers.In order to investigate this,we checked all the possible such graphs and concluded that there is no such graphs.On the other hand,we investigated the relationship between Ramsey graphs and quasi-regular graphs,which gives some encouragement to look for new(5,5;42)-graphs;By computer searches,we obtained the new lower bounds of R(6,8),R(7,9) and R(8,17),which are 129,235 and 937 respectively.(2) It is well known that it is difficult to determine the exact values of the Ramsey numbers such as R(C_m,B_n),R(K_m,n,K_p,q) and R(B_m,B_n).In this thesis,Ramsey numbers R(C_m,B_n),R(K_m,n,K_p,q),R(B₂,B₃) and R(B₃,B₄) are obtained.By regular graphs, we obtained new lower bounds for R(K_2,5,K_2,9),R(K_2,6,K_2,9) and R(K_2,7,K_2,9),which match the exact values of them.(3) Of the 3-color Ramsey numbers,the Ramsey numbers on paths,cycles and their mixed cases were investigated comparatively widely.Combining the computer constructive proof with mathematical proof,we obtained new small Ramsey numbers for path and cycles in some mixed cases and determined the values of R(P₄,P₅,C_k) and R(P₄,P₆,C_k) for some k.(4) It is proved that R(C₄,K₉)≤32,R(C₄,K₁₀)≤39 and gave new bounds for some multicolor Ramsey number involving quadrilateral.(5) The Ramsey multiplicity M(G) of a graph G is defined as the smallest number of copies of G in any two-coloring of edges of K_R(G,G).The determination of the exact values of Ramsey multiplicity of a graph is also a very hard problem.With the help of computer algorithms,we obtain 17 exact values and 5 upper bounds of Ramsey multiplicity for isolate-free graphs with five vertices.(6) With the help of computer,new upper bounds are improved as follows. F_v(3,5;6)≤16,F_v(3,6;7)≤18,F_v(3,7;8)≤22 and F_v(3,8;9)≤23.Based on these upper bounds,a new recurrent inequality on F_v(3,k;k+1) is given.With an efficient algorithm,the lower bounds for F_v(4,4;5) is improved from 16 to 17.In addition,the upper bound for F_v(4,4;5) is improved from 25 to 23 and it is proved that F_v(k,k;k+1)≥4k-1 for k≥4 and F_e(3,4;5)≥22.(7) The Ramsey numbers for multigraph are introduced and research systematically,in which many important results for classic Ramsey numbers are generalized.