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

بسیاری از قضایا یی که در دهه های ۶۰ و ۷۰ میلادی در ترکیبیات و نظریه ی گراف توسط پژوهشگران توسعه داده شده اند، امروزه در طراحی الگوریتم ها و حل مسائل جدید همچنان کاربرد دارد. هدف این مقاله این است که نشان دهیم چیزهای مفیدی در گذشته رخ داده است که نباید آنها را فراموش کنیم و باید با نگاهی خلاقانه از آنها استفاده کنیم. لم بلاباس، که در دهه ۱۹۷۰ مطرح شد یک مسئله معروف در حوزه ترکیبیات است. در این مسئله، یک خانواده از مجموعه های A_۱, A_۲,\ldots,A_m هر کدام با اندازه a و خانواده ای دیگر از مجموعه ها B_۱, B_۲,\ldots,B_m هر کدام با اندازه b داریم. هدف یافتن بیشترین مقدار m از تعداد مجموعه ها است به طوری که برای هر اندیس i داشته باشیم A_i\cap B_i = \emptyset و همچنین A_i\cap B_j \neq \emptyset، برای هر i \neq j. لم بلاباس کران بالایی برای حداکثر تعداد این مجموعه ها به صورت m\leq \binom{a+b}{b} بیان می کند. در این مقاله، پس از بیان حالات لم و اثبات موجود برای این لم، اثبات دیگری بر پایه احتمال برای لم بلاباس ارائه می دهیم و سپس با نگاهی متفاوت به این مسئله ترکیبیاتی، به بررسی کاربردهای جالب این لم در مسائل نظریه گراف و الگوریتم های پارامتری می پردازیم.

کلیدواژه ها:

لم بلاباس ، الگوریتم پارامتری ، مجموعه معرف