Article ID Journal Published Year Pages File Type
4657513 Journal of Combinatorial Theory, Series B 2007 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics