Some New Ramsey-type Results In Graph Theory

Ramsey theory has been a research focus in combinatorics. It refers to the study of partitions of large structures, which indicates that complete disorder is impossible. There are four independent roots of Ramsey theory. In 1892, to study the irreducibili-ty of rational functions with integral coefficients, D. Hilbert proved the Hilbert’s cube lemma:If the positive integers are finitely colored, then one color class contains affine cubes of arbitrary length. In 1916, to reprove a theorem on a modular version of Fer-mat’s conjecture, I. Schur obtained the following lemma:If the positive integers are finitely colored, then one color class contains x, y, z with x+y=z. In 1927, B.L. van der Waerden showed, if the positive integers are finitely colored, then one color class contains arithmetic progressions of arbitrary length. In 1930, to study the de-cision procedure for propositional logic, F.P. Ramsey proved that, if a graph contains sufficiently many vertices (dependent on k), then it must contain either a complete set or an independent set of vertices of size k.The main mathematical idea of Ramsey theory is this:no matter how large and elaborate a system S is, and how large a positive integer k is, we can choose a large enough super system Q containing S, so that no matter how Q is colored in k colors, Q contains a monochromatic copy of S. The ideas and techniques of Ramsey theory have been widely used in a broad range of mathematical areas, including set theory, combinatorial number theory, geometry, logic, probability theory and even theoretical computer science. The researchers include Wolf Prize winners P. Erdos, L. Lovasz,-Fields Prize winners T. Gowers, T. Tao, Abel Prize winner E. Szemeredi and so on. The book Ramsey Theory written by R.L. Graham, B.L. Rothschild and J.H. Spencer is a classic monograph in this field.Generalized Ramsey numbers is a significant branch in Ramsey theory. Given two graphs F and H, the (generalized) Ramsey number R(F, H) is the smallest integer N such that, for any graph G of order N, G contains F as a subgraph, or the complement of G contains H as a subgraph. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey theory. The subject has grown amazingly with regard to asymptotic bounds for various types of Ramsey numbers. In the last three decades, considerable progress has also been obtained on evaluating the exact numbers. The thesis aims at promoting the calculation of some exact values of Ramsey numbers.The thesis consists of six chapters with new results in wheel-wheel Ramsey num-bers, cycle-wheel Ramsey numbers, tree-fan Ramsey numbers, star-wheel Ramsey numbers, star-critical Ramsey numbers and induced Ramsey numbers, respectively. The latter two are not general Ramsey numbers but some variations. People study dif-ferent types of variations of Ramsey numbers, in order to characterize the property of Ramsey numbers deeply and obtain some more meaningful results.1. Wheel-wheel Ramsey numbersThere are only six known values of Ramsey numbers for wheels, which are R(Wn, Wm) for 3≤m≤n≤5. And the calculation of four of them need the help of computers. The six values are as follows.We extend the known values to infinity. The main theorem is as below.Theorem 1.2. Cycle-wheel Ramsey numbersThe research of Ramsey numbers for cycles versus wheels is meaningful and has a prospective future to be fully solved. Let Cm denote a cycle of order m and Wn a wheel of order n+1. We achieve considerable progresses on R(Wn, Cm), which is as follows.Theorem 2. R(Wn, Cm)= 2n+1 for m odd, n≥3(m-1)/2 and (m, n)≠ (3,3), (3,4).Theorem 3.R(Wn, Cm)= 3m-2 for m, n odd and m< n< 3(m-1)/2.Theorem 4. R(Wn, Cm)= 3m-2 for n odd, m even and m<n< 3m/2.The above results narrow the gap on cycle-wheel Ramsey numbers, and offer tools for other Ramsey numbers involving cycles and wheels.3. Tree-fan Ramsey numbersFor Ramsey numbers involving an arbitrary tree Tn, there are only a few results. We show that Tn is Fm-good for positive integers n≥3m2-2m-1, that is, Theorem 5. R(Tn, Fm)= 2n-1 for all integers n≥3m2-2m-1.4. Star-wheel Ramsey numbersA star and a wheel of order n+1 are denoted by K1,n and Wn, respectively. Several papers have been published on star-wheel Ramsey numbers, leaving R(Wm, K1,n) with even m and 10≤m≤ n+1 as the only open case. We will partially solve this open case by using Erdos-Simonovits Stability Theorem.The Stability Theorem says that, for every ε> 0 and forbidden subgraph class (?) there is a δ> 0, and no such that if n> no and G is an n-vertex, (?)-free graph with e(G)≥(1 - 1/p) (2n) - δn2, then one can change (add and delete) at most εn2 edges of G and obtain a complete p-partite graph. Using this theorem as a lemma, we have the following result.Theorem 6. For fixed even m≥6 and sufficiently large n, R(Wm, K1,n)= 2n+ m/2 - μ, where μ= 1 if both m/2 and n are even, and μ= 0 otherwise.5. Star-critical Ramsey numbersHook and Isaak introduced the definition of the star-critical Ramsey number. Let Kr-1 (?) K1,k denote the graph obtained from Kr-1 and an additional vertex v by joining v to k vertices of Kr-1. The star-critical Ramsey number r*(G1, G2) is the small integer k such that, for any red-blue edge coloring of Kr-1 (?) K1,k, there is a red G1 or a blue G2, where r denotes the Ramsey number R(G1, G2).Before that,Erdos and Faudree considered two related defintion:the upper and lower size Ramsey humber. The upper size Ramsey humber u(G1,G2)is the smallest integer q such that for an arbitrary graph G with G(?)K and e(G)≥q and for any red_blue edge colorying of G,there is a red G1 or a blue G2,where r denotes the Ramsey number R(G1,G2).The lower size Ramsey number l(G1,G2)is the smallest integer p such that there exists a graph G with G(?)K and at least p edges,for any red-blue edge coloring of G,there is a red G1 or a blue G2,where r denotes the Ramsey number R(G1,G2).We study the relations of these definitions.We notice that there are two subclasses of star-critical Ramsey numbers:if r*(G1,G2)=R(G1,G2)一1,we say the graph pair (G1,G2)is Ramsey-full;if r*(G1,G2)and R(G1,G2)can be connected via Ramsey goodness,we have the definition size Ramey goodness.Let G2 be a connected graph with at least two vertices which is G1-good.Let V1,V2,…,Vχ(G1)be the Color classes of G1 ander a proper vertex coloring usingχ(G1)colors and assume that |V1|≤|V2|≤ …≤|Vχ(G1)|.choose a vertex coloring such that |V1| is as small as possible,and letσ(G1)denote this |V1|.Under all proper vertex colorings with |V1|=σ(G1),let τ.(G1):min{|E(v,Vi)||v∈V1,2≤i≤χ(G1)},which is the minimum degree of some vertex of V1 in Vi for some 2≤i≤χ(G1).Ifσ(G1)=1,or σ(G2)=1,or κ(G2)≥2,then we have r*(G1,G2)≥(χ(G1)一2)(|V(G2)|-1)+σ(G1)+δ(G2)+ T(G1)-2.If equality holds,then G2 is called G1-size good. We also have the following two theorems.Theorem 7.Given two integers k,l≥3,if m and nare large,then r*(mKk,nKl)-(k-1)m+(l-1)n+max{m,n)+R(Kk-1,Kl-1)-3Theorem 8.For m odd,n>m≥3,u(Cn,Cm)=2(n-1)2+2. For m odd,n≥m≥3 and(m,n)≠(3,3),r*(Cn,Cm)=n+1.6.Induced Ramsey humbersFor graphs G1 and G2,the induced Ramsey humberIR(G1,G2)is the smallest integer N such that,there exists a graph G of order N with the property that,for any red-blue edge coloring of G,either G contains G1 as an induced subgraph all of whose edges are red,or G contains G2 as an induced subgraph all of whose edges are blue. We study the exact values of the induced Ramsey humbers involving matchings,stars, complete graphs,complete multipartite graphs,quadrilateral,and so on.We have the following five theorems.Theorem9.For n1≥n2≥…≥nl≥2,we have,IR(kK2,Kn1∪Kn2∪…∪Knl)= kn1+n2+…+nl.Theorem 10.IR(kK2,Kn-e)=kn for odd n≥3,or for k=1,2,3 and even n≥4.Theorem 11.IR(2Km,Kn)=2R(Km,Kn)for m,n≥2.Theorem 12.IR(K1,k,Kn-1+lK1)=(k-1)n(n-1)/2+n+l-1 for k≥l+1 and n≥2.Theorem 13.IR(C4,K1,k)≤min{「3t/2+k/t+k+1/2(?)|t∈{(?),(?)+ 1}},and equality holds for 1≤k≤5.