（应用数学专业论文）ramsey理论中若干问题的研究.pdf

摘要 中文摘要 本文我们主要研究r a m s e y 理论中的以下三个问题 ( 1 ) 在c a r o ，l i ，r o u s s e a u 和z h a n g 给出的r ( c ，) 的渐近上界的基础上，我们由 分析方法得到了r ( 啊。，) 的渐近上界即：当n 趋向于无穷时，对于不小于4 的偶数 m ，有 帆矧 0 b yt h es a m em e t h o d ， w eo b t a i nt h ea s y m p t o t i cr e l a t i o nb e t w e e nr ( 矸，m ，) a n dr ( ，) c o m b i n i n gw i t ht h e s p e n c e r sa s y m p t o t i cl o w e rb o u n d sf o rr a m s e y f u n c t i o n sw eo b t a i nt h ea s y m p t o t i cb o u n d sf o r r ( k 4 ，) m o r e o v e r ，w eg i v et h ea s y m p t o t i cu p p e r b o u n d sf o rr ( g k + c m ，) ，i ea sn _ ， 慨耶( - 俐蚓m ) ( 赤) 蚪八一2 ” f o r f i x e de v e n m 4a n d ，c 凰+ g 。，丘名，sc + 。e t ，岛c 。，f ，兰：燮l o g n 、1 。+ 2 “”一” f o rf i x e do d dm23 ，b ye m p l o y i n gm a t h e m a t i c a li n d u c t i o no nk ，w i t ht h eu p p e rb o u n d sf o r r ( w k ，) v e r i f i e d f i r s t ( 2 ) l ih a sp r o v e d ar a m s e yg o o d u e s sr e s u l tf o rg r a p h sw i t hm a n yp e n d e n te d 9 8 一i ”p i 。d b yt h i s b yt r a n s p l a n t i n gl i sm e t h o da n d m a t h e m a t i c a li n d u c t i o no nx ( g ) ，w eg 8 8 。y 9 0 0 d n e s sr e s u i tf o rg r a p h sw i t h al a r g ep e n d e n tt 嗡i el e t 日b ea n yc o n n e c t e dg r a p ho f o 。d e r 硕士学位论文；r a m s e y 理论中若干问题的研究 n a n d l e t h | b e ag r a p ho f o r d e r n + jw h i c h i so b t a i n e d f r o m hb ya d d i n g 氆p e n d e n t j t r e e ， a n dl e t 坞d e n o t et h ec l a s so fa l lg r a p h s ：马，i f j i s l a r g ee n o u g h ，t h er a m s e yn u n b e rr ( a ，玛) s a t i s f i e sr ( a ，h j ) = ( x 一1 ) ( n + j 一1 ) + s ( 3 ) z h o u h a sp r o v e dt h a tr ( b m ，砰，n ) = 2 n + 1f o rm 1 ，忆5 m + 3a n dr ( b m ，k 2 + g ) = 2 n + 3f o rn29i f m = 1o rn ( ，n 一1 ) ( 1 6 m 3 + 1 6 m 2 2 4 m 一1 0 ) + 1i f m22 w h e r et h eb o o kb m i s t h e j o i n k 2a n d 碟，d e n o t e sa w h e e l w i t h ns p o k e s g u h a sg i v e nr ( b i ，k l + 晶) = 2 n + 1 f o rn 3a n dr ( b m ，k 1 + t n ) = 2 n + 1f o rm 1 ，礼5 m + 2 t h ea b o v et w oa r ea l s or a m s e y g o o d n e s sr e s u l t i n s p i r e db yt h e s e ，w eo b t a i nk 2 + i sk 3 一g o o db y c o m b i n a t o r i c a lm e t h o d a n dm a t h e m a t i c a li n d u c t o i no i lnw i t hr ( 虬，鲍+ t 4 ) = 1 1v e r i f i e df i r s t k e y w o r d s ：r a m s e yn u m b e r s ；w h e e l s ；i n d e p e n d e n tn u m b e r ；c o m p l e t eg r a p h s ；p e n d e n t t r e e ；c h r o m a t i cn u m b e r ；t r i a n g l e 序言 第一章序言 1 1r a m s e y 理论的发展与现状 在一个六个人的群体中，必定有三个人互相认识或互相不认识当无限大时，如 果对阶完全图的边集进行红、蓝二着色，则存在某个无限大的集合mcn ，所有连 接集合m 中点的边获得同样的颜色以上这两个论断都是r a m s e y 在1 9 3 0 年提出的一 个定理的特例这个由r a m s e y 最初提出的定理已经在许多方面获得推广，产生了现今人 们所称的r a m s e y 理论，一个表达了深厚的数学原理的博大精深的理论分支。它推广 了鸽笼原理：即无论我们如何将一个大的系统划分成小的集合，必定存在某 个集合中含有该大系统的子系统在r a m s e y 理论中我们也是要寻找在同一个集合中 的大的子系统：我们不仅需要无限多的红边，我们还需要连接一个无限大点集的所有的 边必须是红的比如，在第一个例子中，我们不仅需要三对互相认识，还需要这三个熟 人构成一个三角形 r a m s e y 理论揭示了数学中一个重要的哲学思想：无序是相对的，当量达到一定程度 时，某种有序的结构必定出现。r a m s e y 数则定义为保证这种结构必定出现的量的最小 值有人认为，数学归纳法和l h m s e y 理论是数学的两大分支。数学归纳法是从有限情形 推知无限情形的方法，而r a m s e y 理论是研究从无限情形中发现有限个例外情形r a m s e y 数相当于数学归纳法所要的最小奠基数数学归纳法所要的奠基数通常易于发现，而确 切的r a m s e y 数一般很难断定 经典的r a m s e y 理论涉及到比图更丰富的数学结构，这一点体现在先于r a m s e y 定理 提出的v a dd e rw a e r d e n 定理，它指出：给定正整数护，如果是足够大的整数，我们 把数集f 1 ，2 ，w ) 分成k 个子集合，则必存在某一个子集合，其中含有参数为p 的数 项级数 r 。r n s e y 理论是组合学的一个美丽而广泛的领域，许多数学分支的技巧和方法被广泛 的应用于该领域，使得她获得了蓬勃的发展；同时，r a m s e y 理论中的许多结果又反作用 与其他学科，对图论和组合学产生了巨大影响。目前集合论、数理逻辑、分析、代数、几 一1 一 堡主兰焦论文! r a m s e y 理论中若干问题的研究 何等领域中都有r a m s e y 理论的应用 1 9 3 0 年，英国青年数学家f r a n k r a m s e y 在关于数理逻辑的一篇基础性文章中给出如 下的r a m s e y 定理：给定正的自然数，和n ，如果n 充分大，而且集合x ： l ，2 ， 的所有k 元子集用r 种颜色任意的着色，则必定存在x 的一个n 元子集y ，使得y 的 所有元子集具有同样的颜色就是这个定理奠定了r a m s e y 理论的基础。 起初r a m s e y 定理并没有受到人们的重视，直到1 9 3 5 年p a u le r d 5 s 和g e o r g es z e k e r e s 获得了一个重要发现，即：对于任意整数m2 2 和n 2 ，r a m s e y 数r ( m ，n ) 存在并满 足r ( m ，n ) r ( m 一1 ，n ) + n ，n 一1 ) ；r ( m ，n ) sg m 一+ n 1 2 直到如上这个e r d s s s z e k e r e 8 定理的发现，人们才对r a m s e y 定理普遍关注。 十九世纪七十年代以前这方面理论研究的文章并不多见。为庆祝p a u le r d s s 的6 0 岁 生日， 1 9 7 3 年在匈牙利巴拉顿湖举行组合论大会这次大会是r a m s e y 理论发展史上的 一个里程碑，在这次大会上有二十多个报告是关于r a m s e y 理论的会后许多文章被发 表。大约4 0 多篇文章被归入广义r a m s e y 理论类别，美国数学会主办的m a t h e m 。t i c a l r e v i e w s 将这一类文献的索引号记为0 5 c 5 5 。这个学科的发展极为迅猛，尤其是关于各 种类型的r a m s e y 数的渐近界的研究此外，在最近十年小图的r a m s e y 数( s m a l lr a m s e y n u m b e r ) 的研究也取得了相当大的进展，而这些进展的取得主要归功于计算机算法的应 用。 但是有很长一段时间经典的r a m s e y 数的计算进展不是很快。现在所得到的非平庸 的经典的r a m s e y 数r ( m ，礼) 列表如下 3456789 3691 41 82 32 8 3 6 41 82 5 从上表可见，我们所得到的经典的r a m s e y 数的具体数值几乎很少，这个领域的研究 并非易事。其中r ( 3 ，9 ) 就是由我国数学家张克明应用计算机算法获得的 不象经典的r a m s e y 数，广义r a m s e y 数方面我们获得了较多的准确结果。而且他 们中的大部分还非常著名广义r a m s e y 数主要分为三大类：r a m s e yg o o d n e s s 问题、 2 一 序言 d e g e n e r a t e 问题、“b o o k ”问题 目前，r a m s e y 理论的研究方法正处于由初等方法向高等方法过渡的阶段现代的 研究方法主要包括分析方法( a n 由t i em e t h o d ) 、概率方法( p r o b a b i l i s t i cm e t h o d ) 、代数方 法( a l g e b r a i cm e t h o d ) 一3 硕士学位论文：r a m s e y 理论中若干问题的研究 1 2 基本概念和表示法 本文中我们应用b o l l o b 拈【4 】所著的现代图论中的基本概念和术语我们说g ，= ( ，) 是g = ( k e ) 的子图( s u b g r a p h ) ，如果y ，e ，记作g g 如果g 是g 中所有连接中两顶点的边构成的，则g 称为g 的由v 导出( i n d u c e d ) 或生成 ( s p a n n e d ) 的子图，记作g v 7 如果v 7 = v ，则g 称为g 的生成( s p a n n i n g ) 子图如 果阿v ( a ) ，而且e ( g 吲) = 西，则我们说是g 的一个独立集( i n d e p e n d e n ts e t ) 。 g 的所有独立集的最大基数称为g 的独立数( i n d e p e n d e n c en u m b e r ) 。 如果我们用某些种颜色给图g 的顶点着色，把具有同种颜色的顶点集称为g 的一个 色部( a c o l o rd a s s ) 。图g 的一个适宜的点着色，或简单地称为点着色，是指图g 的某一 种着色，使相连的顶点着不同种颜色对图g 进行点着色，有一种着色所需要的颜色数最 少，我们称这个颜色数为g 的色数，记为x ( a ) 。我们用s ( a ) 表示用x ( a ) 种颜色给图g 点着色的各种方案中最小的色部所含的顶点数，称为色数剩余。如果p 1 p 2 p k ， 则x ( k ( p l ，p k ) ) = ，且s ( k ( p l ，m ) ) = p 1 对于完全图k ，我们用红、蓝两种颜色对其边进行着色，把所有的红边导出的子 图( 包含所有的孤立点) 记为( r ) ，或简单地记为r 。类似地，所有的蓝边导出的子图 ( 包含所有的孤立点) 记为( b ) ，简记为b 。在图g 的某一红、蓝着色中，对于任意一 点u ，我们把所有与u 在( r ) 中相连的点集合叫做u 的红邻域，记为n n ( u ) ，相应地， 有蓝邻域n b ( u ) 。红邻域中所含点的个数叫做u 的红度，记为d n ( u ) ，相应地，有蓝度， d 日( “) 。且d r ( u ) = i n r ( u ) l ，d b ( u ) = i 丑( u ) i 图k 和日的和( j o i n ) ，记为k + 日，是在点不相交的k 和h 的基础上，将 u v ( u 矿( k ) ， y ( 日) ) 加到边集中形成的图。即k + h 的顶点集为v ( k ) u v ( h ) ，边 集为e ( k ) u e ( h ) u u v ( u y ( 耳) ，u y ( 日) ) 。 我们用j g 表示p 个顶点的完全图用，。表示完全二部图。k 1 ，。称为星( s t a r ) 长为n 的路和圈分别记作p 扎和g 。无圈的连通图称为树( 打e e ) 书b h 是指施与耳m 的和，即b 。= 砀+ 瓦。= k 1 + k 1 ，。= k l ，l ，。w r m = k i + g 表示有m 个辐条的轮， 其中l 为其轴心。 一d 一 序言 设g 和日是无向简单图，g 和日的r a m s e y 数r ( g ，h ) 是指最小的正整数，使 得对于阶完全图k n 的边集的任何一种红、蓝着色中，要么，g 包含于红边生成的子 图( 包含孤立点) ，要么日包含于蓝边生成的子图( 包含孤立点) 它的一个等价定义是：设g 和日是无向简单图，g 和目的r a r n s e y 数r ( g ，h ) 是 指最小的正整数，使得对于任意的阶图f ，要么f 包含g 作为其子图，要么f 的 补图f 包含日作为其子图。 若g = k m ，h = i f ，则记r ( 玛。，k n ) = r ( m ，n ) ，称之为经典的p 阻m s e y 数；如果 g 或者日不是完全图，则称r ( g ，h ) 为广义的r a m s e y 数本文我们研究的都是广义的 r a m s e y 数若g = h ，则记r ( e ，g ) = r ( g ) ，称之为对角r a m s e y 数。 易见，r ( g ，h ) = r ( h ，g ) ；对于图g 和日，如果g 和日分别是g 和日的子图， 则r ( ，h ) r ( g ，h ) 。 另外，有两个平庸的结论r ( k 1 ，g ) = 1 ，r ( k 2 ，g ) = l y ( g ) i 一5 硕土堂位论文：r a m s e y 理论中若干问题的研究 1 3 主要结论和主要方法 在这篇论文中我们研究如下的r a m s e y 理论中的三个问题： 首先，在c a r o ，l i ，r o u s s e a u 和z h a n g 给出的r ( 0 k ，k n ) 的渐近上界的基础上，我们 用分析方法给出r ( w ，m ，) 的渐近上界，这里用到函数 i m ( 。) ：， j 0 2 7 o ；m 1 也是用同样的方法，我们得出r ( w m ，) 和r ( c ，) 渐近关系结合 s p e n c e r 给出的r a m s e y 函数的渐近下界，我们也得出r ( 凰，矗) 的渐近上、下界这个结 果正好和前人用其他方法给出的结果相吻合此外，我们在已证明的r ( w ，m ，) 的渐近 上界的基础上，对k 应用数学归纳法得出r ( 凰+ c k ，墨。) 的上界， 这一章我们用到的主要思路是： 设g 是阶为n = r ( 仉，m ，j k ) 一1 的i 临界图，即g 不含有矿纛作为其子图，而且 o ( g ) n 一1 贝4 ( 1 ) 点v 的度至多为r ( g 。，) 一1 ( 2 ) g 。的最大度进而平均度至多为r ( f 乩) 一l ，这里p m 一1 表示长 为m 一1 的路( p a t h ) 。 从而 n o ( g ) ( r ( c m ，墨。) 一1 ) n 厶( r ( g t ，j 0 ) ) 再将r ( g 矗，) 的渐近上界代入上式，在无穷远处应用分析计算，求出渐近上界。 第二，l i 曾证明：若g 的参数为x 和8 ，将一个连通图爿增加足够多的悬挂边，形 成h j ，则集合h ，是g g o o d 的通过移植l i 的方法，我们得到将一个连通图h 增加 足够大的悬挂树，形成马，则集合玛是g g o o d 的这里用到的主要方法是对x ( g ) 使用数学归纳法：x ( g ) = l 提供归纳假设的基础。当x ( g ) 2 时，去掉g 的最大色部得 g ，由归纳假设知当j 充分大时，h j 是g 一g o o d 的在此基础上推出玛是g g o o d 一6 一 序言 的 第三，我们考虑对完全图g = 鲍l 的红、蓝二着色取任意的 v ( g ) ，则2 d r ( v ) 5 。我们按照d r ( v ) 的大小来分类讨论，确定每一条边的颜色，利用反证得出 r ( 蚝，+ t 4 ) s1 1 再在r ( k 3 ，+ 孔) = 1 1 的基础上，利用归纳法得出鲍+ t ni s 凰一g o o d 的。这一证明主要通过给出若干事实导出矛盾 7 硕士学位论文： r a m s e y 理论中若干问题的研究 第二章轮对完全图的r a m s e y 数的渐近上界 h o = i + c k 表不曹有m 个辐条的轮这一苹主要研究袷( w h e e l ) 对完全图的 p , a m s e y 数的渐近上界其中包括：第一，当n _ o 。时，对于不小于4 的偶数m ，有 r ( ，) 墨( 1 + 。( 1 ) ) g 。( _ 嚣) “_ 2 7 阳 2 ；对于不小于3 的奇数m ，有，( ，) s ( 1 + 0 ( 1 ) ) 仍( 露r ”“叫其次，我们得出当。日寸，。( 南。纠酬 ( 1 + 。( 1 ) 1 ：岛这一推论，它跟前人用其他途径证明的结果恰好吻合此外，我们给出轮 的推广图( 虬+ g 。) 对完全图的p n m s e y 数的渐近上界，即：对于不小于4 的偶数m ， 有r ( 凰+ c k ，) ( 1 + 。( 1 ) ) e 5 ( m ) ( 溃i ) “7 ”州；对于不小于3 的奇数数m ，有 r 呱+ ，) s ( 1 + 。【1 ) ) g ( m ) f ( 簪) 2 1 基本定义和背景 c h v j t a l f l4 曾证明了对于任意的m 阶的树了k 有r ( t k ，坼。) = 1 + ( m1 ) ( n 1 ) 。作 为s p e n c e r 的结论f 3 1 】的一个推广f 2 7 】指出对于连通图g ，当且仅当g 是树( k r e e ) 时， r ( g ，e 。) 的值关于n 是线性的，而当g 中含有圈( c y c l e ) 时情况就复杂得许多( 可参见本 文引理2 ) 非线性的问题是目前国际上研究的热点，而且对此类问题的研究主要集中在 r a m s e y 数的渐近上界研究方法包括分析、代数( 有限域) 、概率方法( 基本估计) 本 章主要应用近几年来国际上兴起的一类分析方法，它是借助于高斯超几何函数得到的一 个非常有效的函数 对于r ( 仇，) 的研究起始于b o n d y 和e r d s s ，他们在【3 中给出r ( 吼，矗) ! k n 2 后来，e r d 5 s ，f a u d r e e ，r o u s s e a u 和s c h e l p 在1 1 6 中把上界改进为c ( k ) n + 13 加，这里 m = ( k 一1 ) 2 i ，c ( 七) 是关于k 的正数。s p e n c e r 在 8 1 中给出了一个r ( c ，k n ) 的一般 下界对于m ：4 的情形，大约1 9 8 0 年左右，s z e m e r 6 d i 和e r d h s 分别在报告中指出 帕川c ( 赤) 2 然而，由于没有正式发表，所以证明的细节后来被人们遗忘了 一8 硕士学位论文：r a m s e y 理论中若干问题的研究 第二章轮对完全图的r a m s e y 数的渐近上界 孵n = k 1 + ( k 表示舍有m 个辐条的轮这一章主要研究轮( w h e e l ) 对完全图的 p m m s e y 数的渐近上界其中包括：第一，当n _ o 。时，对于不小于4 的偶数m ，有 r ( ，凰) ( 1 + 。( 1 ) ) g 1 ( _ 嚣) 2 ”_ 2 7 ”- 2 ；对于不小于3 的奇数m ，有，( ，) s ( 1 + o ( 1 ) ) 伤( 带)其次，我们得出当n - o 。时，c ( i 而n ) 5 2 兰r ( k 4 ，k n ) ( 1 + o ( 1 ) ) 毒知这一推论，它跟前人用其他途径证明的结果恰好吻合此外，我们给出轮 的推广图( 讯+ c k ) 对完全图的r a m s e y 数的渐近上界，即：对于不小于4 的偶数m ， 有r ( 讯+ c k ，编) ( 1 + 。( 1 ) ) 晚( m ) ( i 去) “7 “- 2 ”；对于不小于3 的奇数数m ，有 r ( 甄十，) ( 1 + 。0 ) ) o d i n ) ( 正譬) 2 1 基本定义和背景 c h v a t a l 【1 4 曾证明了对于任意的m 阶的树有r ( ，) = 1 + ( m 1 ) ( n 一1 ) 。作 为s p e n c e r 的结论【3 1 】的一个推广【2 7 指出对于连通图g ，当且仅当g 是树( t r e e ) 时， r ( g ，) 的值关于n 是线性的，而当g 中含有圈( c y c l e ) 时情况就复杂得许多( 可参见本 文引理2 ) 。非线性的问题是目前国际上研究的热点，而且对此类问题的研究主要集中在 r a m s e y 数的渐近上界。研究方法包括分析、代数( 有限域) 、概率方法( 基本估计) 本 章主要应用近几年来国际上兴起的一类分析方法，它是借助于高斯超几何函数得到的一 个非常有效的函数。 对于r ( 仇，j ) 的研究起始于b o n d y 和e r d s s ，他们在【3 中给出r ( 瓯，) k n 2 。 后来，e r d 6 s ，f a u d r e e ，r o u s s e a u 和s c h e l p 在1 1 6 中把上界改进为c ( ) n ( “+ 1 ) m ，这里 m ：l ( k 一1 ) 2 j ，c ( k ) 是关于女的正数。s p e n c e r 在【3 1 中给出了一个r ( c ，k n ) 的一般 下界。对于m ：4 的情形，大约1 9 8 0 年左右，s z e m e r 6 d i 和e r d s s 分别在报告中指出 帕蕊) l o g ( _ x m - ) 一- 1 ，。 r 茁 ( 2 3 ) ( 令( x m ) = l 十u ，上面最后一个不等式等价于( 1 十2 u ) l o g ( 1 + “) “，由l o g ( 1 + “) “( 1 + u ) 知该不等式对于所有的u 0 都成立参见 1 1 】) 而且，参见 2 5 】，我们可以知道：当z m 时， ，n ( z ) 21 ( 1 + )( 2 4 ) 下面的引理1 给出这一章我们所需要的独立数的下界对于点”g ，在本章下面 的行文当中，我们用g 。表示由”在g 中的邻域所导出的g 的子图 引理1 设g 是一个含有个顶点，平均度为d 的图。如果对于任何一点 g ，g 。的 平均度至多为a ，则o ( g ) n 厶+ l ( d ) 这个引理的证明参见【2 5 】。 结合r ( c k ，) 的渐近上界和引理l ，我们得到下面的r ( w ，m ，j 0 ) 的渐近上界 定理1 ( i ) 对于任意取定的偶数m 4 ，当n 充分大时，有 慨鲫+ o ( 1 ) 删m ) ( 去) 怛一2 胁， 其中岛( m ) = 型哗业 ( i i ) 对于任意取定的奇数m 3 。当n 充分大时，有 概 吐( g ) n 厶( r ( ，) 一1 ) 2 矗( r ( g k ，) ) ， ( 2 5 ) 这里a = r ( 蹋乩甄) = ( m 一2 ) ( n 一1 ) + l ( ”o ( 1 ) ) 南l o g 毗 蒜( 去) 州吨， 故当n 一。时， 怖川珊1 0 ， 使得 啦g 川，( 南) 沁卜”“一2 1 证明从略。 引理2 是如下的s p e n c e r 的结论【3 1 】的一个推广 引理3p ，对于任意取定的整数m 3 ，存在常数c 0 使得 临川c ( 赤) 一v 押。2 7 证明从略 下面一个引理4 我们给出的r ( c k ，) 与r ( 研。，) 的渐近关系 硕士学位论文： ! ：t a m s e y 理论中若干问题的研究 引理4 对于任意取定的整数m 3 ，当n 一时，有 r ( ，) ( 1 + 。( 1 ) ) ( m 一2 ) r ( ，) 赤 ( 2 删 证明：设图g 是阶为n = r ( w m ，) 一1 的临界图，即g 不包含矸，m 作为其子图，并且 g 的独立数a ( g ) n 一1 则对于任意一点”g ，我们有： ( 1 ) ，点 的度至多为r ( ，) 一1 ， ( 2 ) ，瓯的最大度进而平均度至多为r ( 尸。，) 一l 。 则由( 2 , 3 ) 和引理3 ，得 n2 n f o ( r ( ，) ) 1 l o g 掣砑疆r - 1 嗡豢卷 c i 祀，1 0 9 礼j 、”叫，、 ( 注意到这里n = ( m 一2 ) 一1 ) + i 0 使得 c ( 赤) 5 2 r ( 甄 ( 1 + o ( 1 ) ) 南 l i ，r o u s s e a u 和z a n g 在 2 5 中给出下面的引理5 引理5 取定整数k , l ，当n _ + 0 0 时，有 慨+ 一k l 蚓 d ( g ) n 厶( r ( ，m ；n ) 一1 ) n y 。( r ( k ，m ；n ) ) ， ( 2 8 ) 这里。：r ( 一1 , r e ；n ) 。对于任意取定的正数0 m ，就有 删 ( 卜。) 警 为此，我们把“大”的自然数集按下面的方法分成两大类n 和礼”： 群等 ( n f ) 1 1r ( 一l ，m ；d ) 、4 和 r ( k 警1 热 ( 1 一) l o ri 日f 二1 丽1 一q ”8 ” 不失一般性，我们可以假设对于所有的，都有( n ) ( 1 一) m 这样，由( 2 - 8 ) ，我们有 n 厶( 7 - ( ，m ；n ) ) 轮对完全图的r a m s e y 数的渐近上界 这里a = r ( k l ，m ；0 ) 因此 ( 1 一e ) 币l o g 而可 臀 禹嚯 由对r ( ，m ；n ) 的归纳假设知， 对于n ”的情形，由公式( 2 4 ) ， 于是，有 要求的不等式对r ( k + 1 ，m ；n ) 成立 当。o 时，有 厶( $ ) 1 ( 1 + 。) n ” ，n ( r ( ，r n ；n ”) ) 南 这里o = r ( 一1 ，m ；n ”) r ( k ，m ；n ”) 因此 而且，当n “充分大时 n sn ”( 1 + r ( k ，m ；n ”) ) n ”( 1 + ( n ”) 1 一r ( 女一l ，m ；n ”) ) ( n ”) 2 一 0 使得，当n n 时，有m i n r ( k n ，c ) ：c c ) m n ， r a i n r ( k n ，c ) ：c c 1 ) m n 那么，满足什么条件时，不等式能取到等号呢? 下面的引理8 给出了一个条件 引理8 脚设h 是一个连通图的集合若h 中所有图的阶相同，而且h 中有一个图是 g g o o d 的，则r ( g ，h ) = m i n r ( g ，h ) ：h h ) 。 3 2r a m s e yg o o d n e s s 结论 引理8 说明如果h 的每一个成员都是连通的n 阶图，而且h 中有一个成员日是 g g o o d 的，则集合的r a m s e y 数r ( g ，h ) = ( x ( g ) 一1 ) m 一1 ) + s ( g ) 在上述这些引理的 基础上我们给出本章的主要结论。 定理3 设g 是任意不合孤立点的图，日是阶为n2s ( g ) 的连通图将某一阶的树的 某一点连接到v ( h ) 的某一点上，形成图丑j 。我们用h j 表示所有图h j 的集合则当 j 充分大时，存在某一个皿h j ，使得 r ( g ，玛) = ( x ( e ) 一1 ) + j 一1 ) + 3 ( g ) 这样，r ( g ，h j ) = m i n r ( g ，g j ) ：g j 马 证明：因为h j 的每个成员都是阶为n + j 连通图，且n + j n 4 g ) ，则有引理6 知 对于每一个毋h j ，都有 r ( g ，屿) ( x ( v ) 一1 ) ( 7 2 + j 一1 ) + s ( g ) 为证明存在某个玛h j ，使得 r ( g ，h j ) ( x ( g ) 一1 ) ( 7 2 + j 一1 ) 十s ( g ) 我们对x ( g ) 应用数学归纳法 如果x ( g ) = 1 ，则g = 瓦从而r ( g ，g j ) = s = ( x ( g ) 一1 ) ( n + j 1 ) + 5 ( g ) 。易知 一2 1 一堡主堂垡堡壅：垦婴! 望堡鲨主董囹望塑墅塞 结论成立 ( 虽然这种情况违背了我们的前提条件： g 和好都不含孤立点，但是它确实为我 们提供了归纳假设的基础) 假设x ( g ) 2 。我们用x ( g ) 种颜色给图g 进行点着色，使得g 的色部c 1 ，岛， ，g 满足 s ( a ) = l c ij l 岛is si c xj 茎i ( g ) 令g ，= g 一嚷。则x ( c ) = x ( g ) 一1 ，而且3 ( g ) = d c ) 。由对) ( ( g ) 的归纳假设知，存 在n 0 使得当j n 时，我们可以找到一个h h j ，h 7 是g g o o d 的，也就是 r ( g ，月。) = ( x ( g ) 一2 ) ( n + j 一1 ) + s ( g ) 令日。表示在目的某一点上增加某一固定的悬挂i 阶树所得到的n + i 阶的图。例如，我们可 以令这个i ( g ) 阶的树为一条路( p a t h ) 马。取定n l 使得( x ( g ) 一1 ) + l 一1 ) + s ( g ) r ( g ，日1 ) 。对于j n i ，令p = ( x ( a ) 一1 ) ( n + j 一1 ) + s ( g ) ，设( r ，_ b ) 为完全图的 任意红、蓝二着色。我们的目的是证明要么g ，要么存在某一个日”玛使得 日” 。 我们用反证法。假设g 垡 ，而且 不包含h 的任一个成员。由p r ( g ，h 1 ) ，g 壁 ，我们可以知道h 1 所以，我们可以假设存在某一个 数i ( 0si p ，则对于任意的 o ( q p ) ( q 一1 ) 存在c 使得r ( g ，k 1 m ) n + m o ，等等 这方面的一个核心问题是e r d s s 的猜想：给定图g 和数d 若h 是一个充分大的连 通图，且日的每一个点的度不超过d ，则日是g g o o d 的这个猜想在感觉上应该是 正确的，但是目前却没有人能给出确切的证明。人们也曾作过许多尝试，例如，有人先假 定h = 磷，这里k 固定，n 充分大；还有人提出设日为一个双星树( b i n a r y t r e e ) ，但是 这种情形的证明似乎更难 对此问题的另一个研究方向就是推广g g o o d n e s s 这个概念