| There are many interesting applications of Ramsey theory in mathematics, computer science, information theory, finance and economics. Relations of Ramsey-type theorems to various fields in computer science, such as logic, complexity, parallel computation, approximation algorithms, computational geometry, are well documented in research papers and books.Extremal graph theory is an important part of graph theory, it is founded on the basis of Turan problem. Its main focus is on the maximum number edges in graphs without some given forbidden graphs. Given a set of graphs y/={H1, H2,.... Hm}, the Turan number ex(n;ψy) is the maximum size of a graph of order n which does not contain any subgraph Hi{1≤i≤m), and EX(n;ψ) denotes the set of such graphs of size ex(n; ψ). Since the number of edges of each monochromatic subgraph is no more than its extremal value, this theory can help to determine the upper bounds on some multicolor Ramsey numbers.Ramsey properties of random graphs have been investigated extensively for a long time. Although the classical Ramsey results do not involve explicitly random structures, the proofs are often based on the use of probabilistic techniques. The theory of random graphs was founded by Erdos and Renyi who discovered that probabilistic methods were often useful in attacking extremal problems in graph theory. One of the aims of such investigations is to find sharp thresholds for various Ramsey properties that a random graph may satisfy.By the methods combining computer construction and mathematical proofs, the Ramsey numbers involving cycles, corresponding extremal graph problems and asymmetric online Ramsey games involving cycles are studied in this dissertation. The main results are as follows:Bipartite Ramsey numbers6(C2m; C2n). By designing new2-coloring methods of type (C2m, C2n) for complete bipartite graphs Km+n,m+n-2and K2m-1,2m-1, the lower bounds on b(C2m; C2n) are obtained. Then the upper bounds on b(C2m;C2n) are proved by induction. Utilizing the induction hypothesis, there exist at least one C2m-2in the subgraph whose edges are in the first color. By analyzing the adjacency between the C2m-2and the four vertices which are not on the C2m-2, the result that b(C2m;K2,2)=m+1 for m≥4is proved. The proof for b(C2m;C6) is similar to that of b(C2m;K2,2). however it is much more difficult than the former. By constructing the proof of eight subcases, the result b(C2m; C6)=m+2for m≥4is obtained.The four color Ramsey numbers R(C6,H1,H2, H3), where H1, H2and H3are C4or C6. First, by constructing the4-coloring of K17and K18avoiding forbidden subgraphs, the lower bounds on(C6,H1,H2, H3) are obtained, and then using Turan numbers ex(n;{C4})and ex(n;{C6}) for n=19and20, the results of R(C6, C4, C4, C4)=19and R(C6, C6, C4, C4)≤20are obtained. In order to prove the upper bounds on R4(C6) and R(C6,C6, C6, C4), the concept of good bijection between the vertex sets of two graphs is introduced. Using the properties of the only two graphs in EX(20;{C6}), we prove that there is no such good bijection, which shows that they cannot be joined, and thus we obtain R4(C6)<20and R(C6,C6,C6, C4)≤20. Moreover, the algorithms for joining graphs and coloring edges are designed, and then the upper bounds on R(C6, C6, H1, H2) are further improved by computations. Finally, the following results are obtained:R(C6, C4,C4,C4)=19,18≤R(C6, C6, C4, C4)≤19,18<R(C6, C6, C6, C4)≤19and18≤R4(C6)≤19.Turan numbers involving cycles. A distributed algorithm based on MapReduce for constructing extremal graphs is designed. By mapping the key-value pairs properly, dividing the datasets evenly and avoiding reading and writing operations frequently, the efficiency of the algorithm is substantially improved. Using this algorithm, all the graphs in EX(n;{C6}) for n≤28were constructed. The results of experiments show that the average efficiency of the distributed algorithm is75.48%. Secondly, by extending the edges of some base graphs, a method for constructing larger graphs not containing C2k is designed and the new lower bounds on ex(n;{C2k}) are obtained. Finally, the extremal graphs of girth9, or EX(n;{C3, C4,..., C8}), are studied. Based on the three graphs of girth no less than9, the lower bounds on ex(n;{C3, C4,...,C8}) for n≤57are obtained. By studying the structures of the extremal graphs of girth9, the relationship between the neighborhood of the vertices in Dk (the set of all vertices with degree k) and the maximum degree is obtained. Utilizing this relationship, the graphs in EX(n;{C3, C4,...,C8}) for n=13,16,18,22,26are obtained, and using these graphs, the exact values of ex(n;{C3, C4,...,Cg}) are derived for23≤n≤30.The asymmetric online Ramsey games involving cycles. By a greedy strategy we first obtain the stop condition for an online Ramsey game, that is, when a dangerous graph Fr appears. Then, we prove that the special graph (Fr)*has the minimum density among the dangerous graphs, namely d(Fr)≥d(F)*. To prove this property, the case for two colors is studied first. By analyzing the merging of the outer edges and vertices of graph F2, the trend of density variation is obtained when F2is transformed to (F2)*, and then we prove that d{F2)≥d{F2)’. In order to generalize this approach to r colors, the edges of Fr are partitioned into r layers, then the change of vertices and edges in each layer and its effect on the density of the dangerous graph are studied, and the result that d(Fr)≥d(Fr) is proved. Finally, the lower bound on the threshold function No(S, r, n) for symmetric online Ramsey game involving cycles is obtained by the probabilistic method, for S={Ck1, Ck2,..., Ckr}, k1≥k2≥...≥kr. |
PDF Full Text Request