Classical Ramsey Theory And Its Applications

The lower bounds for classical Ramsey numbers are studied with new constructive methods. In the bicolor case, this problem is turned into the problem of looking for isomorphic induced subgraphs of two given graphs satisfying some properties. Then the constructive method is generalized to the multicolor case. Our result improves the commonly used inequality r(k,p + q -1)≥r(k, p) + r(k,q)-1. In multicolor case, by constructing composition of two graphs, Abbott got some inequalities about the lower bounds for multicolor diagonal Ramsey numbers, among which most inequalities were generalized to the off-diagonal case by Song Enmin later. In chapter 3, we improve the results of Abbott and Song Enmin with some new constructive methods.By using the theorems proved, we get many lower bounds for Ramsey numbers, all of which are better than the best results in the early references. They are r(4,13) > 133 ,r(4,14) ≥ 141, r(4,15) ≥ 153,r(6,7) ≥ 111,r(6,11) ≥ 253, r5(4) ≥ 2328, r4(6) ≥ 10507, r4(7) ≥ 42407 , r(3,3,10) ≥ 141,r(3,3,11) ≥ 157,r(3,3,3, 11) ≥ 561,r4(5) ≥ 2550,r5(5) ≥ 26082 etc.In chapter 4 we study the bound of rn (3), which is important in the research of the Shannon capacity of communication channel. The Shannon capacities of the complements of odd cycles are discussed. We prove that every(k, l) Ramsey graph is connected, if k is an integer and k≥3. The connectivity of (k, l) Ramsey graph is also discussed.