2022/08/01 by Jianfeng Hou, Hou, Jianfeng, Heng Li +5 · 2 citations
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2208.00794
openalex publication_date 2022/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let r≥ 2 be an integer. The real number α∈ [0,1] is a jump for r if there exists a constant c > 0 such that for any ε>0 and any integer m ≥ r, there exists an integer n0(ε, m) satisfying any r-uniform graph with n≥ n0(ε, m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c. A result of Erdős, Stone and Simonovits implies that every α∈ [0,1) is a jump for r=2. Erdős asked whether the same is true for r≥ 3. Frankl and Rödl gave a negative answer by showing that 1-\frac1lr-1 is not a jump for r if r≥ 3 and l>2r. After that, more non-jumps are found using a method of Frankl and Rödl. In this note, we show a method to construct maps f \colon [0,1] → [0,1] that preserve non-jumps, if α is a non-jump for r given by the method of Frankl and Rödl, then f(α) is also a non-jump for r. We use these maps to study hypergraph Turán densities and answer a question posed by Grosu.