Construction And Random Graphs On Ramsey Theory

Ramsey theory is an important branch of combinatorics mathematics, and graph Ramsey number is a main branch of Ramsey theory.Ramsey theory is widely applied in various areas, such as number theory, finite field, topology, information theory and computer information searches. These fields reveal that there must be a given structure in a larger structure from these fields. It's NP-hard for Determining Ramsey numbers, and there are few exact values of Ramsey numbers known by us until now. Going with computer science, the application of computer in Ramsey theory makes graph Ramsey number more active. Combining mathematical method with computer constructive proof, the three color Ramsey numbers R ( P_m,C_n,C_l ), Lovász- Ramsey numbers, multigraph Ramsey numbers and multigraph Folkman numbers are researched as follows:1. An algrothim for computing the upper bounds of three color Ramsey numbers R ( P_m,C_n,C_l ) is given, and the lower bounds of R ( P_m,C_n,C_l ) is investigated by the simulated annealing algorithm. With the computer constructive proof and mathematical proof, some small Ramsey numbers for path and cycles in some mixed cases are obtained in this dessertation.2. Lovász-Ramsey numbers is defined, and the relations between Lovász-Ramsey numbers and classic Ramsey numbers are discussed; Some results of classic Ramsey numbers are extended to Lovász-Ramsey numbers, and some small Lovász-Ramsey numbers are obtained by the algrothim and theory proof.3. Some inequalities on multigraph Ramsey numbers are given by the constructive method and set-coloring theory; the theory of random graphs is extended to multigraphs, with this efficient method, the lower bounds of multigraph Ramsey numbers are improved, and some lower parameter bounds are given; finally, an upper bound of multigraph Ramsey numbers is proved by inductive principle.4. Set-coloring's vertex Folkman numbers of simple graph and multigraph edge Folkman numbers are defined; we discuss the relations between multigraph edge Folkman numbers with simple graph edge Folkman numbers, and that between Set-coloring's vertex Folkman numbers and simple graph vertex Folkman numbers; F_e⁽²⁾ (3,3,3;4) = 11 is proved by studying the edges coloring of graph.