On Substructure Densities of Hypergraphs

详细信息    查看全文

• 作者：Yuejian Peng
• 关键词：Extremal problems in hypergraphs ; Tur¨¢n density ; Erd?s jumping constant conjecture
• 刊名：Graphs and Combinatorics
• 出版年：2009
• 出版时间：November, 2009
• 年：2009
• 卷：25
• 期：4
• 页码：583-600
• 全文大小：230.3 KB

文摘

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n ₀ such that any r-uniform graph with n > n ₀ vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erd?s and Stone that every α ∈ [0, 1) is a jump for r = 2. Erd?s also showed that every number in [0, r!/r r ) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and R?dl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erd?s’ by Frankl, Peng, R?dl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.