Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657513 | Journal of Combinatorial Theory, Series B | 2007 | 13 Pages |
Let r⩾2 be an integer. The real number α∈[0,1] is a jump for r if there exists c>0 such that for every positive ϵ and every integer m⩾r, every r-uniform graph with n>n0(ϵ,m) vertices and at least edges contains a subgraph with m vertices and at least edges. A result of Erdős, Stone and Simonovits implies that every α∈[0,1) is a jump for r=2. For r⩾3, Erdős asked whether the same is true and showed that every is a jump. Frankl and Rödl gave a negative answer by showing that is not a jump for r if r⩾3 and l>2r. Another well-known question of Erdős is whether is a jump for r⩾3 and what is the smallest non-jumping number. In this paper we prove that is not a jump for r⩾3. We also describe an infinite sequence of non-jumping numbers for r=3.