素数阶循环图和两个经典ramsey数r_8_n_的新下界

江西科学第17卷第2期VOL17NO21999年6月JIANGXISCIENCEJUN,1999文章编号10012367919990220072205素数阶循环图和两个经典RAMSEY数R8,N的新下界罗海鹏1,苏文龙211广西科学院,广西南宁53003121梧州一中,广西梧州543002摘要研究了素数阶循环图的基本性质,提出了寻求有效参数构造正则循环图的新方法,得到了2个经典RAMSEY数的新下界R8,16614,R8,17678这2个结果填补了关于RAMSEY数综述2的上下界表中的2个空白关键词RAMSEY数下界正则循环图中图分类号O1575TP312文献标识码A确定RAMSEY数是组合数学和图论中著名的难题1只有9个形如RM,NM3,N3,NM的RAMSEY数被确定2这9个RAMSEY数如表1表1被确定的9个形如RM,NM3,N3,NM的RAMSEY数N3456789M369141823283641825其他的RAMSEY数RM,N的值都还是未知的,人们常常用给出某个具体的RAMSEY数的上界或下界,并且不断地改进它们的方法,来逐步接近这个RAMSEY数的准确值对于R5,5,已知的情况是43R5,549前任美国数学会主席RLGRAHAM曾说过,在100年之内我们不可能获得RAMSEY数R5,5的准确值一般地说,用两种颜色对N阶完全图KN的各边任意染色要考察2NN1/2种情形,所遇到的计算量随着N的增大而呈指数型的增长,当N较大时即使借助于规模和速度非常之大的计算机也很难求得更多的RAMSEY数为了提高运算效率,以降低准确度为代价,三十多年来人们在用构造性方法研究RAMSEY数的下界时通常采用循环图的方法,即以正N边形为模型,把长度相同的边含对角线统一染成同一种颜色,理论上要考虑2N/2种情况人们借助于功能日益收稿日期1998204220修订日期1999203226基金项目广西自然科学基金资助项目桂科回字9817143作者简介罗海鹏1947,男,广东东莞市人,广西科学院研究员,1970年7月毕业于中国科学技术大学数学系应用数学专业第2期罗海鹏等素数阶循环图和两个经典RAMSEY数R8,N的新下界73强大的计算机构造循环图陆续得到一些新的成果但当N较大时寻求有效参数构造一般循环图仍然是极其困难的关于RAMSEY数R8,N,除了平凡的R8,28,要确定它们的准确值是非常困难的1990年BDMCKAY和张克民3利用11台SUN工作站运算了20000H证明了R8,328当N4时,目前仅知道3个不平凡的下界R8,4534、R8,5955和R8,82826除此之外,人们就只能根据上述结果利用熟知的递推公式7N1N21RM,RM,N11RM,N211计算出其他平凡的下界了为此我们研究了素数阶循环图的基本性质,大幅度地提高了计算机的运算效率,给出了多个RAMSEY数的新下界811本文进一步提出了寻求有效参数构造正则循环图的新颖有效的方法,得到了2个经典RAMSEY数的新下界素数阶循环图的同构变换给定素数P5,约定以下各项运算包括加、减、乘、乘方的结果都取模P同余归结到模P的剩余系1ZP1P/2,定义1选定参数集合,2,1,0,1,2,P1/2S0AJ1AJBJ1I并且有01时正则参数集合S3各元素的指数递增的步长A1,更快跑过集合Z,运算量大大减少了,能以较高的运算效率找到有效参数构造素数阶循环图,得到P一些RAMSEY数的较好的下界2个经典RAMSEY数的新下界根据上述理论,我们构造了2个素数阶循环图1给定素数P1613与图G边集的参数集合S11,2,3,6,8,9,10,12,19,22,23,27,28,30,31,37,38,39,43,44,47,54,56,57,60,61,64,65,66,67,68,74,76,77,79,81,82,83,84,86,88,90,94,100,111,116,117,123,128,129,130,131,134,136,141,142,143,156,159,161,162,166,168,169,171,172,173,180,182,183,184,188,190,191,192,195,197,198,200,201,204,211,213,216,217,219,220,222,224,226,227,232,233,234,238,240,243,245,247,248,252,253,255,256,260,263,265,270,271,272,277,280,286,287,289,294,296,298,3002给定素数P2677与图G边集的参数集合S21,2,5,8,9,11,14,15,16,18,21,23,32,35,37,39,40,43,44,46,47,51,53,54,58,59,62,63,64,70,73,74,75,77,80,81,85,87,88,89,92,93,95,99,100,102,103,107,115,116,117,119,124,126,127,129,131,135,137,139,140,144,145,146,148,150,151,155,163,171,173,175,176,419942013CHINAACADEMICJOURNALELECTRONICPUBLISHINGHOUSEALLRIGHTSRESERVEDHTTP/WWWCNKINET江西科学1999年第17卷76183,184,185,188,191,193,200,202,206,211,212,218,220,221,223,228,230,237,242,243,246,250,251,252,253,254,256,262,263,270,271,273,278,288,289,291,292,293,294,295,297,301,305,306,311,312,315,316,317,319,320,321,325,329,333,335,336在计算机上验证了如前定义的素数阶循环图G613S1中既不含8点团K8,也不含16独立点集K16循环图G677S2中既不含8点团K8,也不含17独立点集K17由于这些结论并根据RAMSEY定理,我们就证明了定理2R8,16614,R8,17678。上述2个结果填补了关于RAMSEY数综述2的上下界表中的2个空白参考文献李乔RAMSEY理论M长沙湖南教育出版社,1991146148RADZISZOWSKISPSMALLRAMSEYNUMBERSJTHEELECTRONICJOURNALOFCOMBINATORICS,REVISION,1997,1127MCKAYBD,ZHANGKE2MINTHEVALUEOFTHERAMSEYNUMBERR3,8JJOURNALOFGRAPHTHEORY,1992,1699105EXOOGAPPLYINGOPTIMIZATIONALGORITHMTORAMSEYPROBLEMSAINGRAPHTHEORY,COMBINATORICS,ALGORITHMS,ANDAPPLICATIONSYALAVIED,SIAMPHILADELPHIA,1989175179PIWAKOWSKIKAPPLYINGTABUSEARCHTODETERMINENEWRAMSEYGRAPHSJTHEELECTRONICJOURNALOFCOMBINA2TORICS,R6,1996,314BURLINGJP,REYNERSWSOMELOWERBOUNDSOFTHERAMSEYNUMBERSNK,KJJOURNALOFCOMBINATORIALTHEORY,SERIESB,1972,13168169黄益如RAMSEY极图的性质J上海大学学报,1995,13237240苏文龙,罗海鹏,李乔经典RAMSEY数R4,12、R5,11和R5,12的新下界J科学通报,1997,42222460苏文龙,罗海鹏,吴康经典RAMSEY数R5,12、R5,13、R5,14和R5,15的新下界J广西大学学报,1997,224298299罗海鹏,苏文龙,李乔经典RAMSEY数R6,12、R6,14和R6,15的新下界J科学通报,1998,431213361337苏文龙,罗海鹏,吴康若干RAMSEY数RN5的新下界J广西科学,1997,431831851234567891011PRIMEORDERCYCLICGRAPHANDNEWLOWERBOUNDSOFTWOCLASSICALRAMSEYNUMBERSR8,NLUOHAI2PENG1,SUWEN2LONG211GUANGXIACADEMYOFSCIENCES,NANNINGGUANGXI530031,PRC21WUZHOUFIRSTMIDDLESCHOOL,WUZHOUGUANGXI543002,PRCABSTRACTBASICCHARACTEROFPRIMEORDERCYCLICGRAPHWERESTUDIEDSOMESKILLSFORSEEKINGEFFECTIVEPA2RAMETERSTOSTRUCTUREREGULARCYCLICGRAPHWERERELEASEDNEWLOWERBOUNDSOFTWOCLASSICALRAMSEYNUM2BERSWEREOBTAINEDASFOLLOWSR8,16614,R8,17678TWORESULTSMENTIONEDABOV