A step towards the Ramsey-Turán conjecture for $K_3$ and $K_6$

Abstract

Ramsey-Turán type problems were initiated by Erdős and Sós in 1969. Given integers $p,q\ge 2$, a graph $G$ is $(K_p,K_q)$-free if there exists a red/blue edge coloring of $G$ such that it contains neither a red $K_p$ nor a blue $K_q$. For any $\delta >0$, the Ramsey-Turán number $RT(n,p,q,\delta n)$ is the maximum number of edges in an $n$-vertex $(K_p,K_q)$-free graph with independence number at most $\delta n$. Let $\rho (p,q,\delta )=\underset{n\to \infty }{\lim }\frac{RT(n,p,q,\delta n)}{n^2}$. Kim, Kim and Liu (2019) showed that $\rho (3,6,\delta )\ge \frac{5}{12}+\frac{\delta }{2}+2{\delta }^2$ via a skillful construction and conjectured the equality holds for sufficiently small $\delta >0$. Using Szemerédi's regularity lemma and a stability argument, we make the first step towards the conjecture by showing that $\rho (3,6,\delta )$ is at most $\frac{5}{12}+\frac{\delta }{2}+2.1025{\delta }^2$.

32 pages