對圖論中一問題的探討

1、對圖論中一問題的探討劉愛蘭（西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院 10級數(shù)學(xué)與應(yīng)用數(shù)學(xué)2班）摘要: Schur于1916年用圖論中的結(jié)論證明了關(guān)于高維Ramsey數(shù)的Schur定理，在習(xí)題中提出=5,=14的特殊情況，本文就在此定理的基礎(chǔ)上對=14進(jìn)行了探討.關(guān)鍵詞：Ramsey數(shù)；Schur定理；探討 Discusses the problems in graph theoryAbstract:With the conclusions of the graph theory, Schur proved Schur theorems about the number of higher dimensio

2、nal Ramsey in 1916,the problem of the proposed=5, =14 of the special circumstances is put forward,this article is on the basis of this theorem to are discussed in this paper.Key words: Ramsey number；Schur theorem；DiscussSchur于1916年用圖論中的結(jié)論證明了關(guān)于高維Ramsey數(shù)的Schur定理，本文對此定理的一個特殊情況作了探討.下面先給出本文涉及到的一些定義.定義1 （

3、完全圖）任意二頂點皆相鄰的圖，記之為.定義2 （ Ramsey數(shù)）對任意取定的正整數(shù)m，m，任意取定以m個自然數(shù)為分量的向量.如果對的邊任意進(jìn)行m邊著色，一定存在一個同色的子圖,，n的最小值稱為m維Ramsey數(shù)，記之為.注 ；.一 Schur定理 定理（Schur定理）設(shè)為的任一分劃，則，使中含有的解.證明：令 ，設(shè)是以為頂點的完全圖，給進(jìn)行邊著色，使著以顏色.由Ramsey數(shù)的定義，可知，使的色相同，不妨設(shè)為，且不妨設(shè)，.中的兩個數(shù)之和等于中的.所以中有的解.注1 設(shè)為滿足上述條件的最小正整數(shù)，則.注2 .下對，作一簡單證明.證明：假設(shè)，這時,對，只有一種劃分，且此劃分中不存在滿足條件的解

4、，所以假設(shè)不成立.時，有，滿足題意，故. 由前面的定義2及其注知，由注2知，又假設(shè)，則存在劃分，.，和中都不存在滿足方程的解，所以假設(shè)不成立，所以.對，考慮的任意劃分,如果或中的某一個集合中只有1，2，3，4，5中某一個數(shù)，則另一個集合中有滿足方程的解；如果或中的某一個集合中只有1，2，3，4，5中的兩個數(shù)：1，3或1，4或1，5或2，3或2，5或3，4或3，5或4，5，則另一個集合中有滿足方程的解；對的其他劃分 ，都，使中含有的解.故對的任意劃分，都，使中含有的解.綜上可知， .二 對Schur定理中情形的探討本文在上面定理的基礎(chǔ)上對的情況作一簡單探討.首先由下面反例知.因劃分 中任一子集無

5、的解，故.考慮的任意劃分,如果1,2,3,4,5處于的某兩個子集中，這時某中有解.下設(shè)每個含1,2,3,4,5中至少一個，如果1,2或2,4或1,3,4或1,4,5或1,2,3,5在同一個中，則該中有解.若1,2且2,4且1,3,4且1,4,5且1,2,3,5都不在同一個中，可以分以下幾種情況:情況1 8或中有解；8，10或中有解；8，106所在的子集里有解.情況2 此時劃分可以根據(jù)7所在的集合分為兩類：7中有解；7，8或中有解；7，86所在的子集里有解.7中有解；7，9或中有解；7，9，8或中有解；7，9，810所在的子集里有解.情況3 此時劃分可以根據(jù)6所在的集合分為兩類：6中有解；6，8

6、或中有解；6，8，7或中有解；6，8，711所在的子集里有解.6中有解；6，10或中有解；6，10，7或中有解；6，10，7，11或中有解；6，10，7，1113所在的子集里有解.情況4 6或中有解；6，10或中有解；6，10，8或中有解；6，10，8，7或中有解；6，10，8，713所在的子集里有解.情況5 此時劃分可以根據(jù)8所在的集合分為兩類：8中有解；8，9或中有解；8，9，7或中有解；8，9，711所在的子集里有解.8中有解；8，10或中有解；8，10，9或中有解；8，10，9，7或中有解；8，10，9，711所在的子集里有解.情況6 6或中有解；6，8或中有解；6，8，7或中有解；6

7、，8，7，13或中有解；6，8，7，139所在的子集里有解.情況7 此時劃分可以根據(jù)10所在的集合分為兩類：10中有解；10，9或中有解；10，9，11或中有解；10，9，11，6或中有解；10，9，11，67所在的子集里有解.10中有解；10，8或中有解；10，8，9或中有解；10，8，9，7或中有解；10，8，9，7，11或中有解；10，8，9，7，1112所在的子集里有解.情況8 7或中有解； 7，6或中有解； 7，68所在的子集里有解.情況9 8或中有解； 8，10或中有解； 8，106所在的子集里有解.情況10 此時劃分可以根據(jù)10所在的集合分為兩類：10中有解；10，6或中有解；10，6，11或中有解；10，6，11，,8 14所在的子集里有解.10中有解；10，8或中有解；10，8，13或中有解；10，8，13，12或中有解；10，8，13，12 ，7 或中有解；10，8，13，12 ，76所在的子集中有解；情況11 此時劃分可以根據(jù)6所在的集合分為兩類：6中有解；6，10或中有解；6，107所在的子集里有解.6中有解；6，8或中有解；6，8，11或；6，8，11，7或中有解；6，8，11，710所在的子集里有解.綜上可知，對的任一分劃，則