کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650999 | 1342515 | 2007 | 13 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 307, Issue 14, 28 June 2007, Pages 1754–1766