On Bipartite Graphs with Linear Ramsey Numbers |
| |
Authors: | R L Graham V Rödl A Ruciński |
| |
Institution: | (1) UCSD La Jolla; CA, USA; E-mail: graham@ucsd.edu, US;(2) Emory University Atlanta; GA, USA; E-mail: rodl@mathcs.emory.edu, US;(3) A. Mickiewicz University; Poznań, Poland; E-mail: rucinski@amu.edu.pl, PL |
| |
Abstract: | Dedicated to the memory of Paul Erdős
We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method
we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1.
Received December 1, 1999
RID="*"
ID="*" Supported by NSF grant DMS-9704114
RID="**"
ID="**" Supported by KBN grant 2 P03A 032 16 |
| |
Keywords: | AMS Subject Classification (2000) Classes: 05C55 05D40 05C80 |
本文献已被 SpringerLink 等数据库收录! |