لم اسپرنر
لم اسپرنر در واقع معادل ترکیبیاتی قضیهٔ نقطهٔ ثابت برور می‌باشد و توسط امانویل اسپرنر اثبات شده‌است.
این لم به زبان ساده بیان می‌کند که در هر رنگ آمیزی اسپرنری (که در پایین به تعریف این نوع از رنگ آمیزی خواهیم پرداخت) یک سیمپلکس formula_1 بعدی مثلث بندی شده، حداقل یک سلول شامل تمامی رنگ‌ها دارد (در واقع در این رنگ آمیزی رأس‌ها را رنگ می‌کنیم و این لم بیان می‌کند که حداقل یکی از فضاهای به وجود آمده توسط مثلث‌بندی شدن این سیمپلکس قطعاً در رأس‌های خود تمامی رنگ‌ها را خواهد داشت).
رنگ آمیزی اسپرنری چندین کاربرد دارد که از آن‌ها می‌توان به محاسبهٔ کارآمد نقاط ثابت یک تابع، پیدا کردن ریشه‌های معادله‌ها و تقسیم عادلانه (مسألهٔ برش کیک که یکی از مسایل مطرح در نظریهٔ بازی‌ها است) اشاره کرد.
در اینجا به این می‌پردازیم که این لم در واقع چه چیزی را بیان می‌کند. همان‌طور که در بالا اشاره شد این لم در سیمپلکس‌های n بعدی تعریف می‌شود. برای درک بهتر این لم آن را برای بعدهای پایین formula_2 بیان می‌کنیم تا شهودی نسبت به آن پیدا کنیم.
در حالت یک بعدی این قضیه بیان می‌کند که یک تابع که روی یک فضای گسستهٔ یک بعدی (مثل نقاطی روی یک خط) که تنها مقادیر صفر و یک را به خود اختصاص می‌دهد و با مقدار صفر شروع می‌کند و به مقدار یک تمام می‌شود به تعداد فردی مقدار خود را بین صفر و یک عوض می‌کند. در واقع فرض کنید پاره‌خطی عمودی داریم و نقطهٔ بالایی این پاره‌خط را با رنگ سبز و نقطهٔ پایینی آن را با رنگ آبی رنگ کنیم حتماً تکه‌پاره خطی وجود دارد که رنگ دو سر آن‌ها سبز و آبی (متفاوت) است و تعداد تکه‌پاره‌خط‌های به وجود آمده که دو سر آن‌ها رنگ سبز و آبی (متفاوت) هستند، فرد است.
این حالت از قضیهٔ اسپرنر در واقع حالتی از آن است که بیشتر از بقیهٔ حالت‌های آن مطرح می‌شود که شرح آن به صورت زیر است:
یک مثلث بندی از مثلث formula_3 را در نظر بگیرید. حال فرض کنید که رأس‌های به وجود آمده در این مثلث را با شروط زیر رنگ می‌کنیم. لم اسپرنر بیان می‌کند که در این حالت یکی از مثلث‌ها ایجاد شده در درون مثلث formula_11 هر سه رنگ آبی و قرمز و سبز را در رأس‌های خود دارد (به عبارت دیگر هر راس آن رنگش با رأس‌های دیگر متفاوت است). لم اسپرنر هم چنین بیان می‌کند که تعداد فردی از این مثلث‌های سه رنگ (مثلث‌هایی که رنگ‌های سه راسشان متفاوت از هم است) وجود دارند.
در این‌جا لم اسپرنر را برای حالت formula_12 بعدی بررسی می‌کنیم. فرض کنید formula_13یک سیمپلکس است که formula_14 و ما یک مثلث‌بندی به نام
formula_15از این فضا داریم. formula_16 را مجموعه رأس‌های formula_15بگیرید. تابع formula_18را تابع رنگ آمیزی در نظر بگیرید که به هر راس از مثلث بندی formula_15یکی از رنگ‌های بین formula_20تا formula_21را اختصاص می‌دهد. اما این رنگ‌آمیزی نمی‌تواند به هر صورتی باشد و باید در شرایط زیر صدق کند: صورت صدق کردن تابع formula_28در شرایط بالا داریم که تعداد فردی سیمپلکس از formula_15وجود دارند که رأس‌های آن‌ها با تمامی formula_21
رنگ، رنگ شده باشند.
در این بخش به اثبات لم اسپرنر می‌پردازیم. حالت یک بعدی این لم بسیار بدیهی است. در ابتدا اثباتی برای حالت دو بعدی این لم می‌آوریم. اثبات برای بعدهای بالاتر با استقرا بر روی تعداد بعدها و با استدلالی شبیه به اثبات حالت دو بعدی این لم است.
گراف formula_31 را از روی مثلث‌بندی formula_15 می‌سازیم به اینصورت که به ازای هر مثلث موجود در formula_15 یک راس در formula_31 داریم. یک راس هم در گراف formula_31 اختصاصی برای فضای بیرون از مثلث اصلی قرار می‌دهیم (در واقع نمایندهٔ آن فضا است) که آن را formula_36می‌نامیم. بین راس formula_37، formula_38در گراف
formula_31یال می‌گذاریم اگر و تنها اگر بین این دو ناحیه ضلع مشترک در مثلث‌بندی formula_15وجود داشته باشد و دو سر این ضلع با (البته دقت کنید که راسی که برای فضای بیرون از مثلث اختصاص دادیم به تمامی مثلث‌هایی که یکی از اضلاعشان روی مثلث اصلی قرار دارد، ضلع مشترک دارد و اگر دو سر این ضلع رنگ‌های متفاوت داشته‌باشند یال هم به آن‌ها دارد).
حال راس formula_36را در نظر بگیرید. این راس قطعاً درجهٔ فرد دارد. زیرا بر روی هر ضلع مثلث بزرگ تعداد فردی ضلع وجود دارد که دو سر آن‌ها رنگ‌های متفاوتی داشته‌باشند. تعداد این ضلع‌های فرد روی ضلع اول مثلث بزرگ را اگر formula_42بنامیم و روی ضلع‌های دوم و سوم را به ترتیب formula_43بنامیم داریم:
formula_44
در این صورت پس formula_45 فرد است. پس بنابراین قضیه که در یک گراف متناهی تعداد زوجی راس با درجهٔ فرد حضور دارند، بنابراین لااقل یک راس دیگر با درجهٔ فرد در گراف formula_31 حضور دارد. به سادگی می‌توان مشاهده کرد که بقیه رأس‌های گراف به جز formula_36تنها می‌توانند درجه‌های formula_48 داشته باشند (دقت کنید که برای این رأس‌های گراف تنها سه ضلع هست و بنابراین درجه قطعاً کمتر مساوی formula_49است اما با بررسی حالات مختلف می‌بینیم تنها درجه‌های ممکن formula_50(برای حالتی که تمام رأس‌های مثلث همرنگ هستند) و formula_51(برای حالتی که دو راس مثلث همرنگ باشند) و formula_49(برای حالتی که هر سه راس مثلث رنگ متفاوت داشته باشند) هستند. پس با توجه به اینکه یک راس دیگر با درجهٔ فرد به جز formula_36داریم لااقل یک راس با درجهٔ سه و در واقع یک مثلث تمام‌رنگ (هر سه راس رنگ‌های متفاوتی دارند و بنابراین تمام رنگ‌ها را دارند) داریم. نتیجهٔ کلی‌تر اینکه تعداد فردی مثلث تمام‌رنگ داریم.
برای اثبات لم اسپرنر در حالت کلی از استقرا استفاده می‌کنیم. حالت formula_54 بدیهی است. برای سیمپلکس formula_12 بعدی که formula_56، با فرض اینکه گزاره برای سمپلکس‌های کمتر از formula_12 بعدی درست است، در یک مثلث‌بندی T از سیمپلکس اصلی، در هر وجه formula_58 از formula_13، فرد سیمپلکس formula_60 بعدی کامل وجود دارد. یکی از سیمپلکس‌های formula_60 بعدی کامل وجه formula_62 مانند formula_63 را در نظر می‌گیریم. رأس formula_12ام این سیمپلکس را formula_65 می‌نامیم. اگر رنگ این رأس formula_66 باشد یک سیمپلکس formula_12 بعدی کامل داریم و زنجیره را متوقف می‌کنیم. در غیر اینصورت رنگ formula_65 برابر formula_69 است که formula_70. فرض می‌کنیم formula_71. حال سیمپلکس formula_72 یک سیمپلکس formula_60 بعدی کامل است. رأس formula_74 وجود دارد که با اضافه کردن آن به formula_72 یک سیمپلکس جدید formula_12 بعدی ایجاد می‌شود. مجدد این سیمپلکس یا کامل است یا از یک رنگ دو بار در آن استفاده شده‌است. مانند قبل رأسی در formula_72 که رنگ مشابه با formula_78 را از formula_79 حذف می‌کنیم و رأس جدیدی غیر از رأس حذف شده به آن اضافه می‌کنیم و این فرایند را ادامه می‌دهیم و یک زنجیره از سمپلکس‌های formula_12 بعدی که هر کدام با formula_12 رنگ متفاوت رنگ‌آمیزی شده‌اند می‌سازیم. می‌دانیم برای رسیدن به یک سیمپلکس formula_12 بعدی از یک سیمپلکس formula_12 بعدی دیگر با روش حذف یک رأس و اضافه کردن یک رأس جدید دو روش وجود دارد (یعنی به ازای هر سیمپلکس formula_60 دو رأس وجود دارند که با اضافه کردن آن‌ها به سیمپلکس مذکور، یک سیمپلکس formula_12 بعدی ایجاد می‌شود). حال از آن‌جا که در زنجیره‌ای که در حال ساختن آن هستیم هر به ازای هر سیمپلکس (به جز سیمپلکس اول زنجیره)، دو سیمپلکس دیگری که می‌توانند برای رسیدن به آن به کار برده شوند قبل و بعد از آن آمده‌اند و همچنین از آن‌جا که سیمپلکس اول در مرز (وجه) قرار دارد و تنها یک راه برای رسیدن به آن وجود دارد که همان سیمپلکس دوم زنجیره است، در این زنجیره هیچ‌گاه یک سیمپلکس تکراری دیده نمی‌شود؛ بنابراین طول زنجیره متناهی است. از طرفی زنجیره فقط در دو حالت متوقف می‌شود. حالت اول این است که به یک سیمپلکس formula_12 بعدی کامل برسیم و حالت دوم نیز این است که به یکی از وجه‌ها برسیم و زنجیره دیگر قابل ادامه دادن نباشد. در حالت دوم از آن‌جا که می‌دانیم تمامی سیمپلکس‌های این زنجیره با مجموعهٔ رنگ‌های formula_87 ساخته شده‌اند وجهی که می‌توانیم با رسیدن به آن متوقف شویم همان وجهی است که با آن شروع کرده‌ایم یعنی formula_62. بنابراین تمامی سیمپلکس‌های وجه formula_62 یا با زنجیره‌هایی که در بالا گفتیم دو به دو به هم متصل می‌شوند یا به یک سیمپلکس formula_12 بعدی کامل می‌رسند؛ بنابراین فرد تا از آن‌ها به یک سیمپلکس formula_12 بعدی کامل می‌رسند. از طرف دیگر سیمپلکس‌های formula_12 بعدی کامل با حذف رأسی که رنگ formula_66 دارند و اضافه کردن تنها رأس ممکن دیگر و ساختن زنجیره‌ای مانند بالا، یا به یکی از سیمپلکس‌های وجه formula_62 می‌رسند یا به یک سیمپلکس formula_12 بعدی کامل دیگر می‌رسند، یعنی دو به دو جفت می‌شوند. تعداد آن‌هایی که با حالت دوم جفت می‌شوند زوج است و تعداد آن‌هایی که با حالت اول به وجه formula_62 می‌رسند فرد؛ بنابراین تعداد کل سیمپلکس‌های کامل formula_12 یعدی در formula_13 فرد است.
ابتدا چند تعریف برای ساده‌تر شدن توضیحاتمان ارائه می‌کنیم:
formula_120
formula_121
همچنین می‌توان تعریف formula_125 را بر روی n-زنجیره‌ها به صورت خطی گسترش داد، به‌طوری‌که اگر formula_128 آن‌گاه formula_129.
حالت کلی اسپرنر به صورت زیر تعریف می‌شود:
فرض کنید formula_130 یک k-زنجیره از k-سیمپلکس‌ها باشد که با رنگ‌های مجموعهٔ formula_131 رنگ شده‌است. داریم: formula_132.
با استفاده از تعمیم لم اسپرنر می‌توان اثباتی برای قضیهٔ اساسی جبر ارائه کرد.
فرض کنید یک مثلث، مثلث بندی شده و با رنگ‌های formula_133رنگ‌آمیزی شده باشد. دنبالهٔ چرخشی رنگ رأس‌های مرز مثلث را در نظر بگیرید. درجهٔ رنگ‌آمیزی را برابر با اختلاف تعداد تعویض‌ها از formula_20 به formula_51 و تعداد تعویض‌ها از formula_51به formula_20 در دنبالهٔ یاد شده تعریف کنید. دقت کنید درجه اگر به شکل تعداد تعویض‌ها از formula_51 به formula_49 منهای تعداد تعویض‌ها از formula_49 به formula_51 یا تعداد تعویض‌ها از formula_49 به formula_20 منهای تعداد تعویض‌ها از formula_20 به formula_49 نیز تعریف شود، مقدارش تغییری نمی‌کند. داریم تعداد مثلث‌هایی که سه رأس آن‌ها به formula_49 رنگ متفاوت رنگ شده‌اند حداقل برابر درجهٔ رنگ‌آمیزی است. به خصوص اگر درجه ناصفر باید یه مثلث وجود دارد که formula_49 ضلع آن با رنگ‌های متفاوتی رنگ شده‌اند. اگر رنگ‌آمیزی شرط اسپرنر را رعایت کند، درجهٔ رنگ‌آمیزی دقیقاً برابر formula_20 است.
فرض کنید به جای یک رنگ‌آمیزی، formula_12 رنگ‌آمیزی اسپرنر متفاوت داشته باشیم. زوج‌های (سیمپلکس، جایگشت) را به شکلی در نظر می‌گیریم که رنگ هر رأس سیمپلکس از یک رنگ‌آمیزی متفاوت آمده باشد (بنابراین برای هر سیمپلکس formula_150 زوج متفاوت خواهیم داشت). حال حداقل formula_150زوج وجود دارند که شامل سلولی هستند که رئوس آن با رنگ‌های متفاوتی رنگ شده‌است. روشی دیگری برای بیان این لم به شکل مقابل است. فرض کنید formula_12 نفر برای یه مثلث‌بندی از یک سیمپلکس رنگ‌آمیزی‌های متفاوتی را ارائه داده‌اند. یه سیمپلکس رنگ‌آمیزی شده و یک تطابق از این افراد به رئوس آن سیمپلکس وجود دارد، به‌طوری‌که رنگ هر رأس از سیمپلکس همان رنگی است که فرد متناظر با آن رأس در تطابق، برای آن رأس ارائه داده بود. علاوه بر این تعداد این تطابق‌ها حداقل formula_150 است.
رنگ‌آمیزی اسپرنری (در واقع رنگ‌آمیزی با شرایطی که در قسمت قبل گفته شد) چندین کاربرد محاسباتی دارد؛ یکی از این کاربردها پیدا کردن نقطهٔ ثابت توابع هستند. می‌توان به گونه‌ای یک سیمپلکس را رنگ کرد که سیمپلکس‌های تمام‌رنگ به معنای وجود نقاط ثابت در آن حوالی در یک تابع باشند. با کوچک و کوچک‌تر کردن مثلث‌بندی‌ها می‌توان ثابت کرد که نقطهٔ همگرایی سیمپلکس‌های تمام‌رنگ دقیقاً همان نقطهٔ ثابت تابع است. به همین دلیل از لم اسپرنر می‌توان در الگوریتم‌هایی که برای پیدا کردن ریشهٔ توابع به کار می‌روند. از این روش رنگ‌آمیزی و لم اسپرنر در بعضی از الگوریتم‌های تقسیم عادلانه استفاده می‌شود.
با استفاده از این لم ثابت می‌شود که تقسیم‌بندی بدون رشک کیک بین formula_1نفر با تنها formula_155 برش ممکن است (به عبارت دیگر یک تخصیص پیوستهٔ بدون رشک قطعاً وجود دارد).