资源描述:
《对图论中一问题的探讨.doc》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、对图论中一问题的探讨刘爱兰(西北师范大学数学与统计学院10级数学与应用数学2班)摘要:Schur于1916年用图论中的结论证明了关于高维Ramsey数的Schur定理,在习题中提出=5,=14的特殊情况,本文就在此定理的基础上对=14进行了探讨.关键词:Ramsey数;Schur定理;探讨DiscussestheproblemsingraphtheoryAbstract:Withtheconclusionsofthegraphtheory,SchurprovedSchurtheoremsaboutthenumberofhigh
2、erdimensionalRamseyin1916,theproblemoftheproposed=5,=14ofthespecialcircumstancesisputforward,thisarticleisonthebasisofthistheoremtoarediscussedinthispaper.Keywords:Ramseynumber;Schurtheorem;DiscussSchur于1916年用图论中的结论证明了关于高维Ramsey数的Schur定理,本文对此定理的一个特殊情况作了探讨.下面先给出本文涉及到
3、的一些定义.定义1(完全图)任意二顶点皆相邻的图,记之为.定义2(Ramsey数)对任意取定的正整数m,m,任意取定以m个自然数为分量的向量.如果对的边任意进行m边着色,一定存在一个同色的子图,,n的最小值称为m维Ramsey数,记之为.注;;.一Schur定理定理(Schur定理)设为的任一分划,则,使中含有的解.证明:令,设是以为顶点的完全图,给进行边着色,使着以颜色.由Ramsey数的定义,可知,,使的色相同,不妨设为,且不妨设,.中的两个数之和等于中的.所以中有的解.注1设为满足上述条件的最小正整数,则.注2.下对,作
4、一简单证明.证明:①假设,这时,对,只有一种划分,且此划分中不存在满足条件的解,所以假设不成立.时,,有,满足题意,故.②由前面的定义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,则另一个集合中有满足方程的解;对的其他划分,都,使中含有的解.故对的任意划分,
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都不在同一个中,可以分以下几种情况:情况18或中有解;8,10或中有解;8,106所在的子集里有解.情况2此时划分可以根据7所在的集
6、合分为两类:①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所在的子集里有解.情况46或中有解;6,10或中有解;6,10,8或中有解;6,10,8,7或中有解;6,10,8,713所在的子集里有解.情况5此时划分可以根
7、据8所在的集合分为两类:①8中有解;8,9或中有解;8,9,7或中有解;8,9,711所在的子集里有解.②8中有解;8,10或中有解;8,10,9或中有解;8,10,9,7或中有解;8,10,9,711所在的子集里有解.情况66或中有解;6,8或中有解;6,8,7或中有解;6,8,7,13或中有解;6,8,7,139所在的子集里有解.情况7此时划分可以根据10所在的集合分为两类:①10中有解;10,9或中有解;10,9,11或中有解;10,9,11,6或中有解;10,9,11,67所在的子集里有解.②10中有解;10,8或中有
8、解;10,8,9或中有解;10,8,9,7或中有解;10,8,9,7,11或中有解;10,8,9,7,1112所在的子集里有解.情况87或中有解;7,6或中有解;7,68所在的子集里有解.情况98或中有解;8,10或中有解;8,106所在的子集里有解.情况10此时划分可以根据