لم اسپرنر

لم اسپرنر در واقع معادل ترکیبیاتی قضیهٔ نقطهٔ ثابت برور می‌باشد و توسط امانویل اسپرنر اثبات شده‌است.

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

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

بیان لم

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

حالت یک بعدی

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

حالت دو بعدی

این حالت از قضیهٔ اسپرنر در واقع حالتی از آن است که بیشتر از بقیهٔ حالت‌های آن مطرح می‌شود که شرح آن به صورت زیر است:

یک مثلث بندی از مثلث $ABC$ را در نظر بگیرید. حال فرض کنید که رأس‌های به وجود آمده در این مثلث را با شروط زیر رنگ می‌کنیم.

• راس $A$ را با رنگ سبز، راس $B$را با رنگ قرمز و راس $C$را با رنگ آبی رنگ می‌کنیم.
• رأس‌های روی یال $AB$از مثلث را با دو رنگ سبز و قرمز و رأس‌های روی یال $BC$ را با دو رنگ قرمز و آبی و رأس‌های روی یال $AC$ را با دو رنگ سبز و آبی رنگ می‌کنیم (در واقع رأس‌های روی یال‌های $ABC$تنها با رنگ‌های دوسر یالشان در مثلث بزرگ رنگ می‌شوند).

لم اسپرنر در حالت تک بعدی.

لم اسپرنر بیان می‌کند که در این حالت یکی از مثلث‌ها ایجاد شده در درون مثلث $ABC$ هر سه رنگ آبی و قرمز و سبز را در رأس‌های خود دارد (به عبارت دیگر هر راس آن رنگش با رأس‌های دیگر متفاوت است). لم اسپرنر هم چنین بیان می‌کند که تعداد فردی از این مثلث‌های سه رنگ (مثلث‌هایی که رنگ‌های سه راسشان متفاوت از هم است) وجود دارند.

حالت چند بعدی

در این‌جا لم اسپرنر را برای حالت $n$ بعدی بررسی می‌کنیم. فرض کنید $A$یک سیمپلکس است که $A=A_{1}A_{2}...A_{n+1}$ و ما یک مثلث‌بندی به نام

$T$از این فضا داریم. $S$ را مجموعه رأس‌های $T$بگیرید. تابع $f:S\rightarrow {1,2,...,n+1}$را تابع رنگ آمیزی در نظر بگیرید که به هر راس از مثلث بندی $T$یکی از رنگ‌های بین $1$تا $n+1$را اختصاص می‌دهد. اما این رنگ‌آمیزی نمی‌تواند به هر صورتی باشد و باید در شرایط زیر صدق کند:

• رأس‌های سیمپلکس بزرگ باید با رنگ‌های متفاوت رنگ شده باشند (هر راس یک رنگ متفاوت از بقیهٔ رأس‌های سیمپلکس اصلی از بین $n+1$رنگ موجود را به خود بگیرد). ما در این‌جا در نظر می‌گیریم که $f(A_{i})=i$.
• راس‌هایی از $T$که در یک زیرفضای $k$ بعدی قرار دارند همانند $A_{i_{1}}A_{i_{2}}...A_{i_{k+1}}$باید تنها با رنگ‌های $i_{1}i_{2}...i_{k+1}$رنگ شده باشند.

لم اسپرنر در حالت ۲ بعدی

صورت صدق کردن تابع $f$در شرایط بالا داریم که تعداد فردی سیمپلکس از $T$وجود دارند که رأس‌های آن‌ها با تمامی $n+1$

رنگ، رنگ شده باشند.

اثبات

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

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

گراف $G$ را از روی مثلث‌بندی $T$ می‌سازیم به اینصورت که به ازای هر مثلث موجود در $T$ یک راس در $G$ داریم. یک راس هم در گراف $G$ اختصاصی برای فضای بیرون از مثلث اصلی قرار می‌دهیم (در واقع نمایندهٔ آن فضا است) که آن را $v_{out}$می‌نامیم. بین راس $v$، $u$در گراف

$G$یال می‌گذاریم اگر و تنها اگر بین این دو ناحیه ضلع مشترک در مثلث‌بندی $T$وجود داشته باشد و دو سر این ضلع با (البته دقت کنید که راسی که برای فضای بیرون از مثلث اختصاص دادیم به تمامی مثلث‌هایی که یکی از اضلاعشان روی مثلث اصلی قرار دارد، ضلع مشترک دارد و اگر دو سر این ضلع رنگ‌های متفاوت داشته‌باشند یال هم به آن‌ها دارد).

حال راس $v_{out}$را در نظر بگیرید. این راس قطعاً درجهٔ فرد دارد. زیرا بر روی هر ضلع مثلث بزرگ تعداد فردی ضلع وجود دارد که دو سر آن‌ها رنگ‌های متفاوتی داشته‌باشند. تعداد این ضلع‌های فرد روی ضلع اول مثلث بزرگ را اگر $F_{1}$بنامیم و روی ضلع‌های دوم و سوم را به ترتیب $F_{2},F_{3}$بنامیم داریم:

