THE RAMSEY NUMBER R(3,T) HAS ORDER OF MAGNITUDE T(2)/LOG-T

被引:252
作者
KIM, JH
机构
[1] Mathematical Science Research Center, AT&T Bell Laboratories, Murray Hill, New Jersey
关键词
D O I
10.1002/rsa.3240070302
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. This paper proves that R(3, t) is bounded below by (1 - o(1))t(2)/log t times a positive constant. Together with the known upper bound of (1 + o(1))t(2)/log t, it follows that R(3, t) has asymptotic order of magnitude t(2)/log t. (C) 1995 John Wiley & Sons, Inc.
引用
收藏
页码:173 / 207
页数:35
相关论文
共 39 条
[1]   A NOTE ON RAMSEY NUMBERS [J].
AJTAI, M ;
KOMLOS, J ;
SZEMEREDI, E .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1980, 29 (03) :354-360
[2]  
Ajtai M., 1981, EUROPEAN J COMBIN, V2, P1
[3]  
ALON N, 1992, PROBABILISTIC METHOD
[4]  
Azuma K., 1967, TOHOKU MATH J, V19, P357, DOI DOI 10.2748/TMJ/1178243286
[5]  
BOLLOBAS B, 1988, COMBINATORICS
[6]  
Bollobas B., 1979, GRAPH THEORY INTRO C
[7]  
BOLOBAS B, 1985, RANDOM GRAPHS
[8]  
BONDY JA, 1976, GRAPH THEORY APPLICA
[9]  
Breiman L., 1968, PROBABILITY
[10]   GRAPH THEORY AND PROBABILITY .2. [J].
ERDOES, P .
CANADIAN JOURNAL OF MATHEMATICS, 1961, 13 (02) :346-&