کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657513 1343743 2007 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on the jumping constant conjecture of Erdős
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A note on the jumping constant conjecture of Erdős
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 97, Issue 2, March 2007, Pages 204-216