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

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه ریاضی کاربردی و علوم کامپیوتر، دانشکده ریاضی و آمار، دانشگاه اصفهان

2 گروه کامپیوتر و علوم اطلاعات، دانشگاه لینشوپینگ، سوئد

چکیده

بسیاری از قضایا‌یی که در دهه‌های ۶۰ و ۷۰ میلادی در ترکیبیات و نظریه‌ی گراف توسط پژوهشگران توسعه داده شده‌اند، امروزه در طراحی الگوریتم‌ها و حل مسائل جدید همچنان کاربرد دارد. هدف این مقاله این است که نشان دهیم چیزهای مفیدی در گذشته رخ داده است که نباید آنها را فراموش کنیم و باید با نگاهی خلاقانه از آنها استفاده کنیم. لم بلاباس، که در دهه 1970 مطرح شد یک مسئله معروف در حوزه ترکیبیات است. در این مسئله، یک خانواده از مجموعه‌های $A_1, A_2,\ldots,A_m$ هر کدام با اندازه $a$ و خانواده‌ای دیگر از ‌مجموعه‌ها $B_1, B_2,\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} $ بیان می‌کند. در این مقاله، پس از بیان حالات لم و اثبات موجود برای این لم، اثبات دیگری بر پایه احتمال برای لم بلاباس ارائه می‌دهیم و سپس با نگاهی متفاوت به این مسئله ترکیبیاتی، به بررسی کاربردهای جالب این لم در مسائل نظریه گراف و الگوریتم‌های پارامتری می‌پردازیم.

کلیدواژه‌ها


[1] B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar., 16 (1965) 447–452.
[2] B. Bollobás, The art of mathematics. Coffee time in Memphis, Cambridge University Press, New York, 2006.
[3] C. Bey, Polynomial LYM inequalities, Combinatorica, 25 no. 1 (2005) 19–38.
[4] F. V. Fomin and P. Kaski, Exact exponential algorithms, Communications of the ACM, 56 no. 3 (2013) 80–88.
[5] L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Academic Press, London-New York, (1977) 45–86.
[6] M. Naor, L. J. Schulman and A. Srinivasan, Splitters and near-optimal derandomization, InProceedings of IEEE 36th Annual Foundations of Computer Science, (1995) 182–191.
[7] M. Cygan, F. V. Fomin, L. Kowalik ,D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized algorithms, Springer (2015).