Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Asymptotic Upper Bounds for Ramsey Functions
| |
|
Asymptotic Upper Bounds for Ramsey Functions
Yusheng Li1, Cecil C. Rousseau2 and Wenan Zang3
| (1) |
Department of Mathematics and Physics, Hehai University, Nanjing, Jiangsu 210098, P. R. China, CN |
| (2) |
Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA, US |
| (3) |
Department of Mathematics, The University of Hong Kong, Hong Kong, P. R. China e-mail: wzang@maths.hku.hk, CN |
Abstract. We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf
a
+1( d), where f
a
+1( d)=∫ 0
1(((1− t) 1/(
a
+1))/( a+1+( d− a−1) t)) dt. Based on this result, we prove that for any fixed k and l, there holds r( K
k
+
l
, K
n
)≤ ( l+ o(1)) n
k
/(log n)
k
−1. In particular, r( K
k
, K
n
)≤(1+ o(1)) n
k
−1/(log n)
k
−2.
Key words. Ramsey number - Independence number - Average degree - Convex function
Received: May 11, 1998 Final version received: March 24, 1999
Fulltext Preview (Small, Large)
|
|
|
|
|
|