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

【摘要】：Ramsey定理是組合數(shù)學(xué)的一個(gè)基本結(jié)果,它指:階數(shù)充分大的邊染色完全圖中一定有你需要的單色團(tuán).這結(jié)果的第一版本由英國數(shù)學(xué)家及哲學(xué)家F.P.Ramsey在1930年給出.由此開創(chuàng)了組合數(shù)學(xué)的一分支,現(xiàn)在稱之為Ramsey理論.Ramsey理論敘述的是:完全的無序是不可能的.Ramsey理論中的問題常常以這樣的方式提出:某結(jié)構(gòu)中元素達(dá)到多大時(shí)能保證某特定的性質(zhì)出現(xiàn)?Ramsey理論一直是組合數(shù)學(xué)的研究熱點(diǎn).除了組合學(xué),Ramsey理論在眾多其他數(shù)學(xué)分支的發(fā)展中也扮演重要角色,涉及代數(shù)學(xué),集合論,邏輯學(xué),概率論和幾何學(xué)等等.其研究者包括Wolf獎(jiǎng)得主P.Erdos,L.Lovasz,Fields獎(jiǎng)得主T.Gowers,陶哲軒,Abel 獎(jiǎng)得主 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,滿足對(duì)任意k-邊染色的完全圖KN,一定存在i ∈ {1,2,...,k}使得KN包含i色的子圖G,.如果一個(gè)kk-邊染色的完全圖滿足對(duì)每個(gè)i ∈ {1,2,...,k}它都不包含i色的子圖Gi且其階達(dá)到R(G1,G2,...,Gk)-1,我們稱之為(G1,G2,...,Gk)-Ramsey圖.對(duì)2-色情形,我們也可以用"補(bǔ)圖"的語言定義Ramsey數(shù)和Ramsey圖.給定圖G1,G2,Ramsey數(shù)R(G1,G2)指最小的整數(shù)N,滿足對(duì)任意N階圖G,要么G包含子圖G1要么它的補(bǔ)圖G包含子圖G2.我們稱自身不包含子圖G1且其補(bǔ)圖不包含子圖G2的R(G1,G2)-1階圖為(G1,G2)-Ramsey圖.設(shè)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)建立了一個(gè)緊的世界.定理A.對(duì)所有n≥2,R(C4,K1,n)≤n+「(?)」+ 2.而且,如果n=l2+1且 l ≥ 1,則 R(C4,K1,n)≤n+(?)+1.進(jìn)一步,在該論文中,利用極圖Gq,它的構(gòu)造分別由Brown及由Erdos,Renyi和Sos在1966年獨(dú)立完成,Parsons證明了:當(dāng)g為素?cái)?shù)冪而n = g2或g2+1時(shí),R(4 K1,n)的值恰好取到定理A中的上界.換句話講,他證明了:定理B.設(shè)g為素?cái)?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)的一個(gè)下界:定理C.如果n充分大,則R(C4,K1,n)n+「(?)-6nα/2」,其中α為一個(gè)小于11/20的常數(shù).在該論文中,他們還給出了下面猜想,為此,作者之一 Erdos懸賞$100征求該猜想的證明或否定.Burr猜想.對(duì)任意的常數(shù)c,總有無窮個(gè)n使得R(C4,K1n+(?)-c.但是到目前為止,我們甚至找不到一個(gè)n使得R((C4,K1,n)n+(?).也就是說,似乎Burr猜想沒有事實(shí)根據(jù)的.由于K1,n是Wn的一個(gè)生成子圖,故對(duì)任意的n,R(C4,K1,n)≤R(C4,Wn).張閆博等發(fā)現(xiàn)當(dāng)n≥6時(shí)所有已確定的Ramsey數(shù)R(C4,Wn)和R(C4,K1,n)都相等.在 2014 年,他們證明這一事實(shí)[Electronic Journal of Graph Theory and Applications,2(2014),110-114]:定理D.對(duì)所有n ≥ 6,R(C4,K1,n)= R(C4,Wn).基于對(duì)Burr猜想的興趣和受上面四個(gè)定理的啟發(fā),我們開始研究與C4相關(guān)的一些Ramsey數(shù),得到了一些關(guān)于四圈,星,輪的多色Ramsey數(shù)(包括2-色情況)的新結(jié)果,詳細(xì)證明請(qǐng)閱讀本文的第2章至第5章.1.Ramsey 數(shù) R(C4,K1,n)也許因?yàn)?C4,K1,n)-Ramsey圖的構(gòu)造極其困難的緣故,至今Burr猜想尚未解決,事實(shí)上已確定的Ramsey數(shù)R(C4,K1,n)的值相當(dāng)少.設(shè)g為素?cái)?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.設(shè)g為素?cái)?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為奇素?cái)?shù)冪而t滿足1≤t≤2「q/4]且t ≠ 2「q/4」-1的情形.我們的主要想法是基于對(duì)極圖Gq的局部結(jié)構(gòu)的分析進(jìn)行構(gòu)造所需Ramsey圖.尤其,我們針對(duì)奇數(shù)t所構(gòu)造的(C4,K1,q2-t)-Ramsey圖并不是Gq的子圖.下面定理是第2章的主要結(jié)果之一.定理1.設(shè)g為奇素?cái)?shù)冪.如果1≤t≤2「q/4]且t≠2「q/4」-1,則R(C4,K1,q2-t))= q2 + q-(t-1).值得注意的是,這些Ramsey數(shù)確定的n值都在一個(gè)素?cái)?shù)冪附近.既然Burr猜想仍然是未解決的,我們好奇當(dāng)n不在素?cái)?shù)冪附近時(shí)R(C4,K1,n 的取值.當(dāng)然,越多類型n的R(C4,K1,n)值確定,我們就越有可能接近R(C4,K1,n)的好的一般下界.于是,我們開始嘗試去對(duì)其他類型的n研究R(C4,K1,n)的值.為此,我們?cè)贕alois域上的平面內(nèi)構(gòu)造了一個(gè)階為q2-1的無四圈圖Γq.基于對(duì)該類圖的結(jié)構(gòu)分析,我們獲得幾類(C4,K1,n)-Ramsey圖.利用這些圖,我們證明了下面兩個(gè)定理,即第2章的另外兩個(gè)主要定理.定理2.設(shè)q≥4為偶素?cái)?shù)冪且t=1,0,-2.則R(C4,K1,(g-1)2+t)=(q-1)2 + q +t.定理3.設(shè)q≥5為奇素?cái)?shù)冪且t=2,4,...,2「q/4」.則R(C4,K1,q(q-1)t)=q2-t容易驗(yàn)證定理1,2和3中的Ramsey數(shù)的取值要么恰好為定理A中通常的上界n + 「(?)」+ 2或者與該界僅相差1.2.三色 Ramsey 數(shù) R((C4,C4,K1,n)Turan數(shù)ex(t,C4)指無四圈的t階圖能達(dá)到最大邊數(shù).設(shè)g為素?cái)?shù)冪.有趣的是:不管對(duì) Turan 數(shù) ex(g2 + g + 1,C4)還是對(duì) Ramsey 數(shù) R(C4,K1,q2+1),Gq都是一個(gè)極值圖.顯然,每個(gè)Kq2+q+1包含一個(gè)Gq的嵌入.一個(gè)自然的問題:Kg2+q+1至多能嵌入多少個(gè)邊不交的Gq?這兒,我們沒能給出確切的答案,但利用Singer差集我們發(fā)現(xiàn)每個(gè)Kq2+q+1至少能夠包含兩個(gè)邊不交的Gq嵌入.基于這個(gè)發(fā)現(xiàn),我們能夠精巧地構(gòu)造一類(C4,C4,K1 n)-Ramsey圖.在第3章,我們僅考慮三色Ramsey數(shù)R((C4,C4,K1,n).首先,我們建立了一個(gè)R(C4,C4,K1,n)的上界：讀者在該章也可以看到R(C4,C4,K1,5= 13,也就是說,當(dāng)n = 5時(shí)該界取到,所以它是緊的.更進(jìn)一步,我們證明了:如果l為素?cái)?shù)冪,定理4中對(duì)n =l2-l的相應(yīng)Ramsey數(shù)的上界 恰好取到.也就是說,我們確定無窮個(gè)R(C4,C4,K1,n)的值如下:定理5.對(duì)所有的素?cái)?shù)冪3.三色 Ramsey 數(shù)R(C4,C4,Wn)由定理D,我們知道:當(dāng)n≥6時(shí),定理A中R(C4,K1,n)的上界也是R(C4,Wn)的上界.一個(gè)自然的問題:定理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)的一個(gè)上界.取k = 1,2,我們將分別得到定理A和定理4.也就是說,定理8推廣了定理A和定理4.進(jìn)一步,對(duì)每個(gè)充分大的n,結(jié)合代數(shù)方法和概率方法,我們構(gòu)造了一個(gè)階數(shù)相當(dāng)大的(k+1)-邊染色完全圖使得對(duì)任意1 ≤i≤k它不包含i-色C4也不包含(k+1)-色K1,n.利用這些(k+1)-邊染色完全圖,我們獲得(k+1)-色Ramsey數(shù)R(C4,…,C4,K1,n)的一個(gè)通常下界:定理9.如果n充分大,則(?)n+「k(?)-6knα/2」,其中α為一個(gè)小于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敘述:對(duì)所有n≥6,R(C4,Wn)=R(C4,K1,n).對(duì)于一般的k,由于K1,n是Wn的一個(gè)生成子圖,顯然,R(C4,…,C4,K1,n)至多為R(C4,...,C4,Wn).自然地,我們要問:是否存在整數(shù)N,使得當(dāng)n≥N時(shí)R(C4,...,C4,K1,n)和R(C4,...,C4)相等?答案是肯定的,事實(shí)上,在定理8和9基礎(chǔ)上,我們可以證明:定理10.對(duì)充分大的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 涓，

本文編號(hào)：1633480