Article ID Journal Published Year Pages File Type
4650999 Discrete Mathematics 2007 13 Pages PDF
Abstract

Let r⩾2r⩾2 be an integer. A real number α∈[0,1)α∈[0,1) is a jump for rr if for any ε>0ε>0 and any integer m⩾rm⩾r, any rr-uniform graph with n>n0(ε,m)n>n0(ε,m) vertices and density at least α+εα+ε contains a subgraph with mm vertices and density at least α+cα+c, where c=c(α)>0c=c(α)>0 does not depend on εε and mm. A result of Erdős, Stone and Simonovits implies that every α∈[0,1)α∈[0,1) is a jump for r=2r=2. Erdős asked whether the same is true for r⩾3r⩾3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumping numbers for every r⩾3r⩾3. However, there are a lot of unknowns on determining whether or not a number is a jump for r⩾3r⩾3. In this paper, we find two infinite sequences of non-jumping numbers for r=4r=4, and extend one of the results to every r⩾4r⩾4. Our approach is still based on the approach developed by Frankl and Rödl.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,