Two Ramsey-Turán numbers involving triangles

Abstract

Given integers $p,q\ge 2$, we say that 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$. Fix a function $f(n)$, the Ramsey-Turán number $RT(n,p,q,f(n))$ is the maximum number of edges in an $n$-vertex $(K_p,K_q)$-free graph with independence number at most $f(n)$. For any $\delta >0$, let $\rho (p,q,\delta )=\underset{n\to \infty }{\lim }\frac{RT(n,p,q,\delta n)}{n^2}$. We always call $\rho (p,q):=\underset{\delta \to 0}{\lim }\rho (p,q,\delta )$ the Ramsey-Turán density of $K_p$ and $K_q$. In 1993, Erdős, Hajnal, Simonovits, Sós and Szemerédi proposed to determine the value of $\rho (3,q)$ for $q\ge 3$, and they conjectured that for $q\ge 2$, $\rho \left(3,2q-1\right)=\frac{1}{2}(1-\frac{1}{r(3,q)-1})$. Recently, Kim, Kim and Liu (2019) conjectured that for $q\ge 2$, $\rho (3,2q)=\frac{1}{2}(1-\frac{1}{r(3,q)})$. Erdős et al. (1993) determined $\rho (3,q)$ for $q=3,4,5$ and $\rho (4,4)$. There is no progress on the Ramsey-Turán density $\rho (p,q)$ in the past thirty years. In this paper, we obtain $\rho (3,6)=\frac{5}{12}$ and $\rho (3,7)=\frac{7}{16}$. Moreover, we show that the corresponding asymptotically extremal structures are weakly stable, which answers a problem of Erdős et al. (1993) for the two cases.

30 pages. The proofs have been slightly revised, especially the second part