قضیه دیلورث

در یک مجموعهٔ جزئاً مرتب P، یک پادزنجیر، یک زیرمجموعه از P است که هیچ دو عضوش با یکدیگر قابل مقایسه نیستند، و یک زنجیر، زیرمجموعه‌ای از P است که هر دو عضوش با یکدیگر قابل مقایسه‌اند.

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

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

اثبات قضیهٔ دیلورث، با استفاده از قضیهٔ کونیگ

جهت اثبات قضیهٔ دیلورث با استفاده از قضیهٔ کونیگ برای یک مجموعهٔ جزئاً مرتب S با n عضو، یک گراف دوبخشی G = (U, V, E) تعریف می کنیم به طوری که U = V = S و (u, v) یک یال در G است به طوری که u < v در S باشد. با توجه به قضیهٔ کونیگ، یک جورسازی M و یک مجموعه از رئوس C در G وجود دارد، به طوری که هر یال در گراف شامل حداقل یک رأس از C باشد و تعداد اعضای M و C، برابر m باشد. گیریم A مجموعه‌ای از اعضای S باشد که به هیچ رأسی از مجموعهٔ C مرتبط نباشند، بنابراین A حداقل m-n عضو دارد. گیریم P خانواده‌ای از زنجیرهایی باشد که اگر یال (x,y) در جورسازی M باشد، آنگاه زنجیرهایی که شامل x و y می‌باشد را در یک زنجیر قرار می‌دهد، بنابراین P هم شامل n-m زنجیر می باشد. پس ما یک افراز ترتیب جزئی به زنجیرها و یک پادزنجیر ساخته‌ایم که اندازه هر دو یکسان است.

برای اثبات قضیهٔ کونیگ با استفاده از قضیهٔ دیلورث برای یک گراف دوبخشی G = (U,V،E)، یک ترتیب جزئی روی رأس های G تشکیل می دهیم که در آن u < v، دقیقاً وقتی که u در V، v در Uو یک یال در E، از u به v، وجود داشته باشد. طبق قضیهٔ دیلورث، یک پادزنجیر A و یک افراز ترتیب جزئی به خانواده P از زنجیرها وجود دارند، که هر دو اندازهٔ مشابه دارند. اما فقط زنجیرهای مهم در ترتیب جزئی، جفت اعضای مرتبط به یال‌ها در گراف می باشد. بنابراین زنجیرهای مهم در P، تشکیل یک جورسازی در گراف می دهند و مکمل A، یک پوشش رأسی در G با تعداد اعضای برابر با جورسازی، تشکیل می دهد. این اتصالات در جورسازی گراف دوبخشی، اجازه می‌دهد که طول هر ترتیب جزئی، بتواند در زمان چند جمله‌ای محاسبه شود.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Dilworth's theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱ آوریل ۲۰۱۶.