کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424548 | 1632979 | 2015 | 22 صفحه PDF | دانلود رایگان |
Let f(n) be a function and H be a graph. Denote by RT(n,H,f(n)) the maximum number of edges of an H-free graph on n vertices with independence number less than f(n). ErdÅs and Sós [12] asked if RT(n,K5,cn)=o(n2) for some constant c. We answer this question by proving the stronger RT(n,K5,o(nlogâ¡n))=o(n2). It is known that RT(n,K5,cnlogâ¡n)=n2/4+o(n2) for c>1, so one can say that K5 has a Ramsey-Turán phase transition at cnlogâ¡n. We extend this result to several other Ks's and functions f(n), determining many more phase transitions. We formulate several open problems, in particular, whether variants of the Bollobás-ErdÅs graph exist to give good lower bounds on RT(n,Ks,f(n)) for various pairs of s and f(n). Among others, we use Szemerédi's Regularity Lemma and the Hypergraph Dependent Random Choice Lemma. We also present a short proof of the fact that Ks-free graphs with small independence number are sparse: on n vertices have o(n2) edges.
Journal: Journal of Combinatorial Theory, Series B - Volume 114, September 2015, Pages 148-169