On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers (Q653983): Difference between revisions

For fixed integers \(2 \leq s < t\), define \[ f_{s,t}(n) = \min\{\max\{| S| ~ : ~ S\subseteq V(H) ~ \text{and} ~ \langle S\rangle_H ~ \text{contains no} ~ K_s\}\} \] where the min is taken over all \(K_t\)-free graphs \(H\) of order \(n\). Bounds on this Ramsey function are investigated, and the following surprising result is proved. For every integer \(s \geq 2\), there is a positive constant \(c = c(s)\) so that for every integer \(n\), \[ f_{s,s+1}(n) \leq cn^{2/3}. \] Previously, it was suggested that for any given \(\epsilon > 0\), \(f_{s,s+1}(n) \geq n^{1 - \epsilon}\). The following more general result along with a corollary was proved. Given any \(\epsilon > 0\) and integer \(k \geq 2\), there is a constant \(s_0 = s_0(\epsilon, k)\) such that for \(s \geq s_0\), \[ c_1n^{1/(1 + (\frac{s}{s-1})^{k-1})} \leq f_{s, s+k}(n) \leq c_2n^{\frac{k+1}{2k+1} + \epsilon}, \] where \(c_1\) and \(c_2\) are positive constants depending only on \(s\). An immediate corollary of this for \(k\) sufficiently large is the following: \[ c_1n^{\frac12 - \epsilon} \leq f_{s, s+k}(n) \leq c_2n^{\frac12 + \epsilon}, \] where \(c_1\) and \(c_2\) are constants depending on \(k\) and \(s\). These results are applied to the vertex Folkman number \(F(r,s,t)\) for \(s < t\), which is the smallest integer \(n\) such that there exists a \(K_t\)-free graph \(G\) of order \(n\) such that every \(r\)-coloring of the vertices of \(G\) yields a monochromatic \(K_s\). Each of the results on the function \(f_{s, t}(n)\) yields a corresponding result on the vertex Folkman number. For example, in the case of the corollary there is the following result: For any \(\epsilon > 0\) and sufficiently large \(s\), \(t\), \(k\), \(c_1\) and \(c_2\), \[ c_1r^{2 - \epsilon} \leq F(r, s, s + k) \leq c_1r^{2 + \epsilon}. \]