为了正常的体验网站,请在浏览器设置里面开启Javascript功能!
首页 > 拉姆齊定理

拉姆齊定理

2011-06-05 42页 pdf 140KB 24阅读

用户头像

is_482458

暂无简介

举报
拉姆齊定理 Small Ramsey Numbers Stanisław P. Radziszowski Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, spr@cs.rit.edu http://www.cs.rit.edu/~spr Submitted: June 11, 1994; Accepted: July 3, 1994 Revision #12: August 4, 2009 ABSTRACT...
拉姆齊定理
Small Ramsey Numbers Stanisław P. Radziszowski Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, spr@cs.rit.edu http://www.cs.rit.edu/~spr Submitted: June 11, 1994; Accepted: July 3, 1994 Revision #12: August 4, 2009 ABSTRACT: We present data which, to the best of our knowledge, includes all known nontrivial values and bounds for specific graph, hypergraph and multicolor Ramsey numbers, where the avoided graphs are complete or complete without one edge. Many results per- taining to other more studied cases are also presented. We give refer- ences to all cited bounds and values, as well as to previous similar compilations. We do not attempt complete coverage of asymptotic behavior of Ramsey numbers, but concentrate on their specific values. Mathematical Reviews Subject Number 05C55. Revisions 1993, February preliminary version, RIT-TR-93-009 [Ra2] 1994, July 3 accepted to the ElJC, posted on the web 1994, November 7 ElJC revision #1 1995, August 28 ElJC revision #2 1996, March 25 ElJC revision #3 1997, July 11 ElJC revision #4 1998, July 9 ElJC revision #5 1999, July 5 ElJC revision #6 2000, July 25 ElJC revision #7 2001, July 12 ElJC revision #8 2002, July 15 ElJC revision #9 2004, July 4 ElJC revision #10 2006, August 1 ElJC revision #11 2009, August 4 ElJC revision #12 - 1 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 Table of Contents 1. Scope and Notation 3 2. Classical Two Color Ramsey Numbers 4 2.1 Bounds on R (k , l ) for k ≤ 10, l ≤ 15 4 2.2 Bounds on R (k , l ) for l ≥ 15 6 2.3 Other results on R (k , l ) 7 3. Two Colors - Most Studied Cases 9 3.1 Dropping one edge from complete graph 9 3.2 Complete bipartite graphs 11 3.3 Cycles, cycles versus complete graphs 14 3.4 Cycles versus wheels 16 3.5 Cycles versus books 17 4. General Graph Numbers in Two Colors 18 4.1 Paths 18 4.2 Wheels 18 4.3 Books 19 4.4 Trees and forests 19 4.5 Stars, stars versus other graphs 20 4.6 Fans, fans versus other graphs 21 4.7 Paths versus other graphs 21 4.8 Triangle versus other graphs 21 4.9 Cycles versus other graphs 22 4.10 Wheels versus other graphs 23 4.11 Books versus other graphs 23 4.12 Trees and forests versus other graphs 24 4.13 Cases for n (G ), n (H ) ≤ 5 24 4.14 Mixed cases 25 4.15 Multiple copies of graphs, disconnected graphs 26 4.16 General results for sparse graphs 26 4.17 Other general two color results 27 5. Multicolor Ramsey Numbers 29 5.1 Bounds for classical numbers 29 5.2 General results for complete graphs 31 5.3 Cycles 32 5.4 Paths, paths versus other graphs 35 5.5 Special cases 36 5.6 Other general results 36 6. Hypergraph Numbers 38 7. Cumulative Data and Surveys 40 7.1 Cumulative data for two colors 40 7.2 Cumulative data for three colors 41 7.3 Surveys 41 8. Concluding Remarks 42 References 44-72 - 2 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 1. Scope and Notation There is vast literature on Ramsey type problems starting in 1930 with the original paper of Ramsey [Ram]. Graham, Rothschild and Spencer in their book [GRS] present an exciting development of Ramsey Theory. The subject has grown amazingly, in particular with regard to asymptotic bounds for various types of Ramsey numbers (see the survey papers [GrRo¨, Nes˘, ChGra2]), but the progress on evaluating the basic numbers themselves has been unsatis- factory for a long time. In the last three decades, however, considerable progress has been obtained in this area, mostly by employing computer algorithms. The few known exact values and several bounds for different numbers are scattered among many technical papers. This compilation is a fast source of references for the best results known for specific numbers. It is not supposed to serve as a source of definitions or theorems, but these can be easily accessed via the references gathered here. Ramsey Theory studies conditions when a combinatorial object contains necessarily some smaller given objects. The role of Ramsey numbers is to quantify some of the general existen- tial theorems in Ramsey Theory. Let G 1, G 2, . . . , Gm be graphs or s -uniform hypergraphs (s is the number of vertices in each edge). R ( G 1, G 2, . . . , Gm ; s ) denotes the m -color Ramsey number for s -uniform graphs/hypergraphs, avoiding Gi in color i for 1 ≤ i ≤ m . It is defined as the least integer n such that, in any coloring with m colors of the s -subsets of a set of n elements, for some i the s -subsets of color i contain a sub-(hyper)graph isomorphic to Gi (not necessarily induced). The value of R ( G 1, G 2, . . . , Gm ; s ) is fixed under permutations of the first m arguments. If s = 2 (standard graphs) then s can be omitted. If Gi is a complete graph Kk , then we can write k instead of Gi , and if Gi = G for all i we can use the abbreviation Rm (G ; s ) or Rm (G ). For s = 2, Kk − e denotes a Kk without one edge, and for s = 3, Kk − t denotes a Kk without one triangle (hyperedge). The graph nG is formed by n disjoint copies of G , and the join G + H of vertex disjoint graphs G and H is obtained by adding all the edges between vertices of G and H . Pi is a path on i vertices, Ci is a cycle of length i , and Wi is a wheel with i −1 spokes, i.e. a graph formed by some vertex x , connected to all vertices of some cycle Ci −1 (thus Wi = K 1 + Ci −1). Kn ,m is a complete n by m bipartite graph, in particular K 1,n is a star graph. The book graph Bi = K 2 + Ki = K 1 + K 1,i has i + 2 vertices, and can be seen as i triangular pages attached to a single edge. The fan graph Fn is defined by Fn = K 1 + nK 2. For a graph G , n (G ) and e (G ) denote the number of vertices and edges, respectively, and δ(G ) and ∆(G ) minimum and maximum degree in G . Finally, let χ(G ) be the chromatic number of G . In general we follow the notation used by West [West]. Section 2 contains the data for the classical two color Ramsey numbers R (k , l ) for com- plete graphs, and section 3 for the most studied two color cases. Section 4 lists other often studied two color cases for general graphs. The multicolor and hypergraph cases are gathered in sections 5 and 6, respectively. Finally, section 7 gives pointers to cumulative data and to the other surveys. - 3 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 2. Classical Two Color Ramsey Numbers 2.1. Upper and lower bounds on R (k , l ) l 3 4 5 6 7 8 9 10 11 12 13 14 15 k 40 46 52 59 66 73 3 6 9 14 18 23 28 36 43 51 59 69 78 88 35 49 56 73 92 97 128 133 141 153 4 18 25 41 61 84 115 149 191 238 291 349 417 43 58 80 101 125 143 159 185 209 235 265 5 49 87 143 216 316 442 633 848 1139 1461 1878 102 113 130 169 179 253 262 317 401 6 165 298 495 780 1171 1804 2566 3705 5033 6911 205 216 237 289 405 416 511 7 540 1031 1713 2826 4553 6954 10581 15263 22116 282 317 817 861 8 1870 3583 6090 10630 16944 27490 41525 63620 565 580 9 6588 12677 22325 39025 64871 89203 798 1265 10 23556 81200 Table I. Known nontrivial values and bounds for two color Ramsey numbers R (k , l ) = R (k , l ; 2). l 4 5 6 7 8 9 10 11 12 13 14 15 k Ka2 GR Ka2 Ex5 Ka2 Ex12 Piw1 Ex8 WW 3 GG GG Ke´ry GY MZ GR RK2 RK2 Les RK2 RK2 Les Ka1 Ex9 Ex3 Ex15 Ex17 HaKr 2.3.e SLL 2.3.e XXR XXR 4 GG MR4 MR5 Mac Mac Mac Mac Spe3 Spe3 Spe3 Spe3 Spe3 Ex4 Ex9 CET HaKr Ex17 Ex17 Ex17 Ex17 Ex17 Ex17 Ex17 5 MR5 HZ1 Spe3 Spe3 Mac Mac HW+ HW+ HW+ HW+ HW+ Ka1 Ex17 XSR2 XXER Ex17 XXR 2.3.e XXER 2.3.h 6 Mac Mac Mac Mac Mac HW+ HW+ HW+ HW+ HW+ She1 2.3.e XSR2 2.3.h XXER 2.3.e XXR 7 Mac Mac HZ1 Mac HW+ HW+ HW+ HW+ HW+ BR XXER XXER 2.3.h 8 Mac Ea1 HZ1 HW+ HW+ HW+ HW+ HW+ She1 2.3.e 9 ShZ1 Ea1 HW+ HW+ HW+ HW+ She1 2.3.h 10 Shi2 Yang References for Table I. HW+ abbreviates HWSYZH. - 4 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 We split the data into the table of values and a table with corresponding references. In Table I, known exact values appear as centered entries, lower bounds as top entries, and upper bounds as bottom entries. For some of the exact values two references are given when the lower and upper bound credits are different. The task of proving R (3, 3) ≤ 6 was the second problem in Part I of the William Lowell Putnam Mathematical Competition held in March 1953 [Bush]. Greenwood and Gleason [GG] in 1955 established the initial values R (3,4)=9, R (3,5)=14 and R (4,4)=18. Ke´ry [Ke´ry] in 1964 found R (3,6)=18, but only recently an elementary and self-contained proof of this result appeared in English [Car]. All the critical graphs for the numbers R (k , l ) (graphs on R (k , l ) − 1 vertices without Kk and without Kl in the complement) are known for k = 3 and l = 3, 4, 5 [Ke´ry], 6 [Ka2], 7 [RK3, MZ], and there are 1, 3, 1, 7 and 191 of them, respectively. All (3, k )-graphs, for k ≤ 6, were enumerated in [RK3], and all (4,4)-graphs in [MR2]. There exists a unique criti- cal graph for R (4,4) [Ka2]. There are 430215 such graphs known for R (3,8) [McK], 1 for R (3,9) [Ka2] and 350904 for R (4, 5) [MR4], but there might be more of them. In [MR5] evi- dence is given for the conjecture that R (5, 5) = 43 and that there exist 656 critical graphs on 42 vertices. The graphs constructed by Exoo in [Ex9, Ex12, Ex13, Ex14, Ex15, Ex16, Ex17], and some others, are available electronically from http://ginger.indstate.edu/ge/RAMSEY. The construction by Mathon [Mat] and Shearer [She1] (see also sections 2.3.i, 5.2.h and 5.2.i), using data obtained by Shearer [She3] for primes up to 7000, gives the following lower bounds for higher diagonal numbers: R (11,11) ≥ 1597, R (13,13) ≥ 2557, R (14,14) ≥ 2989, R (15,15) ≥ 5485, and R (16,16) ≥ 5605. Similarly, R (17,17) ≥ 8917, R (18,18) ≥ 11005 and R (19,19) ≥ 17885 were obtained in [LSL], though the first two of these bounds follow also from the data in [She3]. The same approach does not improve on an easy bound R (12,12) ≥ 1637 [XXR], which can be obtained by applying twice 2.3.e. Only some of the higher bounds implied by 2.3.* are shown, and more similar bounds could be easily derived. In general, we show bounds beyond the contiguous small values if they improve on results previously reported in this survey or published elsewhere. Some easy upper bounds implied by 2.3.a are marked as [Ea1]. Cyclic (or circular ) graphs are often used for Ramsey graph constructions. Several cyclic graphs establishing lower bounds were given in the Ph.D. dissertation by J.G. Kalbfleisch in 1966, and many others were published in the next few decades (see [RK1]). Only recently Harborth and Krause [HaKr] presented all best lower bounds up to 102 from cyclic graphs avoiding complete graphs. In particular, no lower bound in Table I can be improved with a cyclic graph on less than 102 vertices. See also item 2.3.k and section 4.16 [HaKr]. The claim that R (5, 5) = 50 posted on the web [Stone] is in error, and despite being shown to be incorrect more than once, this value is still being cited by some authors. The bound R (3, 13) ≥ 60 [XieZ] cited in the 1995 version of this survey was shown to be incorrect in [Piw1]. Another incorrect construction for R (3, 10) ≥ 41 was described in [DuHu]. - 5 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 There are really only two general upper bound inequalities useful for small parameters, namely 2.3.a and 2.3.b. Stronger upper bounds for specific parameters were difficult to obtain, and they often involved massive computations, like those for the cases of (3,8) [MZ], (4,5) [MR4], (4,6) and (5,5) [MR5]. The bound R (6, 6) ≤ 166, only 1 more than the best known [Mac], is an easy consequence of a theorem in [Walk] (2.3.b) and R (4, 6) ≤ 41. T. Spencer [Spe3], Mackey [Mac], and Huang and Zhang [HZ1], using the bounds for minimum and maximum number of edges in (4,5) Ramsey graphs listed in [MR3, MR5], were able to establish new upper bounds for several higher Ramsey numbers, improving on all of the pre- vious longstanding results by Giraud [Gi3, Gi5, Gi6]. We have recomputed the upper bounds in Table I marked [HZ1] using the method from the paper [HZ1], because the bounds there relied on an overly optimistic personal communica- tion from T. Spencer. Further refinements of this method are studied in [HZ2, ShZ1, Shi2]. The paper [Shi2] subsumes the main results of the manuscripts [ShZ1, Shi2]. The upper bound marked in Table I [Yang] was obtained by Yang using the method of [HWSYZH] (abbreviated in the table as HW+). 2.2. Bounds on R (k , l ), higher parameters l 15 16 17 18 19 20 21 22 23 k 73 79 92 99 106 111 122 131 137 3 WW WW WWY1 Ex17 WWY1 Ex17 WWY1 WSLX2 WSLX2 153 163 182 187 213 234 242 282 4 XXR Ex17 LSS1 2.3.e 2.3.g Ex17 SLZL SL 265 289 388 395 407 421 441 485 521 5 Ex17 2.3.h XSR2 2.3.e XSR2 2.3.h 2.3.h 2.3.h 2.3.h 401 434 548 614 710 878 1070 6 2.3.h SLLL SLLL SLLL SLLL SLLL SLLL 711 725 908 1214 7 2.3.g 2.3.h SLLL SLLL 861 937 1045 1236 1617 8 2.3.h ShaXP 2.3.g 2.3.g 2.3.h l 24 25 26 27 28 29 30 31 k 143 154 159 167 173 184 190 199 3 WSLX1 WSLX2 WSLX1 WSLX1 WSLX2 WSLX2 WSLX2 WSLX2 l 32 33 34 35 36 37 38 39 k 214 218 226 231 239 244 256 3 WSLX2 WuCXS WuCXS WuCXS WuCXS WuCXS WuCXS Table II. Known nontrivial lower bounds for higher two color Ramsey numbers R (k , l ), with references. - 6 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 The upper bounds of 88, 99, 110, 121 133, 145, 158 on R (3, k ) for 15 ≤ k ≤ 21, respec- tively, were obtained in [Les]. The lower bounds marked [XXR], [XXER], 2.3.e and 2.3.h need not be cyclic. Several of the Cayley colorings from [Ex17] are also non-cyclic. All other lower bounds listed in Table II were obtained by construction of cyclic graphs. The graphs establishing lower bounds marked 2.3.g can be constructed by using appropriately chosen graphs G and H with a common m -vertex induced subgraph, similarly as it was done in several cases in [XXR]. Yu [Yu2] constructed a special class of triangle-free cyclic graphs establishing several lower bounds for R (3, k ), for k ≥ 61. Only one of these bounds, R (3, 61) ≥ 479, cannot be easily improved by the inequality R (3, 4k + 1) ≥ 6R (3, k + 1) − 5 from [CCD] (2.3.c) and data from Tables I and II. Finally, for higher parameters we mention two more cases which improve on bounds listed in earlier revisions: R (9, 17) ≥ 1411 is given in [XXR] and R (10, 15) ≥ 1265 can be obtained by using 2.3.h. In general, one can except that the lower bounds in Table II are weaker than those in Table I, in the sense that with some work many of them should not be hard to improve, in contrast to the bounds in Table I, especially smaller ones. 2.3. Other results on R (k , l ) (a) R (k , l ) ≤ R (k −1, l ) + R (k , l −1), with strict inequality when both terms on the right hand side are even [GG]. There are obvious generalizations of this inequality for avoiding graphs other than complete. (b) R (k , k ) ≤ 4R (k , k − 2) + 2 [Walk]. (c) Explicit construction for R (3, 4k + 1) ≥ 6R (3, k + 1) − 5, for all k ≥ 1 [CCD]. (d) Constructive results on triangle-free graphs in relation to the case of R (3, k ) [BBH1, BBH2, Fra1, Fra2, FrLo, Gri, KM1, Loc, RK3, RK4, Stat, Yu1]. (e) Bounds for the difference between consecutive Ramsey numbers, in particular the bound R (k , l ) ≥ R (k , l − 1) + 2k − 3 for k , l ≥ 3 [BEFS]. (f) By taking a disjoint union of two critical graphs one can easily see that R (k , p ) ≥ s and R (k , q ) ≥ t imply R (k , p + q −1) ≥ s + t −1. Xu and Xie [XX1] improved this construc- tion to yield better general lower bounds, in particular R (k , p + q −1) ≥ s + t + k − 3. (g) For 2 ≤ p ≤ q and 3 ≤ k , if (k , p )-graph G and (k , q )-graph H have a common induced subgraph on m vertices without Kk −1, then R (k , p + q − 1) > n (G ) + n (H ) + m . In partic- ular, this implies the bounds R (k , p + q − 1) ≥ R (k , p ) + R (k , q ) + k − 3 and R (k , p + q − 1) ≥ R (k , p ) + R (k , q ) + p − 2 [XX1, XXR]. (h) R (2k − 1, l ) ≥ 4R (k , l − 1) −3 for l ≥ 5 and k ≥ 2, and in particular for k = 3 we obtain R (5, l ) ≥ 4R (3, l − 1) −3 [XXER]. (i) If the quadratic residues Paley graph Qp of prime order p = 4t + 1 contains no Kk , then R (k , k ) ≥ p + 1 and R (k + 1, k + 1) ≥ 2p + 3 [She1, Mat]. Data for larger p was obtained in [LSL]. See also 3.1.c, and items 5.2.h and 5.2.i for similar multicolor results. - 7 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 (j) Study of Ramsey numbers for large disjoint unions of graphs [Bu1, Bu9], in particular R (nKk , nKl ) = n (k + l − 1) + R (Kk −1, Kl −1) − 2, for n large enough [Bu8]. (k) R (k , l ) ≥ L (k , l ) + 1, where L (k , l ) is the maximal order of any cyclic (k , l )-graph. A compilation of many best cyclic bounds was presented in [HaKr]. (l) The graphs critical for R (k , l ) are k − 1 vertex connected and 2k − 4 edge connected, for k , l ≥ 3 [BePi]. (m) Two color lower bounds can be obtained by using items 5.2.k, 5.2.l and 5.2.m with r = 2. Some generalizations of these were obtained in [ZLLS]. In the last six items of this section we only briefly mention some pointers to the litera- ture dealing with asymptotics of Ramsey numbers. This survey was designed mostly for small, finite, and combinatorial results, but still we wish to give the reader some useful and represen- tative references to more traditional papers looking first of all at the infinite. (n) In a 1995 breakthrough Kim proved that R (3, k ) = Θ(k 2/ log k ) [Kim]. (o) Explicit triangle-free graphs with independence k on Ω(k 3/ 2 ) vertices [Alon2, CPR]. (p) Other general and asymptotic results on triangle-free graphs in relation to the case of R (3, k ) [AKS, Alon2, CCD, CPR, Gri, FrLo, Loc, She2]. (q) In 1947, Erdo¨s gave an amazingly simple probabilistic proof that R (k , k ) ≥ c .k 2 k / 2 [Erd1]. Spencer [Spe1] improved the constant in the last result. More probabilistic asymptotic lower bounds for other Ramsey numbers were obtained in [Spe1, Spe2, AlPu]. (r) Other asymptotic bounds for R (k , k ) can be found, for example, in [Chu3, McS] (lower bound) and [Tho, Con1] (upper bound), and for many other bounds in the general case of R (k , l ) consult [Spe2, GRS, GrRo¨, Chu4, ChGra2, LiRZ1, AlPu, Kriv]. (s) Explicit construction of a graph with clique and independence k on 2c log2k / log log k ver- tices by Frankl and Wilson [FraWi]. Further constructions by Chung [Chu3] and Grol- musz [Grol1, Grol2]. Explicit constructions like these are usually weaker than known probabilistic results. - 8 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12 3. Two Colors - Most Studied Cases 3.1. Dropping one edge from complete graph This section contains known values and nontrivial bounds for the two color case when the avoided graphs are complete or have the form Kk − e , but not both are complete. H K 3 − e K 4 − e K 5 − e K 6 − e K 7 − e K 8 − e K 9 − e K 10 − e K 11 − e G K 3 − e 3 5 7 9 11 13 15 17 19 37 42K 3 5 7 11 17 21 25 31 38 47 29 34 41K 4 − e 5 10 13 17 28 38 27 37K 4 7 11 19 36 52 31 40K 5 − e 7 13 22 39 66 30 43K 5 9 16 34 67 112 31 45 59K 6 − e 9 17 39 70 135 37K 6 11 21 55 116 205 40 59K 7 − e 11 28 66 135 251 28 51K 7 13 34 88 202 Table III. Two types of Ramsey numbers R (G , H ), includes all known nontrivial values. (a) The exact values in Table III involving K 3 − e are obvious, since one can easily see that R (K 3 − e , Kk ) = R (K 3 − e , Kk +1 − e ) = 2k − 1, for all k ≥ 2. (b) The bound R (K 4 − e , K 8) ≤ 45 is given in [LinMac], and R (K 3, K 12 − e ) ≥ 46 in [MPR]. Wang, Wang and Yan [WWY2] constructed cyclic graphs showing R (K 3, K 13 − e ) ≥ 54, R (K 3, K 14 − e ) ≥ 59 and R (K 3, K 15 − e ) ≥ 69. It is known that R (K 4, K 12 − e ) ≥ 128 [Shao] using one color of the (4,4,4;127)-coloring defined in [HiIr]. (c) If the quadratic residues Paley graph Qp of prime order p = 4t + 1 contains no Kk − e , then R (Kk +1 − e , Kk +1 − e ) ≥ 2p + 1. In particular, R (K 14 − e , K 14 − e ) ≥ 2987 [LiShen]. See also item 2.3.i. - 9 - THE ELECTRONIC J
/
本文档为【拉姆齊定理】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索