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

Home

Search

Subjects

About Erdös

About This Site

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

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.