ON POSSIBLE TURAN DENSITIES

被引:22
作者
Pikhurko, Oleg [1 ,2 ]
机构
[1] Univ Warwick, Inst Math, Coventry CV4 7AL, W Midlands, England
[2] Univ Warwick, DIMAP, Coventry CV4 7AL, W Midlands, England
基金
美国国家科学基金会; 欧洲研究理事会;
关键词
EXTREMAL PROBLEMS; HYPERGRAPH; GRAPHS; MULTIGRAPH;
D O I
10.1007/s11856-014-0031-5
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The Turan density pi(T) of a family F of k-graphs is the limit as n -> infinity of the maximum edge density of an F-free k-graph on n vertices. Let Pi((k))(infinity) consist of all possible Turan densities and let Pi((k))(fin) subset of Pi((k))(infinity) be the set of Turan densities of finite k-graph families. Here we prove that Pi((k))(fin) contains every density obtained from an arbitrary finite construction by optimally blowing it up and using recursion inside the specified set of parts. As an application, we show that Pi((k))(fin) contains an irrational number for each k >= 3. Also, we show that Pi((k))(infinity) has cardinality of the continuum. In particular, Pi((k))(infinity) not equal Pi((k))(fin).
引用
收藏
页码:415 / 454
页数:40
相关论文
共 50 条
  • [41] A Generalized Turan Problem and Its Applications
    Gishboliner, Lior
    Shapira, Asaf
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 760 - 772
  • [42] Signed spectral Turan type theorems
    Kannan, M. Rajesh
    Pragada, Shivaramakrishna
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2023, 663 : 62 - 79
  • [43] On Substructure Densities of Hypergraphs
    Peng, Yuejian
    GRAPHS AND COMBINATORICS, 2009, 25 (04) : 583 - 600
  • [44] Generalized Turan problems for even cycles
    Gerbner, Daniel
    Gyori, Ervin
    Methuku, Abhishek
    Vizer, Mate
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 145 : 169 - 213
  • [45] A Brualdi-Hoffman-Turan problem on cycles
    Li, Xin
    Zhai, Mingqing
    Shu, Jinlong
    EUROPEAN JOURNAL OF COMBINATORICS, 2024, 120
  • [46] Note on a Turan-type problem on distances
    Li, Xueliang
    Ma, Jing
    Shi, Yongtang
    Yue, Jun
    ARS COMBINATORIA, 2015, 119 : 211 - 219
  • [47] Turan Numbers of Multiple Paths and Equibipartite Forests
    Bushaw, Neal
    Kettle, Nathan
    COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (06) : 837 - 853
  • [48] On the Turan number of some ordered even cycles
    Gyori, Ervin
    Korandi, Daniel
    Methuku, Abhishek
    Tomon, Istvan
    Tompkins, Casey
    Vizer, Mate
    EUROPEAN JOURNAL OF COMBINATORICS, 2018, 73 : 81 - 88
  • [49] Solving Turan's tetrahedron problem for the l2$\ell _2$-norm
    Balogh, Jozsef
    Clemen, Felix Christian
    Lidicky, Bernard
    JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2022, 106 (01): : 60 - 84
  • [50] Some sharp results on the generalized Turan numbers
    Ma, Jie
    Qiu, Yu
    EUROPEAN JOURNAL OF COMBINATORICS, 2020, 84