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 条
  • [21] Inverting the Turan problem
    Briggs, Joseph
    Cox, Christopher
    DISCRETE MATHEMATICS, 2019, 342 (07) : 1865 - 1884
  • [22] On the Turan Density of Uniform Hypergraphs
    Chang, An
    Gao, Guo-Rong
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2023, 39 (03): : 638 - 646
  • [23] Generalized Planar Turan Numbers
    Gyori, Ervin
    Paulos, Addisu
    Salia, Nika
    Tompkins, Casey
    Zamora, Oscar
    ELECTRONIC JOURNAL OF COMBINATORICS, 2021, 28 (04)
  • [24] Turan's theorem inverted
    Nikiforov, Vladimir
    DISCRETE MATHEMATICS, 2010, 310 (01) : 125 - 131
  • [25] Turan numbers for disjoint paths
    Yuan, Long-Tu
    Zhang, Xiao-Dong
    JOURNAL OF GRAPH THEORY, 2021, 98 (03) : 499 - 524
  • [26] TURAN NUMBERS OF BIPARTITE SUBDIVISIONS
    Jiang, Tao
    Qiu, Yu
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (01) : 556 - 570
  • [27] The Turan problem for projective geometries
    Keevash, P
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2005, 111 (02) : 289 - 309
  • [28] Generalized rainbow Turan problems
    Gerbner, Daniel
    Methuku, Abhishek
    Meszaros, Tamas
    Palmer, Cory
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (02)
  • [29] Turan numbers and batch codes
    Bujtas, Csilla
    Tuza, Zsolt
    DISCRETE APPLIED MATHEMATICS, 2015, 186 : 45 - 55
  • [30] On Turan numbers for disconnected hypergraphs
    Mulas, R.
    Nie, J.
    ACTA MATHEMATICA HUNGARICA, 2023, 170 (01) : 168 - 182