لم اسپرنر

لم اسپرنر در واقع معادل ترکیبیاتی قضیهٔ نقطهٔ ثابت برور می‌باشد و توسط امانویل اسپرنر اثبات شده‌است.
این لم به زبان ساده بیان می‌کند که در هر رنگ آمیزی اسپرنری (که در پایین به تعریف این نوع از رنگ آمیزی خواهیم پرداخت) یک سیمپلکس  بعدی مثلث بندی شده، حداقل یک سلول شامل تمامی رنگ‌ها دارد (در واقع در این رنگ آمیزی رأس‌ها را رنگ می‌کنیم و این لم بیان می‌کند که حداقل یکی از فضاهای به وجود آمده توسط مثلث‌بندی شدن این سیمپلکس قطعاً در رأس‌های خود تمامی رنگ‌ها را خواهد داشت).
رنگ آمیزی اسپرنری چندین کاربرد دارد که از آن‌ها می‌توان به محاسبهٔ کارآمد نقاط ثابت یک تابع، پیدا کردن ریشه‌های معادله‌ها و تقسیم عادلانه (مسألهٔ برش کیک که یکی از مسایل مطرح در نظریهٔ بازی‌ها است) اشاره کرد.

بیان لم

در اینجا به این می‌پردازیم که این لم در واقع چه چیزی را بیان می‌کند. همان‌طور که در بالا اشاره شد این لم در سیمپلکس‌های n بعدی تعریف می‌شود. برای درک بهتر این لم آن را برای بعدهای پایین  بیان می‌کنیم تا شهودی نسبت به آن پیدا کنیم.

حالت یک بعدی

در حالت یک بعدی این قضیه بیان می‌کند که یک تابع که روی یک فضای گسستهٔ یک بعدی (مثل نقاطی روی یک خط) که تنها مقادیر صفر و یک را به خود اختصاص می‌دهد و با مقدار صفر شروع می‌کند و به مقدار یک تمام می‌شود به تعداد فردی مقدار خود را بین صفر و یک عوض می‌کند. در واقع فرض کنید پاره‌خطی عمودی داریم و نقطهٔ بالایی این پاره‌خط را با رنگ سبز و نقطهٔ پایینی آن را با رنگ آبی رنگ کنیم حتماً تکه‌پاره خطی وجود دارد که رنگ دو سر آن‌ها سبز و آبی (متفاوت) است و تعداد تکه‌پاره‌خط‌های به وجود آمده که دو سر آن‌ها رنگ سبز و آبی (متفاوت) هستند، فرد است.

اثبات

در این بخش به اثبات لم اسپرنر می‌پردازیم. حالت یک بعدی این لم بسیار بدیهی است. در ابتدا اثباتی برای حالت دو بعدی این لم می‌آوریم. اثبات برای بعدهای بالاتر با استقرا بر روی تعداد بعدها و با استدلالی شبیه به اثبات حالت دو بعدی این لم است.

اثبات حالت دو بعدی

