لم بلاباس: تحلیل، کاربرد و الگوریتم

بسیاری از قضایا‌یی که در دهه‌های 60 و 70 میلادی در ترکیبیات و نظریه‌ی گراف توسط پژوهشگران توسعه داده شده‌اند، امروزه در طراحی الگوریتم‌ها و حل مسائل جدید همچنان کاربرد دارد. هدف این مقاله این است که نشان دهیم چیزهای مفیدی در گذشته رخ داده است که نباید آنها را فراموش کنیم و باید با نگاهی خلاقانه از آنها استفاده کنیم. لم بلاباس، که در دهه 1970 مطرح شد یک مسئله معروف در حوزه ترکیبیات است. در این مسئله، یک خانواده از مجموعه‌های a_1, a_2,ldots,a_m هر کدام با اندازه a و خانواده‌ای دیگر از ‌مجموعه‌ها b_1, b_2,ldots,b_m هر کدام با اندازه b داریم. هدف یافتن بیشترین مقدار m از تعداد مجموعه‌ها است به‌طوری‌که برای هر اندیس i داشته باشیم a_icap b_i = emptyset و همچنین a_icap b_j neq emptyset، برای هر i neq j. لم بلاباس کران بالایی برای حداکثر تعداد این مجموعه‌ها به‌صورت mleq binom{a+b}{b} بیان می‌کند. در این مقاله، پس از بیان حالات لم و اثبات موجود برای این لم، اثبات دیگری بر پایه احتمال برای لم بلاباس ارائه می‌دهیم و سپس با نگاهی متفاوت به این مسئله ترکیبیاتی، به بررسی کاربردهای جالب این لم در مسائل نظریه گراف و الگوریتم‌های پارامتری می‌پردازیم.

bollobás lemma: analysis, application, algorithm

many of the theorems that were developed by researchers in the 1960s and 1970s in combinations and graph theory as mathematical theorems, are still used today in designing algorithms and solving new problems. the purpose of this article is to show that useful things happened in the past that we should not forget and use them with a creative eye. bollobás lemma cite{bollobas}, which was proposed in the 1970s, is a well-known problem in combinatorics. in this problem, we have a family of sets a_1, a_2,ldots,a_m each with size a and another family of sets b_1, b_2,ldots,b_m each with size b. the goal is to find the maximum size m, the number of sets so that for each index i we have a_i cap b_i = emptyset and also a_i cap b_j neq emptyset where (i neq j). the bollobás lemma expresses the upper bound for the maximum number of these sets as mleq binom{a+b}{b}. in this paper, after stating the versions of the lemma and the existing proof for this lemma, we present another probability-based proof for the bollobás lemma, and then with a different look at this combinatorial problem, we investigate the interesting applications of this lemma in graph theory problems and parameterized algorithms.