Abstract: Let $t$ be an integer, $f(n)$ a function, and $H$ a graph. Define the $t$-Ramsey-Turán number of $H$, $RT_t(n, H, f(n))$, to be the maximum number of edges in an $n$-vertex, $H$-free graph $G$ with $\alpha_t(G) \leq f(n)$, where $\alpha_t(G)$ is the maximum number of vertices in a $K_t$-free induced subgraph of $G$. Erdõs, Hajnal, Simonovits, Sós, and Szemerédi posed several open questions about $RT_t(n,K_s,o(n))$, among them finding the minimum $\ell$ such that $RT_t(n,K_{t+\ell},o(n)) = \Omega(n^2)$. We answer this question by proving that $RT_t(n,K_{t+2},o(n)) = \Omega(n^2)$. From the other side, it is easy to see that $RT_t(n,K_{t+1},o(n)) = o(n^2)$. Our constructions which show that $RT_t(n,K_{t+2},o(n)) = \Omega(n^2)$ also imply several results on the Ramsey-Turán numbers of hypergraphs.
This is a work in progress, it is joint work with John Lenz.
Minden érdeklõdõt szeretettel várunk,
Péter