کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428637 686850 2011 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász Local Lemma
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász Local Lemma
چکیده انگلیسی

Schweitzer [Inform. Process. Lett. 109 (2009) 229–232] described a connection between the incompressibility method and the Lovász Local Lemma. The idea was illustrated on the problem of lower bounding van der Waerden numbers. However, his result using incompressibility is worse than that obtained by Local Lemma by a multiplicative factor of 4/e4/e. In this paper we improve his method to give exactly the same result as the Lovász Local Lemma.

Research highlights
► Incompressibility arguments sometimes give us identical results as Local Lemma.
► We present case study for lower bounding of Van der Waerden numbers.
► We sharpen similar result of Pascal Schweitzer.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 9, 1 April 2011, Pages 436–439
نویسندگان
, ,