Radziszowski, Stanisław P.

Small Ramsey numbers

Electron. J. Comb. DS1, 84 p., electronic only (2011)

Summary

Summary: 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 pertaining to other more studied cases are also presented. We give references 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 first posted on the web at the ElJC 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 2011, August 22 ElJC revision #13 - 1 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2011), DS1.13 Table of Contents 2 1. Scope and Notation 3 2. Classical Two-Color Ramsey Numbers 4 2.1 Values and bounds for R (k , l ), k $\leq 10$, l $\leq 15$ 4 2.2 Bounds for R (k , l ), higher parameters 6 2.3 General results on R (k , l ) 7 3. Two Colors: K - n e , K 3, Km , n 10 3.1 Dropping one edge from complete graph 10 3.2 Triangle versus other graphs 12 3.3 Complete bipartite graphs 12 4. Two Colors: Numbers Involving Cycles 16 4.1 Cycles, cycles versus paths and stars 16 4.2 Cycles versus complete graphs 17 4.3 Cycles versus wheels 19 4.4 Cycles versus books 20 4.5 Cycles versus other graphs 21 5. General Graph Numbers in Two Colors 22 5.1 Paths 22 5.2 Wheels 22 5.3 Books 23 5.4 Trees and forests 23 5.5 Stars, stars versus other graphs 24 5.6 Paths versus other graphs 25 5.7 Fans, fans versus other graphs 25 5.8 Wheels versus other graphs 26 5.9 Books versus other graphs 26 5.10 Trees and forests versus other graphs 27 5.11 Cases for n (G ), n (H ) $\leq 5$ 27 5.12 Mixed cases 28 5.13 Multiple copies of graphs, disconnected graphs 29 5.14 General results for special graphs 29 5.15 General results for sparse graphs 30 5.16 General results 31 6. Multicolor Ramsey Numbers 33 6.1 Bounds for classical numbers 33 6.2 General results for complete graphs 35 6.3 Cycles 36 6.4 Paths, paths versus other graphs 40 6.5 Special cases 42 6.6 General results for special graphs 42 6.7 General results 43 7. Hypergraph Numbers 44 7.1 Values and bounds for numbers 44 7.2 Cycles and paths 45 7.3 General results for 3-uniform hypergraphs 45 7.4 General results 46 8. Cumulative Data and Surveys 47 8.1 Cumulative data for two colors 47 8.2 Cumulative data for three colors 48 8.3 Surveys 48 9. Concluding Remarks 50 References 51-84 - 2 - THE ELECTRONIC JOURNAL OF COMBINATORICS (2011), DS1.13

Downloads