亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        對角Ram sey數(shù)R(22,23)的新下界

        2012-08-29 07:03:38許成章梁文忠
        梧州學(xué)院學(xué)報 2012年2期
        關(guān)鍵詞:自同構(gòu)下界子圖

        許成章,梁文忠

        (1.2.梧州學(xué)院,廣西 梧州 543002)

        對角Ram sey數(shù)R(22,23)的新下界

        許成章1,梁文忠2

        (1.2.梧州學(xué)院,廣西 梧州 543002)

        研究Ramsey數(shù)下界的問題,發(fā)現(xiàn)了Paley圖的一個新的自同構(gòu),形成計算Paley圖團(tuán)數(shù)的一個新方法,為解決Radziszowski問題提供一個新思路,獲得階段性成果:計算出14813階Paley圖的團(tuán)數(shù),得到一個對角Ramsey數(shù)的新下界:R(23,23)≥29629。

        Ramsey數(shù);下界;Paley圖;團(tuán)數(shù);自同構(gòu)

        1 引言

        英國數(shù)學(xué)家F.P.Ramsey[1]在1928年證明了一個定理,后世學(xué)者稱之為Ramsey定理,相關(guān)函數(shù)稱為Ramsey數(shù),于是確定Ramsey數(shù)就成為組合數(shù)學(xué)中非常困難的問題[2-4]。對于任意給定的整數(shù)n≥3,所謂對角Ramsey數(shù)R(n,n) 是指滿足如下性質(zhì)的最小正整數(shù)r:用兩種顏色把r階完全圖Kr的邊任意染色后,在Kr中一定有單色的Kr。

        人們對Ramsey數(shù)R(n,n) 所知甚少。數(shù)十年來,各國學(xué)者努力探索Ramsey數(shù)的上界和下界,試圖逐步逼近Ramsey數(shù)的準(zhǔn)確值.這是涉及到巨量運算的非常困難的一個NP-C問題,任何理論和方法上的創(chuàng)新以及所獲得的新成果,都能使人們對Ramsey數(shù)加深認(rèn)識而引起學(xué)術(shù)界的關(guān)注。

        關(guān)于研究Ramsey數(shù)的困難程度,匈牙利數(shù)學(xué)家Erdǒs說:“需要過上百萬年,人們才會得到一些認(rèn)識,甚至那時也不能達(dá)到完全的認(rèn)識”[3]147。曾任美國數(shù)學(xué)會主席的Graham猜測人們至少在100年內(nèi)發(fā)現(xiàn)不了 的準(zhǔn)確值[3]146。我國數(shù)學(xué)家李喬說Ramsey數(shù)研究的“這個問題是對人類智慧的真正挑戰(zhàn)”[3]17。

        1947年匈牙利數(shù)學(xué)家Erdǒs[5]首創(chuàng)概率方法得到對角Ramsey數(shù)下界的漸近估計.1955年美國數(shù)學(xué)家Greenwood和Gleason[6]首創(chuàng)構(gòu)造性方法,得到歷史上第一批Ramsey數(shù)的準(zhǔn)確值,其中兩個對角Ramsey數(shù)是這樣得到的:首先利用Paley圖計算出R(3,3)>5 和 R(4,4)>17,再用存在性的方法證明 R(3,3)≤6 和 R(4,4)≤18,就得到 R(3,3)=6 和 R(4,4)=18。

        所謂Paley圖,是指用4k+1型素數(shù)的二次剩余構(gòu)造的循環(huán)圖。美國學(xué)者Radziszowski的動態(tài)綜述論文[7]記錄了幾十年來學(xué)術(shù)界計算Paley圖的團(tuán)數(shù)和研究對角Ramsey數(shù)的非常緩慢的進(jìn)程:直到2002年,羅海鵬、蘇文龍等學(xué)者方才計算出4457、5501、8941階的Paley圖的團(tuán)數(shù),得到 R(17,17)≥8917、R(18,18) ≥11005、R(19,19) ≥17885[8]。Radziszowski希望學(xué)術(shù)界有所創(chuàng)新,推動Ramsey數(shù)的研究進(jìn)展,在http://www.cs.rit.edu/~spr/topics.html中提出如下問題:

        “計算20000階以內(nèi)的Paley圖的團(tuán)數(shù)”。

        注意到,用通常的方法計算Paley圖的團(tuán)數(shù),要反復(fù)計算大量同構(gòu)子圖,運算效率低下,因而這是非常困難的問題,迄今尚未見有文獻(xiàn)報道這個問題的研究進(jìn)展。筆者發(fā)現(xiàn)了Paley圖的一個新的自同構(gòu),能夠減少大量同構(gòu)子圖的重復(fù)計算,改進(jìn)了計算對角Ramsey數(shù)的方法,用計算機探索得到一個尚未見有文獻(xiàn)報道的新成果。

        2 Paley圖的二級導(dǎo)出子圖及其自同構(gòu)

        設(shè)p≥29是4k+1型素數(shù),Zp={-2K,…,-2,-1,0,1,2,…,2K}是有限域,約定以下所有運算結(jié)果都在模P同余的意義下歸結(jié)到Zp。

        定義1 設(shè)A是由模P的平方剩余形成的集。無向簡單圖Gp稱為Paley圖,其頂點集V(Gp)=Zp,邊集

        引理 A[9]設(shè) B= {x|x∈A,x-1∈A},Gp在 B上的導(dǎo)出子圖記為Gp[B],則Gp[B]有如下六個自同構(gòu):f0(x)=x,f1(x)=x-1,f2(x)=1-x-2,f3(x)=x(1-x)-1,f4(x)=x(1-x)-1,f5(x)=1-x,其中x∈B。

        上述自同構(gòu)確定的等價關(guān)系“~”把B分拆成如下若干個等價類。其中代表元是α的等價類記為〈a〉各等價類代表元形成的集記為N 。

        引理 B[8]|B|= (p-5)/4。設(shè) S=|B|mod 6,則有S=0,2,3,5四種情形。B1中的等價類一般都是如①所示的6元集,當(dāng)且僅當(dāng)S=0時B中的等價類都是6元集,當(dāng)且僅當(dāng) S=2或S=3時在B中有一個S元等價類,當(dāng)且僅當(dāng)S=5時在B中有一個2元等價類和一個3元等價類。

        不妨把上述所說的導(dǎo)出子圖、自同構(gòu)和等價類分別稱為一級導(dǎo)出子圖、一級自同構(gòu)和一級等價類,本文在此基礎(chǔ)上引進(jìn)圖的二級導(dǎo)出子圖、二級自同構(gòu)、二級等價類等新概念。

        定義 2 設(shè) B1=B={x|x∈A,x-1∈A} ≠○,A a∈B1,令 B2= {x|x∈B1,x-a∈A},稱a為B2的導(dǎo)出元,B2為a的導(dǎo)出集。

        定理1 設(shè)a∈B1是B2的導(dǎo)出元,令

        證明 易知f1作成Zp的一個置換。注意A到a∈B1∪A,由 B1,B2,f1的定義與 A 的性質(zhì),x,y∈B1∪A,當(dāng) xy≠0 時有

        3 全序“ ”與B2的改進(jìn)

        4 計算Paley圖團(tuán)數(shù)的一個新方法

        我們運用一般的計算機完成上述兩例的計算,耗時不到1s.

        5 主要結(jié)果

        在CPU為Intel·i3/2100的計算機上,我們完成上述運算大約耗時70h。

        [1]Ramsey F P.On a problem of formal logic[N].Proceedings of the London Mathem aticalSociety,1930,30:264~286.

        [2]R.L.Graham,B.L.Rothschild,J.H.Spencer.Ram sey theory[M].JohnWiley&Sons,1990.

        [3]李喬.拉姆塞數(shù)理論[M].長沙:湖南教育出版社.1991.

        [4]李喬.組合數(shù)學(xué)基礎(chǔ)[M].北京:高等教育出版社,1993.

        [5]P.Erd·s.Some remarks on the theory of graphs[J].Bulletin of the American Mathematical Society,1947,53:292~294.

        [6]R.E.Greenwood and A.M.Gleason,Combinatorial relations and chromatic grap hs[J].Canadian JournalofMathematics,1955(7):1~7.

        [7]S.P.Radziszowski.Small Ramsey Numbers[J].The Electronic Journalof Combinatorics,View the Journal,Dynam ic Surveys,2011,August22 ElJC revision#13,2011,DS1.13:1~84

        [8]Luo Haipeng,SuWenlong,Li Zhengchong.The properties of self-complementary graphsand new lower bounds for diagonal Ramsey numbers[J].Australasian Journal of Combinatorics,2002(25):103~116.

        [9]SuWenlong,Luo Haipeng,LiQiao,Lowerbounds formulticolor Classical Ramsey Numbers[J].Science in China(seriesA),1999,42(10):1019~1024.

        New Lower Bounds for Diagonal Ram sey Numbers R(22,23)

        Xu Chengzhang1,Liang W enzhong2
        (1.2.W uzhou University,W uzhou 543002,China)

        The paper studies the lower bounds for Ramsey numbers.In light of a new discovery automorphism of Paley Graphs,a new method of computing clique numbers of Paley graphs is proposed,which sheds new light on solving the problem raised by Radziszowski.Staged results are obtained:the clique number of Paley graphs with order 14813 is computed and a new lower bound for diagonal Ramsey numbers R(23,23)≥29629 is obtained.

        Ramsey number;lower bound;Paley graph;clique number;automorphism

        O157

        A

        1673-8535(2012)02-0075-06

        許成章(1976-),男,廣西梧州人,梧州學(xué)院講師,研究生,主要研究方向:圖論、組合數(shù)。

        梁文忠(1963-),男,廣西賀州人,梧州學(xué)院副教授,研究方向:組合數(shù)學(xué)的研究。

        (責(zé)任編輯:高 堅)

        2012-01-12

        國家自然科學(xué)基金資助項目(60563008);廣西自然科學(xué)基金項目(0991278);廣西教育廳科研項目(200911LX433);梧州學(xué)院科研項目(2009B013,2009B011)資助

        猜你喜歡
        自同構(gòu)下界子圖
        一類無限?ernikov p-群的自同構(gòu)群
        關(guān)于有限Abel p-群的自同構(gòu)群
        臨界完全圖Ramsey數(shù)
        剩余有限Minimax可解群的4階正則自同構(gòu)
        Lower bound estimation of the maximum allowable initial error and its numerical calculation
        基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
        矩陣Hadamard積的上下界序列
        最大度為10的邊染色臨界圖邊數(shù)的新下界
        有限秩的可解群的正則自同構(gòu)
        常維碼的一個構(gòu)造性下界
        日韩一线无码av毛片免费| 一二三四区中文字幕在线| 久久不见久久见免费影院国语| 欧美黑人巨大xxxxx| 亚洲国产字幕| av在线入口一区二区| 医院人妻闷声隔着帘子被中出| 婷婷成人基地| 亚洲最稳定资源在线观看| 日本少妇熟女一区二区| 久久亚洲精品成人无码| 亚洲精品成人片在线观看| 国产小车还是日产的好| 偷拍视频网址一区二区| 成人做受视频试看60秒| 9999精品视频| 一区二区三区观看在线视频| 免费a级毛片又大又粗又黑| 67194熟妇在线永久免费观看 | 免费在线视频一区| 一区二区三区少妇熟女高潮| 爽爽影院免费观看| 国自产偷精品不卡在线| 97超级碰碰碰久久久观看| 国产三级av大全在线爽| 特级精品毛片免费观看| 在线视频制服丝袜中文字幕| 精品一区二区亚洲一二三区| 久青草影院在线观看国产| 少妇脱了内裤让我添| 欧美人与动牲交片免费| 青青草视频是针对华人| 99视频30精品视频在线观看| 国产成人啪精品午夜网站| 国产一区二三区中文字幕| 欧洲熟妇色xxxx欧美老妇软件| 美女自卫慰黄网站| 亚洲一区二区三区成人在线| 熟女一区二区三区在线观看| 欧洲人妻丰满av无码久久不卡| 午夜无码熟熟妇丰满人妻|