Minimum clique number, chromatic number, and Ramsey numbers (Q426827)

Summary: 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,\lceil n/3 \rceil)\) is asymptotically equivalent to the inverse function of \(R(4,t)\).