On the Ramsey-Turán numbers of graphs and hypergraphs

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 where f(n) is larger than 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 s such that $R{T}_t(n,K_{t+s},o(n))=\Omega (n^2)$, where it is easy to see that $R{T}_t(n,K_{t+1},o(n))=o(n^2)$. In this paper, we answer this question by proving that $R{T}_t(n,K_{t+2},o(n))=\Omega (n^2)$; our constructions also imply several results on the Ramsey-Turán numbers of hypergraphs.

arXiv comment20 pages, 2 figures

Cited by in corpus (5)

• The critical window for the classical Ramsey-Turán problem
• Phase transitions in the Ramsey-Turán theory
• Hypergraphs with Zero Chromatic Threshold
• A Ramsey-Turán theory for tilings in graphs
• A generalised isodiametric problem