گراف  را از روی مثلث‌بندی  می‌سازیم به اینصورت که به ازای هر مثلث موجود در  یک راس در  داریم. یک راس هم در گراف  اختصاصی برای فضای بیرون از مثلث اصلی قرار می‌دهیم (در واقع نمایندهٔ آن فضا است) که آن را می‌نامیم. بین راس ، در گراف
یال می‌گذاریم اگر و تنها اگر بین این دو ناحیه ضلع مشترک در مثلث‌بندی وجود داشته باشد و دو سر این ضلع با (البته دقت کنید که راسی که برای فضای بیرون از مثلث اختصاص دادیم به تمامی مثلث‌هایی که یکی از اضلاعشان روی مثلث اصلی قرار دارد، ضلع مشترک دارد و اگر دو سر این ضلع رنگ‌های متفاوت داشته‌باشند یال هم به آن‌ها دارد).
حال راس را در نظر بگیرید. این راس قطعاً درجهٔ فرد دارد. زیرا بر روی هر ضلع مثلث بزرگ تعداد فردی ضلع وجود دارد که دو سر آن‌ها رنگ‌های متفاوتی داشته‌باشند. تعداد این ضلع‌های فرد روی ضلع اول مثلث بزرگ را اگر بنامیم و روی ضلع‌های دوم و سوم را به ترتیب بنامیم داریم:
در این صورت پس  فرد است. پس بنابراین قضیه که در یک گراف متناهی تعداد زوجی راس با درجهٔ فرد حضور دارند، بنابراین لااقل یک راس دیگر با درجهٔ فرد در گراف  حضور دارد. به سادگی می‌توان مشاهده کرد که بقیه رأس‌های گراف به جز تنها می‌توانند درجه‌های  داشته باشند (دقت کنید که برای این رأس‌های گراف تنها سه ضلع هست و بنابراین درجه قطعاً کمتر مساوی است اما با بررسی حالات مختلف می‌بینیم تنها درجه‌های ممکن (برای حالتی که تمام رأس‌های مثلث همرنگ هستند) و (برای حالتی که دو راس مثلث همرنگ باشند) و (برای حالتی که هر سه راس مثلث رنگ متفاوت داشته باشند) هستند. پس با توجه به اینکه یک راس دیگر با درجهٔ فرد به جز داریم لااقل یک راس با درجهٔ سه و در واقع یک مثلث تمام‌رنگ (هر سه راس رنگ‌های متفاوتی دارند و بنابراین تمام رنگ‌ها را دارند) داریم. نتیجهٔ کلی‌تر اینکه تعداد فردی مثلث تمام‌رنگ داریم.

اثبات حالت چند بعدی

برای اثبات لم اسپرنر در حالت کلی از استقرا استفاده می‌کنیم. حالت  بدیهی است. برای سیمپلکس  بعدی که ، با فرض اینکه گزاره برای سمپلکس‌های کمتر از  بعدی درست است، در یک مثلث‌بندی T از سیمپلکس اصلی، در هر وجه  از ، فرد سیمپلکس  بعدی کامل وجود دارد. یکی از سیمپلکس‌های  بعدی کامل وجه  مانند  را در نظر می‌گیریم. رأس ام این سیمپلکس را  می‌نامیم. اگر رنگ این رأس  باشد یک سیمپلکس  بعدی کامل داریم و زنجیره را متوقف می‌کنیم. در غیر اینصورت رنگ  برابر  است که . فرض می‌کنیم . حال سیمپلکس  یک سیمپلکس  بعدی کامل است. رأس  وجود دارد که با اضافه کردن آن به  یک سیمپلکس جدید  بعدی ایجاد می‌شود. مجدد این سیمپلکس یا کامل است یا از یک رنگ دو بار در آن استفاده شده‌است. مانند قبل رأسی در  که رنگ مشابه با  را از  حذف می‌کنیم و رأس جدیدی غیر از رأس حذف شده به آن اضافه می‌کنیم و این فرایند را ادامه می‌دهیم و یک زنجیره از سمپلکس‌های  بعدی که هر کدام با  رنگ متفاوت رنگ‌آمیزی شده‌اند می‌سازیم. می‌دانیم برای رسیدن به یک سیمپلکس  بعدی از یک سیمپلکس  بعدی دیگر با روش حذف یک رأس و اضافه کردن یک رأس جدید دو روش وجود دارد (یعنی به ازای هر سیمپلکس  دو رأس وجود دارند که با اضافه کردن آن‌ها به سیمپلکس مذکور، یک سیمپلکس  بعدی ایجاد می‌شود). حال از آن‌جا که در زنجیره‌ای که در حال ساختن آن هستیم هر به ازای هر سیمپلکس (به جز سیمپلکس اول زنجیره)، دو سیمپلکس دیگری که می‌توانند برای رسیدن به آن به کار برده شوند قبل و بعد از آن آمده‌اند و همچنین از آن‌جا که سیمپلکس اول در مرز (وجه) قرار دارد و تنها یک راه برای رسیدن به آن وجود دارد که همان سیمپلکس دوم زنجیره است، در این زنجیره هیچ‌گاه یک سیمپلکس تکراری دیده نمی‌شود؛ بنابراین طول زنجیره متناهی است. از طرفی زنجیره فقط در دو حالت متوقف می‌شود. حالت اول این است که به یک سیمپلکس  بعدی کامل برسیم و حالت دوم نیز این است که به یکی از وجه‌ها برسیم و زنجیره دیگر قابل ادامه دادن نباشد. در حالت دوم از آن‌جا که می‌دانیم تمامی سیمپلکس‌های این زنجیره با مجموعهٔ رنگ‌های  ساخته شده‌اند وجهی که می‌توانیم با رسیدن به آن متوقف شویم همان وجهی است که با آن شروع کرده‌ایم یعنی . بنابراین تمامی سیمپلکس‌های وجه  یا با زنجیره‌هایی که در بالا گفتیم دو به دو به هم متصل می‌شوند یا به یک سیمپلکس  بعدی کامل می‌رسند؛ بنابراین فرد تا از آن‌ها به یک سیمپلکس  بعدی کامل می‌رسند. از طرف دیگر سیمپلکس‌های  بعدی کامل با حذف رأسی که رنگ  دارند و اضافه کردن تنها رأس ممکن دیگر و ساختن زنجیره‌ای مانند بالا، یا به یکی از سیمپلکس‌های وجه  می‌رسند یا به یک سیمپلکس  بعدی کامل دیگر می‌رسند، یعنی دو به دو جفت می‌شوند. تعداد آن‌هایی که با حالت دوم جفت می‌شوند زوج است و تعداد آن‌هایی که با حالت اول به وجه  می‌رسند فرد؛ بنابراین تعداد کل سیمپلکس‌های کامل  یعدی در  فرد است.

درجات

فرض کنید یک مثلث، مثلث بندی شده و با رنگ‌های رنگ‌آمیزی شده باشد. دنبالهٔ چرخشی رنگ رأس‌های مرز مثلث را در نظر بگیرید. درجهٔ رنگ‌آمیزی را برابر با اختلاف تعداد تعویض‌ها از  به  و تعداد تعویض‌ها از به  در دنبالهٔ یاد شده تعریف کنید. دقت کنید درجه اگر به شکل تعداد تعویض‌ها از  به  منهای تعداد تعویض‌ها از  به  یا تعداد تعویض‌ها از  به  منهای تعداد تعویض‌ها از  به  نیز تعریف شود، مقدارش تغییری نمی‌کند. داریم تعداد مثلث‌هایی که سه رأس آن‌ها به  رنگ متفاوت رنگ شده‌اند حداقل برابر درجهٔ رنگ‌آمیزی است. به خصوص اگر درجه ناصفر باید یه مثلث وجود دارد که  ضلع آن با رنگ‌های متفاوتی رنگ شده‌اند. اگر رنگ‌آمیزی شرط اسپرنر را رعایت کند، درجهٔ رنگ‌آمیزی دقیقاً برابر  است.

جایگشت‌ها

فرض کنید به جای یک رنگ‌آمیزی،  رنگ‌آمیزی اسپرنر متفاوت داشته باشیم. زوج‌های (سیمپلکس، جایگشت) را به شکلی در نظر می‌گیریم که رنگ هر رأس سیمپلکس از یک رنگ‌آمیزی متفاوت آمده باشد (بنابراین برای هر سیمپلکس  زوج متفاوت خواهیم داشت). حال حداقل زوج وجود دارند که شامل سلولی هستند که رئوس آن با رنگ‌های متفاوتی رنگ شده‌است. روشی دیگری برای بیان این لم به شکل مقابل است. فرض کنید  نفر برای یه مثلث‌بندی از یک سیمپلکس رنگ‌آمیزی‌های متفاوتی را ارائه داده‌اند. یه سیمپلکس رنگ‌آمیزی شده و یک تطابق از این افراد به رئوس آن سیمپلکس وجود دارد، به‌طوری‌که رنگ هر رأس از سیمپلکس همان رنگی است که فرد متناظر با آن رأس در تطابق، برای آن رأس ارائه داده بود. علاوه بر این تعداد این تطابق‌ها حداقل  است.

کاربردهای رنگ‌آمیزی اسپرنری

رنگ‌آمیزی اسپرنری (در واقع رنگ‌آمیزی با شرایطی که در قسمت قبل گفته شد) چندین کاربرد محاسباتی دارد؛ یکی از این کاربردها پیدا کردن نقطهٔ ثابت توابع هستند. می‌توان به گونه‌ای یک سیمپلکس را رنگ کرد که سیمپلکس‌های تمام‌رنگ به معنای وجود نقاط ثابت در آن حوالی در یک تابع باشند. با کوچک و کوچک‌تر کردن مثلث‌بندی‌ها می‌توان ثابت کرد که نقطهٔ همگرایی سیمپلکس‌های تمام‌رنگ دقیقاً همان نقطهٔ ثابت تابع است. به همین دلیل از لم اسپرنر می‌توان در الگوریتم‌هایی که برای پیدا کردن ریشهٔ توابع به کار می‌روند. از این روش رنگ‌آمیزی و لم اسپرنر در بعضی از الگوریتم‌های تقسیم عادلانه استفاده می‌شود.

کاربردهای لم اسپرنر در برش کیک

با استفاده از این لم ثابت می‌شود که تقسیم‌بندی بدون رشک کیک بین نفر با تنها  برش ممکن است (به عبارت دیگر یک تخصیص پیوستهٔ بدون رشک قطعاً وجود دارد).