Partite Turan-densities for complete r-uniform hypergraphs on r

被引:0
|
作者
Markstrom, Klas [1 ]
Thomassen, Carsten [2 ]
机构
[1] Umea Univ, Dept Math & Math Stat, SE-90187 Umea, Sweden
[2] Tech Univ Denmark, Dept Appl Math & Comp Sci, DK-2800 Lyngby, Denmark
基金
瑞典研究理事会;
关键词
Turan problem; mulitpartite; hypergraph; MINIMAL DENSITY; TRIANGLES; REGULARITY; BOUNDS; LEMMA;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper we investigate density conditions for finding a complete r-uniform hypergraph K-r+1((r)) on r + 1 vertices in an (r + 1)-partite r-uniform hypergraph G. First we prove an optimal condition in terms of the densities of the (r + 1) induced r-partite subgraphs of G. Second, we prove a version of this result where we assume that r-tuples of vertices in G have their neighbours evenly distributed in G. Third, we also prove a counting result for the minimum number of copies of K-r+1((r)) when G satisfies our density bound, and present some open problems. A striking difference between the graph, r = 2, and the hypergraph, r >= 3, cases is that in the first case both the existence threshold and the counting function are non-linear in the involved densities, whereas for hypergraphs they are given by a linear function. Also, the smallest density of the r-partite parts needed to ensure the existence of a complete r-graph with (r + 1) vertices is equal to the golden ratio t = 0.618 ... for r = 2, while it is r/r+1 for r >= 3.
引用
收藏
页码:235 / 245
页数:11
相关论文
共 13 条
  • [1] CODEGREE TURAN DENSITY OF COMPLETE r-UNIFORM HYPERGRAPHS
    Lo, Allan
    Zhao, Yi
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 1154 - 1158
  • [2] On Hamilton cycle decompositions of r-uniform r-partite hypergraphs
    Schroeder, Michael W.
    DISCRETE MATHEMATICS, 2014, 315 : 1 - 8
  • [3] On Lagrangians of r-uniform hypergraphs
    Peng, Yuejian
    Tang, Qingsong
    Zhao, Cheng
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 30 (03) : 812 - 825
  • [4] On r-uniform hypergraphs with circumference less than r
    Kostochka, Alexandr
    Luo, Ruth
    DISCRETE APPLIED MATHEMATICS, 2020, 276 (276) : 69 - 91
  • [5] On Laplacian Energy of r-Uniform Hypergraphs
    Yalcin, N. Feyza
    SYMMETRY-BASEL, 2023, 15 (02):
  • [6] Matching and domination numbers in r-uniform hypergraphs
    Kang, Liying
    Li, Shan
    Dong, Yanxia
    Shan, Erfang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) : 656 - 659
  • [7] Matching and domination numbers in r-uniform hypergraphs
    Liying Kang
    Shan Li
    Yanxia Dong
    Erfang Shan
    Journal of Combinatorial Optimization, 2017, 34 : 656 - 659
  • [8] On r-uniform linear hypergraphs with no Berge-K2,t
    Timmons, Craig
    ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (04)
  • [9] Connection Between Continuous Optimization and Turan Densities of Non-uniform Hypergraphs
    Guo, Xiao-bing
    Peng, Yue-jian
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2021, 37 (04): : 858 - 866
  • [10] Hamiltonian decomposition of complete bipartite r-hypergraphs
    Jirimutu
    Jianfang W.
    Acta Mathematicae Applicatae Sinica, 2001, 17 (4) : 563 - 566