（运筹学与控制论专业论文）van+der+waerden数与ramsey数问题的研究.pdf

摘要 本篇硕士论文主要研究组合数学中v d , 1 1d e rw a e r d e n 数和r a m s e y 数。它以广义 v a 4 d c rw a e r d e n 数的上界，圆周上v a i ld e rw a c r d c n 数的上界和r a m s e y 数的新上界 公式作为研究目标和研究重点。本文首先介绍了v a i ld e rw a e r d e n 问题和r a m s e y 理 论的发展历程和研究现状以及作者的主要工作。 本文的研究工作主要分为两个方面。第一部分：研究广义v a d d e rw a e r d e n 数 和圆周上的v o , nd e rw a e r d e n 数。我们已通过建立几个定理比较了圆周上v a i ld e r w a e r d e n 数研。( n ，n ) 和经典的v a d e rw a e r d e n 数( 吼n ) 之间的关系，求取圆周 上v a nd e rw a e r d e n 数h 名( 仉n ) 而对经典的v & r ld e rw a e r d e n 数( n ，n ) 的上界作出 一些改进我们利用计算机编程算出了几个广义v 8 nd e rw a e r d e n 数和圆周上的v d d _ d e rw a c r d c n 数我们试图避开抽屉原理，构造新方法，推广v a i ld e rw a e r d e n 数， 把v a nd c rw a e r d e n 问题转化为线性不定方程组的求解问题我们已建立了线性不 等式方程组且指出它的解是可求的第二部分：在原有的r a m s e y 理论研究的基础 上，我们运用新的上界公式对r a z n s c y 数的上、下界公式做出一些改进，得到了含 参数的r a m s e y 数的新上、下界公式和一些较好的结果 关键词： v a nd e rw a e r d e n 数w ( m ，n ) ， r a m s e y 数r ( m ，n ) ，圆周上的nd e r w a e r d e n 数w d m ，n ) ，分拆，抽屉原理。 a b s t r a c t i i t h i sm a s t e rt h e s i sf o c u s e so i lv a nd e rw a e r d e nn u m b e ra n dr a m s e yn u m b e ri n c o m b i n a t i o nm a t h e m a t i c s t h er e s e a r c ha i m sa n dm a i np o i n t sa r et h eu p p e rb o u n d so f t h eg 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 s lt h eu p p e rb o u n d so fv a nd e rw a e r d e nn u m b e r s o nc i r c l e ，a n dt h en e w u p p e rb o u n df o r m u l a so fr a m s e yn u m b e r s f i r s t l y ，w ei n t r o d u c e t h ed e v e l o p m e n ts u r v e ya u dm a i nr e s e a r c hd i r e c t i o n so fv a nd e rw a e r d e np r o b l e ma n d r a m s e yt h e o r y , a n dt h ea u t h o r sr e s e a r c hw o r k s t h er e s e a r c hw o r k so ft h i st h e s i sc o n s m t so ft w op a r t s t h ef i r s ta s p e c to ft h er e s e a r c h w o r ki ss t u d yt h eg 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 dv d 2 1d e rw a e r d e nn u m b e r so n c i r c l ew ec o m p a r ev a nd e rw a e r d e nn u m b e r so nc i r c l ew h ( n ，忆) w i t hc l a s s i c a lv a i ld e r w a e r d e nn u u l b e r sw ( n ，n ) b yf o u n d i n gs e v e r a lt h e o r e m s w ea s kf o rw a ( n 1n ) t om a k e s o m ei m p r o v e m e n tf o rt h eu p p e rb o u n d so fw ( n ，n ) w ec a l c u l a t es o m eu p p e rh o u n d s o ft h eg e n e r a l i z e dv a i ld e rw a e r d e nn u m b e r sa n dv a nd e rw a e r d e nn u m b e r so l lc k d eb y c o m p u t e r ，a n dg e ts o m er e s u l t s w et r yt oa v o i dd r a w e rp r i n c i p l e ，b u i l dt h e wm e t h o d s ， g e n e r a l i s ev a nd e rw a e r d e nn u m b e r s ，a n dt r a n s f o r mv a i ld e rw a e r d e np r o b l e mi n t ot h e s o l u t i o n so fl i n e a ri n e q u a l i t i e se q u a t i o n s w eh a v eb u i l tt h el i n e a ri n e q u a l i t i e se q u a t i o n s ， a n dp o i n to u tt h a ti t ss o l u t i o n sc a r lb ea s k e d t h eo t h e rp a r to ft h er e s e a r c hw o r ki st h a t w eg e tan e wu p p e r l o w e rb o u n df o r m u l a sf o rr a m s e yn u m b e r sw i t hp a r a m e t e r sa n da s e r i e so fb e t t e rr e s u l t s ，b yu s i n gt h en e wu p p e rb o u n df o r m u l a s ，o nt h ef o u n d a t i o no ft h e a k e a d ye x i s t i n gr e s e a r c ho fr a m s e yt h e o r y k e y w o r d s ：v a nd e rw a e r d e nn u m b e r w ( m ，n ) ，r a m s e yn u m b e r 兄( m ，n ) v 8 1 1d e rw a e r d e nn u m b e ro nc i r c l e i h ( m ，n ) ，p a r t i t i o n ，d r a w e rp r i n c i p l e 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：翅鸳 日期：型圭竺 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：j 雌导师签 第一章绪论 1 1 引言 组合数学，也称为组合学或组合分析，它是一门既古老而又年轻的数学分支 组合数学与很多数学分支相交叉，因此很难对它下一个正式的定义不过大体上可 以说，组合数学从事于把一些元素安排成种种集合的研究这些元素的个数通常是 有限的，而这种安排必须服从所论问题提出的限制条件近几十年来，由于计算机科 学的飞速发展，使得这门古老的数学分支焕发了新的生机，它已经能够解决以前难 以想像的大规模计算问题。更重要的是，现时代为组合数学展现了一系列有吸引力 的新问题的更广阔的范围，这些问题出自抽象代数，拓扑学，图论，博弈论，线性 规划及其他许多领域这也为组合数学中的一大难题v a i ld e rw a e r d e a 问题的解决 和改进提供了可能性 图论是组合数学的一个重要组成部分，近几十年来，它已经发展成为数学的一 个重要分支，是一门应用十分广泛而又极其有趣的新兴数学分支由于电子计算机 的广泛应用，离散数学问题处于越来越重要的位置，图论作为一门提供一种离散数 学模型的应用数学学科也得到了迅速的发展应用图论来解决运筹学，物理，化学， 生物学，计算机科学，网络理论，信息论，控制论，社会科学以及经济管理等方面 的问题已显示出极大的优越性与此同时，图论本身的理论也取得了很大的进展， 它与其他数学学科( 如群论，矩阵论，概率论，拓扑，数值分析等等) 联系紧密。 起到了相互促进的作用。在图论中的极图理论当中，最著名且最值得研究的领域就 是r a m s e y 理论。 v a nd e rw a e r d e n 问题和r a m s e y 问题是数学界的两大经典难题，迄今为止尚未 解决。v a nd e rw a e r d e n 定理是1 9 2 7 年德国数学家v a l ld e rw a e r d e n 在l f i c h u r 猜想 的基础上提出的【1 1 ，由于它反复应用了数学中的一个基本原理一一抽屉原理，故 造成了它奇大的上界。至今，v a i ld e rw a e r d e n 数的精确值只求出了五个【4 ，27 】v a n d e rw a e r d c n 定理表述之简单与其数w ( n ，n ) 庞大的上界形成了极大的反差。不少 著名的数学家都给予了极大的重视和极高的评价，并对此进行了不懈的努力，试图 求取其比较适度的上界 r a m s e y 理论是由1 9 3 0 年英国逻辑学家f p r a m s e y 提出的一个定理形成的 f 1 3 1 。r a m s e y 理论是数学世界的一株奇葩它整个的理论，包括其主要内容，所 2 0 0 5 年上海大学理学硕士e - 位论文 2 研究的问题，所得到的结论连同结论的证明，只需要用很少的点数学语言就能表 述。但到目前为止，精确的r a m s e y 数r ( m ，n ) 只求出了九个【1 6 ，2 1 。数学家们也 只是刚刚开始探索r a m s e y 理论的真谛和影响 1 9 5 2 年苏联数学家辛钦( a y a s h i n c h i n ) 称v a nd e rw a e r d e n 问题为数论中的三 颗明珠之一。1 9 5 8 年荣获f i e l d s 奖的著名数学家k f r o t h ，他的工作的一部分就是 关于v a nd c rw a e r d e n 问题的近几年来国际上重要的数学奖项1 9 9 7 年的f u l k e r s o n 奖得主j hk i m ， 1 9 9 8 年的f i e l d s 奖得主w t c o w e r s ，1 9 9 9 年的w o l f 奖得主 ll o v d s z ，均与他们在v a nd e rw a e r d e n 问题和r a m s c y 理论有关方面的杰出成就相 关。 1 2 v a nd e rw a e r d e n 问舾简介 1 2 1 v a nd e rw a e r d e n 问题的来源 1 9 2 0 年舒尔( i s c h u r ) 提出以下猜想： “如果把正整数集任意分拆成二部分，那么对于任意给定的一个正整数2 ，= 部分中必有一部分含有2 项等差数列。” 1 9 2 6 年，当时在德国汉堡大学的范德瓦尔登( v a nd e rw a e r d e n ) 从哥丁根大 学的一位荷兰学生包特( b a u d e t ) 那里得知了这个猜想，并最终完全证明了这个 猜想成立。范德瓦尔登本人在1 9 7 1 年写了一篇文章，题目叫“包特猜想的证明是 怎样找到的”( 刊于祝贺拉多( rr a d o ) 6 5 岁的文集纯数学研究( s t u d i e si n p u r em a t h e m a t i c s ) ，这篇论文被认为是关于数学发现的心理学的重要文献文章 一开始这样描述了当时的情景：“1 9 2 6 年的一天，在我同阿丁( e a r t i n ) 和许莱 尔( o s c h r e i e r ) 一起吃午饭的时候，我告诉了他们荷兰数学家包特的猜想( 即舒 尔的猜想，范氏一直称它为包特猜想) 午饭后，我们走进阿丁的办公室，试着去找 一个证明。我们在黑板上画了几个图，这时候，有一些想法突然闪入脑中这类新 想法曾多次给讨论以新转机，而其中一个想法最终导致了问题的解决” 想法之一( 范德瓦尔登把它归功于许莱尔) 是；可以把无限集改成有限集 f n l ，这里n 是与2 有关的一个充分大的正整数；另一个想法( 范德瓦尔登把它归 功于阿丁) 是：“分拆成2 部分”可以改成。分拆成部分”，这里是任意给定 的一个正整数，而范德瓦尔登则最终完全证明了后来以他命名的下述定理： 2 0 0 5 年上海大学理学硕士学位论文 3 v a nd e r w a e r d e n 定理【1 】 对任意给定的n ，k n ，存在w = w ( n ，”，n ) 、_ - - - - 、，_ - 一 k 个n ，使得把【w 任意分拆成k 部分后，其中必有一部分有n 项等差数列 另外，设w = p + 1 ，则至少存在一个分拆= a l u a 2 u u m 使得每个集合a 中皆不存在n 阶等差数列。1 i k 范德瓦尔登在与阿丁和许莱尔一同研究这个猜想之前就已经注意到，n = 2 是 平凡情形，因为显然可取w ( 2 ，2 ) = 3 ，而且对任一也有w ( 2 ，k ) = k + 1 一一抽旌 原理( 抽屉原理；如果将n 个物体放入m 个抽屉，则至少有一个抽屉里有【2 搴j + 1 件或更多件物体) 。对于n = 3 ( k = 2 ) ，他也通过穷举知道可取w ( 3 ，3 ) = 9 ，因为 1 12 ，8 可以用几种方法分拆成2 部分，使得每一部分都不含有3 项等差数列 例如 【8 = 1 2 ，5 ，6 ) u 3 ，4 ，7 ，8 ) 就是这种2 拆分但不管把9 加进哪一部分，都会产生3 项等差数列! ( 注意这 时范德瓦尔登所考虑的还是原始的猜想，但却已发现可能把无限集改成有限数 段【 了) 当然，这种通过穷举所有可能情况而得到w ( 3 ，3 ) = 9 的证明无法进一 步推广。在他们三人讨论过程中，范德瓦尔登重新考察了这个n = 3 ，k = 2 的简单 情形，给出了另一个看上去比穷举复杂，但却有可能进一步推广的证明这时可取 w ( 3 ，3 ) = 3 2 5 ，论证如下； 若正整数已分成二部分，则3 个相继整数中必有2 个属于同一部分；而以这2 个属同一部分的数为前2 项的等差数列的第3 项虽然未必属于同一部分，但一定在 由这3 个相继整数再后接2 个共5 个相继整数组成的块中如果第3 项属同一部 分，则已得3 项等差数列，故可设它属于另一部分因为这种5 数块共有2 5 = 3 2 种不同的2 。分拆，所以在3 3 个5 数块中必有2 块的分拆同型，即它们的2 - 分拆所 产生的2 部分分别由排列在同样位置上的数组成在前3 3 块中找到这样2 块后再 往后取这样的笫3 块它到离第2 块与第2 块离第1 块一样远，则在这3 个5 数块 所含的1 5 个数中一定有3 项等差数列。下面用具体数字来说明： 先把3 2 5 1 等分成6 5 块，再把这些块依次记成b x = 1 ，5 ，b 2 = 【6 ，1 0 l ， b 6 5 = ( 3 2 1 ，3 2 5 】。【3 2 5 】的一个2 染色自然在每个b 上产生一个2 - 染色，而且 在2 5 + 1 = 3 3 块b 1 ，b 2 ，b 3 3 中必有2 块，比方说b l l = 5 1 ，5 2 ，5 3 ，5 4 ，5 5 和 b “6 = 1 2 6 1 2 7 ，1 2 8 ，1 2 9 ，1 3 0 的2 染色同型再看b n 的前3 个数，它们中至少有 2 0 ( 5 年上海大学理学硕士学位论文 4 2 个同色，比方况第一个和第三个数5 1 和5 3 同色( 我f f no 和表示二颜色，设 5 1 和5 3 同为) 。若5 5 也是，则已得等差数列5 1 ，5 3 ，5 5 ，故设5 5 是o 因 口2 6 有同型的2 一染色，故1 2 6 ，1 2 8 是，1 3 0 是o 。再考察第3 块b 4 l 的最后一 个数2 0 5 。如果2 0 5 是o ，则有同色之等差数列5 5 ，1 3 0 ，2 0 5 ；如果2 0 5 是， 则有同色之等差数列5 1 ，1 2 8 ，2 0 5 。 范德瓦尔登在1 9 7 1 年的回忆文章中写道：“在对k 一2 和n = 3 这个特殊情 况找到了证明之后，我把它向阿丁和许莱尔作了解释。我感到同样的证法必定能用 来证一般情形。他们不相信，于是我就进而去证下一步 = 3 ，n = 3 的情形”我 们在这里不具体讲下去了，因为这时要用到不少记号和相当大的数量，尽管证明的 思想是和前面一样明确。猜想的最终证明是对n 进行归纳：因为对于n = 2 和所 有的k 数w = w ( 2 ，2 ，2 ) 存在，假设当n 2 时对n 一1 和所有的数w 一 、_ _ _ _ 。、，_ _ _ _ _ ， 女个2 w ( n 一1 ，n 一1 ，n 一1 ) 存在，再证明对n 及任意给定的k 数w = ( n ，n ，n ) 、，- 一、- v _ 一 k 个n 一1k 个n 存在。但要具体写出定理的证明仍然非常繁。 这里不写出定理的原始证明的另一个原因是，范德瓦尔登的证明在1 9 2 7 年发 表后，不少数学家给出了这个定理( 或它的推广) 的新证明其中有的证明很简短 例如，格雷厄姆和罗斯切特在1 9 7 4 年发表的一个证明不到二页 2 6 】他们在高度概 括了范德瓦尔登的原始证明精神实质后，非常精炼地证明了一个比范德瓦尔登定理 更强些的结论，他们的证明为时下各种著作所采用 范德瓦尔登定理是拉姆赛理论( r a m s e yt h e o r y ) 发展的一大源泉 5 ，1 6 】 1 2 2 v a l ld e rw a e r d e n 问题的发展历程 我们把v a i ld e rw a e r d e n 定理中断言其必存在的数的最小值叫做v a i ld e rw a e r d e n 数，若k = 2 ，记为w ( n ，n ) 至今，( n ，n ) 的精确值只求得五个 4 ，27 。在这五个精确值中，w ( 3 ，3 ) 是用穷 举法证得的，而其他的四个精确值是运用计算机搜索求得的它们是；w ( 3 ，3 ) = 9 ， w ( 3 ，3 ，3 ) = 2 7 ，w ( 3 ，3 ，3 ，3 ) = 7 6 ，w ( 4 ，4 ) = 3 5 ，w ( 5 ，5 ) = 1 7 8 。 另外w ( 6 ，6 ) 猜想约等于1 1 0 0 1 6 实际上七十多年来人们对v e l * id e rw a e r d e n 数最有兴趣的不是求得其精确值一 这似乎超出了人们现有的能力，而是希望对它有较好的估计，特别是想得到比较“适 度”的上界。 2 0 ( ) 6 年上海大学理学硕士学位论文4 2 个同色，比力、悦第一个和第三个数5 1 和5 3 同色( 我们用o 和表示二颜色，设 5 1 和5 3 耐为j 。若5 5 也是，则已得等差数列5 1 。5 3 ，5 5 ，故设5 5 是o 。困 口2 6 有同型的2 一染色，故1 2 6 ，1 2 8 是，1 3 0 是o 。再考察第3 块b 4j 的最后一 个数2 0 5 。如果2 0 5 是o ，则有同色之等差数列5 5 ，1 3 0 ，2 0 5 ；如果2 0 5 是， 则有同色之等差数列5 1 ，1 2 8 ，2 0 5 范德瓦尔登在1 9 7 1 年的回忆文章中写道“在对k 一2 和n = 3 这个特殊情 况找到了证明之后，我把它向阿丁和许莱尔作了解释。我感到同样的证法必定能用 来证一般情形。他们不相信，于是我就进而去证下一步k = 3 n = 3 的情形。”我 们在这里不具体讲下去了，因为这时要用到不少记号和褶当大的数量，尽管证明的 思想是和前面一样明确。猜想的最终证明是对，。进行归纳：因为对于n = 2 和所 有的k 数w = w ( 2 ，2 ，- ，2 ) 存在，假设当n 2 时对n 一1 和所有的k 数w = 、- - - - - - 、- 一 k 干- 2 w ( n 一1 ，n 1 一，n 1 ) 存在，再证明对n 及任意给定的数w = w ( n ，n ，n ) 、。“。、，。一、_ _ _ _ 。v 。一 个n lk 十h 存在。但要具体写出定理的证明仍然非常繁 这里不写出定理的原始证明的另一个原因是，范德瓦尔登的证明在1 9 2 7 年发 表后，不少数学家给出了这个定理( 或它的推广) 的新证明其中有的证明很简短 例如，格雷厄姆和罗斯切特在1 9 7 4 年发表的一个证明不n - - 页f 2 6 j 他们在高度概 括了范德瓦尔登的原始证明精神实质后，非常精炼地证明了个比范德瓦尔登定理 更强些的结论，他们的证明为时下各种著作所采用 范德觅尔登定理是拉姆赛理论( r a m s e yt h e o r y ) 发展的一大源泉 5 ，1 6 】1 s 1 2 2 v a i ld e rw a e r d e n 问题的发展历程 我们把v a i ld e rw a e r d e n 定理中断言其必存在的数的最小值叫做1d e rw a e a d e n 数，若k = 2 ，记为w 0 , ，n ) 。 至今，w _ n ) 的精确值只求得五个【4 , 2 7 在这五个精确值中，( 3 ，3 ) 是用穷 举法证得的，而其他的四个精确值是运用计算机搜索求得的，它们是：w ( 3 ，3 ) = 9 ， w ( 3 ，3 ，3 ) = 2 7 ，w ( 3 ，3 ，3 ，3 ) = 7 6 ，w ( 4 ，4 ) = 3 5 ，w ( 5 ，5 ) = 1 7 8 。 另外w ( 6 ，6 ) 猜想约等于1 1 0 0 1 6 实际上七十多年来人们对y a a 2d e rw a e r d e n 数最有兴趣的不是求得其精确值 这似乎超出了人们现有的能力，而屉希望对它有较好的估计，特别是想得到比较“适 这似乎超出了人们现有的能力，而是希望对它有较好的估计。特别是想得到比较“适 度”的上界。 2 0 0 5 年上海大学理学硕士学位论文 5 1 9 8 7 年，以色列数学家谢拉( s s h e l a h ) 取得了重大突破他在题为。关于范德 瓦尔登数的原始递归的上界”的论文中证明了f 23 ： ( n ，n ) 2 的2 w ( n l ， 一1 ) 层塔幂， 即 2 2 w ( n ，n ) 2 7 2 w ( n 1 ，n 一1 ) 个2 。 这是目前得到的最好的上界，但这个上界大的出奇，连n n 都无法与他相比。 例如，当n = 5 0 0 0 时，根本不必动用5 0 0 0 个2 ，而只需五个2 ，便有 2 2 。2 = 2 2 r = 2 2 埔= 2 ( 2 4 r = 2 1 6 4 = 2 6 5 5 3 6 ( 2 1 a ) 5 0 = ( 2 5 8 * 3 2 ) 5 。0 0 5 0 0 0 6 0 0 0 v a nd e rw a e r d e n 数上界奇大的原因在于它反复应用了数学中的一个基本原理 一一抽屉原理，而被急剧的放大了 目前有关v a nd e rw a e r d e n 数的研究一种是推广v a nd e rw a e r d e n 数，如图上 v a nd e rw a c r d e n 数和多项式v a s td e rw a e r d e n 数【7 ，8 】其目的仍然是要对v a i ld e r v v h e r d c n 数给出一些定性描述，或者通过v a nd e rw a e r d e n 数的研究发现算术数列 的有关性质。我们试图通过求取圆周上的v a i ld e rw a e r d e n 数而对经典的、，a nd e r w a e r d e n 数w ( n ，n ) 的上界作出一些改进；同时，试图避开抽屉原理，构造新方法， 推广v a i ld c rw a e r d e n 数，如，建立纷i 生不定方程组 v a i ld e rw a e r d e n 数的有关结论可以应用到某些领域，比如在拓扑空间的应用 9 ，物理学中的应用【1 0 】作为与数论相关的研究领域，v a nd e rw a e r d e n 数的研 究结果还可以用于编码理论等方面。 1 3r 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 ) 归纳出了一个重要而基本的组合学中的原理：抽屉原理 1 9 世纪以来，这个原理首先是用来建立有理数理论，尔后逐渐应用到不同的数学领 域，如在数论，组合论，几何学等方面有着重要的应用，并且常常得到一些令人惊 异的结果然而，最具深刻而重要的推广工作乃是英国逻辑学家f p r a m s e y 作出 的，这就是著名的r a m s e y 定理和l 肚f f n s e y 数【1 1 ，1 2 】。 r a m s e y 理论实际上起源于1 9 3 0 年英国逻辑学家f p r a m s e y 在一篇关于数理 逻辑的基础性文章中的这样一个定理【13 ： 2 0 0 5 年上海大学理学硕士学位论文 6 设k ，r ，n 为正整数，对于集合x = 1 ，2 ，) 的所有元子集任意的用r 种颜 色着色，如果_ 充分大，那么存在x 的一个n 元子集y ，使得y 的 元子集是 单色的。这就是著名的l 娃u n s e y 定理。 在7 0 年代以前，关于r a m s e y 问题研究的文章不是很多。1 9 7 3 年在匈牙利的 布达佩斯召开的组合数学大会，成为r a m s e y 理论发展的里程碑 r a m s e y 理论近年来有了很大的发展，取得了丰富的成果 1 6 】。确切的r a m s e y 数一般很难断定，迄今为止，经过几代数学家的努力再加上计算机的帮助，所有非 平凡的经典r a m s e y 数的精确值也只求出了9 个，见 1 6 ，2 1 】，由此可见其研究的 艰难性。近年来r a m s e y 数的研究进展大多在其数r ( m ，n ) 的渐近估计值上【1 5 。 如今，r a m s e y 理论的研究中越来越多的应用了许多现代的数学方法，如：规划方 法，代数方法，分析方法，随机图方法等等可以说，几乎每一个新的r a m s e y 数的 确定都伴随着一种新方法的产生 作为与v a nd e rw a e r d e n 数有很大关系的r a m s e y 数的研究我们已经取得了一些 丰富的成果，美国罗切斯特工学院( r o c h e s t e ri n s t i t u t eo ft e c h n o l o g y ) 的著名学者 s p r a d z i s z o w s k i 在每年一次的“s m a l lr m n s e yn u m b e r s ”进展报告中都有关于这 项工作的评价( 该报告刊于t h ee l e c t r o n i cj o u r n a lo fc o m b i n a t o r i c s ) 。 r a m s e y 理论对现代计算机的设计和研究有着很大的作用，被认为是一条重要 的定理。同时，它也被广泛地应用于几何凸边形问题，矩阵理论等各种研究领域， 前景应用十分广阔。 1 4 本文的主要工作 本文的主要工作是组合数学中v a nd e rw a e r d e n 数和r a m s e y 数的研究它以广 义v a nd e rw a e r d e n 数的上界以及圆周上v 毗ld e rw a e r d e n 数的上界和r a m s e y 数的 新的上界公式作为研究目标和研究重点分为以下= 大部份； 第一部分；研究广义v a nd e rw a e r d c n 数和圆周上v md e rw a e r d e n 数我们 已通过建立几个定理比较了圆周上v a nd e rw a e r d e n 数w h ( n ，n ) 和经典的v a i ld e r w a e r d e n 数w ( n ，n ) 之间的关系，通过求取圆周上v a i ld e rw a e r d e n 数w h ( n ，n ) 而 对经典的md e rw a e r d e n 数( n ，n ) 的上界作出一些改进同时，我们又利用计 算机编程对几个广义v a nd e rw a e r d e n 数和圆周上v a nd e rw a e r d e n 数的上界作出比 2 0 0 5 年上海大学理学硕士学位论文 7 较好的估计。我们已计算出了几个结果，如 w ( 3 ，4 ) = 1 8 ，w h ( 3 ，3 ) = 9 ，w h ( 3 ，4 ) 1 5 ，w i ( 4 ，4 ) 茎2 3 ，w h ( s ，3 ，3 ) 2 5 ( 此结果已被上海大学学报正式出版，且已被m a t h e m a t i c sr e v i e w s 检索) 其次，我们试图避开抽屉原理，构造新方法推广v a nd c rw a e r d e n 数，把v a n d e rw a e r d e n 问题转化为线性不定方程组的求解问题我们已建立了线性不等式方 程组，且指出它的解是可求的。 第二部分：在原有的r a m s e y 理论研究的基础上，我们运用新的上界公式对 r a m s e y 数的上、下界公式做出一些改进，得到了含参数的r a _ s c y 数的新上、下界 公式，并且得到了 r ( k s e ，k 6 ) 1 1 6 ，r ( k 6 一e ，k 7 ) 2 0 2 等比较好的结果。( 此结果已被上海大学学报录用) 第二章v a n d e rw a e r d e n 问题 v a nd e rw a e r d e n 定理【1 对任意给定的n ，n存在w = ( n ，n ，n ) 、_ - - _ _ 、，- - - - _ ， k 个n ，使得把 任意分拆成部分后，其中必有一部分有”项等差数列 另外，设w = p + 1 ，则至少存在一个分拆m = a 1 u a 2 u u m 使得每个集合a 中皆不存在n 阶等差数列，1s i sk 2 1 v a nd e rw a e r d e n 数 2 1 1 v a i ld e rw a e r d e n 数的基本概念 我们把v a i ld e rw a e r d e n 定理中断言其必存在的数的最小值叫做v a nd e rw a e r d e n 数，若一2 ，记为w ( n ，n ) 。可以预料，对函数w 的定量研究将会非常困难 首先会想到w = ( n ，”一，n ) 的精确德前面已经说过，n = 2 时，w ( 2 ，) = 、。- _ l _ _ 一 个n k + l 是平凡结果；另外可以用穷举法证得w ( 3 ，3 ) = 9 除此之外，借助于计算机搜索 还求出了4 个值【4 ，2 7 】。表1 - 1 列出了至今已确定的所有非平凡的w = w ( 2 ：! ：2 ) 个n 值。 口| k 23 4 3 92 77 6 43 5 51 7 8 表l 一1 使用“非构造性方法”可得到下界 帅，咖乏一： 8 2 0 0 5 年上海大学理学硕士学位论文 9 当n 是素数时，通过具体构造可得到更好的下界4 但这些下界与目前人们所得到的w ( n ，n ) 的上界有天壤之别。事实上所得的上界如 此之大一一更确切地说，( n ，n ) 的已知上界作为n 的函数其递增速度是如此之 快，以至于必须用被称为阿克曼层次( a c k e r m a nh i e r a r c h y ) 的一系列专门的函数才 能表示它。第m 层次的阿克曼函数记为a 。( m 1 ) ，它定义在正整数集上 第1 层函数a 1 ( n ) = 2 n ，是“加倍函数”；第2 层函数a 2 ( n ) = 2 n ，是递增很快 的指数函数。a 2 可以用a 1 来描述ta 2 ( n ) 等于a 1 在自变量1 处重复作用n 次， 例如 a 2 ( 3 ) = a l ( a l ( a l ( 1 ) ) ) = 2 2 2 = 2 3 所以也可以递推地定义 a 2 ( 1 ) = a i ( 1 ) = 2 ，a 2 ( n ) = a i ( a 2 ( n 一1 ) ) m 1 ) 同样我们用a ：来定义山： a a ( 1 ) = a 2 ( 1 ) = 2 ， a 3 ( n ) 等于a ：在自变量l 处重复作用n 次；或者递推地定义 a a ( n ) = a a ( a a ( n 一1 ) ) m 1 ) 例如： a 3 ( 2 ) = a 2 ( 3 ( 1 ) ) = 2 2 ， a 3 ( 3 ) = a 2 ( a ( 2 ) ) = 2 一般的，不难看出有a a ( n ) = _ _ 4 2 ( a 3 m 一1 ) ) = 2 a 3 ( n - 1 ) ，因此可以写成下面这 种2 的“n 层塔幂”的形式： a 3 ( n ) ；2 2 2 ( 共n 个2 ) 所以第3 层函数a 3 也称为2 的“塔幂函数”，其递增速度异常之快； 山( 3 ) ：2 ”= 1 6 ，a a ( 4 ) = 2 ”= 6 5 5 3 6 ，a a ( 5 ) = 2 6 5 5 ”，一 a 3 ( 5 ) 已经非常大了，要把它写成十进位整数的话将近2 0 万位 2 0 0 5 年上海大学理学硕士学位论文 1 0 a 。比起a a 来又微不足道了第4 层函数是这样定义的： a 4 ( 1 ) = a 3 ( 1 ) = 2 ，a 4 ( n ) = a 3 ( a 4 ( n 一1 ) ) 1 ) 所以： a 4 ( 2 ) = a 3 ( a 4 ( 1 ) ) = a 3 ( 2 ) = 2 2 = 4 ， a 4 ( 3 ) = a 3 ( 血( 2 ) ) = a 3 ( 4 ) = 2 ”= 6 5 5 3 6 ， a 4 ( 4 ) = a 3 ( a 4 ( 3 ) ) = 2 的6 5 5 3 6 层塔幂 数a t ( 4 ) 已经大得难以置信格雷厄斯和斯彭塞是这样形容数a 4 ( 4 ) 的：。即 使一个数大得必须用世界上所有数的全部篇幅再加上所有计算机的全部存储能力 才能把他容纳进去，这个数同a 4 ( 4 ) 相比仍小得微不足道”斯彭塞建议把函数a a 叫做“w o w 函数”( w o w 是表示惊叹的一个口语感叹词，可勉强译成“哇! ”) 一般地，从第k 层函数氐可以定义第k + 1 层函数a + l ： a k + 1 ( 1 ) = a k ( 1 ) = 2 ，a k + l ( n ) = a k ( a k + 1 ( n 1 ) ) ( 他 1 ) 从m 到a * + - ，函数的递增速度又上了一层但不管怎么说，对一个固定的正整数 m 来说，a 。( n ) 作为n 的函数还是限于第m 个层次，其递增速度有所约束下面 定义的函数a 将突破任何固定的层次，或者说它凌驾于任一层次之上；定义 a ( n ) = a 。( n ) ， 即 a ( 1 ) = a 1 ( 1 ) = 2 ，a ( 2 ) = a 2 ( 2 ) = 4 ，a ( 3 ) = a 3 ( 3 ) = 1 6 ，a ( 4 ) = a a ( 4 ) ， 把函数a 叫做a c h c r m a n 函数 从范德瓦尔登在1 9 2 7 年首先证明以他命名的这个定理以来，7 0 年间又找到了 不少新的证明。但所有证明对量w ( n ，n ) 的估计都必须相当于a ( n ) 也就是说， 只有把从1 到a ( n ) 这样大的每个整数任意分拆成两部分后，才能保证其中必定有 一部分含有n 项等差数列! 范德瓦尔登定理表述之简单与其相应的数w ( n ) 如此庞大的上界形成极大 的反差数学家当然不会对这种现象安置若紊，但试图改变状况的努力均告失败 1 9 5 0 年，厄尔多斯( p e r d s s ) 和另一位著名的组合学家拉多( r a a d o ) 用概 率方法求得( n ，n ) 的下界 2 8 】： ( n ，n ) 2 ( “1 。g “】| 2 0 0 5 年上海大学理学硕士学位论文1 1 1 9 6 8 年，贝勒坎普( b e r l e k a m p ) 改进为 2 9 】：w ( n ，n ) 2 n 1 9 8 0 年，格林( r l g r a k a m ) 等人用代数的方法证明了4 ： 当p 是素数时，w ( p + 1 ，p + 1 ) p 2 p 。 1 9 8 7 年，阻色列数学家谢拉( s s h e l a h ) 证明了 2 , 3 ； w ( n ，) s2 的2 w ( n 一1 ) 层塔幂 根据前面的定义不难证明， 2 的2 w ( n 一1 ，n 一1 ) 层塔幂= a a ( 2 w ( n 一1 ，n 一1 ) ) a 4 ( n ) 从而可知w ( n ，n ) 的上界不超过第4 层函数a 4 ( n ) _ 4 a ( n ) 与a ( n ) = a 。( n ) 相比当然已经根本性地减小。但数学家并不就此满足， 数学家们很自然地追问：谢拉所得的上界是不是真正反映了w ( n ，n ) 的量级? 注意 到w ( n ，n ) 的已有下界属第2 层次，而谢拉的上界属第4 层次，问题就更富于挑战 性了实际上早在1 9 8 3 年，格雷厄姆就在世界数学家大会上提出了下述猜想f 5 ) ： w ( n ，n ) a 3 ( n ) ( = 2 的 层塔幂) 格雷厄姆此后一再重提这个猜想，并悬赏1 0 0 0 美元征求对这个猜想的证明或 否定。 对范德瓦尔登定理中涉及的数，也就是范德瓦尔登数的界的研究正方兴未艾， 十分引人注目，这也正是本文所研究的主要内容之一 2 1 2 符号说明及基本定义 本文凡表示数字的字母一般表示正整数，以下的 a ，翻表示b a + 1 个相连的 整数集合h a + 1 ，耐，a n 一2 d 矛盾 这就证明，k 色集合不含n 个项的等差数列 对于为奇数的情况，证明大体相同，这里从略 这个定理的证明反复应用了抽屉原理，这在估计v a nd e rw a e r d e n 数的上下界 时经常用到。也正因为这样，得到的上下界不可能是精确的，和确切值相去甚远。 我们所做的工作就是尽可能的缩小v a l ld e rw a e r d e n 数的上下界 引理21记，( z ) = a x + 肛，则z l ，x 2 ，。与f ( z 1 ) ，( z 2 ) ，( 。) 同是( 或 同不是) n 阶等差数列。 定理2 2若记 c a l ld e r w a e r d e n 数( n ，) = p + 1 ，由、，a nd e r w a e r d e n 定理 知道，至少存在一个2 分拆肼= a l j b ，使得a ，b 中皆不存在n 阶等差数列，但 在且，b 中却皆存在型为d ，2 d ，( n 一1 ) d 以及w d ，w 一2 d ，w 一一a ) d 的 n 一1 阶等差数列。 证明：由v