本文選題：Ramsey數(shù)　切入點：多色Ramsey數(shù)　出處：《南京大學》2017年博士論文　論文類型：學位論文

【摘要】：Ramsey定理是組合數(shù)學的一個基本結(jié)果,它指:階數(shù)充分大的邊染色完全圖中一定有你需要的單色團.這結(jié)果的第一版本由英國數(shù)學家及哲學家F.P.Ramsey在1930年給出.由此開創(chuàng)了組合數(shù)學的一分支,現(xiàn)在稱之為Ramsey理論.Ramsey理論敘述的是:完全的無序是不可能的.Ramsey理論中的問題常常以這樣的方式提出:某結(jié)構(gòu)中元素達到多大時能保證某特定的性質(zhì)出現(xiàn)?Ramsey理論一直是組合數(shù)學的研究熱點.除了組合學,Ramsey理論在眾多其他數(shù)學分支的發(fā)展中也扮演重要角色,涉及代數(shù)學,集合論,邏輯學,概率論和幾何學等等.其研究者包括Wolf獎得主P.Erdos,L.Lovasz,Fields獎得主T.Gowers,陶哲軒,Abel 獎得主 E.Szemeredi 等人.R.L.Graham,B.L.Rothschild和J.H.Spencer的著作Ramsey Theory是這一領(lǐng)域的經(jīng)典教材.給定圖G1,G2,...,Gk,k≥ 2,色Ramsey數(shù)R(G1,G2,...,Gk)指最小的整數(shù)N,滿足對任意k-邊染色的完全圖KN,一定存在i ∈ {1,2,...,k}使得KN包含i色的子圖G,.如果一個kk-邊染色的完全圖滿足對每個i ∈ {1,2,...,k}它都不包含i色的子圖Gi且其階達到R(G1,G2,...,Gk)-1,我們稱之為(G1,G2,...,Gk)-Ramsey圖.對2-色情形,我們也可以用"補圖"的語言定義Ramsey數(shù)和Ramsey圖.給定圖G1,G2,Ramsey數(shù)R(G1,G2)指最小的整數(shù)N,滿足對任意N階圖G,要么G包含子圖G1要么它的補圖G包含子圖G2.我們稱自身不包含子圖G1且其補圖不包含子圖G2的R(G1,G2)-1階圖為(G1,G2)-Ramsey圖.設Gm為長度為m的圈,而K1,n和Wn分別為n+ 1階星和輪.這篇論文,我們將關(guān)注與四圈,星及輪相關(guān)的多色Ramsey數(shù).如果僅考慮2-色情形,我們有一些已知的結(jié)果.在1975年,Parsons[Transactions American Mathematical Society,209(1975),33-44]為R(C4,K1,n)建立了一個緊的世界.定理A.對所有n≥2,R(C4,K1,n)≤n+「(?)」+ 2.而且,如果n=l2+1且 l ≥ 1,則 R(C4,K1,n)≤n+(?)+1.進一步,在該論文中,利用極圖Gq,它的構(gòu)造分別由Brown及由Erdos,Renyi和Sos在1966年獨立完成,Parsons證明了:當g為素數(shù)冪而n = g2或g2+1時,R(4 K1,n)的值恰好取到定理A中的上界.換句話講,他證明了:定理B.設g為素數(shù)冪.則R(C4,K1,q2+1)=g2+g+2和R(C4,K1,q2= g2+g+1.在 1989 年,Burr 等[Annals ofDiscrete Mathematics,41(1989),79-89]給出R(C4,K1,n)的一個下界:定理C.如果n充分大,則R(C4,K1,n)n+「(?)-6nα/2」,其中α為一個小于11/20的常數(shù).在該論文中,他們還給出了下面猜想,為此,作者之一 Erdos懸賞$100征求該猜想的證明或否定.Burr猜想.對任意的常數(shù)c,總有無窮個n使得R(C4,K1n+(?)-c.但是到目前為止,我們甚至找不到一個n使得R((C4,K1,n)n+(?).也就是說,似乎Burr猜想沒有事實根據(jù)的.由于K1,n是Wn的一個生成子圖,故對任意的n,R(C4,K1,n)≤R(C4,Wn).張閆博等發(fā)現(xiàn)當n≥6時所有已確定的Ramsey數(shù)R(C4,Wn)和R(C4,K1,n)都相等.在 2014 年,他們證明這一事實[Electronic Journal of Graph Theory and Applications,2(2014),110-114]:定理D.對所有n ≥ 6,R(C4,K1,n)= R(C4,Wn).基于對Burr猜想的興趣和受上面四個定理的啟發(fā),我們開始研究與C4相關(guān)的一些Ramsey數(shù),得到了一些關(guān)于四圈,星,輪的多色Ramsey數(shù)(包括2-色情況)的新結(jié)果,詳細證明請閱讀本文的第2章至第5章.1.Ramsey 數(shù) R(C4,K1,n)也許因為(C4,K1,n)-Ramsey圖的構(gòu)造極其困難的緣故,至今Burr猜想尚未解決,事實上已確定的Ramsey數(shù)R(C4,K1,n)的值相當少.設g為素數(shù)冪.除定理 B 中 R(C4,K1,q2)和R(C4,K1,K1,q2+1)值,Parsons 也考慮R(C4 K1,q2-t)的值其中t為某給定范圍的整數(shù),并得到下面結(jié)果[Aequationes Mathematicae,14(1976),167-189].定理E.設g為素數(shù)冪.如果g是偶數(shù),1≤t≤q+1且t≠q,或g是奇數(shù),0 ≤ t≤ 2 「q/4」且 t 是偶數(shù),則R(C4,K1,q2-t)= q2 +q-(t-1).注意到定理B和定理E中所有確定的Ramsey數(shù)的取值恰好是定理A所提供的上界,于是,我們知道這些值的獲取主要工作在于Ramsey圖的構(gòu)造.而Parsons所需要的Ramsey圖都是由極圖Gq的子圖提供的.在第2章,首先,我們將定理E推廣至g為奇素數(shù)冪而t滿足1≤t≤2「q/4]且t ≠ 2「q/4」-1的情形.我們的主要想法是基于對極圖Gq的局部結(jié)構(gòu)的分析進行構(gòu)造所需Ramsey圖.尤其,我們針對奇數(shù)t所構(gòu)造的(C4,K1,q2-t)-Ramsey圖并不是Gq的子圖.下面定理是第2章的主要結(jié)果之一.定理1.設g為奇素數(shù)冪.如果1≤t≤2「q/4]且t≠2「q/4」-1,則R(C4,K1,q2-t))= q2 + q-(t-1).值得注意的是,這些Ramsey數(shù)確定的n值都在一個素數(shù)冪附近.既然Burr猜想仍然是未解決的,我們好奇當n不在素數(shù)冪附近時R(C4,K1,n 的取值.當然,越多類型n的R(C4,K1,n)值確定,我們就越有可能接近R(C4,K1,n)的好的一般下界.于是,我們開始嘗試去對其他類型的n研究R(C4,K1,n)的值.為此,我們在Galois域上的平面內(nèi)構(gòu)造了一個階為q2-1的無四圈圖Γq.基于對該類圖的結(jié)構(gòu)分析,我們獲得幾類(C4,K1,n)-Ramsey圖.利用這些圖,我們證明了下面兩個定理,即第2章的另外兩個主要定理.定理2.設q≥4為偶素數(shù)冪且t=1,0,-2.則R(C4,K1,(g-1)2+t)=(q-1)2 + q +t.定理3.設q≥5為奇素數(shù)冪且t=2,4,...,2「q/4」.則R(C4,K1,q(q-1)t)=q2-t容易驗證定理1,2和3中的Ramsey數(shù)的取值要么恰好為定理A中通常的上界n + 「(?)」+ 2或者與該界僅相差1.2.三色 Ramsey 數(shù) R((C4,C4,K1,n)Turan數(shù)ex(t,C4)指無四圈的t階圖能達到最大邊數(shù).設g為素數(shù)冪.有趣的是:不管對 Turan 數(shù) ex(g2 + g + 1,C4)還是對 Ramsey 數(shù) R(C4,K1,q2+1),Gq都是一個極值圖.顯然,每個Kq2+q+1包含一個Gq的嵌入.一個自然的問題:Kg2+q+1至多能嵌入多少個邊不交的Gq?這兒,我們沒能給出確切的答案,但利用Singer差集我們發(fā)現(xiàn)每個Kq2+q+1至少能夠包含兩個邊不交的Gq嵌入.基于這個發(fā)現(xiàn),我們能夠精巧地構(gòu)造一類(C4,C4,K1 n)-Ramsey圖.在第3章,我們僅考慮三色Ramsey數(shù)R((C4,C4,K1,n).首先,我們建立了一個R(C4,C4,K1,n)的上界：讀者在該章也可以看到R(C4,C4,K1,5= 13,也就是說,當n = 5時該界取到,所以它是緊的.更進一步,我們證明了:如果l為素數(shù)冪,定理4中對n =l2-l的相應Ramsey數(shù)的上界 恰好取到.也就是說,我們確定無窮個R(C4,C4,K1,n)的值如下:定理5.對所有的素數(shù)冪3.三色 Ramsey 數(shù)R(C4,C4,Wn)由定理D,我們知道:當n≥6時,定理A中R(C4,K1,n)的上界也是R(C4,Wn)的上界.一個自然的問題:定理4中R(C4,C4,K1,n)的上界也是R(C4,G4,Wn)的上界嗎?在第4章,我們關(guān)注三色Ramsey數(shù)R(C4,C4,K1,n)和R(C4,C4,Wn)的之間關(guān)系,獲得關(guān)于三色Ramsey數(shù)R(C4,C4,Wn)的一個上界.取k = 1,2,我們將分別得到定理A和定理4.也就是說,定理8推廣了定理A和定理4.進一步,對每個充分大的n,結(jié)合代數(shù)方法和概率方法,我們構(gòu)造了一個階數(shù)相當大的(k+1)-邊染色完全圖使得對任意1 ≤i≤k它不包含i-色C4也不包含(k+1)-色K1,n.利用這些(k+1)-邊染色完全圖,我們獲得(k+1)-色Ramsey數(shù)R(C4,…,C4,K1,n)的一個通常下界:定理9.如果n充分大,則(?)n+「k(?)-6knα/2」,其中α為一個小于11/20的常數(shù).取k= 1,我們就得到定理C.也就是說,定理9推廣了定理C.最后,我們關(guān)注(kk+1)-色Ramsey數(shù)R(C4,…,C4,K1,n)和R(C4,…,C4,Wn)之間關(guān)系.如果k=1,定理D敘述:對所有n≥6,R(C4,Wn)=R(C4,K1,n).對于一般的k,由于K1,n是Wn的一個生成子圖,顯然,R(C4,…,C4,K1,n)至多為R(C4,...,C4,Wn).自然地,我們要問:是否存在整數(shù)N,使得當n≥N時R(C4,...,C4,K1,n)和R(C4,...,C4)相等?答案是肯定的,事實上,在定理8和9基礎上,我們可以證明:定理10.對充分大的n,(?)
[Abstract]:The Ramsey theorem is a basic result, it refers to the combination of Mathematics: the order of sufficiently large edge colored complete graphs must have you need monochromatic group. First version of this result by the British mathematician and philosopher F.P.Ramsey in 1930. This was the beginning of a given branch of combinatorial mathematics, now known as the Ramsey.Ramsey narrative theory the theory is: complete disorder is not possible in.Ramsey theory often put forward in such a way that the element of a structure to achieve much when you can guarantee a certain property? Ramsey theory has been a hot research topic in combinatorial mathematics. Besides combinatorics, Ramsey theory in the development of many other mathematical branches in play an important role in involving algebra, set theory, logic, probability and geometry and so on. The researchers including Wolf L.Lovasz, Fields P.Erdos award winner, Tao Zhe prize winner T.Gowers Abel prize, Hennessy 涓，

本文編號：1633480