University of Illinois Chicago
Browse

Some Exact Ramsey-Turan Numbers

Download (281.11 kB)
journal contribution
posted on 2013-12-03, 00:00 authored by Jozsef 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/

Publisher

Oxford University Press

Language

  • en_US

issn

0024-6093

Issue date

2012-12-01

Usage metrics

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC