کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657513 | 1343743 | 2007 | 13 صفحه PDF | دانلود رایگان |
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.
Journal: Journal of Combinatorial Theory, Series B - Volume 97, Issue 2, March 2007, Pages 204-216