$deg(v_{out})=F_{1}+F_{2}+F_{3},F_{1}\;and\;F_{2}\;and\;F_{3}\;are\;odd$

در این صورت پس $deg(v_{out})$ فرد است. پس بنابراین قضیه که در یک گراف متناهی تعداد زوجی راس با درجهٔ فرد حضور دارند، بنابراین لااقل یک راس دیگر با درجهٔ فرد در گراف $G$ حضور دارد. به سادگی می‌توان مشاهده کرد که بقیه رأس‌های گراف به جز $v_{out}$تنها می‌توانند درجه‌های $0,2,3$ داشته باشند (دقت کنید که برای این رأس‌های گراف تنها سه ضلع هست و بنابراین درجه قطعاً کمتر مساوی $3$است اما با بررسی حالات مختلف می‌بینیم تنها درجه‌های ممکن $0$(برای حالتی که تمام رأس‌های مثلث همرنگ هستند) و $2$(برای حالتی که دو راس مثلث همرنگ باشند) و $3$(برای حالتی که هر سه راس مثلث رنگ متفاوت داشته باشند) هستند. پس با توجه به اینکه یک راس دیگر با درجهٔ فرد به جز $v_{out}$داریم لااقل یک راس با درجهٔ سه و در واقع یک مثلث تمام‌رنگ (هر سه راس رنگ‌های متفاوتی دارند و بنابراین تمام رنگ‌ها را دارند) داریم. نتیجهٔ کلی‌تر اینکه تعداد فردی مثلث تمام‌رنگ داریم.

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

برای اثبات لم اسپرنر در حالت کلی از استقرا استفاده می‌کنیم. حالت $n=1$ بدیهی است. برای سیمپلکس $n$ بعدی که $n>1$، با فرض اینکه گزاره برای سمپلکس‌های کمتر از $n$ بعدی درست است، در یک مثلث‌بندی T از سیمپلکس اصلی، در هر وجه $A_{0}...A_{i-1}A_{i+1}...A_{n}$ از $A$، فرد سیمپلکس $n-1$ بعدی کامل وجود دارد. یکی از سیمپلکس‌های $n-1$ بعدی کامل وجه $A_{0}A_{1}...A_{n-1}$ مانند $a_{0}a_{1}...a_{n-1}$ را در نظر می‌گیریم. رأس $n$ام این سیمپلکس را $a_{n}$ می‌نامیم. اگر رنگ این رأس $c_{n}$ باشد یک سیمپلکس $n$ بعدی کامل داریم و زنجیره را متوقف می‌کنیم. در غیر اینصورت رنگ $a_{n}$ برابر $c_{i}$ است که $i<n$. فرض می‌کنیم $f(a_{n})=c_{0}$. حال سیمپلکس $a_{1}a_{2}...a_{n}$ یک سیمپلکس $n-1$ بعدی کامل است. رأس $a{n+1}\neq a_{0}$ وجود دارد که با اضافه کردن آن به $a_{1}a_{2}...a_{n}$ یک سیمپلکس جدید $n$ بعدی ایجاد می‌شود. مجدد این سیمپلکس یا کامل است یا از یک رنگ دو بار در آن استفاده شده‌است. مانند قبل رأسی در $a_{1}a_{2}...a_{n}$ که رنگ مشابه با $a_{n+1}$ را از $a_{1}a_{2}...a_{n+1}$ حذف می‌کنیم و رأس جدیدی غیر از رأس حذف شده به آن اضافه می‌کنیم و این فرایند را ادامه می‌دهیم و یک زنجیره از سمپلکس‌های $n$ بعدی که هر کدام با $n$ رنگ متفاوت رنگ‌آمیزی شده‌اند می‌سازیم. می‌دانیم برای رسیدن به یک سیمپلکس $n$ بعدی از یک سیمپلکس $n$ بعدی دیگر با روش حذف یک رأس و اضافه کردن یک رأس جدید دو روش وجود دارد (یعنی به ازای هر سیمپلکس $n-1$ دو رأس وجود دارند که با اضافه کردن آن‌ها به سیمپلکس مذکور، یک سیمپلکس $n$ بعدی ایجاد می‌شود). حال از آن‌جا که در زنجیره‌ای که در حال ساختن آن هستیم هر به ازای هر سیمپلکس (به جز سیمپلکس اول زنجیره)، دو سیمپلکس دیگری که می‌توانند برای رسیدن به آن به کار برده شوند قبل و بعد از آن آمده‌اند و همچنین از آن‌جا که سیمپلکس اول در مرز (وجه) قرار دارد و تنها یک راه برای رسیدن به آن وجود دارد که همان سیمپلکس دوم زنجیره است، در این زنجیره هیچ‌گاه یک سیمپلکس تکراری دیده نمی‌شود؛ بنابراین طول زنجیره متناهی است. از طرفی زنجیره فقط در دو حالت متوقف می‌شود. حالت اول این است که به یک سیمپلکس $n$ بعدی کامل برسیم و حالت دوم نیز این است که به یکی از وجه‌ها برسیم و زنجیره دیگر قابل ادامه دادن نباشد. در حالت دوم از آن‌جا که می‌دانیم تمامی سیمپلکس‌های این زنجیره با مجموعهٔ رنگ‌های $...$ ساخته شده‌اند وجهی که می‌توانیم با رسیدن به آن متوقف شویم همان وجهی است که با آن شروع کرده‌ایم یعنی $A_{0}A_{1}...A_{n-1}$. بنابراین تمامی سیمپلکس‌های وجه $A_{0}A_{1}...A_{n-1}$ یا با زنجیره‌هایی که در بالا گفتیم دو به دو به هم متصل می‌شوند یا به یک سیمپلکس $n$ بعدی کامل می‌رسند؛ بنابراین فرد تا از آن‌ها به یک سیمپلکس $n$ بعدی کامل می‌رسند. از طرف دیگر سیمپلکس‌های $n$ بعدی کامل با حذف رأسی که رنگ $c_{n}$ دارند و اضافه کردن تنها رأس ممکن دیگر و ساختن زنجیره‌ای مانند بالا، یا به یکی از سیمپلکس‌های وجه $A_{0}A_{1}...A_{n-1}$ می‌رسند یا به یک سیمپلکس $n$ بعدی کامل دیگر می‌رسند، یعنی دو به دو جفت می‌شوند. تعداد آن‌هایی که با حالت دوم جفت می‌شوند زوج است و تعداد آن‌هایی که با حالت اول به وجه $A_{0}A_{1}...A_{n-1}$ می‌رسند فرد؛ بنابراین تعداد کل سیمپلکس‌های کامل $n$ یعدی در $A$ فرد است.

تعمیم‌ها

تعمیم لم اسپرنر

ابتدا چند تعریف برای ساده‌تر شدن توضیحاتمان ارائه می‌کنیم:

• به یک سیمپلکس $k$ بعدی یک $k$-سیمپلکس می‌گویند.
• به یک ترکیب خطی صحیح از $k$-سیمپلکس‌ها، $k$-زنجیره می‌گویند.
• مرز $\partial (S)$ یک $k$-سیمپلکس $S=<p_{0},p_{1},...,p_{k}>$ برابر با $\partial (S)=\sum _{j}(-1)^{j}<p_{0},...,p_{j-1},p_{j+1},...,p_{k}>$است.
• یک $k$تایی مرتب از اعداد صحیح و نامنفی مانند $q_{k},...,q_{1},q_{0}$را در نظر بگیرید. $N(q_{0},q_{1}...,q_{k})$را به این صورت تعریف می‌کنیم. اگر این جایگشت زوج باشد (یکی اینکه این $k$تایی اعداد جایگشتی از $0,1,...,k-1$باشند و بتوان با زوج دفعه جابجایی دوتایی اعداد، به جایگشت مرتب شده رسید) این مقدار را برابر با $+1$می‌گیریم. اگر این جایگشت فرد (یکی اینکه این $k$تایی اعداد جایگشتی از $0,1,...,k-1$باشند و بتوان با فرد دفعه جابجایی دوتایی اعداد، به جایگشت مرتب شده رسید) باشد این مقدار را برابر با $-1$ و اگر این $k$تایی یک جایگشت از اعداد $0,1,...,k-1$نباشد این مقدار برابر $0$ است. برای مثال داریم:$N(0,1,2,3)=N(1,2,0,3)=N(1,0,3,2)=1$

$N(0,1,3,2)=N(3,0,1,2)=N(0,2,1,3)=-1$

$N(0,0,1)=N(2)=N(1,279)=0$

• حال با فرض اینکه $S=<p_{0},p_{1},...,p_{k}>$ یک $k$-سیمپلکس جهت‌دار است که به هر رأس رنگ $f(k)$ نسبت داده شده‌است. تعریف تابع $N$ برای آن به شکل زیر می‌شود: $N(S)=N(f(p_{0}),f(p_{1}),...,f(p_{k}))$

همچنین می‌توان تعریف $N$ را بر روی n-زنجیره‌ها به صورت خطی گسترش داد، به‌طوری‌که اگر $C=\sum _{j}\alpha _{j}S_{j}$ آن‌گاه $N(C)=\sum _{j}\alpha _{j}N(S_{j})$.

حالت کلی اسپرنر به صورت زیر تعریف می‌شود:

فرض کنید $C$ یک k-زنجیره از k-سیمپلکس‌ها باشد که با رنگ‌های مجموعهٔ $\{0,1,...,k\}$ رنگ شده‌است. داریم: $N(C)=(-1)^{k}N(\partial (C))$.

با استفاده از تعمیم لم اسپرنر می‌توان اثباتی برای قضیهٔ اساسی جبر ارائه کرد.

درجات

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

جایگشت‌ها

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

کاربردها

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

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

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

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