Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.jctb.2016.09.002 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Ramsey,Turán,Finite geometries | Journal | 122 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
P BENNETT | 1 | 15 | 5.42 |
Andrzej Dudek | 2 | 114 | 23.10 |