用循环图计算经典ramsey数r_3_q_的下界

文章编号10005463200802002504用循环图计算经典RAMSEY数R3,Q的下界康1,苏文龙2,罗海鹏3,许晓东3吴1华南师范大学数学科学学院,广东广州5106312梧州学院数学系,广西梧州5430023广西科学院,广西南宁530022摘要构造了3个循环图,利用循环图计算得一些经典RAMSEY数的新的下界R3,33216,R3,34224,R3,35228等关键词RAMSEY数下界循环图中图分类号O167文献标识码ALOWERBOUNDSFORCLASSICALRAMSEYNUMBERSR3,QBASEDONCYCLICGRAPHSWUKANG1,SUWENLONG2,LUOHAIPENG3,XUXIAODONG31SCHOOLOFMATHEMATICS,SOUTHCHINANORMALUNIVERSITY,GUANGZHOU510631,CHINA2DEPARTMENTOFMATHEMATICS,WUZHOUUNIVERSITY,WUZHOU,GUANGXI543002,CHINA3GUANGXIACADEMYOFSCIENCES,NANNING530022,CHINAABSTRACTBYCONSTRUCTINGTHREECYCLICGRAPHS,THELOWERBOUNDSFORTHREECLASSICALRAMSEYNUMBERSR3,QAREOBTAINEDR3,33216,R3,34224,R3,35228KEYWORDSRAMSEYNUMBERSLOWERBOUNDSCYCLICGRAPH1本文的主要结果确定经典RAMSEY数是组合数学中非常困难的问题1鉴于迄今尚未见到取得重大突破的迹象,人们常用各种方法计算RAMSEY数的界1955年,GREENWOOD和GLEASON2首创构造性方法,在确定历史上第一批RAMSEY数的准确值的时候,利用循环图计算出R3,35,R3,48,R3,513,R4,417,R3,3,316等下界近年来,各国学者应用这种方法获得了许多新成果论文3综述了迄今已知的RAMSEY数的准确值和上、下界,其中当22Q32时,R3,Q的下界见表1收稿日期20070806基金项目国家自然科学基金资助项目60563008,10671076广东省自然科学基金资助项目05005928,5300084广西自然科学基金资助项目桂科字0640037梧州学院科研项目2007B007作者简介吴康1957,男,广东高州人,华南师范大学副教授,EMAILWUKANG12345126COM华南师范大学学报自然科学版2008年26表1R3,Q的部分下界2223242526272829303132Q下界125136143153159167172182187198212我们在文献48中用循环图计算得一些经典RAMSEY数的下界本文在此基础上深入研究,构造了3个循环图,得到新的结果定理1R3,33216,R3,34224,R3,352282若干引理N给定整数N5,令M对于整数ST,记S,TS,S1,T约定,当N是奇数2时,ZNM,M当N是偶数时,ZN1M,M以下除非特别说明,所有模N整数的运算结果都理解为模N后属于ZN,并用通常的等号“”表示“模N相等”定义1对于集合S1,M的一个2部分拆SS1S2,记AIXSI,设N阶X完全图KN的顶点集VZN,边集E是ZN的所有2元子集的集且有分拆EE1E2,其中EIX,YX,YE且XYAI,I1,2把EI中的边叫做AI色的,记KN中AI色边所导出的子图为GPAI,其团数记为GNAI,这里I1,2于是,我们按照参数集合A1或A2即S1或S2把KN的边2染色,得到素数阶循环图GNAI据RAMSEY数的定义1,显然有引理1引理2对任意设设KIGNAI,I1,2,则RK11,K21N1ZN,则ZN到自身的变换FXXB是GNAI的同构变换BI1,2,考察GNAI的团和团数由引理2易知,图GNAI的团数等于GNAI中含顶点0的团的最大阶,因此只须考察含顶点0的团据定义1知这样的团的其他非零顶点是集合AI的元,故有引理3记图GNAI中顶点集为AI的导出子图为GNAI,其团数为AI,则有GNAIAI1于是,求GNAI的团数就转化为求GNAI的团数为了求得AI,引进AI的一个全序对于任意AAI,考察顶点A的度数记DIAYAIAYAI,DIADIA一般地,当AA时有YAIYAI,YAAI,YAAI故有DIADIA,即AI的二元子集A,A的两个元的度数相等易知,二元子集A,A中有且仅有一个元属于SI,特别地,当AA时,二元子集A,A退化为一元子集A显然,当N为偶数且M时,有且仅有一个退化了的一元子集MAISI为了叙述简便,以下把二元子集A,A与退化了的一元子集A统称为AI的子集并且第2期吴康等用循环图计算经典RAMSEY数R3,Q的下界27形式地记为A,A约定,当AA时,AI的子集A,A表示退化了的一元子集A定义2设XSI,记DIXYXYAI,DIXDIX在AI上的序规定AI如下设A,BSI,则1AI的子集A,A对于序构成区间,并且当2对于AI中分属不同子集的元XA,A和YDIB,或者当DIADIB时ABAA时AAB,B,规定XY当且仅当DIA由上述讨论可知,在AI的子集A,A中有且仅有一个元属于SI,因此序是明确定义的易知AI,是全序集XY称为X前于Y或Y后于X引理4如果对于任意XSI,都有DIX0,那么AI1证明我们用反证法来证明这个结论假设对于任意XSI,都有DIX0,且有AI2,则GNAI3,在图GNAI中有3阶团0,X,Y,其中X,YAI且XYAI有如下情形如果如果DIX,X或YSI,就有DIX1或DIY1,与已知条件矛盾X与YSI,则由引理2知0,X,Y也是图GNAI的3阶团,就有YDIXDIX1,与已知条件矛盾定义3全序集AI,上的长为KK1的链X0X1XK称为起点为X0的长为K的AI色链,如果对于0HJK有XHXJAI起点是X0的链的最大长记为LIX0如果起点是X0的长为K1的链不存在,就令LIX0SISI与0引理5AI1MAXLIAA证明设AI1,即对于任意AAI,据定义3有LIA0YAI,恒有YA从而有MAXLIAASI0,引理5成立由定义3知链X0X1XK的K1个元构成以下考察AI1KK1的情形GNAI的一个团,即得AI1MAXLIASI以下再证AI1MAXLIAAASI设AI1K2则GNAI中有K1个顶点按排序后得AI,上的长为K的链,再在AI,上所有长为K的链中取起点按来说最前面的一条,记为X0X1XK,我们断言一定有X0SI假若不然,即X0SI作ZN到自身的变换FXX,由引理2知这是GNSI的同构变换,从而也是GNAI的同构变换,它把GNAI中K1个顶点的团X0,X1,XK变成另一个团X0,X1,XK据定义3可知,这K1个元X0,X1,XK在AI,上构成长为K的链由定义2所规定的全序集AI,的排序方式可知这条AI色链可表示为X0X1XK,其起点X0X0因此,原来给定的链X0X1XK不是“起点按来说最SI为真从而有AI1MAXLIAA前”的一条,矛盾于是断言X0SI引理5得证引理5表明,为了计算GNAI的团数,只须寻求以A这样能够提高运算效率SI为起点的AI色的链就可以了3定理1的证明1取整数N215,则M107令S11,7,10,13,15,32,41,49,52,68,70,72,88,92,华南师范大学学报自然科学版2008年2897容易验证GNA12A2色链76763358848410135620按照上述理论,用计算机算得图GNA1中的第一条长度为30的588080100106106645111150222525535362787810455此后没有更长的A2色链据引理5有A21MAXL2AAGNA2A2132,据引理1有R3,33216S231,据引理3有为了简便,以下只写出整数N与参数集S1,以及计算得到的R3,Q的新下界2取整数N223,令S11,7,10,12,23,38,44,53,62,66,71,80,93,96,98,101计算得R3,342243取整数N227,令S11,5,7,24,28,49,51,60,63,66,74,76,92,96,106,108计算得R3,35228我们在CPU为AMD3600的计算机上完成上述运算的时间约为5H参考文献12李乔组合数学基础M北京高等教育出版社,1993GREENWOODRE,GLEASONAMCOMBINATORIALRELATIONSANDCHROMATICGRAPHSJCANADIANJOURNALOFMATHEMATICS,1955,717RADZISZOWSKISPSMALLRAMSEYNUMBERSJTHEELECTRONICJOURNALOFCOMBINATORICS,2006,DS111160吴康,苏文龙,罗海鹏8个经典多色RAMSEY数的新下界J南京师范大学学报自然科学版,2000,2331519吴康,苏文龙,罗海鹏5个三色RAMSEY数R3,3,Q下界J华南师范大学学报自然科学版,20002104110苏文龙,罗海鹏,李乔多色经典RAMSEY数RQ,Q,Q的下界J中国科学A辑,1999,295408413SUWENLONG,LUOHAIPENG,SHENYUNQIUNEWLOWERBOU