（应用数学专业论文）一致超图的ramsey性质与代数性质.pdf

摘要 作为一般图得推广，超图特别是一致超图能够更好得刻画现实生活中的 问题本文着重讨论了一致超图的r a m s e y 性质与代数性质。首先利用现代 图论研究中普遍采用的概率方法和l o v i s z 局部引理，我们分别得到了关于 一致超图独立数的下界以及对称与非对称的双色r a m s e y 数下界估计，同时 还得到了多色r a m s e y 数的下界。本文的另一主要内容是关于一致超图谱半 径的讨论利用p e r r o n - f r o b e n i u s 定理我们通过讨论一致超图邻接矩阵的行 和来研究图的谱半径，同时还引入一个与超图邻接矩阵相似的矩阵，通过研 究相似矩阵特征根来分析原来矩阵的特征根，也得到了较好的结果。 关键词：一致超图、r a m s e y 性质、代数性质、局部引理、谱半径 v a b s tr a c t a sag e n e r a l i z a t i o no fg r a p h ，h y p e r g r a p h ，e s p e c i a l l yu n i f o r mh y p e r g r a p h h ag r e a ta p p h c a t i o no i ld e s c r i b i n gp r o b l e m sf r o md a i l yl i f e i nt h i sp a p e r w em a i n l yd i s c u s st h er a m s e yp r o p e r t ya n da l g e b r a i cp r o p e r t yo fu n i f o r m h y p e r g r a p h f i r s t ，w eo b t a i nt h el o w e rb o u n do ft h ei n d e p e n d e n tn u m b e r a n da s y m p t o t i cl o w e rb o u n do ns ，x n m e t r i ca n da s y m m e t r i cf o r mo fr a m s e y n u m b e rb ) rt h ep r o b a b i l i s t i cm e t h o da n dl o v 出s zl o c a ll e m m a ，w h i c hw e r e c o m m o n l yu s e di nt h es t u d y i n go fg r a p ht h e o r y i na d d i t i o n 、ar e s u l to n m u l t i c o l o rr a m s e yn u m b e ro fu n i f o r mh y p e r g r a p hi sp r e s e n t e d s e c o n d ，w e f o c u so nt h ea l g e b r a i cp r o p e r t yo fu n i f o r mh y p e r g r a p hw ed i s c u s s e dt h e s p e c t r a lr a d i u so fh y p e r g r a p h st h r o u g ht h er o ws u n lo ft h ec o r r e s p o n d i n g i n c i d e n c em a t r i xa n dt h ew e l l - k n o w np e r r o n - f l r o b e n i u st h e o r e m a n o t h e r r e s u l to nt h el o w e rb o u n do fu n i f o r mh y p e r g r a p hi so b t a i n e db yi n t r o d u c i n g t h es i m i l a rm a t r i xw h i c hh a st h es a m ee i g e n v a l u e sa n de i g e n v e c t o r sw i t ht h e o r i g i n a lm a t r i x k e y w o r d s ：u n i f o r mh y p e r g r a p h 、r a a n s e yp r o p e r t y 、a l g e b r a i c p r o p e r t y 、l o c a ll e m m a 、s p e c t r a lr a d i u s v i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 建垫鱼如年；月2 7 日 ( 注：手写亲笔签名) 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者c 签孙枣至壑“年多月一7 日 ( 注：手写亲笔签名) 第一章预备知识 1 基本概念与符号说明 在现实生活中，很多事情可以通过图形来得到更好的描述。比方说用点 来代表人，同时连接两点的边表示这两个人是好朋友。这样就得到了一个记 录特定人群人际关系的图。事实土，在刚才的描述中，我们只是关心两点是 否相连。下面将给出图的数学定义。 一个图g 是一个有序的三元集( v ( c ) ，f ( g ) ，抛) ，其中v ( e ) 是一个 非空的顶点集合，e ( g ) 包含了图g 所有的边，而妇是图g 的关联函数。 如果e 是图g 的一条边，“和u 是图g 的顶点使得妒g ( e ) = 卢 ，那么我 们说在图g 中边e 连接顶点p 和u ，同时p 和”也被称为边e 的端点。 如果一个图g 的顶点集v ( g ) 和边集e ( g ) 均为有限集，图g 被称为有限 图。顶点集中所含元素的数目被称之为图的阶若一条边的两个顶点相同， 则该边被称为环同时如果两条边拥有相同的端点，那么我们称这两条边为 重边。图g 被称为简单图当且尽当不含环和重边。 如果一个n 阶的简单图中任意两点都有边相连，我们称该图为完全图， 记为蚝；反过来，如果一个n 阶的图不含有任何一条边，我们称之为空 图，记为了i 。一个图被称之为二部图是指其顶点集能够分成两部份x 和 y ，使得每一条边在x 和y 中各有一个端点。而一个完全的二部图是指一 个简单的二部图满足：x 中的每一个顶点和y 中的每一个顶点相连。如果 l x i = m ，i y l = n ，记，。为该完全二部图。 对于图g 如果满足v ( g7 ) v ( e ) 和e ( g7 ) e ( g ) ，那么就称图g 是g 的子图，记为g ，g 特别的，若有y ( ) = v ( g ) 成立，图g 7 是g 的支撑子图。通过删除图g 中的环与多余的重边，所得到的新图称为图g 的支撑简单子图。假定y 是v 的一个非空子集，由v 7 导出的子图是指图 a i r l ，其顶点集为v ，边集是由图g 中的端点都在v 中的边构成。与顶 点导出子图一样我们还可以定义边导出子图。若e 7 为e 的一个非空子集， 记g e 7 1 为由e 导出的子图。其顶点集由e 7 的顶点组成，边集就是e 7 。 图g 中的一条道路是指一组非空序列w 。”o e l ”1 8 2 1 也仇，在序 列中图g 中的顶点和边交互出现。如果在序列中每条边只出现一次，此时 道路也称之为迹进一步，如果每个顶点也只出现一次的话，该道路被称之 为路径。对于图g 中的两个顶点肛和 ，如果在图中存在一条( “，u 卜路 2 一致超图的基本概念2 径，那幺就说顶点p 和u 是连通的。显然连通是一个等价关系，这样可以将 图g 的顶点集分成若干各互不相交的非空子集u ，k ，。皈。另外称导出 于图g 】，g 【k 1 ，g u 】为原图的连通分支。 无环图g 的一个一边着色管是指将k 种颜色分配给图的边集如皋 这种分配还满足任意两相邻的边都有不同的颜色，那么k 一边着色铲被称 为一个正常女一边着色。如果图g 有一个正常的一边着色，我们就称g 是k 一边可着色的。图g 的边色数x7 ( g ) 是指最小的正整数，使得g 是 一边可着色的 图g 的一个一顶点着色( 简称为一着色) 是指将k 种颜色分配给图 的顶点集如果一种着包还使得任意相邻的顶点分配给不同的颜色，我们称 这个着色是一个正常的一着色。显然每一个正常的一着色将图g 的顶 点被剖分成k 个点不相交的子集，每个子集还被称之为个色部。在所有的 正常k 一着色中，含顶点数最少的色部的势称为色数剩余，用s ( g ) 表示， 如果图g 有一个正常的七一着色，我们就称g 是七一可着色的。图g 的色 数x ( c ) 是指最小的正整数，使得g 是k 一可着色的 设s 为图g 顶点集的一非空子集，如果s 中的任意两点都不相连，就 称s 为图g 的一个独立集。令s 为图g 的一个独立集，若不存在其他的 独立集s 使得1 j s l ，称s 为图的最大独立集，且最大独立集的势称之 为图g 的独立数，记为a ( g ) 。反之，若s 为图g 顶点集的一非空子集使 得v s 1 为一完全子图，我们称s 为图的一个团。若不存在其他的团使 得j s i i sj ，称s 为图的最大团，且最大团的势称之为图“的团数，记为 u f g ) 。 令，7 比，n 女为正整数，r a m s e y 数r ( 礼i n 2 ，7 ) 是指最小 的正整数使得对k 的任意一个k 边着色中，总是存在颜色i ，由被着 以颜色 的边导出的子图g 【最】中含有妃。作为其子图。 本文中用到的其他术语而没有在此说明的请参阅圈论教材，4 ，6 1 。 2 一致超图的基本概念 令x = 扛1 ，勘，z 。 为一个有限集。关于x 上的一个超图口 髓，马，k 是x 上的一个有限子集簇，使得t 致，、e 。 是x 上的一个有限子集簇，使得： 3 图论中的概率方法 1 厩o ( i = l ，2 ，m ) 2 ue=x 此夕p ，若一个超图9 = e 1 ，e 2 ， 还满足最ce ，= i = ，则称9 为简单超图( 或”s p e n c e r 簇”) 。在超图毋中，x 中的元素z 1 ：z 2 ，- ，x 。 称为顶点；集合e 1 ，岛，k 称为超边。显然，简单图就是每一条边均含 有两个顶点的简单超图。若超图中每条边的元素数目相同，则称之为一致超 图。 若l ，为超图边集的子集，并且l ，中任意两条边互不相交，则称，为超 图g 的一个独立边集。该集合中元素的总和称为图9 的一个边独立数。对 于任意的超图，总存在一个最大的边独立数，我们记此数为超图的最大边独 立数o ( 9 ) 。类似的，超图的独立集是其顶点集的一子集s ，并且s 中不 舍任意超边。令s 为超图9 的一个独立集，若不存在其他的独立集y 使 得i s 7 l s i ，称s 为超图的最大独立集，且最大独立集中顶点的数目称之 为超图9 的独立数，记为“( g ) 其他关于超图的概念请参见f 2 , 4 1 。 令k ，n l ，n 2 ，n k 为正整数，关于r 一致超图的r a m s e y 数r ( ( n 1 ，n 2 ， ，? k ) 是指最小的正整数使得对于r 一致完全超图尼的任意一个k 边着色中，总是存在颜色i ，由被着以颜色i 的边导出的子图毋f 且1 中含有 仉阶的r 一致完全超图坛涮。 3 图论中的概率方法 3 1 概率论中的基本知识 近些年来，概率方法在图论中的运用逐步得到推广与重视，并且成为一 个强有力的工具，广泛的应用在组合计数方面。其迅速发展的一个主要原因 是随机陛这一思想在计算机理论研究中所起到的重要角色而许多离散数学 中研究和讨论的问题正是来源于这一领域。概率方法可以大致描述为：为了 试图证明具有某些特定性质组合结构的存在性，我们先构造出一个概率空间 然后证明我们所希望发生的事件在这一概率空间中的概率为正数。这一重要 的思想最先由p e r d 6 s 提出，在随后的5 0 年里为了完善这一理论作了大量 3 图论中的概率方法4 的工作，因而概率方法也被称之为“pe r d 5 s 方法，”他的贡献不仅在于其 利用这一重要工具所得到的大量结果，更在于他在图论与组台学中所提出的 诸多问题及一系列猜想。这些问题极大的推动了这些学科的发展，本文所讨 论的关于一致超图的r a m s e y 性质也是由他提出1 j 。 一个概率空间实际上一个三元有序对( n ，p r ) ，其中n 是一个集合 ( 本文中该集合为有限集) ，是由n 的子集组成的一个a 一代数。所是 上的一个非负测度，并且p r ( f 2 ) = 1 。特别地，当n 为有限集时，就是由n 的所有子集组成的幂集p ( n ) 。这样p r 就是一个由n 一0 ，1 1 ，u p r ( f u 决定地函数，即： p r ( a ) = p r ( m ) ，4c i 2 一个实值的随机变量x 是定义在概率空间上的可测实值函数，x ：q r 。对于一个给定的实数值随机变量x ，我们记它的分布函数为tf ( z ) = p r ( x z ) ，( 一。 x o 。) ，这样f ( x ) 就是个单调递增，并且为左连续 的函数。另外有： l i mf ( z ) = 0 ，和l i mf ( 。) = 1 如果还存在这样的函数，( z ) ，使得 f ( z ) = 7f ( t ) d t ， 那么我们称f ( x ) 为随即变量x 的密度函数。如果一组随机变量( 。) 满 足： 。l 。i r a 。p r ( n ) 二! n 证明：设 。d 为随机变量x 所有可能的取值。那么由期望的定义知 e ( x ) = 啦p r ( x = a 。) a i p r ( x = a i ) t o a p r ( x = a 。) o o n 尸r ( x2 ) ， 命题得证。l 特别地，如果x 只取j e 负整数，并且e ( x ) 0 那么就有下面的不等式成立： p r ( i x p l n ) s i c r 2 证明；对于任意的正数a ，由m a r k o v 不等式有 口2 = e ( ( x 一“) 2 ) a 2 p r ( ( x 一，z ) 2 n 2 ) = n 2 p r ( j x 肛i 。) ， 3 图论中的概率方法 6 命题得证。i 一个特别的情况是如果p 0 ，那么 p r ( x = 0 ) p r ( i x 一肛l 肛) 事实上，这一上界可以得到更好的估计，记f 2 0 = u ：x ( u ) o ) 。由c a u c h y 不等式得： e ( x ) 2 = ( 矗。x d p r ) 2 ( 厶。d p r ) ( f n 。l d p r ) 一e 畔) 2 1 一p r ( x = o ) ) 解方程得孙m ：0 1 0 ，在 集合c e 发生的情况下，集合a e 的概率定义为： p r ( a i c ) = p 7 ( anc ) p r ( g ) 这样p r g = p r ( i c ) 也是概率空间( n ，) 上的一个测度。如果随机变量x 认为是概率空间( q ，p r c ) 上的函数，那么这一新的随机变量的期望就被 称之为条件期望，用符号e ( x i c ) 表示 援引f e l l e r 在1 9 6 6 午用到的一个记号( 。) ，一z ( z 1 ) ( m r + 1 ) 。 这样就有，( ”) 。一( n ) ，t = n ! 和( ：) = ( n ) t ( k ) 。下面定义随机变量x 的r 阶因子矩日( x ) = f “x ) ， 。如果有： 1 3 图论中的概率方法 那么就有： b ( x ) 7 注意到如果令x 为某一集合所含元素的总个数，那么日( x ) 的含义就是定 义在这一集合上的r 元有序组合的平均数 对于任意的正整数n ，如果随机变量序列x 。，x 。，满足： nn p r ( n 托= 。) = i i p r ( x 。= 乜) ， l = 1t = l 那么就称该随机变量序列独立。如果机变量x 和y 独立，那么等式e ( x 十 y ) = e ( x ) + s ( v ) 恒成立。另外若随机变量序列1 ，恐，独立，并且 e ( x ) = ，“和e ( 鼍一，k ) 2 = 井，我们还可以得到： f ( x 。) = 胁 以及 一2 ( 咒) = e 陇 3 3s t i f l i n g 公式 在我们的计算过程中，下面的这个公式被用来替代阶乘，通常也称之为 s t i f l i n g 公式。 l e m m a3 1 ( s t i f l i n g 公式j 对于所有的正整数n ，有： n ! = 厮( ；) “e 印 高矗) ， 这里的0 0 ，当n 足够大时有： ( 掣) “ ( ：) ( 等) “， 这样( n 。) = ( 半) ”。 3 4 两个常见的分布 为了方便起见，在本文中我们一直假定0 p 1 以及q = l p 。我们 说随机变量x 服从均值为p 的b e r n o u l l i 分布当且尽当x 的取值为0 或者 l ，并且有_ p r ( x = 1 ) = p 和p r ( x = 0 ) = q 。我们可以把x 理解为抛硬 币的结果，出现正面的概率为p 。假设x l ，x 2 、为一组独立的b e r n o u l l i 随机变量，每一个五的均值为p 这样记录随机地抛n 次硬币出现正面次 数的随机变量品，p = b x i 就满足： p r ( s k ，= 七) = 。( 后；n ，p ) = ( ：) p k q “一k 同时，我们称s ，p 服从参数为n 和p 的二项分布。注意到6 ( ；n ，p ) 为n 次事件 中有k 次成功的概率。又因为e ( 置) = p 以及0 - 2 ( 墨) = e ( x 一p ) 2 ) = p q ， 这样服从参数为n 和p 的二项分布的随机变量品，有： e ( 品，p ) = n p 和口2 ( & ，p ) = n p q 容易观察到，当趋于，的期望n p 时，b ( 女；n ，p ) 取到最大值。事实 上，我们注意到： 罂生：1+盟罂型b(kl ；n ，p ) 蜘 因此，如果m 为唯一满足p ( n + 1 ) 一1 m 茎p ( n 十1 ) 的正整数，6 ( ；n ，p ) 在小于k = m l 之前严格递增，而从k = m 后严格递减。另外，除了 m = p ( n + 1 ) 时等式成立，否则b ( m l ；n ，p ) 6 ( m ；n ，p ) 。根据s t i f l i n g 公式，对于给定的p 当n o 。，不难得到t 峄吣m 一丽1 ；= 去 3 图论中的概率方法 另外一个分布函数为正态分布函数。如果随机变量的密度函数为 巾) = 而1 e 一( 胁誓 9 那么我们称随机变量是均值为z 方差为o - 2 的正态分布。该分布通常记为 ( 卢：口) 。同时记( t ) 和西( ) 分别表示标准正态分布的密度函数和分布函 数。 ) 一而1e 。2 和吣) = = ：= 而1 e 卑恤 在随机图论中我们通常需要对于二项分布的尾项要有很好的估计。因此 下面的几个定理在实际中也经常被用到。 t h e o r e m3 3 肛，p l 讲假设n p21 ，以及1 h n q 3 。当女p n + h 时。就有： 啪；n 志e 印卜丽h 2 + 面h + 等) 由上述定理可以很容易地推倒出关于二项分布尾项的一个上界。 t h e o r e m3 4 p ，p 1 1 假设n p21 ，以及1 sn q 3 。当p n + h 时，就有； p r ( ) 恸p q n ，v 2 知卜荪h 2 + 惫+ 筹) 另外还有c h e r n o f f 2 1 在1 9 5 2 也得到了一个上界的估计。令0 p l ，以及q = 1 一p 。记乜( z ) 为赋权的墒函数， 岛( z ) = 。l o g ( p 。) + ( 1 z ) l 。g ( g ( 1 。) ) ， 这里0 1 注意到珥( m ) = h 。( 1 一z ) 。这样我们就得到 _ p r ( & ，k ) e x p n 珥( ) ) 对于所有的k n p 同样的有： p r ( 品，p ) 5e z p n ( n ) ) 对于所有的k n p 4 随机图的基本模型 事实上，上述不等式对于n 个独立的b e r n o u l l i 随机变量x l ：托，x 。 之和x = 兰1 x i 也是成立的。其中，p r ( 五一1 ) = f ( 墨) = p ，以及 是】p i = n p 。对于所有的n p 0 ，我们有： p r ( x k ) = p r ( e 。e 肚) e - 肚e ( e p 。) = e - 肚ne ( e i z ) 2 1 1 = e - 肚r l + a ) = ( 2 - “k ( g + p 扩) “ 显然上式右端在扩= q k p ( n k ) 处取得最小值，因此 p r ( x 纠= ( 掣) 2 ) “ = ( 警) ( 罴) ” = e x p n e ( n ) ) 4 随机图的基本模型 在本文中，我们主要讨论有标号的超图，也就是说超图中的顶点之间是 有区别的。一个主要的原因是这样的超图模型便于处理，另外许多关于标号 超图的结论可以比较容易的转化成无标号超图的结果。为了方便起见，我们 不妨假定超图的顶点集为：v 一 1 ，2 ，n ) 。特别地，本文讨论的是一 致超图的代数性质与i ：l a m s e y 性质，因此记簖为古n 个顶点的r 一致超 图。 通常g ( ) ( n ，m ) 和g ( ”) ( 7 l ，p r ( h y p e r e d g e ) = p ) 是我们常用到的两种 关于一致超图的随机图模型5 1 。前者是由含有n 个顶点和m 条超边的r 一致超图构成，其中每一个超图出现的概率相同。本文中如不特别说明，总 是记n = ，是由这n 个顶点所能够生成的最大的r 组合数目，也是含有 个定点的r 一致完全超图的边数这样0sm n 。同时空间g ( r ) ( n ，m ) 中有( n 。，) 个元素，显然每个元素出现的概率为( 薪) 1 。在实际应用中，m 骋随机图的基本模型 多为n 的函数： m = m ( 礼) 。如果我们特别想强调空间g ( r ( n ，m ( n ) ) 中 的概率与期望，通常也用p r ( ) = p r m ( 。) ( ) 以及e m ( x ) = e m f 。) ( x ) 来替代尸r ( ) 和e ( x ) 。 在模型g ( n ，p r ( h y p e r e d g e ) = p ) 中0 0 的含义是对于某一给定的边着色 中，不存在上面所描述的集合s t 而这正是我们所求的在下面的证明过程 中我们将更为详细地解释并如何应用该方法。 首先我么给出一个平庸的结论如果 那么 p r ( n 砑 0 另外一方面，如果a ，a 。，4 。为相互独立的事件，并且p r ( a 1 ) = 鼢 0 对于实际问题中，要求事件间相互独立十分严格，因此部分独立的概念替代 了相互独立，这样对于事件本生的限制就有所降低。l o v s z 局部引理的证 明正是利用了这一原理。 设有事件a 和b ，并且p r ( b ) o ，那么在b 事件发生的条件下， 事件a 发生的概率记为： p r ( a i b ) = 笔簪 4 p 。 5l o v d s z 局部引理 1 3 如果事件a 和b 相互独立，就有p r ( a i b ) = p r ( a ) 。因此俩事件a 和b 相互独立的充分必要条件是p r ( anb ) = p r ( a ) p r ( b 1 。 令d 为由n 个顶点 1 ，2 ，n ) ( i 表示事件a 。) 构成的简单图。如果对 于任意的l isn ，事件a 。和所有的事件4 ，相互独立，其中a ，是那些 在图_ d 中与顶点i 不相邻的顶点所代表的事件。那么我们就称图d 为事件 依赖图。也就是说，事件a ；和这些如事件的布尔函数也独立。这一要求略 强于事件a t 和事件m 相关，这里的m 是那些在图d 中与顶点i 相邻的 顶点所代表的事件。 下面我们给出s p e n c e r 在1 9 7 7 提到的l o v a s z 局部引理的一般形式。最 初的l o v d s z 局部引理参见e r d s s 和l a y 缸z 的f 3 0 1 - t h e o r e m 5 1 ( s p e n c e r 5 可，1 9 7 7 ) 令a l ，以2 ，a 。为概率空间( f 2 ，p r ) 中的事件，d 为上面所描述的事件依赖舀。假定存在这样的实数z 1 ，x 2 ，一、z 。 使得对于任意的i ( 0 t 。 1 ) 有0 厕1 上面的推导过程中的最后一步用到了这样一个常用的不等式( 1 - bd ) 4 o，i 为了得到非对角型经典r a m s e y 的下界，s p e n c e r 提出了下面的非对称 形式的局部引理同时该形式与上面的对称形式相比更加容易应用 t h e o r e m 5 3 ( s p e n c e r 5 吖，1 9 7 7 ) 令a 1 ，a 2 ，- - a 。为概率空间( n ，p r ) 中的事件，d 为上面所描述的事件依赖图。如果存在这样的正整数y 1 ，y 2 ，鲰 使得 y j p r ( a j ) 0 。令q 为 l o v 矗s z 局部引理的一般形式申要求的参数，取： 戡 玑2 丽 n 泖 z 样这 0 一a 。n m 阶 5 5l o v s z 局部引理 这样，局部引理中的要求 可以写成 两边取自然对数得到 p r ( a 。) 轨( 1 i j e e ( d ) 赃；，旦。碱1 玎e ( d ) 副、川 l o g y i 一l o g ( t y j p r ( 冯) ) 可e e ( d 】 因此如果存在这样的正整数玑，y 2 ，y 。使得 以及上式成立的话 命题得证 1 5 o ) 否 。n m 阶 第二章一致超图的r a m s e y 性质 6 引言 对于任意给定的简单图g 和，我们记r ( c ，h ) 为最小的正整数使 得每一个含有个顶点的图口，或者g 4 含有g 为圭t - y 图，或者口的补图 石f 含有h 为其子图。我们也可以理解为最小的正整数，使得对于阶完 全图的任意一个红蓝两种颜色的边着色中，或者出现红色的g ，或者出 现蓝色的h 。当图g 和均为完全图时，我们记r ( m ，? 1 ) = r ( k 。，k 。) ， 这样的r a m s e y 数也被称之为经典的r a m s e y 数 e r d 6 s 和s z e k e r e s 3 1 1 在1 9 3 5 年给出了经典r a j n s e y 数r ( m ，n ) 的一个 上界。随后在 9 4 7 年，e r d 6 s 2 7 l 利用概率方法碍到了对称型经典r e m m e y 数r ( n ，n ) 的一个下界。下面的结论在确立r a m s e y 理论和组合概率方法方 面起到了至关重要的作用。 ( ，+ 0 ( 1 ) ) 去他们 胁，n ) ( 2 。n 一- - 。2 ) 在过去的尽六十年里，这方面的研究收效甚微。现在最好的上下阶分别 由t h o m a s o n 5 9 和s p e n c e r 5 6 得到。 ( 俐) 雩群2 3 时，是否有下面的等式成立 r ( c k ，) = ( m 1 ) ( 礼一1 ) + 1 这个同题在m 舻一2 的情形下是成立的1 1 ，3 3 1 令q ， 1 i ) 为一个简单图序列，我们记r ( a 一，g 女) 为最小的 正整数，使得对于阶完金图k 的任意一个着色中，总是存在一 个整数i ( isi ) 并且由那些被着以第i 色的边生成的图含有g 。为其子 图，同时我们还记r ( n ，n m ) = r ( k ，k ，。) 。这就是通常所说的多 色r a m s e y 问题很早以前，e r d 6 s 就提出了下面的问题，并且悬赏$ 2 5 0 以求得答案 p r o b l e m6 2 确定下面表达式的极限 恕( 幽) v k 5 7 一致超图的r a m s e y 数下界的渐进估计 1 8 此问题的背景可以追溯到图论中的另一重要研究分支：t u r d n 数的估 计。s c h u r 5 0 曾证明： r ( 3 ，3 ) e k ! 、。、u ，。一 k 事实上，c h u n g 2 2 1 就证明了函数： f ( k ) = r ( 3 ，3 ) 。，一 为超可乘函数，因而其极限必定存在。尽管已经知道了函数的极限存在，但 是该极限值是否有限却仍然不为我们所知。为此，e r d s s 也悬赏了$ 2 5 0 以求 得答案。即便是对于较小k 值的一个改进都能得到一更好的下界。现在关于 下界估计的最好结果( 3 2 1 ) “是由e x o o 3 2 1 通过构造一个5 一色的r a m s e y 图得到。 在本章中，我们利用局部引理得到若干关于一致超图的r a m s e y 函数的 下界估计。 7 一致超图的r a m s e y 数下界的渐进估计 在本节中，我们先介绍r 一致超图的双色r a m s e y 数下界的估计，然后 将其推广到多色的经典r a m s e y 数下界。 t h e o r e m7 1 当7 9 , 一o 。时，对于任意的正整数r 2 ，我们有 r ( 娜) ( 1 一。( 1 ) ) 里2 骐 e 证明：我们用两种颜色红和绿随机地并且相互独立地给一致超图g = 丘嚣的每一条超边着色。每条超边被着红色或者绿色的概率均为p = 1 2 。 记s 为超图顶点集y ( 毋) 的一个n 子集。同时事件a s 表示该n 子集在某一 给定的着色中颜色单一，即任取s 中的r 个顶点构成的超边都被着以相同 的颜色。s 取遍顶点集中所有的1 3 , 子集按照如下的方法构造图d ，每一个 顶点均代表一个n 子集。那么两个顶点s 和t 相连当且仅当l s n t f r 。 在这种情况下，s 与t 之间的着色就会彼此影响。有可能会存在一条公共 的超边，在s 中被着以红色，而在t 中被着以绿色这样事件瓜就和那些 7 一致超图的r a m s e y 数下界的渐进估计 1 9 在图d 中不与顶点s 相邻的顶点t 所代表的事件独立。这样构造的图d 满足l o v f i s z 局部引理中对于依赖图的要求。同时有： p ，( a s ) = 2 ( ；1 e = 2 x o ) 注意到在图d 中每一个顶点的度都可以如下界定： a = l 丁：i s n t i r ) l ( ：) ( ：二j ) ( 。叫1 ) ) ( 罴) 尝 7 一致超留的r a m s e y 数下界的渐进估计 2 0 证明：与上面的证明类似，我们用两种颜色红和绿| 瞳机地并且相互独立 地给一致超图9 = _ 】c 的每一条超边着色。注意到定理f 7 1 是关于对称型 的r a m s e y 数，因而令每条超边被着以红色和绿色的概率一样。但是在本命 题中，一个参数固定不变，这样就不可能让每一条超边等概率的着以红色或 者绿色。令每条超边被着红色的概率均为p ，而着绿色的概率为q = l p 。 记s 为超图顶点集y ( g ) 的一个m 子集。同时事件凡表示由该 l t l 子集生 成红色的一致完全超图。这里s 取遍顶点集中所有的m 子集。记_ _ r 为超图 顶点集v ( g ) 的一个n 子集。同时事件b t 表示由该n 子集生成绿色的一致 完全超图这里丁取遍顶点集中所有的“子集。这样就有： p r ( m ) ：p ( ：) 和p r ( 毋) ：g ( 为了下面叙述的方便，我们记( t ) m = ( 一1 ) ( 一2 ) ( m + 1 ) 和 。= ( ：) = ( ) 。m ! 。那么就有k 个a s 这样的事件和如个b r 这样的 事件。注意到当事件山和事件毋相关当且仅当由他们生成的一致超图至 少含有一条公共的超边因此我们就有下面的断言t ( a ) 每个以事件最多除了( ? ) ( 一r ) ( ? ) n 个a 事件外，和 其他所有的a 事件都相互独立。即最坏的情况下，a 事件与某个另外的a 事件仅共有一条超边。同时在最坏的情况下和所有的_ 日事件相关，即最多 除了。个b 事件外，和其他所有的b 事件都相互独立。 ( b ) 每个b 事件最多除了( ：) ( n r ) 一， ( ：) r ”个a 事件外，和 其他所有的a 事件都相互独立。同时也是最多除了厶个b 事件外，和其他 所有的b 事件都相互独立。相应的理由与( a ) 相似，这样放大的目的就是为 了使后面的运算简单一些 为了能够应用非对称形式的l o v 缸z 局部引理5 3 1 ，我们试图找到这样 的常数a 和b ，使得对于a 事件取y i = a ，而对于b 事件取玑= b 。同时 还需满足下面两个不等式： l 。s 。一( ? ) l 。g ( 1 一n p ( ? ) ) 一如l 。g ( 1 6 。( 匀) ( 7 1 ) 和 l 。gb 一( ：) n m - r l o g ( 1 一印：) 一如l 。g ( 1 6 9 ? )( 72 ) 如果存在上面所要求的常数n 和b ，那么就存在对g = k g 的一个双着色，使 得它既不含有红色的瑞也不含有绿色的砖，也就是说r ( r ( m ，n ) n 。 5 7 一致超图的r , a m s e y 数下界的渐进估计 令 卢2 两m - r p = o l n p a= b= 几= 2 1 兵中c i ，c 2 ，c 3 和c 4 均为待定常数。注意到， = ( ：) 州2 = e z p c 4 l o g n ( n l o g n ) 圻。1 ) ( 7 a ) 同时应用基本不等式l 一。 e ，( 该不等式对于所有的正数t 都成立1 。 当取正整数时，有( 1 一z ) 。 三。限。o ( 7 9 ) 0 3 丁o i “0 2 c j 【7 9 j 为了得到满足要求的常数c 1 ，c 2 ，c 3 和c a ，我们不妨先假定不等式( 7 7 ) ( 7 8 ) 和( 7 9 ) 均取等式。这样就得到c 2 = 1 ，以及 击c 一c 4 = c s = 再1c ， ( 7 1 0 ) q = ( 南) “p 。， 由于函数，( z ) = z z ( ? ) 在区间【o ，1 】上为凹函