Let \( rt(n, k; \ell)\) denote the Ramsey-Turán number ; the maximum number of edges in a graph on \( n\) vertices with no complete subgraph on \( k\) vertices, and no independent set of size \( \ell\).

Problem[1]

Is it true that for some \( c > 0\), \(rt(n,4;\frac{n}{\log n}) < (\frac 1 8 -c) n^2 ? \)

It is known that \( rt(n, 4; o(n)) = \frac{1}{8} n^2 (1 + o(1))\) [3], so this question is asking whether \( K_4\)-free graphs without linear-sized independent are any bigger than those without \( \frac{n}{\log n}\)-sized independent sets.

Sudakov [4] showed that

\(\displaystyle rt(n, 4; n e^{\omega(n) \sqrt{\ln n}}) = o(n^2)\)

where \( \omega(n)\) is any function tending to infinity.

Bibliography
1	P. Erdös, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., 397-406, Wiley, New York, 1991.
2	P. Erdös, A. Hajnal, M. Simonovits, V. T. Sós and E. Szemerédi, Turán-Ramsey theorems and simple asymptotically extremal structures, Combinatorica 13 (1993) no. 1, 31-56.
3	P. Erdös, A. Hajnal, V. T. Sós and E. Szemerédi, More results on Ramsey-Turán type problems, Combinatorica 3 (1983) no. 1, 69-81.
4	B. Sudakov, Few remarks on the Ramsey-Turan-type problems, J. Combinatorial Theory Ser. B 88 (2003), 99-106.

Upper bound for \(rt(n, 4; n/log(n))\)

Problem[1]