2015/10/14 by Patrick Bennett, Bennett, Patrick, Andrzej Dudek +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1510.03950
25 pp
arxiv created 2015/11/14 · arxiv updated 2015/11/17
Let s be an integer, f=f(n) a function, and H a graph. Define the Ramsey-Turán number RTs(n,H, f) as the maximum number of edges in an H-free graph G of order n with αs(G) < f, where αs(G) is the maximum number of vertices in a Ks-free induced subgraph of G. The Ramsey-Turán number attracted a considerable amount of attention and has been mainly studied for f not too much smaller than n. In this paper we consider RTs(n,Kt, nδ) for fixed δ<1. We show that for an arbitrarily small ε>0 and 1/2<δ< 1, RTs(n,Ks+1, nδ) = Ω(n1+δ-ε) for all sufficiently large s. This is nearly optimal, since a trivial upper bound yields RTs(n,Ks+1, nδ) = O(n1+δ). Furthermore, the range of δ is as large as possible. We also consider more general cases and find bounds on RTs(n,Ks+r,nδ) for fixed r≥2. Finally, we discuss a phase transition of RTs(n, K2s+1, f) extending some recent result of Balogh, Hu and Simonovits.