【doc】素数阶循环图与经典ramsey数r（8,17）和r（8,19）的新下界

素数阶循环图与经典RAMSEY数R（8,17）和R（8,19）的新下界|O第15卷第3期1999年9月长沙交通学院JOURNALOFCHANGSHACOMMUNICATIONSUNIVERSRRYVOL15NO3SEPT1999文章壤号I0009779【199903000704素数阶循环图与经典RAMSEY数R8,17和R8,19的新下界垄兰姿,蒸圭垄,罗海鹏1长沙变通学院湖南长沙4100762广西计算中心,广西南宁5300223广西科学院广西南宁530031J摘要研究了素数骱循环圉的基本性质,提出了寻求有效参数构造正则循环圉的新方法,得到了2个经典RAMSEY致的新下界R8171702,R8191770它们超过了目前已知萎I602R8,19圉隶J2J廊IL闺关词啪3EY敷下界正则循环圉啦II鼻V1,L王L中田分类号O1575TP312文献标识码A确定RAMSEY数是组合数学和图论中着名的难题,只有9个形如RMNM/3,N/3,NM的RAMSEY数被确定,这9个RAMSEY数见表1其他的RAMSEY数RM,N的值都还是未知的人们常常用给出某个具体的RAMSEY数的上界或下裹1披确定的9个RAMSEY数R小H的值界并且不断地改进它们的方法,来逐步接近这个RAMSEY数的准确值一般地说把N阶完全圈K的各边任意染色要考察2一1种情形,所遇到的计算量随着N的增大而呈指数型的增长当较大时即使借助于规模和速度非常之大的计算机也很难求得更多的RAMSEY数为了提高运算效率降低准确度为代价,30多年来人们在用构造性方法研究RMREY数的下界时通常采用循环图舶方法,即以正N边形为模型,把长度相同的边古对角线统一染成同一颜色,理论上要考虑2H种情形人们借助于功能日益强大的计算机构造循环图陆续得到一些新的成果,但当N较大时寻求有效参数构造一般循环图仍然是极其困难的对于RAMSEY数R5,5,已知的最好下界是43,最好上界是49,即43R5,549现任美国数学会主席的GRAHAMRL曾说过“在100年之内我们不可能获得RAMSEY数R5,5的准确值“关于RAMSEY数R8,N,除了平凡的R8,28要确定它们的准确值是非常困难的1990年MCKAYBD和张克民L3采用穷举法,利用11台SUN工作站运算了20000H,证明了R8,328当4时目前仅知道7个不平凡的下界R8453,R85951,R8,8/2821和R8,17602,R818642,R819684,R820/762L7J除此之外人们就只能根据上述结果利用熟知的递推公式8为此,我们研究了素数阶循环图的基本性质,大幅度地提高了计算机的运算效率,给出了多个RAMSEY数的新下界本文进一步提出了寻求有效参数构造正则循环图的新颖有效的方法,得到了2个经典RMSEY数的新下界收稿日期19980622基金项目广西壮族自治区自然科学基金资助项目作者简介尤之速1943一,男长沙交通学院助理研究员1一LMRLNMR1M0R界F的凡乎触其出算汁8长沙变通学院第15卷1素数阶循环图的同构变换给定素数P5,约定以下各项运算包括加,减,乘,乘方结果都取模同余归结到模P的剩余系ZT1一P/2,一2,一1O,1,2,P1/2定义1选定参数集合SCZ12,P1/2,设图G的顶点集GZ,边集EGT,ITZY1SZ,Z,我们称图G为关于参数集合S的P阶循环图并记为GS上述表达式LZL表示复合运算先把Z2/的结果取模P同余归结到,再取绝对值归结到Z这里Z一0以下关于表达式LZL的意义也是这样引理1设G是的一个原根,则对于任意IZP,图GS和GS同构,其中参数集合SJJGXJ,SJ证明考察映射FG,有F一FG,于是FF铮,从而F作成顶点集VG的11变换易知L一2OJS舒LF一FLS,这就证明了图GS中的两个顶点F与F的相邻当且仅当GS中相应的两个顶点Z与相邻因此,F作成这两个图的同构变换2参数集合的正则条件与正则循环图定义2参数集合S所含相舁元素的个数FSF称为图GS的度数不考虑ISF1的简单情形定义3设G是P的一个原根,参数集合SI1,L旷,I,旷L,L一L称为正则的,如果FST2且满足正则条件0日L日2NLP一1/21和NLMINL12L,N2121,3日2,一,日L一日2一1/2N一22则参数集合是正则的P阶循环图,称为正则循环图定理1任意一个度数2的图GPS都同构于一个度数相同的正则循环图GS证明易知对于P的任意一个原根G都有LLGL,IZ因此,任意一个图GPS的参数集合可表示为SLLG6J,LG6J,】L其中1S112不失一般性,设061B2BP1/23注意到G是的原根,有G一1为了叙述方便,我们引进记号6BJP一1/21J,并且把集合S扩充注意蓟LLZ2LFL1J因此,扩充后的集合TLF,JGL,LJ,LGL,LGZ一只含个相异元素以这集合为参数集合作成的P阶循环图与图GS完全一样,以下仍然记为图GS由3式得0B1B2B声一1/2BLB2P一14设MMILLF一B1,B3B2,B2一B2一15注意到B】60,L一61J“,因此不姑设“I0F1一B,这里是1,2,N中的某一个对图S作变换FZG,据引理1知图GPS与图GS同构,其中SFF一一F,FG一F,盯一F,G,FRZF,GB一FF注意到,集合S中仍然只含个相异元素,淘汰重复元素重复的两个元素只保留一个后可表示为STLGL,LGL,LTJ,IG一TTLL第3期尤之速等素数阶循环图与经典RAMSEY数R8,17和R8,19的新下界记ABJBOI,则对于0,由4,5式得到AJ1一QBI1IBJM06并且有0LM2A3A一17D1RAINLALA0,D2一DI,一,一IA一28特殊的情形是I1此时由D的定义有D一1B一B1户一1/2一B1户一1/2一般地,当2I时由D的定义有A一1F一1一BFB一LP一1/2一B由3式知一1一B0,这就得到D一IP一1/2因此,当1I时恒有A一1P一1/2由7式知1式成立由6式得到D一LA一1一D一2D一2一D一3,D1一DOI一1即得M一1D一IP一1/2IP一1/2N一2由8式知2式也成立综上述可知,参数集合S满足正则条件这就证明了任意一个图GS都同构于度数相同的正则循环图GPS3探索RAMSEY数下界的新方法用循环图探索NMNSEY数下界的关键是寻找有效的参数通常的方法是凭经验选定一个适当的度数然后再运用“字典排列法“,度数太大或太小都不易获得有效参数,并且需要重复计算大量同构的图,运算量是非常巨大的,当IG较大时很难得到较好的结果本文的理论提供了一个新的方法,利用正则循环图可以避免大量同构的图的重复计算上述正则条件固定了参数集合的最小元素1,另一个元素ITI指数A只须在很小的范围内变动,而且度数随着A的增大而急剧减小特别是当N1时正则参数集合S各元素的指数递增的步长N,更快跑过集合Z,运算量大大减少了,能以较高的运算效率找到有效参数构造素数阶循环图,得到一些RAMSEY数的较好的下界4两个RAMSEY数的新下界根据上述理论,我们构造了两个素数阶循环图1给定素数P1701与图G边集的参数集合S1,2,3,8,12,13,16,18,19,21,25,27,29,31,37,38,44,46,49,53,56,57,6O,61,64,65,66,67,68,69,71,77,79,84,86,88,89,91,96,98,99,100,106,110,112,113,117,120,124,126,129,130,132,135,140,142,144,145,148,149,150,151,152,164,167,168,173,177,18L,186,188,189,191,194,195,200,202,203,206,214,218,222,223,225,226,228,229,230,232,239,241,243,247,248,253,262,270,279,289,290,291,292,295,296,302,303,304,306,307,312,313,319,320,322,327,328,332,333,334,335,338,339,340,342,348,3492给定素数P2769与图G边集的参数集合S,1,3,7,9,11,14,16,19,21,23,27,29,33,35,40,42,43,46,48,52,57,61,62,63,69,71,73,81,87,88,97,99,100,104,105,109,112,115,119,120,122,126,129,130,131,133,134,136,137,138,长沙交通学院第15卷142,143,144,146,148,151,155,156,163,164,167,171,173,176,179,182,183,186,189,202,206,207,209211,212,213,218,219,220,223,224,227,232,236,239,241,242,243,250,251,254,256,260,261,264,266,268,277,280,291,296,297,300,301,302,304,305,308,311,312,314315,316,317,325,326,327,329,331,332,335,336,337,340,341,343345,355357,358359,360361,362,365,366,367,368,370376,377,378,379,382我们在计算机上验证了如前定义的素数阶循环圈G70LS1中既不含8点团KB,也不含17独立点集17循环图G7S2中既不含8点团KB,也不含19独立点集19由于这些结论并根据RAMSEY定理,我们就证明了定理2R8,17702,R8,19770上述2个结果超过了目前已知的最好下界R8,17602和R8,19684参考文献1李乔RAMSEY理论M长沙朝南教育出版杜,19912RADZISZOWSKISPSMALLRAMSEYNUMBERSJTHEELEEAONICJMTMALOFCOMBINATORIESTREVISION199711273MCKAYBC,ZHANGKEMINTHEVALUEOFTHERANMEYNUMBERR38JJOINHALOFGRAPHTHEORY,199216991054EXOOGAPPLNGOPFIMIZATIONALGORITHMTORAMSEYPROBLEMSAINGRAPHTHEORY,COMBINATORIES,ALGORITHMSTANDAPPLICATIONSCSIAMPHILADELPHIA,198917517956789【101213PIWAKOWSKIKAPPLYINGTABUSEARCHTODETERMINENEWRARASEYGRAPHSJTHEELECTZONICJOURNALOFCOMHINATORICS,R6,1996314BURLINGJP,REYNERSWSOMELOWERBOUNDSOFTHERAMSEYNUMBEMK,K刀JOURNALOFCOMBINATORIALTHEOYSERIESB1972,13168169苏文龙罗海鹛,张正铀5个新的素数阶循环图J广西科学,1998,5I45黄益如RAMSEY极图的性质J上海大学1995,I3237240苏文龙罗海鹛,李乔经典RAMSEY敷R4,12,R511和R5,12的新下界J科学通报,1997,42222460苏文龙,罗海鹛,吴康经典RANMEY散R5,12,R5,13,R5,I4和R5,I5的新下界J广匿大学,1997,224298299LOUHAIPENG,SUWENLONG,LIQIAONEWIOWEZBOUNDSOFCLASSICALRAMSEYNUMBERSR6,12,R6,14ANDR615JCHINESESCIENCEBULLETIN,19984310817818苏文龙,罗海鹏,吴康若干RANMEY数R5的新下界J广西科学,1997,43183185尤之述,苏文龙罗海鹏RAMSEY数RIO3的新下界J长沙变通学院1998,141I3PRIMEORDERCYCLICGRAPHANDNEWLOWERBOUNDSOFCLASSICALRAMSEYNUMBERSR8,17ANDR8,19YOUZHISHU,SUWENGTONG,LUOHAIPENG1CHANGSHACONUNUNIV,CHENGSHA410076,CHINA2GUANGXICOMPUTERCENTRE,NANING530022,CHINA3GUANGXIACADEMYOFSCIENCESNANNING530031,CHINAABSTRACTSOMEBASICCHARACTEROFPRIMEORDERCYCHCGRAPHWERES