Some exact Ramsey-Turan numbers

被引:9
作者
Balogh, Jozsef [1 ]
Lenz, John [2 ]
机构
[1] Univ Illinois, Dept Math, Champaign, IL 61821 USA
[2] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USA
关键词
D O I
10.1112/blms/bds053
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:1251 / 1258
页数:8
相关论文
共 17 条
  • [1] A NOTE ON RAMSEY NUMBERS
    AJTAI, M
    KOMLOS, J
    SZEMEREDI, E
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1980, 29 (03) : 354 - 360
  • [2] EXTREMAL UNCROWDED HYPERGRAPHS
    AJTAI, M
    KOMLOS, J
    PINTZ, J
    SPENCER, J
    SZEMEREDI, E
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1982, 32 (03) : 321 - 335
  • [3] Ajtai M., 1981, European J. Combin, V2, P1
  • [4] Balogh J., ISRAEL J MA IN PRESS
  • [5] RAMSEY-TURAN TYPE PROBLEM
    BOLLOBAS, B
    ERDOS, P
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1976, 21 (02) : 166 - 168
  • [6] Erdoos P., 1970, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, P395
  • [7] CONSTRUCTION OF CERTAIN GRAPHS
    ERDOS, P
    ROGERS, CA
    [J]. CANADIAN JOURNAL OF MATHEMATICS, 1962, 14 (04): : 702 - &
  • [8] MORE RESULTS ON RAMSEY TURAN TYPE PROBLEMS
    ERDOS, P
    HAJNAL, A
    SOS, VT
    SZEMEREDI, E
    [J]. COMBINATORICA, 1983, 3 (01) : 69 - 81
  • [9] ON THE STRUCTURE OF LINEAR GRAPHS
    ERDOS, P
    STONE, AH
    [J]. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) : 1087 - 1091
  • [10] Erdos P., 1994, Combin. Probab. Comput., P297