Some Exact Ramsey-Turan Numbers
PublisherOxford University Press
MetadataShow full item record
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.