حدس دینیتز

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

حدس دینیتز

در سال ۱۹۷۸ Jeff Dinitz مساله زیر را در نظریه گراف بیان کرد:

فرض کنید L مربع از مرتبه n باشد.که در هر خانه (i,j) از L لیست (C(i,j از n رنگ مختلف داریم.آیا می‌توان به هر خانه از L یکی از رنگ‌های لیست آن خانه را نسبت داد به طوری که هر رنگ در هر سطر و در هر ستون حداکثر یک بار ظاهر شود؟

این مساله در حالتی که همه لیستها برابر با {n،...۳،۲،۱} باشند، ساده است، کافیست ۱ تا n را در سطر اول بنویسیم، و در هر سطر دیگر اعداد سطر قبل را یک واحد چرخش دهیم تا یک مربع لاتین چرخشی به دست می‌آید که بوضوح شروط مساله را ارضا می‌کند.

ولی مساله همیشه به این سادگی نیست.مربعی ۲*۲ را در نظر بگیرید که

{c (۱،۱) ={۱،۲ و {c (۱،۲) ={۲،۳ و {c (۲،۱) ={۱،۳ و {c (۲،۲) ={۳،۲ .

اگر کسی خانه (۱،۱) را با ۱ و خانه (۱،۲) را با ۲ رنگ کند دیگر نمی‌تواند مربع را کامل کند.چرا که هم خانه (۲،۱) و هم خانه (۲،۲) باید با ۳ رنگ شود.

این مساله را می‌توان با قرار دادن یک راس در هر خانه مربع و وصل کردن دو راس که در در یک سطر یا یک ستون هستند، به یک مساله رنگ آمیزی لیستی گراف‌ها تبدیل کرد.گرافی که اینگونه از این مربع به دست آمد را (G(L بنامید.

اکنون به قضیه زیر درباره عدد رنگی لیستی در گراف‌های جهتدار که توسط Bondy-Boppana-Siegel اثبات شده توجه کنید.

قضیه: اگر (D=(V,E یک گراف جهتدار باشد که به هر راس v از آن یک مجموعه (C(v به عنوان لیست رنگی نسبت دهیم و (C(v بیشتر از درجه خروجی v عضو داشته باشد، و هر زیرگراف القایی راسی از D دارای هسته باشد در این صورت می‌توان هر راس را با یکی از رنگهای لیستش رنگ کرد که هر دو راس مجاور همرنگ نباشند.

در ادامه نیاز به مفهومی به نام تطابق پایدار داریم:

فرض کنید [G[X,Y یک گراف دو بخشی باشد که برای هر راس v از G همسایه‌های راس v یک ترتیب و اولویتی برای v دارند.تطابق M را پایدار گوییم هرگاه برای هر یال uv از G که در M نیست، یا یال uy در M هست که از نظر u, راس y اولویت بیشتری نسبت به v دارد و یا یال vx در M هست که از نظر v, راس x اولویت بیشتری نسبت به u دارد.

Gale در سال ۱۹۶۲ ثابت کرد هر گراف دو بخشی یک تطابق پایدار دارد.

اکنون در ادامه اثباتی از (Galvin ۱۹۹۳) ارایه میدهیم که نشان میدهد پاسخ سوال مطرح شده توسط Dinitz همواره مثبت است.نشان میدهیم (G(L عدد رنگی لیستی n دارد.برای این کار یال‌های (G(L را طوری جهت میدهیم که درجه خروجی هر راس برابر n-۱ باشد و هر زیر گراف القایی (G(L دارای هسته باشد.پس بنابر قضیه بالا هر راس v از (G(L را می‌توان با یکی از رنگ‌های لیستش رنگ کرد که با رنگ راس‌های همسایه (راس‌های هم سطر یا هم ستون) v متفاوت باشد.یعنی هر رنگ در هر سطر یا ستون حد اکثر یکبار ظاهر میشود.

فرض کنید خانه‌های L را با اعداد ۳،۲،۱،...، n طوری پر کرده ایم که L یک مربع لاتین از مرتبه n شود.عدد نوشته شده در خانهٔ (i,j) این مربع را (L(i,j بنامید.یال های (G(L را به شرح زیر جهت دهید:

اگر (L(i,j از (L(i,k کمتر بود جهت یال ((i,j)(i,k)) در (G(L از (i,j) به (i,k) باشد، و اگر (L(i,j از (L(k,j بیشتر بود جهت یال ((i,j)(k,j)) در (G(L از (i,j) به (i,k) باشد،

بدیهیست که درجه خروجی هر راس برابر n-۱ است.

فرض کنید A زیر مجموعه‌ای از راس‌های (G(L باشد

گراف دو بخشی [H[X,Y را در نظر بگیرید:

X = مجموعه سطرهای L,

Y = مجموعه ستون‌های L,

راس i از X به راس j از Y متصل است اگر (i,j) عضو A باشد،

برای هر i از X، اولویت ستون j از ستون k بیشتر است اگر (L(i,k از (L(i,j کمتر باشد،

برای هر j از Y، اولویت سطر i از سطر k بیشتر است اگر (L(i,j از (L(k,j کمتر باشد،

میدانیم هر گراف دو بخشی تطابق پایدار دارد، پس H هم تطابق پایداری مثل M دارد، دقت کنید هر یال M بین راس i از X و j از Y متناظر با راس (i,j) از (G(L است، به راحتی دیده میشود راس‌های متناظر M یک هسته برای زیر گراف القای <A> میسازند.

پس ثابت کردیم هر زیر گراف القایی از (G(L هسته دارد، پس حکم ثابت شد.

منابع[ویرایش]