موضوع مقاله: لم اسپرنر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # لم اسپرنر | مقدمه: لم اسپرنر در واقع معادل ترکیبیاتی قضیهٔ نقطهٔ ثابت برور می‌باشد و توسط امانویل اسپرنر اثبات شده‌است. | ## بخش 1: لم اسپرنر | این لم به زبان ساده بیان می‌کند که در هر رنگ آمیزی اسپرنری (که در پایین به تعریف این نوع از رنگ آمیزی خواهیم پرداخت) یک سیمپلکس بعدی مثلث بندی شده، حداقل یک سلول شامل تمامی رنگ‌ها دارد (در واقع در این رنگ آمیزی رأس‌ها را رنگ می‌کنیم و این لم بیان می‌کند که حداقل یکی از فضاهای به وجود آمده توسط مثلث‌بندی شدن این سیمپلکس قطعاً در رأس‌های خود تمامی رنگ‌ها را خواهد داشت). رنگ آمیزی اسپرنری چندین کاربرد دارد که از آن‌ها می‌توان به محاسبهٔ کارآمد نقاط ثابت یک تابع، پیدا کردن ریشه‌های معادله‌ها و تقسیم عادلانه (مسألهٔ برش کیک که یکی از مسایل مطرح در نظریهٔ بازی‌ها است) اشاره کرد. برای درک بهتر این لم آن را برای بعدهای پایین بیان می‌کنیم تا شهودی نسبت به آن پیدا کنیم. حالت یک بعدی در حالت یک بعدی این قضیه بیان می‌کند که یک تابع که روی یک فضای گسستهٔ یک بعدی (مثل نقاطی روی یک خط) که تنها مقادیر صفر و یک را به خود اختصاص می‌دهد و با مقدار صفر شروع می‌کند و به مقدار یک تمام می‌شود به تعداد فردی مقدار خود را بین صفر و یک عوض می‌کند. در واقع فرض کنید پاره‌خطی عمودی داریم و نقطهٔ بالایی این پاره‌خط را با رنگ سبز و نقطهٔ پایینی آن را با رنگ آبی رنگ کنیم حتماً تکه‌پاره خطی وجود دارد که رنگ دو سر آن‌ها سبز و آبی (متفاوت) است و تعداد تکه‌پاره‌خط‌های به وجود آمده که دو سر آن‌ها رنگ سبز و آبی (متفاوت) هستند، فرد است. حالت دو بعدی این حالت از قضیهٔ اسپرنر در واقع حالتی از آن است که بیشتر از بقیهٔ حالت‌های آن مطرح می‌شود که شرح آن به صورت زیر است: یک مثلث بندی از مثلث را در نظر بگیرید. رأس‌های روی یال از مثلث را با دو رنگ سبز و قرمز و رأس‌های روی یال را با دو رنگ قرمز و آبی و رأس‌های روی یال را با دو رنگ سبز و آبی رنگ می‌کنیم (در واقع رأس‌های روی یال‌های تنها با رنگ‌های دوسر یالشان در مثلث بزرگ رنگ می‌شوند). لم اسپرنر هم چنین بیان می‌کند که تعداد فردی از این مثلث‌های سه رنگ (مثلث‌هایی که رنگ‌های سه راسشان متفاوت از هم است) وجود دارند. تابع را تابع رنگ آمیزی در نظر بگیرید که به هر راس از مثلث بندی یکی از رنگ‌های بین تا را اختصاص می‌دهد. اما این رنگ‌آمیزی نمی‌تواند به هر صورتی باشد و باید در شرایط زیر صدق کند: رأس‌های سیمپلکس بزرگ باید با رنگ‌های متفاوت رنگ شده باشند (هر راس یک رنگ متفاوت از بقیهٔ رأس‌های سیمپلکس اصلی از بین رنگ موجود را به خود بگیرد). راس‌هایی از که در یک زیرفضای بعدی قرار دارند همانند باید تنها با رنگ‌های رنگ شده باشند. اثبات برای بعدهای بالاتر با استقرا بر روی تعداد بعدها و با استدلالی شبیه به اثبات حالت دو بعدی این لم است. اثبات حالت دو بعدی گراف را از روی مثلث‌بندی می‌سازیم به اینصورت که به ازای هر مثلث موجود در یک راس در داریم. یک راس هم در گراف اختصاصی برای فضای بیرون از مثلث اصلی قرار می‌دهیم (در واقع نمایندهٔ آن فضا است) که آن را می‌نامیم. بین راس ، در گراف یال می‌گذاریم اگر و تنها اگر بین این دو ناحیه ضلع مشترک در مثلث‌بندی وجود داشته باشد و دو سر این ضلع با (البته دقت کنید که راسی که برای فضای بیرون از مثلث اختصاص دادیم به تمامی مثلث‌هایی که یکی از اضلاعشان روی مثلث اصلی قرار دارد، ضلع مشترک دارد و اگر دو سر این ضلع رنگ‌های متفاوت داشته‌باشند یال هم به آن‌ها دارد). زیرا بر روی هر ضلع مثلث بزرگ تعداد فردی ضلع وجود دارد که دو سر آن‌ها رنگ‌های متفاوتی داشته‌باشند. | ## بخش 2: لم اسپرنر | تعداد این ضلع‌های فرد روی ضلع اول مثلث بزرگ را اگر بنامیم و روی ضلع‌های دوم و سوم را به ترتیب بنامیم داریم: در این صورت پس فرد است. پس بنابراین قضیه که در یک گراف متناهی تعداد زوجی راس با درجهٔ فرد حضور دارند، بنابراین لااقل یک راس دیگر با درجهٔ فرد در گراف حضور دارد. به سادگی می‌توان مشاهده کرد که بقیه رأس‌های گراف به جز تنها می‌توانند درجه‌های داشته باشند (دقت کنید که برای این رأس‌های گراف تنها سه ضلع هست و بنابراین درجه قطعاً کمتر مساوی است اما با بررسی حالات مختلف می‌بینیم تنها درجه‌های ممکن (برای حالتی که تمام رأس‌های مثلث همرنگ هستند) و (برای حالتی که دو راس مثلث همرنگ باشند) و (برای حالتی که هر سه راس مثلث رنگ متفاوت داشته باشند) هستند. پس با توجه به اینکه یک راس دیگر با درجهٔ فرد به جز داریم لااقل یک راس با درجهٔ سه و در واقع یک مثلث تمام‌رنگ (هر سه راس رنگ‌های متفاوتی دارند و بنابراین تمام رنگ‌ها را دارند) داریم. برای سیمپلکس بعدی که ، با فرض اینکه گزاره برای سمپلکس‌های کمتر از بعدی درست است، در یک مثلث‌بندی T از سیمپلکس اصلی، در هر وجه از ، فرد سیمپلکس بعدی کامل وجود دارد. مانند قبل رأسی در که رنگ مشابه با را از حذف می‌کنیم و رأس جدیدی غیر از رأس حذف شده به آن اضافه می‌کنیم و این فرایند را ادامه می‌دهیم و یک زنجیره از سمپلکس‌های بعدی که هر کدام با رنگ متفاوت رنگ‌آمیزی شده‌اند می‌سازیم. می‌دانیم برای رسیدن به یک سیمپلکس بعدی از یک سیمپلکس بعدی دیگر با روش حذف یک رأس و اضافه کردن یک رأس جدید دو روش وجود دارد (یعنی به ازای هر سیمپلکس دو رأس وجود دارند که با اضافه کردن آن‌ها به سیمپلکس مذکور، یک سیمپلکس بعدی ایجاد می‌شود). حال از آن‌جا که در زنجیره‌ای که در حال ساختن آن هستیم هر به ازای هر سیمپلکس (به جز سیمپلکس اول زنجیره)، دو سیمپلکس دیگری که می‌توانند برای رسیدن به آن به کار برده شوند قبل و بعد از آن آمده‌اند و همچنین از آن‌جا که سیمپلکس اول در مرز (وجه) قرار دارد و تنها یک راه برای رسیدن به آن وجود دارد که همان سیمپلکس دوم زنجیره است، در این زنجیره هیچ‌گاه یک سیمپلکس تکراری دیده نمی‌شود؛ بنابراین طول زنجیره متناهی است. حالت اول این است که به یک سیمپلکس بعدی کامل برسیم و حالت دوم نیز این است که به یکی از وجه‌ها برسیم و زنجیره دیگر قابل ادامه دادن نباشد. در حالت دوم از آن‌جا که می‌دانیم تمامی سیمپلکس‌های این زنجیره با مجموعهٔ رنگ‌های ساخته شده‌اند وجهی که می‌توانیم با رسیدن به آن متوقف شویم همان وجهی است که با آن شروع کرده‌ایم یعنی . بنابراین تمامی سیمپلکس‌های وجه یا با زنجیره‌هایی که در بالا گفتیم دو به دو به هم متصل می‌شوند یا به یک سیمپلکس بعدی کامل می‌رسند؛ بنابراین فرد تا از آن‌ها به یک سیمپلکس بعدی کامل می‌رسند. از طرف دیگر سیمپلکس‌های بعدی کامل با حذف رأسی که رنگ دارند و اضافه کردن تنها رأس ممکن دیگر و ساختن زنجیره‌ای مانند بالا، یا به یکی از سیمپلکس‌های وجه می‌رسند یا به یک سیمپلکس بعدی کامل دیگر می‌رسند، یعنی دو به دو جفت می‌شوند. تعداد آن‌هایی که با حالت دوم جفت می‌شوند زوج است و تعداد آن‌هایی که با حالت اول به وجه می‌رسند فرد؛ بنابراین تعداد کل سیمپلکس‌های کامل یعدی در فرد است. تعمیم‌ها تعمیم لم اسپرنر ابتدا چند تعریف برای ساده‌تر شدن توضیحاتمان ارائه می‌کنیم: به یک سیمپلکس بعدی یک -سیمپلکس می‌گویند. اگر این جایگشت زوج باشد (یکی اینکه این تایی اعداد جایگشتی از باشند و بتوان با زوج دفعه جابجایی دوتایی اعداد، به جایگشت مرتب شده رسید) این مقدار را برابر با می‌گیریم. اگر این جایگشت فرد (یکی اینکه این تایی اعداد جایگشتی از باشند و بتوان با فرد دفعه جابجایی دوتایی اعداد، به جایگشت مرتب شده رسید) باشد این مقدار را برابر با و اگر این تایی یک جایگشت از اعداد نباشد این مقدار برابر است. | ## بخش 3: لم اسپرنر | برای مثال داریم: حال با فرض اینکه یک -سیمپلکس جهت‌دار است که به هر رأس رنگ نسبت داده شده‌است. تعریف تابع برای آن به شکل زیر می‌شود: همچنین می‌توان تعریف را بر روی n-زنجیره‌ها به صورت خطی گسترش داد، به‌طوری‌که اگر آن‌گاه . حالت کلی اسپرنر به صورت زیر تعریف می‌شود: فرض کنید یک k-زنجیره از k-سیمپلکس‌ها باشد که با رنگ‌های مجموعهٔ رنگ شده‌است. درجهٔ رنگ‌آمیزی را برابر با اختلاف تعداد تعویض‌ها از به و تعداد تعویض‌ها از به در دنبالهٔ یاد شده تعریف کنید. دقت کنید درجه اگر به شکل تعداد تعویض‌ها از به منهای تعداد تعویض‌ها از به یا تعداد تعویض‌ها از به منهای تعداد تعویض‌ها از به نیز تعریف شود، مقدارش تغییری نمی‌کند. داریم تعداد مثلث‌هایی که سه رأس آن‌ها به رنگ متفاوت رنگ شده‌اند حداقل برابر درجهٔ رنگ‌آمیزی است. به خصوص اگر درجه ناصفر باید یه مثلث وجود دارد که ضلع آن با رنگ‌های متفاوتی رنگ شده‌اند. زوج‌های (سیمپلکس، جایگشت) را به شکلی در نظر می‌گیریم که رنگ هر رأس سیمپلکس از یک رنگ‌آمیزی متفاوت آمده باشد (بنابراین برای هر سیمپلکس زوج متفاوت خواهیم داشت). حال حداقل زوج وجود دارند که شامل سلولی هستند که رئوس آن با رنگ‌های متفاوتی رنگ شده‌است. فرض کنید نفر برای یه مثلث‌بندی از یک سیمپلکس رنگ‌آمیزی‌های متفاوتی را ارائه داده‌اند. یه سیمپلکس رنگ‌آمیزی شده و یک تطابق از این افراد به رئوس آن سیمپلکس وجود دارد، به‌طوری‌که رنگ هر رأس از سیمپلکس همان رنگی است که فرد متناظر با آن رأس در تطابق، برای آن رأس ارائه داده بود. کاربردها کاربردهای رنگ‌آمیزی اسپرنری رنگ‌آمیزی اسپرنری (در واقع رنگ‌آمیزی با شرایطی که در قسمت قبل گفته شد) چندین کاربرد محاسباتی دارد؛ یکی از این کاربردها پیدا کردن نقطهٔ ثابت توابع هستند. می‌توان به گونه‌ای یک سیمپلکس را رنگ کرد که سیمپلکس‌های تمام‌رنگ به معنای وجود نقاط ثابت در آن حوالی در یک تابع باشند. با کوچک و کوچک‌تر کردن مثلث‌بندی‌ها می‌توان ثابت کرد که نقطهٔ همگرایی سیمپلکس‌های تمام‌رنگ دقیقاً همان نقطهٔ ثابت تابع است. به همین دلیل از لم اسپرنر می‌توان در الگوریتم‌هایی که برای پیدا کردن ریشهٔ توابع به کار می‌روند. از این روش رنگ‌آمیزی و لم اسپرنر در بعضی از الگوریتم‌های تقسیم عادلانه استفاده می‌شود. | ## جمع‌بندی | کاربردهای لم اسپرنر در برش کیک با استفاده از این لم ثابت می‌شود که تقسیم‌بندی بدون رشک کیک بین نفر با تنها برش ممکن است (به عبارت دیگر یک تخصیص پیوستهٔ بدون رشک قطعاً وجود دارد).