caa a22 4500 445358416 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00493-011-2626-3 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2626-3 On K s -free subgraphs in K s + k -free graphs and vertex Folkman numbers [Elektronische Daten] [Andrzej Dudek, Vojtěch Rödl] Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K s }}, where the minimum is taken over all K t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n 1/2+o(1)) ≤ f s,s+1(n) ≤ O(n 1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f s,s+1(n) ≤ O(n 2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n 1/2−ɛ ) ≤ f s,s+k (n) ≤ O(n 1/2+ɛ . In addition, we also discuss some connections between the function f s,t and vertex Folkman numbers. János Bolyai Mathematical Society and Springer Verlag, 2011 Dudek Andrzej Department of Mathematical Sciences, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut Rödl Vojtěch Department of Mathematics and Computer Science, Emory University, 30322, Atlanta, GA, USA aut Combinatorica Springer-Verlag 31/1(2011-01-01), 39-53 0209-9683 31:1<39 2011 31 493 https://doi.org/10.1007/s00493-011-2626-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2626-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dudek Andrzej Department of Mathematical Sciences, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 700 1- Rödl Vojtěch Department of Mathematics and Computer Science, Emory University, 30322, Atlanta, GA, USA aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/1(2011-01-01), 39-53 0209-9683 31:1<39 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer