(运筹学与控制论专业论文)关于ramsey类数的几个新上界.pdf_第1页
(运筹学与控制论专业论文)关于ramsey类数的几个新上界.pdf_第2页
(运筹学与控制论专业论文)关于ramsey类数的几个新上界.pdf_第3页
(运筹学与控制论专业论文)关于ramsey类数的几个新上界.pdf_第4页
(运筹学与控制论专业论文)关于ramsey类数的几个新上界.pdf_第5页
已阅读5页,还剩36页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2 0 0 5 上海人学硕士学位论文 摘要 所谓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 理沦研究难点与热点之一。本文给出了r a m s e y 类 数的几个新e 界。在第二章中,我们在黄益如、张克民论文的基础上,借助捌 函数的方法,引入新的参数,给出了几个关于经典r a m s e y 数r ( m ,h 1 t 界的 般递推公式。此公式包含了著名的k w a l k e r 上界公式。并由此得到了几个经典 r a m s e y 数的新上界,它们是:r ( 5 ,1 2 ) 8 4 8 ,r ( 5 ,1 4 ) 1 4 6 1 ,r ( 6 ,1 2 ) 玉2 5 6 6 , r ( 6 ,1 4 ) 茎5 0 3 3 。同时,应用此方法我们还得到r ( m j ) 和r ( m ,5 ,) 类r a m s e y 数的1 + 界递推公式,利用卜述公式我们也得到了较好的卜界r ( 4 , 4 ,4 ) s2 3 6 。 在第三章中,我们研究了另一种重要的r a m s e y 类数v a nd e rw a e r d e n 数。首 先,我们将v a nd e r w a e r d e n 数的概念一般化,随后给出了一般v a nd e r w a e r d e n 数的性质、递推小等式刘一个新上界公式。 关键词:r a m s e y 理论:r a m s e y 数:集合s 的k - 染色;v a nd e r w a e r d e n 数 整数集的分划 2 0 0 5 上海人学硕士学位论文 a b s t r a c t r a m s e yt h e o r y ,w h i c hs h o w st h a tt h e r ee x i s t se n o u g hb i gs u b s y s t e mt h a th a s h i g h e ro r d e rt h a no r i g i n a ls y s t e mi ne v e r ys y s t e mh a v i n gc e r t a i nc l a s s ,h a sb e e na l l a c t i v ef i e l do fc o m b i n a t o r i a la n a l y s i si nr e c e n td e c a d e s a l m o s te a c hk e yt h e o r e mi n r a m s e yt h e o r yi si n v o l v e di nt h el e a s tp o s i t i v ei n t e g e rs ot h a tt h et h e o r e mi st r u e , w h i c hi sc a l l e dr a m s e yt y p en u m b e r s i th a sc u r r e n t l yb e e nb e c o m ed i f f i c u l ta n d f l o u r i n ga r e ao fr a m s e yt h e o r yt of i n dt h ee x a c tv a l u e sa n dp r o p e ri o w e ra n du p p e r b o u n d so ft h e s er a m s e yt y p en u m b e r s i nt h i sd i s s e r t a t i o nw e g i v es o m er e s u l t so n u p p e rb o u n d so fr a m s e yt y p en u m b e r s i nt h es e c o n dc h a p t e rw ef i n ds e v e r a l r e c u r s i o nf o r m u l a so fc l a s s i c a lr a m s e yn u m b e r su p p e rb o u n d se x t e n d i n gt e c h n i q u e s d u et oh u a n gy i - - r ua n dz h a n g k i n - m i n gb yi n t r o d u c i n gn e wp a r a m e t e r sb yv i r t u eo f p e n a l t yf u n c t i o nw a y , w h i c hi n c l u d ew e l l k n o w nk w a l k e r su p p e rb o u n d sf o r m u l a a c c o r d i n gt ot h ef o r m u l a s ,w ea r ea b l et oe s t a b l i s hf o u rn e wu p p e rb o u n d sf o r c l a s s i c a lr a m s e yn u m b e r s t h e s ea r e r ( 5 1 2 ) 8 4 8 ,r ( 5 ,1 4 ) s1 4 6 1 ,r ( 6 1 2 ) s2 5 6 6 a n d r ( 6 1 4 ) s5 0 3 3 m e a n w h i l e ,b ym e a n so ft h es a m et e c h n i q u e ,w ef i n es e v e r a lu p p e r b o u n d sr e c u r s i v ef o r m u l a so fm u l t i c o l o r e d r a m s e yn u m b e r sr ( m s 1a n d r ( m ,h 1 ) u s i n gt h e s er e s u l t sw ee s t a b l i s hr ( 4 ,4 ,4 ) 2 3 6 ,w h i c hi st h eb e s to f o u r k n o w l e d g e i nt h et h i r dc h a p t e lw et u r nt ov a nd e rw a e r d e nn u m b e r s ,w h i c ha r ea l s o a n o t h e ri m p o r t a n tr a m s e yt y p en u m b e r s i nt h i sa r e aw ee x t e n dt h ed e f i n i t i o no f c l a s s i c a lv a nd e rw a e r d e nn u m b e r sf i r m l y w et h e n p r o v es o m ep r o p e r t yo n g e n e r a l i z e dv a nd e rw a e r d e nn u m b e r sa n de s t a b l i s har e c u r s i v ei n e q u a l i t ya n dan e w u p p e rb o u n d sf o r m u l a k e y w o r d s :r a m s e yt h e o r y ;r a m s e yn u m b e r s ;k - c o l o u r i n go fas e to fs ;v a nd e r w a e r d e nn u m b e r s ;p a r t i t i o no fi n t e g e rs e t i i i 原创性声明 本人声明:所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外,论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名:日期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定,即: 学校有权保留论文及送交论文复印件,允许论文被查阅和借阅; 学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名:导师签名;二期: 导师签名;芝丘基蜜绸期: 2 0 0 5 上海人学硕士学能论文 1 1 关于r a m s e y 理论 第一章绪论 r a m s e y 理论是当今组合分析的一个重要分支,所揭示的是:一定类的每个 系统中,存在一个大的子系统,比原来系统具有更高的序;或者说它主要处理 这样一类问题:给定集合s ,3 是s 的一个子集簇,r 是一正整数,将s 任意分 拆成r 个部分:s = c u c 2 u u c r ,是否一定存在某个c 含有f ,其中f 3 。 目前,r a m s e y 理论已成为数学中一个非常活跃的分支,从理论上说,它具有三 种引人注日的特点:( 1 ) 它具有相当鲜明的哲学主导思想,那就是完全无序是 不可能的。( 2 ) 它非常质朴理论的主要内容,包括所研究问题,所得到的结 沦连同结论的证明,只需要用很少一点数学概念就能表述;甚至还可以完伞用 l 【常用语来陈述其绝大部分精彩结果。( 3 ) 它是一门面向未来的学科。这个理 论从一个方面向人们展示了未知数学世界的浩渺无垠,人们普遍认为,数学家 们还只是刚川开始探索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 nd e r w a e r d e n 数、 s o c h u r 数等,精确计算这些数值以及对其界的恰当估计需要高超的数学技巧和 创新的数学方法,同时涉及到儿乎所有的主要数学领域知识,这是当今r a m s e y 理论研究的热点和难点。 1 2 预备知识 为方便起见,现将r a m s e y 理论中常用的一些术语与记号分列如f 。 没s 是个( 有限或无限) 集,k 是正整数,则f 列三种说法互相等价: f 1 1s 的k 染色,意思是把s 的每个元素染成k 种颜色1 , 2 ,k 中的 2 0 0 5 上海人学硕士学位论文 种。( 但完争可能有一种色没有被s 的任一兀所用所以更详细地应说成“s 的 至多 染色”,今后都用简称。) ( 2 ) s 的k 一分拆,或s 分拆成k 个子集,意思是把s 表示成它的k 个子集 的亓: s = s 1 u s 2 u u sk 其中当i j 时,s f q s ,= a 。( 这里1 个子集s ,s :,中可能有的是空 集。这与f 1 1 中可能有的颜色没用上相符,但与大部分文献中定义集合的分拆 ( p a r t i t i o n ) 要求各子集s 都非空不一致。 ( 3 ) a s 到集 1 ,2 ,3 ,k 的一个映射 f :s 斗 1 ,2 ,3 ,k ) i j 述三种不同的表述所说的实际一l 是同一件事,它们显然有下而的关系: ( 1 ) 中的i 色冗的集= ( 2 ) 巾的子集置= ( 3 ) 中的i 在映射f 下的原象,。1 ( i ) 。我们在 后文巾将在不同场合采用某一种表述,也会混用这几种表述,例如在用( 3 ) 时 可以把映射f 叫做集s 的一个k 一染色等,其义自明。特别在采用染色的说法( 1 ) 时,如粜s 的某个予集r 的每个元素都染成同一色,则把丁叫做单色的,而若7 1 的每个元素都是i 色的,则简称子集丁是i 色的。 没r 是正整数,畦号一表示集s 的所有r 元子集的集。 所有l l 二整数的集记为z + 。对n ,b z + ,a s b ,6 一a - i - 1 个相继整数的集 以a + l ,b ) 简记为b b 】。对”z + ,把集【1 ,”】简记成【n 】。如不另有说明,“数” 都指“正整数”。 , f i i j e y 4 s 的元素个数记成蚓a 存不涉及元素特性时,”元素通常用【 】来表 j f 。 对实数a ,l “j 表示d 的最大整数;n 表示口的最小整数。 2 0 0 5 上海人学硕士学何论文 1 3 早期的结果 1 9 1 6 年,s c h u r 在一篇研究有限域上费尔马大定理的论文中证明了下面的 s c h u r 定理i l l 。 s e h u r 定理:给定r ,存在一正整数n = n ( r ) ,将【】进行任意r 染色, 方挫x + y = z 一定存在同色解。 这个后来被称为是s c h u r 定理的定理被认为是第一个r a m s e y 类的定理,它 是r a m s e y 理论的源头之。 1 9 2 7 年b lv a nd e rw a e r d e n 证明了另一个主要的r a m s e y 类定理,被称之 为v a i ld e rw a e r d e n 定理12 。 v a i ld e rw a e r d e n 定理( 有限形式) :对任意给定的,k z + ,存在 w = w ( 1 ,k ) ez + ,使得把【】仟意分拆成r 部分后,其中必有一部分含有f 项等 差数列。 1 9 3 0 年,f r a n kr a m s e y 证明了一个后来以他的名字命名的定理r a m s e y 定弹o ”。 r a m a e y 定理( 通式) :对任意给定的r ,k z + 以及数q l ,q 2 ,q , 存扫:l q oe z + ,使得对任一数”以及【”】( ,) 的任一t 一染色,一定有f e 陋】和相 应的q ,元集s 【”】,使s ( r l 是f 色的。 这个定理集叶1 体现了这个数学分支的精神,并且是一个非常优美的结果, 引起了许多数学家关注,并将他们中许多人的兴趣吸引到组合数学这领域。 然而,当时r a m s e y 定理并没有得到广泛公开,以至于五年后当e r d s s 和s z e k e r e s 各自独立地发现r a m s e y 定理的等价形式时,才知道这个优美的结果早已被 r a m s e y 发现。因此,这数学分支被e r d s s 命名为r a m s e y 理论。但是,在此 后的二十多年中,r a m s e y 理论没有太大的进展,直到1 9 5 5 年g r e e n w o o d 和 g l e a s o n 发现非平凡的r a m s e y 数,而这时已经是r a m s e y 定理公开后的第二 2 0 0 5 上海人学硕士学位论文 卜斤个年头r 。然而,在最近四十年里,由于许多著名的数学家对这一理论的 芙注,特别是p a u le r d j s 自己的工作和对它的传播,使得r a m s e y 理论得到了很 大的发展。今天,r a m s e y 理论已经发展成为一个内容丰富、生动,结果优美, 旺叫极具有技巧性和创造性的数学分支。 1 4 r a m s e y 理论的最近进展 尽管1 9 9 6 年p a u le r d j s 的去世是对r a m s e y 理论发展的一个巨大损失,同 时也标志着个叫代的结束。但他给后人留下了许多值得探讨的数学难题,这 是一笔宝贵的精神财富,其中许多就是关于r a m s e y 理论方面的( 他的 本很好 的公开问题集可以在文献”1 中找到) ,它将k 期激励着数学家们从事这一领域的 研究。最近几年r a m s e y 理论越发充满若生机,一方而,经典的r a m s e y 理论领 域的研究方兴末艾;例如,1 9 9 5 年j h k i m 证明了r a m s e y 数r ( 3 ,月1 的阶数是 2 l o g ( ) 。在这一领域完成另一个突破性进展是b m c k a y 和 s r a d z i s z o w s k i ,他们使用许多台计算机计算出r ( 4 ,5 ) = 2 5 。另一方血,数学 家们将绎鲍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 数的几个新下界。 1 5 论文的主要研究内容 奉论文是以作者攻读硕士学何期间协助导师的研究工作为基础,在第一章 叶 l 荆述了r a m s e y 理论的研究对象、意义以及早期的研究成果和近期的研究现 2 0 0 5 上海人学硕士学 _ 7 _ 论文 t 五个年头了。然而,在最近四十年里,由于许多著名的数学家对这一理论的 芙注,特别是p a u le r d s s 自己的工作和对它的传播,使得r a m s e y 理论得到了很 大的发展。今天,r a m s e y 理论已经发展成为一个内容丰富、生动,结果优美, i 正叫板具有技巧性和创造性的数学分支。 1 4 r a m s e y 理论的最近进展 尽管1 9 9 6 年p a u le r d s s 的去世是对r a m s e y 理论发展的一个巨大损失同 叫也标志若个叫代的结束。但他给后人留下了许多值得探讨的数学难题,这 是 笔宝贵的精神财富,其中许多就是关于r a m s e y 理论方而的( 他的一本很好 的公开问题集可以在文献”1 中找到) ,它将氏期激励着数学家们从事这一领域的 研究。最近几年r a m s e y 理论越发充满着生机,一方而,经典的r a m s e y 理论领 域的研究方必未艾;例如,1 9 9 5 年j h k i m 证明了r a m s e y 数r ( 3 ,n ) 的阶数是 2 l o g ( n ) 。在这一领域完成另个突破性进展是b m c k a y 和 sr a d z i s z o w s k i l 8 ,他们使用许多台计算机计算出r ( 4 ,5 ) = 2 5 。另一方面,数学 家们将绎舆r a m s e y 理论中的概念和结果推广到其他数学分支,例如:数论、 集合沧、逻辑学、几何学、分析学等一些领域,使得r a m s e y 理论更加技繁叶 茂。 随着i l 算机技术的飞速发艘,计算速度的不断提商,r a m s e y 理论将发展到 刚人工方法不可能触及的高度,因为在这个分支里,许多问题是有限问题n 这 样可以想象在小久的将柬,能够使用计算机解决此类大难题,如果能够找到有 效的智能算法和恰当的计算公式。本文的下面就给出新的r a m s e y 数下界训算 公式,升h 根据公式借助计算机我们给出了r a m s e y 数的几个新下界。 1 5 论文的主要研究内容 奉论文是以作者攻读颂士学位期问协助导师的研究工作为基础,存第一章 巾l 剥述了r a m s e y 理论的研究对象、意义以发早期的研究成果和近期的研究现 巾l 剥述了r a m s e y 理论的研究对象、意义以发早期的研究成果和近期的研究现 2 0 0 5 上海人学硕士学位论文 卜斤个年头r 。然而,在最近四十年里,由于许多著名的数学家对这一理论的 芙注,特别是p a u le r d j s 自己的工作和对它的传播,使得r a m s e y 理论得到了很 大的发展。今天,r a m s e y 理论已经发展成为一个内容丰富、生动,结果优美, 旺叫极具有技巧性和创造性的数学分支。 1 4 r a m s e y 理论的最近进展 尽管1 9 9 6 年p a u le r d j s 的去世是对r a m s e y 理论发展的一个巨大损失,同 时也标志着个叫代的结束。但他给后人留下了许多值得探讨的数学难题,这 是一笔宝贵的精神财富,其中许多就是关于r a m s e y 理论方面的( 他的 本很好 的公开问题集可以在文献”1 中找到) ,它将k 期激励着数学家们从事这一领域的 研究。最近几年r a m s e y 理论越发充满若生机,一方而,经典的r a m s e y 理论领 域的研究方兴末艾;例如,1 9 9 5 年j h k i m 证明了r a m s e y 数r ( 3 ,月1 的阶数是 2 l o g ( ) 。在这一领域完成另一个突破性进展是b m c k a y 和 s r a d z i s z o w s k i ,他们使用许多台计算机计算出r ( 4 ,5 ) = 2 5 。另一方血,数学 家们将绎鲍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 数的几个新下界。 1 5 论文的主要研究内容 奉论文是以作者攻读硕士学何期间协助导师的研究工作为基础,在第一章 叶 l 荆述了r a m s e y 理论的研究对象、意义以及早期的研究成果和近期的研究现 2 0 0 5 上海人学硕士学位论文 状。第二章首先研究了经典r a m s e y 数r ( 托h ) 的上界,随历将其研究的方法推 广到对r ( m ,s ) 和r ( m ,巩s ,) 上界的研究上。第一章对v a nd e r w a e r d e n 数的性 质和上、f 界进行r 探索性的研究。最后,弟四章总结全义。 2 0 0 5 上海人学硕士学位论文 2 1 引言 第二章经典r a m s e y 数 “任意六个人的集合,要么有三个人两两互相认识,要么有三个人两两相 互不认识。” 这个著名的集会问题是r a m s e y 定理的典型例子。r a m s e y 定理实质上描述 的是:不管我们怎样将一个“较大”具有一定结构的对象分拆成“若干个”类, 则这些类中,一定至少存在一个,其中含有一个“大”的予系统。它实际上可 以看成是简单鸽洞原理的深刻推广。例如,若我们将一个“较大”的对象分拆 成“若十个”类,d i r i c h l e t 鸽洞原理保证我们有“足够多”的元素在同一类中, 但这些元素之问的关系没有任何要求,而r a m s e y 定理的结论则保证:一个“大” 的子系统在同一类中,也就是说:不仅保证有足够多的元素在同一类中,同时 这些元素之间还存在着一定的关系。例如在上述例子中,我们不仅要求有j 个 人,而且还要求这三个人两两相互认识,即形成一个“三角形”。在这一章中我 们将主要考虑这个r a m s e y 理论的经典定理。 自1 9 3 0 年产生这个定理后,经过几十年的发展,产生了人量优美的结果和 证明,已经形成了一个内容丰富的组合数学分支r a l t l 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 定理以图的边染色形式重新叙述: r a m s e y 定理:任取大于等于2 的正整数毛,如,k ,必存在正整 数n = n ( k ,k :,t ) ,对阶完全图进行任意的边r - 染色,则一定有同色 ( e l ,2 ,r ) 的k ,阶完全子图。 根据卜述定理,一定存在使定理成立的最小自然数,这个就是著名的 r a m s e y 数,记为r ( t ,k 2 ,i ) 。 r a m s e y 定理肯定了r a m s e y 数r ( k ,k 2 ,k ,) 的存在性,但要确定其具体 2 0 0 5 上海人学硕士学位论文 值,或作定量捕述却非常困难。这种与r a m s e y 理论中每个定理相伴相生的现 象,u j 以认为从另一方面反映了这个数学分支的一种相统一的性质。从r a m s e y 定理诞生之u 起,数学家们就一直不停地在寻找r a m s e y 数的精确值及其上、 r 界,但即使是r = 2 这样的最简单情形,( 这类r a m s e y 数通常记为r ( m ,h ) ) 也 收效甚微。关十r a m s e y 数r ( m ,”) 非平凡值,迄今为止最好的研究成果见下表 f 0 1 34567891 0l l1 21 31 41 5 4 04 65 25 9 6 6 7 3 3691 41 82 32 83 6 4 3 5 1 5 9 6 97 8 8 8 3 54 9 5 66 9 8 09 61 2 81 3 3 1 4 l i5 3 4 l82 5 4 1 6 1 8 41 1 5 1 4 91 9 12 3 82 9 13 4 94 1 7 4 35 88 0 9 5 1 2 11 4 l1 5 318 11 9 32 2 l2 4 2 5 4 98 71 4 32 1 63 1 64 4 2 1 0 21 1 l 1 2 7 l5 31 7 72 5 32 6 2 2 7 8 2 9 23 7 4 6 1 6 52 9 84 9 57 8 01 1 7 l 2 0 5 2 1 63 2 2 4 1 65 1 1 7 5 4 01 0 3 11 7 1 32 8 2 6 2 8 23 1 66 3 57 0 3 8 18 7 03 5 8 36 0 9 0 5 6 55 8 0 9 6 5 8 81 2 6 7 7 从上表口j 以看出:迄今为止仅有9 个经典r a m s e y 数r ( m , ) 的精确值被算 山。另方面,数学家们也试图对r a m s e y 数r ( m ,竹) 进行恰当的界估计,但得 到的结果也不甚令人满意,迄今上下界公式主要有: 19 3 5 年r e r d s s 和g s z e k e r e s 给出1 ”l : ! ! ! ! 圭壹叁堂里主兰生堡苎 一一 尺( m ,”) r ( 所一,”) + r ( m ,一- ) ( 小:i 2 ( z _ t ) 当m :n 时,1 9 6 8 年k w a l k e r 得到1 : 尺( ”) 彬 ( ) + d ( ) _ p 锄 在这罩我们将借助于罚函数方法引进参数,利用极大、极小罔原理锝到新 r a m s e y 数卜界公式,并由此得到几个r a m s e y 数的新卜_ 界。 2 2 r a m s e y 数r ( m ,n ) 的几个新上界 定义2 - 2 1r a m s e y 数n ( m ,”) 是r a m s e y 定理中存在的最小正整数p + l , 使得1 t 何p 十l 阶图g 巾都含有一m 阶完全子图k 。,或含有一n 阶子图k ”。 定义2 2 2 设r ( r e , n ) :p + l ,所谓( ,n ,p ) 一r a m s e y 图是 p 阶图,其中 既不含有足。也不含有i 。若( m ,p ) r a m s e y 图中不指明阶数p ,我们简记为 ( ,”1 _ r a m s e y 图。 根据r a m s e y 数的定义,对于任何正整数聃和n ,上述( m ,巩p ) 一r a m s e y 图 是一定存存的,并目容易看出:r ( m , ) = p + l 的充要条件是最大( m ,”) 。r a m s e y 剀有p 个顶点。在这篇义章中,我们记( k ) 和( 瓦,) 分别表示图中含有完全 于陶k ,和完全于图k ,的补i ,的个数。 8 2 0 0 5 上海人学硕士学位论文 定理2 - 2 1 刈于任何,”) 一r a m s e y 图h ,成立下列不等式: ( s + 1 ) n ( k ,+ ) n ( k , ) r ( m - s ,”) 一1 ,0 s 一1 ( 2 2 1 ) ( f + 1 ) ( i w ) ( i r ) 【r ( m ,”- t ) 一1 】,o r ( 3 ,3 ) 一1 :5 , i( k 。) + ( i :) 茎( k ) + ( 瓦) p ( 丘) + v ( i :) 其帅 r ( 4 ,4 ) _ l _ 1 7 l _ ( k ,) 十( i ,) ( k :) + ( i z )其中p r ( 4 ,4 ) 一1 = 1 7 ( 其中 d l , d 2 ,d , 是图g 中的度序列) 由上述结果,我们提出下述猜想: 猜想2 - 2 3 若 和p 是正整数,p r ( n ,”卜1 ,则成立下列小等式: n ( k 。) + ( i “) n ( k 。) + v ( i 一) 若s = f = 1 且p = r ( m ,0 - 1 ,由定理2 - 2 1 ,得到下列1 i 等式: 2 n ( k 2 ) n ( k ) 只( 一1 ,h ) 一1 ( 2 2 4 ) 2 n ( k z ) ( i - ) 胄( m 一1 ) 一1 ( 2 - 2 5 ) 由卜 述两不等式得: p ( p i ) = 2 ( n ( k :) + j v ( i z ) ) - c p e r ( m l ,”) + 尺( m 一1 ) 一2 即 r ( m ,”) r ( m 一1 ,”) + r ( ,”,n - i ) 这就是1 9 3 5 年e r d s s 等人给出的l :界不等式( 2 - 1 1 ) 。 当j = f - 2 时,我们得到下列定理: 定理2 - 2 - 4 设m 4 , 4 ,r ( m 一2 , ) a + l ,r ( m , 一2 ) 3 + 1 , 凡( m 一1 , ) y + l ,r ( , 一1 ) - 0 且f 。 0 时,则成立下列公式 r ( m ,”) f ( f 。) 0 2 0 0 5 上海人学硕士学位论文 证明设r ( m , ) = p + l ,h 是沏,n , p ) - - r a m s e y 图,在定理2 - 2 i 中,令 s = f = 2 ,则得到: 3 n ( k s ) + 3 n ( - k ,) 0 ) 2 0 0 5 上海人学硕士学悔论文 当4 b - 3 a 2 0 , 且f 。= ( x 4 b - 3 a 2 。一爿1 o 时 只。( t o ) = o ,0 ( f 。) 0 故本定理成立。 推论1在定理2 - 2 4 的假设条件下,成立上界1 i 等式 r ( m , n ) g l ( ,) 其1 lg 1 ( f ) = 口+ + 4 一,+ j ( a + 卢+ 2 一,) 2 + 4 j r + ;( 卢一睇+ ,) 2 ,。= ;( i 丽一c ) ,c = z 6 - 2 - ;( 2 岱+ 4 卢) ,。= ( a + + 2 ) 2 + ;( 口一卢) 2 其中 f 0 ,当f + 有诈整数解时g ,( f + ) 有意义。 证明由定理的2 - 2 4 证明知,成立不等式: p ( p 1 ) ( p 一2 一卢) 一3 d j 2 + ( 3 p - 3 - f l + f x ) d ,) 类似于二定理2 - 2 4 的证明可得奉推论。 舀- 表2 - i - l 列出了当今世界关于r ( m ,n ) 的最好上、下界,由上述定理2 - 2 - 4 可得螳更好的卜界: r ( 5 ,1 2 ) 8 4 8( a ,卢,y ,f 。) = ( 5 8 ,4 4 1 ,2 3 7 ,7 3 5 5 ) r ( 5 ,1 4 1 1 4 6 1 r ( 6 ,1 2 ) s2 5 6 6 r ( 6 ,1 4 ) 5 0 3 3 ( 口,卢,t o ) = ( 7 7 ,8 4 7 ,3 4 8 ,1 5 2 0 4 ) ( 口,卢,t o ) = ( 2 3 7 ,1 1 7 0 ,8 4 7 ,1 6 7 9 1 ) ( a ,卢,y ,f o ) = ( 3 4 8 ,2 5 6 5 ,1 4 6 0 ,4 1 1 8 6 ) ( 其中的a ,p ,y 有时山公式( 2 - 1 一1 ) 来取) 定理2 - 2 - 5 设4 , 4 ,r ( m 一2 ,h ) 口+ l ,r ( m ,”一2 ) 9 + 1 ,当 0 x 3 时,成市以下的下界或上界公式 ( 1 ) 当。c x c 罢时, r ( m ,”) 2 + z ( z ,y ) 或 r ( m , ) s2 + g 。( y ) 1 2 2 0 0 5 上海人学硕士学位论文 其中 一( 五y ) = a + 彳2 一b 爿:业竺二盟二垫竺! 1 9 4 x g ,( 马y ) = a - 山2 一b 肚3 瞥94 x ( 一x l f l ( 2 ) 当罢c x c 3u 寸成立 r ( m , n ) 2 十爿+ :两( 这时b 0 ,只取上界公式) o ( 3 ) 当z 2 云时,可得上界公式: r r ( m ,”) 口+ 卢+ 4 + 詈( 口+ 2 p + 3 ) ( 2 口+ + 3 ) + ( 卢一口) 2 证明 记r ( ,月) = p + 1 ,类似于定理2 - 2 - 4 的证明,在( , ,p ) - r a m s e y 图h 内成立0 i 等式: p ( 川) ( p - 2 - a ) 磐3 i 2 + ( 3 p - 3 + 一口) 动 = 喜 一x 虿2 + ( 3 p - 3 + 卢- a - y ) d , 一( s x ) 虿2 十y 孑) 去( 3 一州- o - y ) 2 p + 4 l j y 2 叫p 当。 爿,得不等式 h + 口1 一r ( m ,h 一1 ,l 1 ) 一一 + f + 吃一r ( m 一1 ,以,一1 ) 一匕 + ,3 f + 口3 一r ( m 一1 ,行一i ,) 由此( 2 - 3 3 ) ( 2 - 3 4 ) 得证。 , ( p 1 ) o 一占) 根据上表2 - 2 ,r ( 3 ,3 ,4 ) 3 1 ,和r ( 2 ,4 ,4 ) = 1 8 ,将其代入( 2 3 2 ) 式得 r ( 4 4 ,4 ) 月 + 3 r ( n 一1 ,”一l , , ) 一r - i , , ,”) 一2 ( 2 - 4 - 4 ) 证明: 设h 是( 研,惕,j ;j 口) 一r a m s e y 图,且v 是h 的一顶点,则有下面 不等式成立: :( 世,) ( 乏 一圭 ,( m - l , n - l , l , s ) + ,( m - l , n , l - l , s ) + r ( m - l , n , l , s - 1 ) d : 吉孝2 一 ( m - l , n - l , l , s ) + r ( m - l , n , l - l , s ) + ,( m - l , n , l , s - i ) 沁 8 2 0 0 5 上海人学硕士学位论文 3 1 ( k 3 ) 吉酬( 1 ) 对于颜色2 3 ,4 类似有: j 喜2 _ t + ,( m - l , n - l , l , s ) + ,( m , n - l , l - l , s ) + ,( m , n - l , l , s - 1 ) p 蔓3 n 2 ( 乜) 去窆a :西( 2 ) 圭喜2 一( m - l , n , l - l , s ) + ,( m , n - l , l - l , s ) + ,( m , n , l - l , s - i ) 啦3 3 3 ( k ) i l 厶p 口。3( 3 ) 吉喜2 一 ( m - l , n , l , s - 1 ) + r ( m , n - l , l , s - 1 ) + ,( m , n , l - l , s - 1 ) d : o 有f 列不等 式成立: t p ( p - 1 1 芝 圳( ,+ 1 + a ,+ rm - i ,”一1 f ,s ) + r ( m 一1 ,”,一1 ,s ) + ,( m l ,”,s 一1 ) 一d :) 十( f + l + o r 2 + r ( ,卵一1 ,n 一1 ,j ) + ,( 聊,胛一1 ,一1 ,s ) + r ( ,钾,n - 1 ,s 一1 ) - a ;) + d ? ( t + 1 + 口3 + ,m 一1 ,刀,一1 ,s ) + ,( ,竹,n 一1 ,一1 ,s ) + ,m ,忍,一1 ,- 1 ) - d 7 ) + 刃( ,+ l + + ,m 一1 ,叫,s 1 ) + ,r e , n - 1 ,l , s - 1 ) + rm , n , l 一1 , s - 1 ) 一刃) 。f ) 由上述( 料) 得到: 4 t ( p - 1 ) f + a ,+ rm 一1 , 一1 ,f ,s ) + rm 一1 ,”,一1 ,s ) + ,m 一1 ,肝,s 一1 ) + 1 2 + f + 口:+ rm 一1 ,行一1 ,s ) + ,( 埘,n 一1 ,一1 ,s ) + r ( 肼,胛一1 ,s 1 ) + 1 2 9 ! ! ! ! 圭塑叁兰婴主翌堕堡奎 + e l + 口,+ r ( ,”一l ,咒,一1 ,s ) + ,( m ,胛一1 ,一l ,s ) + ,( m ,卯,一1 ,s 一1 ) + 1 2 + ,+ 哦+ r ( 聊一1 ,门,s 一1 ) + ,( 川,即一l ,s 1 ) + ,( ,咒,一1 ,s 一1 ) + 1 2 根据上式,( 2 4 i ) 和( 2 - 4 - 2 ) 两式得证。 由j d :sy ,d :y ! ,d :y ,d j y 4 ,根据t b 和( 44 ) ,( 2 - 4 - 3 ) ( 2 4 - 4 1 两式得汪,汪毕。 2 0 0 5 上海人学硕二 :学位论文 3 1 引言 第三章v a nd e rw a e r d e n 数 1 9 2 7 年v a nd e r w a e r d e n 证明了1 9 2 0 年舒尔的一个猜想,这就是后来r a m s e y 理论发展源泉之一的v a nd e rw a e r d e n 定理,这个定理的有限形式可以简单叙述 为: vand e rw a e r d e n 定理对任意给定的,k n ,存在= w ( t ,女1 n ,使 得把 】任意分拆成t 部分后,其中必有一部分含有,项等差数列: ,a + d ,d + ( ,一1 ) d 和其它几个r a m s e y 理论经典定理一样,v a nd e rw a e r d e n 定理也断言其必 存在使定理成屯的正整数,其最小值称为范德瓦尔臀数,记为w ( 1 ,k 1 ,它也是 重要的r a

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论