科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let Q(n, c) denote the minimum clique number over graphs with n vertices and chromatic number c. We investigate the asymptotics of Q(n,c) when n/c is held constant. We show that when n/c is an integer alpha, Q(n,c) has the same growth order as the inverse function of the Ramsey number R(alpha + 1, t) (as a function of t). Furthermore, we show that if certain asymptotic properties of the Ramsey numbers hold, then Q(n, c) is in fact asymptotically equivalent to the aforementioned inverse function. We use this fact to deduce that Q(n, inverted right perpendicularn/3inverted left perpendicular) is asymptotically equivalent to the inverse function of R(4, t).
- 出版日期2012-3-19
