Some Multicolor Ramsey Numbers Concerning 4-cycles

Ramsey’s theorem is a foundational result in combinatorics,it states that one will find monochromatic cliques in any edge labelling(with colours)of a sufficiently large com-plete graph.The first version of this result was proved by the British mathematician and philosopher F.P.Ramsey in 1930.This initiated the combinatorial theory now called Ramsey theory which indicates that complete disorder is impossible.Problems in Ramsey theory typically ask a question of the form:"how many elements of some structure must there be to guarantee that a particular property will hold?" Ramsey the-ory has been a research focus in combinatorial mathematics and played an important role in a plethora of mathematical developments with its branches reaching areas as varied as algebra,combinatorics,set theory,logic,probability theory and geometry.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.Ramsey Theory written by R.L.Graham,B.L.Rothschild and J.H.Spencer is a classical textbook in this field.For given graphs G1,G2,...,Ck,k ≥ 2,the k-color Ramsey number,denot-ed by R(G1,G2,...,Ck),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 always contains a monochromatic copy of Gi colored with i,for some 1 ≤i ≤ k.A complete graph of order R(G1,G2,...,Gk)-1 and with a k-edge-coloring is called a(G1,G2,...,Gk)-Ramsey graph if it contains no monochromatic copy of Ci colored with i,for any 1<i<k.For 2-color case,we can also define Ramsey numbers and Ramsey graphs in the"complement" language.Given two graphs G1 and G2,the Ramsey number R(G1,G2)is the smallest positive integer N such that,for any graph G of order N,either G1 is a subgraph of G,or G2 is a subgraph of the complement of G.A(G1,G2)-Ramsey graph is a graph G on R(G1,G2)-1 vertices such that neither G contains a copy of G1 nor the complement graph G contains a copy of G2.Let Cm be a cycle of length m,K1,n a star of order n + 1 and Wn a wheel of order n + 1.In this thesis,we focus on some multicolor Ramsey numbers concerning 4-cycles,stars and wheels.If we only consider the 2-color case,the following results have been known.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.R(C4,K1,n)≤n + 「(?)」+ 2 for all n≥2,and if n =l2+1 andl≥1,then R(C4,K1,2)≤n + 「(?)」+ 1.Moreover,in the same paper,by using the polarity graph Gq,constructed by Brown and by Erdos,Renyi and Sos independently in 1966,Parsons proved that the values of R(C4,K1,n)attain the upper bound in Theorem A when q is a prime power and n = q2 or q2 + 1.In other words,he proved the following theorem.Theorem B.R(C4,K1,q2＋1)= q2+q + 2 and R(C4,K1,q2)= q2+q+1 for any prime power q.In 1989,Burr et al.[Annals of Discrete Mathematics,41(1989),79-89]gave a lower bound of R(C4,K1,n):Theorem C.R(C4,K1,n)>n + 「(?)-6nα/2」for all sufficiently large n where α is a constant less than 11/20.In the same paper,they posed the following conjecture,for which,Erdos,one of the authors,offered $100 for a proof or disproof.Burr’s Conjecture.R(C4 K1,n)<n +(?)-c holds infinitely often,where c is an arbitrary constant.But we haven’t found some one n such that R(C4,K1,n)<n +(?)as yet.Thus,it seems that the above Burr’s Conjecture is not well found.Obviously,K1,n is a spanning subgraph of Wn and so R(C4,K1,n)≤R(C4,Wn)for all n.Observed all known values of R(C4,Wn)and R(C4,K1,n),Zhang et al.found that each pair known values are equal for all n≥6.In 2014,they proved the following theorem[Electronic Journal of Graph Theory and Applications,2(2014),110-114].Theorem D.R(C4,K1,n)=R(C4,Wn)for all n>6.Based on the interest in Burr’s Conjecture and the revelation of the above four theorems,we begin to study some Ramsey numbers concerning 4-cycles and obtain some new results on some multicolor Ramsey numbers(include 2-color case)concern-ing 4-cycles,stars and wheels.The detailed proofs of these results will be read from Chapter 2 to Chapter 5 in this thesis.1.Ramsey Numbers R(C4,K1,n)Perhaps due to the extreme difficulty encountered in finding(C4,K1,n)-Ramsey graphs,the above Burr’s Conjecture is still open and few exact values are known for R(C4,K1,n).Let q be a prime power.Besides the values of R(C4,K1,q2)and R(C4,K1,q2+1)in Theorem B,Parsons also considered the values of R(C4,K1,q2-t)where t an integer with a given range,and obtained the following theorem[Aequa-tiones Mathematicae,14(1976),167-189].Theorem E.R(C4,K1,q2-t)= q2 + q-(t-1)if q is an even prime power,1≤t≤q+1 and t ≠ q,or q is an odd prime power,0 ≤ t ≤ 2「q/4」 and t is even.It is clear that all determined values in Theorems B and E attain just the upper bound provided by Parsons in Theorem A.So we know that the main work for obtain-ing the above Ramsey numbers is to construct correspondent Ramsey graphs.Parsons showed some subgraphs of the polarity graph Gq were Ramsey graphs he needed.In Chapter 2,firstly,we will extend Theorem E for q being an odd prime pow-er and all t with 1≤t≤2「q/4」 and t ≠2「q/4」-1.Our main idea is to construct(C4,K1,q2-t)-Ramsey graphs based on some local structures of the polarity graph Gq.In particular,the(C4,K1,q2-t)-Ramsey graphs we construct for odd t are not the sub-graphs of the polarity graph Gq.One of main results in Chapter 2 is as follow.Theorem 1.Let q be an odd prime power.If 1≤t≤2「q/4」 and t ≠「q/4」-1,then R(C4,K1,q2-t)= q2+ q-(t-1).It is worth noting that these values of n,for which R(C4,K1,n)were determined,are near the square of a prime power.Since Burr’s Conjecture is still open,we wonder what is the value of R(C4,K1,n)when n is not near the square of a prime power.Of course,the more values of R(C4,K1,n)are known for distinct type of n,the more we can approach the good general lower bound of R(C4,K1,n).Motivated by this,we start to study the values of R(C4,K1,n)for other distinct type of n.By constructing a graphΓq on q2-1 vertices without C4 in the plane over Galois fields Fq and analyzing its structure,we get several classes of(C4,K1,n)-Ramsey graphs.Based on these graphs,we prove the following two theorems,that is,the other two main results of Chapter 2.Theorem 2.Let q ≥4 be an even prime power and t=1,0,-2.Then R(C4,K1,(q-1)2+t)=(q-1)2 + q + t.Theorem 3.Let q ≥ 5 be an odd prime power and t=2,4,...,2「q/4」.Then R(C4,K1,q(q-1)-t)= q2-t.It is easy to check that those Ramsey numbers R(C4,K1,n)in Theorems 1,2 and 3 are just the general upper bound n + 「(?)」+ 2 in Theorem A or one far from it.2.Three Color Ramsey Numbers R(C4,C4,K1,n)The Turan number ex(t,C4)is the maximum number of edges in any graph of order t which does not contain a copy of C4.Let q be a prime power.It is interesting that Gq is an extremal graph for the Turan number ex(q2 + q + 1,C4)and so is it for the Ramsey number R(C4,K1,q2+1).Obviously,the complete graph Kq2+q+1 contain-s an embedding of Gq.A natural question is that:what is the maximum number of edge-disjoint embeddings of Gq that the complete graph Kq2+q+1 can contain?Here,we can’t give the exact answer to this question,but we found that each complete graph Kq2+q+1 must have at least two edge-disjoint embeddings of Gq by using Singer differ-ence sets.Based on this property,we can construct a class of(C4,C4,K1,n)-Ramsey graphs elaborately.In Chapter 3,we only consider three color Ramsey numbers R(C4,C4,K1,n).Firstly,we establish an upper bound for R(C4,C4,K1,n).Theorem 4.R(C4,C4,K1,n)≤n + 「(?)」+ 3 for all n,and if n=l2-l and l≥2,then R(C4 C4,K1,n)≤n + 「(?)」 +2.The general upper bound n + 「(?)」+ 3 is also tight since it can be attained for n=5 by a result in Chapter 3,R(C4,C4,K1,s)= 13.Furthermore,we proved that the upper bound n + 「(?)」+ 2 given by Theorem 4 for n = l2-l is attained if l is a prime power.That is to say,we determine infinitely many values for Ramsey numbers R(C4,C4,K1,n)as follow.By Theorem D,the upper bound for R(C4,K1,n)in Theorem A is also an upper bound for R(C4,Wn)for n>6.A natural question is that:is the upper bound for R(C4,C4,K1,n)in Theorem 4 also an upper bound for R(C4,C4,Wn)?In Chapter 4,by focussing on the relation between the two 3-color Ramsey num-bers R(C4,C4,K1,n)and R(C4,C4,Wn),we obtain an upper bound of the 3-color Ramsey numbers R(C4,C4,Wn).4.Multicolor Ramsey Numbers R(C4,...,C4,K1,n)and R(C4,...,C4,Wn)In Chapter 5,we will generalize Theorem A,C and D,these known results on the 2-color case,to the(k + 1)-color Ramsey numbers R(C4,...,C4,K1,n)and R(C4,...,C4,Wn).Firstly,we establish an upper bound of the(k+1)-color Ramsey numbers R(C4,...,C4,K1,n):Theorem 8.If n≥1 unless R(C4,K1,1)=4,thenLet k=1,2,we obtain Theorem A and Theorem 4 respectively.Thus,Theorem 8 is a generalization of Theorem A and Theorem 4.Furthermore,for all sufficiently large n,combining the algebraic method and the probabilistic method,we obtain a complete graph of large enough order and with a(k + 1)-edge-coloring such that it contains no monochromatic copy of C4 colored with i,for any 1<i<k and no monochromatic copy of K1,n colored with k + 1.Based on these(k + 1)-edge-coloring complete graphs,we obtain a lower bound of the(k + 1)-color Ramsey numbers R(C4,...,C4,K1,n):Theorem 9.If n is sufficiently large,then R(?)where a is a constant less than 11/20.Let k=1,we obtain Theorem C.In other words,Theorem 9 is a generalization of Theorem C.Finally,we focus on the relation between the two(k + 1)-color Ramsey num-bers R(C4,...,C4,K1,n)and R(C4,...,C4,Wn).For k = 1,Theorem D states that R(C4,Wn)= R(C4,K1,n)for n>6.For any positive integer k,the two(k + 1)-color Ramsey number satisfy that R(C4,...,C4,K1,n)≤ R(C4,...,C4,Wn)since K1,n(?)Wn.Naturally,we ask a question:does there exist an integer N such that the two(k + 1)-color Ramsey numbers R(C4,...,,C4,K1,n)and R(C4,...,C4,Wn)are equal for all n ≥ N?The answer is affirmative because,with the help of Theorems 8 and 9,we prove that:Theorem 10.R((?)for all sufficiently large n.