【word】 用循环图计算经典ramsey数r（3,q）的下界

用循环图计算经典RAMSEY数R（3,Q）的下界2008年5月MAY2008华南师范大学自然科学版JOURNALOFSOUTHCHINANORMALUNIVERSITYNATURALSCIENCEEDITION2008年第2期NO2,2008文章编号100054632008020O25一O4用循环图计算经典RAMSEY数R3,Q的下界吴康,苏文龙,罗海鹏,许晓东1华南师范大学数学科学学院,广东广州5106312梧州学院数学系,广西梧州5430023广西科学院,广西南宁530022摘要构造了3个循环图,利用循环图计算得一些经典RAMSEY数的新的下界R3,33216,R3,34224,R3,35228等关键词RAMSEY数下界循环图中图分类号0167文献标识码ALOWERBOUNDSFORCLASSICALRAMSEYNUMBERSR3,GBASEDONCYCLICGRAPHSWUKANG,SUWENLONG2,LUOHAIPENG3,XUXIAODONG31SCHOOLOFMATHEMATICS,SOUTHCHINANORMALUNIVERSITY,GUANGZHOU510631CHINA2DEPARTMENTOFMATHEMATICS,WUZHOUUNIVERSITY,WUZHOU,GUANGXI543002,CHINA3GUANGRDACADEMYOFSCIENCESNANNING530022,CHINAABSTRACTBYCONSTRUCTINGTHREECYCLICGRAPHS,THELOWERBOUNDSFORTHREECLASSICALRAMSEYNUMBERSN3,GAREOBTAINEDR3,331216,R3,341224,R3,359228KEYWORDSRAMSEYNUMBERSLOWERBOUNDSCYCLICGRAPH1本文的主要结果确定经典RAMSEY数是组合数学中非常困难的问题鉴于迄今尚未见到取得重大突破的迹象,人们常用各种方法计算RAMSEY数的界1955年,GREENWOOD和GLEASON【2首创构造性方法,在确定历史上第一批RAMSEY数的准确值的时候,利用循环图计算出R3,35,R3,48,尺3,513,N4,417,尺3,3,316等下界近年来,各国学者应用这种方法获得了许多新成果论文综述了迄今已知的RAMSEY数的准确值和上,下界,其中当22G32时,R3,G的下界见表1收稿日期20070806基金项目国家自然科学基金资助项目6056300810671076广东省自然科学基金资助项目05005928,5300084广西自然科学基金资助项目桂科字0640037梧州学院科研项目2007B007作者简介吴康1957一,男,广东高州人,华南师范大学副教授,EMALLWUKANG12345126EOM26华南师范大学自然科学版2008年我们在文献48中用循环图计算得一些经典RAMSEY数的下界本文在此基础上深入研究,构造了3个循环图,得到新的结果定理1R3,33216,R3,34224,R3,352282若干引理给定整数N5,令MI詈I对于整数SF,记S,TS1,T约定,当N是奇数L厶J时,Z一M,M当/7,是偶数时,Z1一M,M以下除非特别说明,所有模/7,整数的运算结果都理解为模/7,后属于Z,并用通常的等号“表示”模/7,相等”定义1对于集合S1,M的一个2部分拆SSUS,记AS,设/7,阶完全图K的顶点集VZ,边集E是Z的所有2元子集的集且有分拆EEUE,其中E,EE且一,EA,I1,2把E中的边叫做AI色的,记K中A色边所导出的子图为A,其团数记为CA,这里I1,2于是,我们按照参数集合A或A即S或把的边2一染色,得到素数阶循环图CA据RAMSEY数的定义L】J,显然有弓I理1设KICAI,IL,2,引进A的一个全序对于任意AA,考察顶点A的度数记A,EAIA一,EA,DADAI一般地,当A一A时有,EAI,一AA一,A,YAAF故有DAD一A,即A的二元子集A,一A的两个元的度数相等易知,二元子集A,一A中有且仅有一个元属于SL,特别地,当A一A时,二元子集A,一N退化为一元子集A显然,当RT为偶数且MES时,有且仅有一个退化了的一元子集MA为了叙述简便,以下把二元子集A,一A与退化了的一元子集A统称为A的子集并且第2期吴康等用循环图计算经典RAMSEY数R3,G的下界27形式地记为口,一口约定,当口RAM,一口时,A的子集口,一口表示退化了的一元子集口定义2设S,记DYAIYEA,DIDI在A上的序规定如下设口,BS,则1A的子集口,一口对于序构成区间,并且当口一口时口一口2对于A中分属不同子集的元口,一口和YB,一B,规定Y当且仅当D口DB,或者当D口DB时口B由上述讨论可知,在A的子集口,一口中有且仅有一个元属于S,因此序是明确定义的易知A,是全序集Y称为前于Y或Y后于引理4如果对于任意S,都有D0,那么AIRAM,1证明我们用反证法来证明这个结论假设对于任意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证明设A1,即对于任意口S与YA,恒有Y一口A,据定义3有2口O从而有IN/IX口口SRAM,0,引理5成立以下考察AIRAM,11的情形由定义3知链,的1个元构成GA的一个团,即得A1MAXLI口I口S以下再证A1MAXLI口I口S设ARAM,12则GA中有1个顶点按排序后得A,上的长为的链,再在A,上所有长为的链中取起点按来说最前面的一条,记为,我们断言一定有S假若不然,即一S作Z到自身的变换一一,由引理2知这是GS的同构变换,从而也是GA的同构变换,它把G中1个顶点的团,一,变成另一个团一,一,一据定义3可知,这1个元一,一一,一在A,上构成长为的链由定义2所规定的全序集A,的排序方式可知这条A色链可表示为一一L一I,其起点一00因此,原来给定的链0L不是”起点按来说最前”的一条,矛盾于是断言S为真从而有A1MAX口L口S引理5得证引理5表明,为了计算GA的团数,只须寻求以口S为起点的A色的链就可以了这样能够提高运算效率3定理1的证明1取整数17,215,则MRAM,107令SLRAM,1,7,1O,13,15,32,41,49,52,68,7O,72,88,92,28华南师范大学自然科学版2008年97容易验证G2按照上述理论,用计算机算得图GA中的第一条长度为30的2色链76一763358一5880一80100106一10664511一11一5084一84一101一3一2225一2553一53一6278一78一10455一56一20此后没有更长的色链据引理5有1MAXZAIAS31,据引理3有G2A2132,据弓F理1有R3,33216为了简便,以下只写出整数N与参数集S,以及计算得到的尺3,Q的新下界2取整数N223,令SLL,7,L0,L2,23,38,4J4,53,62,66,7L,80,93,96,98,101计算得尺3,342243取整数N227,令SL,5,7,24,28,49,51,60,63,66,74,76,92,96,106,108计算得R3,35_228我们在CPU为AMD3600的计算机上完成上述运算的时间约为5H参考文献1李乔组合数学基础M北京高等教育出版社,19932GREENWOODRE,GLEASONAMCOMBINATORIALRELATIONSANDCHROMATICGRAPHSJCANADIANJOURNALOFMATHEMATICS,1955,7173RADZISZOWSKISPSMALLRAMSEYNUMBERSJTHEELECTRONICJOURNALOFCOMBINATORICS,2006,DS1L11604吴康,苏文龙,罗海鹏8个经典多色RAMSEY数的新下界J南京师范大学自然科学版,2000,23315195吴康,苏文龙,罗海鹏5个三色RAMSEY数R3,3,G下界J华南师范大学自然科学版,200021041106苏文龙,罗海鹏,李乔多色经典RAMSEY数RQ,G,G的下界J中国科学A辑,1999,2954084137SUWENLONG,LUOHAIPENG,SHENYUNQIUNEWLOWERBOUNDSFORCL