posted on 2013-12-03, 00:00authored byJozsef Balogh, John Lenz
Let r be an integer, f(n) be a function, and H be a graph. Introduced by Erdos, Hajnal, Sos, and Szemeredi, the r-Ramsey-Turan number of H, RTr(n, H, f(n)), is defined to be the maximum number of edges in an n-vertex, H-free graph G with alpha(r)(G) <= f(n), where alpha(r)(G) denotes the K-r-independence number of G.
In this note, using isoperimetric properties of the high-dimensional unit sphere, we construct graphs providing lower bounds for RTr(n, Kr+s, o(n)) for every 2 <= s <= r. These constructions are sharp for an infinite family of pairs of r and s. The only previous sharp construction (for such values of r and s) was by Bollobas and Erdos for r=s=2.
History
Publisher Statement
This is a pre-copy-editing, author-produced PDF of an article accepted for publication in Bulletin of the London Mathematical Society following peer review. The definitive publisher-authenticated version Balogh J, Lenz J. Some exact Ramsey-Turan numbers. Bulletin of the London Mathematical Society. Dec 2012;44:1251-1258. is available online at: http://blms.oxfordjournals.org/