对图论中一问题探讨.doc

对图论中一问题的探讨 刘爱兰 （西北师范大学数学与统计学院 10级数学与应用数学2班） 摘要: Schur于1916年用图论中的结论证明了关于高维Ramsey数的Schur定理，在习题中提出=5,=14的特殊情况，本文就在此定理的基础上对=14进行了探讨. 关键词：Ramsey数；Schur定理；探讨 Discusses the problems in graph theory Abstract:With the conclusions of the graph theory, Schur proved Schur theorems about the number of higher dimensional 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；Discuss Schur于1916年用图论中的结论证明了关于高维Ramsey数的Schur定理，本文对此定理的一个特殊情况作了探讨.下面先给出本文涉及到的一些定义. 定义1 （完全图）任意二顶点皆相邻的图，记之为. 定义2 （ Ramsey数）对任意取定的正整数m，m，任意取定以m个自然数为分量的向量.如果对的边任意进行m边着色，一定存在一个同色的子图,，n的最小值称为m维Ramsey数，记之为. 注 ；；. 一 Schur定理 定理（Schur定理）设为的任一分划，则，使中含有的解. 证明：令 ，设是以为顶点的完全图，给进行边着色，使着以颜色.由Ramsey数的定义，可知，，使的色相同，不妨设为，且不妨设，.中的两个数之和等于中的.所以中有的解. 注1 设为满足上述条件的最小正整数，则 . 注2 . 下对，作一简单证明. 证明：①假设，这时,对，只有一种划分，且此划分中不存在满足条件的解，所以假设不成立. 时，，有，满足题意，故. ②由前面的定义2及其注知，由注2知，又假设，则存在划分，.，和中都不存在满足方程的解，所以假设不成立，所以. 对，考虑的任意划分,如果或中的某一个集合中只有1，2，3，4，5中某一个数，则另一个集合中有满足方程的解；如果或中的某一个集合中只有1，2，3，4，5中的两个数：1，3或1，4或1，5或2，3或2，5或3，4或3，5或4，5，则另一个集合中有满足方程的解；对的其他划分 ，都，使中含有的解.故对的任意划分，都，使中含有的解. 综上可知， . 二 对Schur定理中情形的探讨 本文在上面定理的基础上对的情况作一简单探讨. 首先由下面反例知. 因划分 中任一子集无的解，故. 考虑的任意划分,如果1,2,3,4,5处于的某两个子集中，这时某中有解.下设每个含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 此时划分可以根据7所在的集合分为两类： ①7中有解； 7，8或中有解； 7，86所在的子集里有解. ②7中有解； 7，9或中有解； 7，9，8或中有解； 7，9，810所在的子集里有解. 情况3 此时划分可以根据6所在的集合分为两类： ①6中有解； 6，8或中有解； 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 此时划分可以根据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，8，7，13或中有解； 6，8，7，139所在的子集里有解. 情况7 此时划分可以根据10所在的集合分为两类： ①10中有解