Multicolor Ramsey Numbers For Cycles And Some Sparse Graphs

Ramsey’s theorem dates back to the early 1930’s,was proved by the British mathemati-cian and philosopher F.P.Ramsey,and still intrigues many who study combinatorics and graph theory today.Ramsey theorem studies the existence of a given substruc-ture in a sufficiently large structure,and it makes the profound assertion that complete disorder is impossible.The ideas and techniques of Ramsey theory have been widely used outside of graph theory,including algebra,set theory,information,logic,prob-ability theory and computer science.Ramsey theory has attracted numerous leading researchers,such as N.Alon,P.Erdos,R.L.Graham and J.H.Spencer.The subject has growing amazingly.Problems in Ramsey theory have been studied extensively,not only on the improvements of asymptotic bounds about various types of Ramsey numbers,but also on determining the exact values of Ramsey type numbers of some graphs.Structural methods,probabilistic methods and algorithmic methods are effi-cient methods to tackle problems in Ramsey theory.The role of Ramsey numbers is to quantify some of the general existential theo-rems in Ramsey theory.For given graphs H1,H2,...,Hk,k≥2,the k-color Ram-sey number,denoted by R(H1,H2,...,Hk),is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors,then it al-ways contains a monochromatic copy of Hi colored with i,for some 1 ≤i≤k.The value of R(H1,H2,...,Hk)is fixed under permutations of the k arguments.If H=H1=H2=…=Hk,we simply write R(H1,H2,…,Hk):=Rk(H).A complete graph of order R(H1,H2,…,Hk)-1 and with a k-edge-coloring is called a(H1,H2,…,Hk)-Ramsey graph if it contains no monochromatic copy of Hi colored with i,for any 1≤i≤k.Let Cl and Pl be a cycle and path of order l,respectively.And K1,l and Wl denote a star and a wheel of order k+1,respectively.In this thesis,we will focus on some multicolor Ramsey numbers concerning cycles,paths,stars and wheels.In chapter 1,we will introduce some useful basic concepts and notations,and then give a relatively complete introduction to the background and known results of the researches in this thesis.In chapters 2-6 include our new results in three color Ramsey numbers concern C4,Gallai-Ramsey numbers of some graphs and some Ramsey numbers in hypergraph,respectively.Gallai-Ramsey number and Ramsey number in hypergraphs are the vari-ations of Ramsey numbers.The former changed in the coloring,and the later in the graph classes.People study different types of variations of Ramsey numbers,in order to characterize the property of some graphs deeply,so that Ramsey theory can be used more widely.1.Ramsey Numbers R(C4,K1,m,Pn)In 1975,Parsons[Transactions American Mathematical Society,209(1975)33-44]established a tight upper bound of R(C4,K1,n)as follow.Theorem A.(?)for all m≥2,and if m=l2+1 and l≥1,then(?).Due to the extreme difficulty in constructing(C4,K1,m)-Ramsey graph,the known exact values of R(C4,K1,m)are very few,and the known Ramsey graphs are construct based on the subgraphs of the polarity graph Gq and some local structures of the po-larity graph Gq.Based on the interest in the structure of polarity graph Gq and the revelation of Theorem A,we first establish an upper bound of R(C4,K1,m,Pn),the obtain of the upper bound is due to an improvement of the Turan number of C4.Theorem 1.(?)for all m,n≥2,and if m+n=l2+3 and l≥1,then(?)Taking n=2 in Theorem 1,we can obtain Theorem A.So,Theorem 1 is a generalization of Theorem A.Then,by further analysis of the polarity graph Gq,we can partition the vertices of Gq graph,and thus construct some(C4,K1,m,Pn)-Ramsey graphs.That is we obtain some exact values of R((C4,K1,m,Pn),which shows that the upper bounds given in Theorem 1 are tight.We obtain the following theorems.Theorem 2.Let q be a prime power.If q≡0(mod t)or q+1≡0(mod t),then R(C4,K1,q2-t+1,Pt+1)=q2+q+1,with the possible exception t=q+1 and q is odd.Theorem 3.Let q be a prime power.If q+1≡0(mod t),then R(C4,K1,q2-t+1,Pt+1)=q2+q+2,except possibly t=q+1.Theorem 4.Let q be aprime power,q=0(mod t)and t≠q.If 1≤s≤[q+1/2]and s≠2[q/4]-1,then(?).Theorem 5.R(C4,K1,q2-t+1,Pt+1)=q2 if q is an even prime power and q-1≡0(mod t).Combining Theorems 2 and 3 and then taking t=1,we have the Parsons’ result[Transactions American Mathematical Society,209(1975)33-44]:Theorem B.R(C4,K1,q2-t+1,Pt+1)=q2+q+1 for any prime power q.Furthermore,taking t=1 in Theorems 4 and 5,we have the following result in which the case for q being odd is due to Zhang,Chen and Edwin Cheng[Discrete Mathematics,340(2017)655-660]and even due to Parsons[Aequationes Mathemati-cae,14(1976)167-189].Theorem C.Let q be a prime power.If q is odd 1≤s≤[q/4]and s≠2[q/4]-1or q is even,1≤s≤[q/2]and s=q+1,then R(C4,K1,q2-s=q2+q-(s-1)..2.Gallai-Ramsey Numbers GRk(Cl)A Gallai coloring of a complete graph is an edge-coloring such that no rainbow triangle(a triangle that all its edges colored differently).A Gallai k-coloring is a Gallai coloring that uses at most k colors.Given an integer k≥1 and graphs H1,...,Hk,the Gallai-Ramsey number GR(H1,...,Hk)is the least integer N such that every Gallai k-coloring of KN contains a monochromatic copy of Hi in color i for some i∈{2,....k}.When H=H1=…=Hk,we simply write GRk(H).Clearly,Gallai-coloring is a special edge coloring,thus GRk(H)≤Rk(H)for all k≥1.For the Ramsey numbers of odd cycles,Bondy and Erdos[Journal of Combina-torial Theory,Series B,14(1973)46-54]conjecture that Rk(C2n+1)=n·2k+1 for all k≥1 and n≥2.Day and Johnson[Journal of Combinatorial Theory,Series B,124(2017)56-63]proved that the conjecture is false for fixed n and k sufficient-ly large by constructing a counterexample.But recently,Jenssen and Skokan[arX-iv:1608.05705.]proved it’s true for all fixed k and all n sufficiently large by using regularity method.In Chapter 3,we will study the Gallai-Ramsey numbers of cycles.We proved that the aforementioned conjecture of Bondy and Erdos holds for all k≥ 1 and all n≥2 under Gallai colorings.We have the following theorem.Theorem 6.For all k≥1 and n≥2,GRk(C2n+1)=n·2k+1.In fact,the Gallai-Ramsey numbers of cycles has been studied by many scholars,some upper and lower bounds also have been established,but all the results are obtained by consider even and odd cycles separately.We found that if we apply the result of even cycles to the prove of odd cycles,the known bound of odd cycles can be improved greatly.With this idea,in order to determine the Gallai-Ramsey numbers of odd cycles,we first made some improvement of the Gallai-Ramsey numbers of even cycles,and found that we can prove the exact values of the Gallai-Ramsey numbers of odd cycles by using the improved bound[arXiv:1809.00227].After consider the Ramsey numbers of odd cycles,we are still curious about even cycles.But multicolor Ramsey numbers for even cycles behave rather differently with odd cycles,because even cycle is bipartite whereas odd cycle is not.And it seems more difficult to study the multicolor Ramsey numbers for even cycles.We known that for all k≥2 and n≥2,Rk(C2n)≥(n-1)k+n+k-1.But little is known about the behavior of Rk(C2n)in general except the lower bound.By using structural analysis,we obtain some existence conditions of cycles and paths in bipartite graph,which enabled us to determine the multicolor Ramsey numbers of all even cycles under Gallai colorings.This result also make the proof of Gallai-Ramsey numbers of odd cycles more simpler in Chapter 3.Theorem 7.For all k≥ 2 and n≥2,#12Note that the Gallai-Ramsey numbers GRk(C2n)in Theorem 7 is strictly less than the values of Rk(C2n).Moreover,it can be easy to obtain the Gallai-Ramsey numbers of path from the Gallai-Ramsey numbers of even cycles.Now that we determined all the exact Gallai-Ramsey numbers of all cycles and paths.3.Gallai-Ramsey Numbers GRk(W2n)In Chapter 4,we focus on the Ramsey numbers of wheels.For 2-color case,we only known that R2(W3)=18,R2(W4)=15 and R2(W5)=17,and nothing is known for multicolor case.Here we studied the Gallai-Ramsey numbers of even wheels.We first construct a general lower bound for all even wheels:Proposition 1.For all n≥ 2 and k≥2,Then we establishes the exact value of GRk(W4)for all k≥ 2,which is equal to the lower bound given in Proposition 1.Theorem 8.For all k≥2,4.Gallai-Ramsey Numbers GR(t1K3,t2K3,...,tkK3)Only few results are known about the Ramsey numbers of complete graph.K3 is the least nontrivial complete graph,thus the Ramsey number involving K3 has been studied by many scholars.Burr,Erdos and Spencer[Transactions American Math-ematical Society,209(1975)87-99]studied two color Ramsey numbers for multiple disjoint copies of K3,they proved that R(mK3,nK3)=3m+2n for all m≥n≥2.In Chapter 5,we general this study to Gallai-colorings.We consider the Gallai-Ramsey numbers of disjoint copies of K3,and establish an upper and lower bound for GR(t1K3,t2K3,...,tkK3):Theorem 9.For all integers k≥2 and t1≥t2≥…≥tk≥1,andNote that,when k is odd and tk-1=tk=1,the lower bound is equal to the upper bound in Theorem 9,that is we can obtain the exact value of GR(t1K3,...,tkK3)at these cases.Moreover,we give the values of GR(t1K3,...,tkK3)for all 2≥t1≥t2≥…≥tk≥1 and k≥ 2.In the following theorem,we use GRk(s;k-s)to denote GR(t1K3,...,lkK3)when l1=…=ls=2 and ts-1=…=tk=1.Theorem 10.Let k≥2 and k≥s≥0 be integers.If k is even,GRk(s,k-s)=5k/2+2s+1.If k is odd(?)5.Ramsey Numbers R(Pm3,Sn2)A hypergraph H is a pair(V,E),where V is a set of vertices and E a family of subsets of V,called hyperedges or simply edges.The hypergraph H is said to be r-uniform if each edge of H is a k-set.For two r-uniform hypergraphs H and G,the Ramsey number R(H,G)is the smallest number N such that each red-blue coloring of the edges of the complete r-uniform hypergraph knr contains either a red copy of H or a blue copy of G.We denote the r-uniform loose path,loose cycle and star with l edges by Plr,Clr and Slr,respectively.The 2-color Ramsey number of 3-uniform loose path and loose cycle has been studied by several researchers,and complete determined by Omidi and Shahsiah[Journal of Combinatorial Theory,Series A,121(2014)64-73].Motivated by their method and the path-star Ramsey numbers,we study the Ramsey numbers for 3-uniform loose path versus star in Chapter 6 and give the following theorem:Theorem 11.For every n≥2m≥2,R(Pm3,Sn3)=2m+1+[m-1/2],and for every m≥[9/4n]≥2.R(Pm3,Sn3)=2m+1.