用循環(huán)圖計算經(jīng)典RAMSEY數(shù)R（3,Q）的下界2008年5月MAY2008華南師范大學(xué)自然科學(xué)版JOURNALOFSOUTHCHINANORMALUNIVERSITYNATURALSCIENCEEDITION2008年第2期NO2,2008文章編號100054632008020O25一O4用循環(huán)圖計算經(jīng)典RAMSEY數(shù)R3,Q的下界吳康,蘇文龍,羅海鵬,許曉東1華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,廣東廣州5106312梧州學(xué)院數(shù)學(xué)系,廣西梧州5430023廣西科學(xué)院,廣西南寧530022摘要構(gòu)造了3個循環(huán)圖,利用循環(huán)圖計算得一些經(jīng)典RAMSEY數(shù)的新的下界R3,33216,R3,34224,R3,35228等關(guān)鍵詞RAMSEY數(shù)下界循環(huán)圖中圖分類號0167文獻標識碼ALOWERBOUNDSFORCLASSICALRAMSEYNUMBERSR3,GBASEDONCYCLICGRAPHSWUKANG,SUWENLONG2,LUOHAIPENG3,XUXIAODONG31SCHOOLOFMATHEMATICS,SOUTHCHINANORMALUNIVERSITY,GUANGZHOU510631CHINA2DEPARTMENTOFMATHEMATICS,WUZHOUUNIVERSITY,WUZHOU,GUANGXI543002,CHINA3GUANGRDACADEMYOFSCIENCESNANNING530022,CHINAABSTRACTBYCONSTRUCTINGTHREECYCLICGRAPHS,THELOWERBOUNDSFORTHREECLASSICALRAMSEYNUMBERSN3,GAREOBTAINEDR3,331216,R3,341224,R3,359228KEYWORDSRAMSEYNUMBERSLOWERBOUNDSCYCLICGRAPH1本文的主要結(jié)果確定經(jīng)典RAMSEY數(shù)是組合數(shù)學(xué)中非常困難的問題鑒于迄今尚未見到取得重大突破的跡象,人們常用各種方法計算RAMSEY數(shù)的界1955年,GREENWOOD和GLEASON【2首創(chuàng)構(gòu)造性方法,在確定歷史上第一批RAMSEY數(shù)的準確值的時候,利用循環(huán)圖計算出R3,35,R3,48,尺3,513,N4,417,尺3,3,316等下界近年來,各國學(xué)者應(yīng)用這種方法獲得了許多新成果論文綜述了迄今已知的RAMSEY數(shù)的準確值和上,下界,其中當(dāng)22G32時,R3,G的下界見表1收稿日期20070806基金項目國家自然科學(xué)基金資助項目6056300810671076廣東省自然科學(xué)基金資助項目05005928,5300084廣西自然科學(xué)基金資助項目桂科字0640037梧州學(xué)院科研項目2007B007作者簡介吳康1957一,男,廣東高州人,華南師范大學(xué)副教授,EMALLWUKANG12345126EOM26華南師范大學(xué)自然科學(xué)版2008年我們在文獻48中用循環(huán)圖計算得一些經(jīng)典RAMSEY數(shù)的下界本文在此基礎(chǔ)上深入研究,構(gòu)造了3個循環(huán)圖,得到新的結(jié)果定理1R3,33216,R3,34224,R3,352282若干引理給定整數(shù)N5,令MI詈I對于整數(shù)SF,記S,TS1,T約定,當(dāng)N是奇數(shù)L厶J時,Z一M,M當(dāng)/7,是偶數(shù)時,Z1一M,M以下除非特別說明,所有模/7,整數(shù)的運算結(jié)果都理解為模/7,后屬于Z,并用通常的等號“表示”模/7,相等”定義1對于集合S1,M的一個2部分拆SSUS,記AS,設(shè)/7,階完全圖K的頂點集VZ,邊集E是Z的所有2元子集的集且有分拆EEUE,其中E,EE且一,EA,I1,2把E中的邊叫做AI色的,記K中A色邊所導(dǎo)出的子圖為A,其團數(shù)記為CA,這里I1,2于是,我們按照參數(shù)集合A或A即S或把的邊2一染色,得到素數(shù)階循環(huán)圖CA據(jù)RAMSEY數(shù)的定義L】J,顯然有弓I理1設(shè)KICAI,IL,2,引進A的一個全序?qū)τ谌我釧A,考察頂點A的度數(shù)記A,EAIA一,EA,DADAI一般地,當(dāng)A一A時有,EAI,一AA一,A,YAAF故有DAD一A,即A的二元子集A,一A的兩個元的度數(shù)相等易知,二元子集A,一A中有且僅有一個元屬于SL,特別地,當(dāng)A一A時,二元子集A,一N退化為一元子集A顯然,當(dāng)RT為偶數(shù)且MES時,有且僅有一個退化了的一元子集MA為了敘述簡便,以下把二元子集A,一A與退化了的一元子集A統(tǒng)稱為A的子集并且第2期吳康等用循環(huán)圖計算經(jīng)典RAMSEY數(shù)R3,G的下界27形式地記為口,一口約定,當(dāng)口RAM,一口時,A的子集口,一口表示退化了的一元子集口定義2設(shè)S,記DYAIYEA,DIDI在A上的序規(guī)定如下設(shè)口,BS,則1A的子集口,一口對于序構(gòu)成區(qū)間,并且當(dāng)口一口時口一口2對于A中分屬不同子集的元口,一口和YB,一B,規(guī)定Y當(dāng)且僅當(dāng)D口DB,或者當(dāng)D口DB時口B由上述討論可知,在A的子集口,一口中有且僅有一個元屬于S,因此序是明確定義的易知A,是全序集Y稱為前于Y或Y后于引理4如果對于任意S,都有D0,那么AIRAM,1證明我們用反證法來證明這個結(jié)論假設(shè)對于任意S,都有O,且有A2,則GA3,在圖GA中有3階團0,Y,其中,YA且一YA有如下情形如果或YS,就有D1或DY1,與已知條件矛盾如果一與一YS,則由引理2知O,一,一Y也是圖GA的3階團,就有一YD一,D一RAM,LD一I1,與已知條件矛盾定義3全序集A,上的長為1的鏈,稱為起點為的長為的A色鏈,如果對于OIL有一A起點是的鏈的最大長記為2如果起點是的長為1的鏈不存在,就令ZRAM,0弓I理5A1IN/IXFI口L口S證明設(shè)A1,即對于任意口S與YA,恒有Y一口A,據(jù)定義3有2口O從而有IN/IX口口SRAM,0,引理5成立以下考察AIRAM,11的情形由定義3知鏈,的1個元構(gòu)成GA的一個團,即得A1MAXLI口I口S以下再證A1MAXLI口I口S設(shè)ARAM,12則GA中有1個頂點按排序后得A,上的長為的鏈,再在A,上所有長為的鏈中取起點按來說最前面的一條,記為,我們斷言一定有S假若不然,即一S作Z到自身的變換一一,由引理2知這是GS的同構(gòu)變換,從而也是GA的同構(gòu)變換,它把G中1個頂點的團,一,變成另一個團一,一,一據(jù)定義3可知,這1個元一,一一,一在A,上構(gòu)成長為的鏈由定義2所規(guī)定的全序集A,的排序方式可知這條A色鏈可表示為一一L一I,其起點一00因此,原來給定的鏈0L不是”起點按來說最前”的一條,矛盾于是斷言S為真從而有A1MAX口L口S引理5得證引理5表明,為了計算GA的團數(shù),只須尋求以口S為起點的A色的鏈就可以了這樣能夠提高運算效率3定理1的證明1取整數(shù)17,215,則MRAM,107令SLRAM,1,7,1O,13,15,32,41,49,52,68,7O,72,88,92,28華南師范大學(xué)自然科學(xué)版2008年97容易驗證G2按照上述理論,用計算機算得圖GA中的第一條長度為30的2色鏈76一763358一5880一80100106一10664511一11一5084一84一101一3一2225一2553一53一6278一78一10455一56一20此后沒有更長的色鏈據(jù)引理5有1MAXZAIAS31,據(jù)引理3有G2A2132,據(jù)弓F理1有R3,33216為了簡便,以下只寫出整數(shù)N與參數(shù)集S,以及計算得到的尺3,Q的新下界2取整數(shù)N223,令SLL,7,L0,L2,23,38,4J4,53,62,66,7L,80,93,96,98,101計算得尺3,342243取整數(shù)N227,令SL,5,7,24,28,49,51,60,63,66,74,76,92,96,106,108計算得R3,35_228我們在CPU為AMD3600的計算機上完成上述運算的時間約為5H參考文獻1李喬組合數(shù)學(xué)基礎(chǔ)M北京高等教育出版社,19932GREENWOODRE,GLEASONAMCOMBINATORIALRELATIONSANDCHROMATICGRAPHSJCANADIANJOURNALOFMATHEMATICS,1955,7173RADZISZOWSKISPSMALLRAMSEYNUMBERSJTHEELECTRONICJOURNALOFCOMBINATORICS,2006,DS1L11604吳康,蘇文龍,羅海鵬8個經(jīng)典多色RAMSEY數(shù)的新下界J南京師范大學(xué)自然科學(xué)版,2000,23315195吳康,蘇文龍,羅海鵬5個三色RAMSEY數(shù)R3,3,G下界J華南師范大學(xué)自然科學(xué)版,200021041106蘇文龍,羅海鵬,李喬多色經(jīng)典RAMSEY數(shù)RQ,G,G的下界J中國科學(xué)A輯,1999,2954084137SUWENLONG,LUOHAIPENG,SHENYUNQIUNEWLOWERBOUNDSFORCL