Generating non-jumps from a known one
摘要
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 and Simonovits (1966) and Erdős and Stone (1946) implies that every α ∈ [0, 1) is a jump for r = 2. Erdős (1964) asked whether the same is true for r ⩾ 3. Frankl and Rödl (1984) gave a negative answer by showing that