Дилвортс теоремасы - Dilworths theorem - Wikipedia

Жылы математика аудандарында тапсырыс теориясы және комбинаторика, Дилворт теоремасы сипаттайды ені кез келген ақырлы жартылай тапсырыс берілген жиынтық тұрғысынан а бөлім тапсырыстың минималды санына дейін тізбектер. Бұл математикке арналған Роберт П. Дилворт  (1950 ).

Ан античайн ішінара реттелген жиынтықта екеуі де бір-бірімен салыстыруға келмейтін элементтер жиынтығы, ал тізбек - бұл әрқайсысы салыстырылатын элементтер жиынтығы. Тізбекті ыдырау - бұл тәртіп элементтерінің бөлімі бөлу тізбектер. Дилворт теоремасы кез-келген ақырындап реттелген жиынтықта ең үлкен антитейнердің мөлшері ең кіші тізбектің ыдырауымен бірдей болатынын айтады. Мұнда антихайнның мөлшері - бұл элементтер саны, ал тізбектің ыдырау мөлшері - оның тізбектерінің саны. Ішінара тәртіптің ені античайн мен тізбектің ыдырауының жалпы мөлшері ретінде анықталады.

Теореманың шексіз ішінара реттелген нұсқасына сәйкес, көптеген тізбектерге ыдырау болған кезде немесе античайнның мөлшерінде ақырғы жоғарғы шек болған кезде, ең үлкен античайнның және ең кіші тізбектің ыдырауының өлшемдері болады. қайтадан тең.

Индуктивті дәлелдеу

Ішінара реттелген жиынтықтың индукциясы бойынша келесі дәлел негізделеді Гальвин  (1994 ).

Келіңіздер ішінара тапсырыс берілген жиынтық болуы. Теорема, егер маңызды емес болса бос. Сонымен, деп ойлаңыз кем дегенде бір элементі бар және рұқсат етіңіз максималды элементі болуы керек .

Индукция бойынша біз кейбір бүтін санды қабылдаймыз жартылай тапсырыс берілген жиынтық қамтуы мүмкін түйіспелі тізбектер және ең болмағанда бір античайн бар өлшемі . Анық, үшін . Үшін , рұқсат етіңіз ішіндегі максималды элемент болу ол античайнға жатады жылы және орнатыңыз . Біз бұны талап етеміз античайн болып табылады. Келіңіздер мөлшерге қарсы античайн болуы бар . Ерекше индекстерді түзетіңіз және . Содан кейін . Келіңіздер . Содан кейін , анықтамасы бойынша . Бұл мұны білдіреді , бері . Рөлдерін ауыстыру арқылы және бұл дәлелде бізде бар . Бұл растайды античайн болып табылады.

Біз қазір қайтамыз . Алдымен солай делік кейбіреулер үшін . Келіңіздер шынжыр бол . Содан кейін таңдау бойынша , мөлшерде античайн жоқ . Индукция соны білдіреді қамтуы мүмкін бастап ажыратылған тізбектер - бұл античайн жылы . Осылайша, қамтуы мүмкін қажет болған жағдайда, ажырату тізбектері. Келесі, егер әрқайсысы үшін , содан кейін - бұл античайн жылы (бері максималды ). Қазір арқылы жабылуы мүмкін тізбектер , дәлелдеуді аяқтау.

Кёниг теоремасы арқылы дәлелдеу

Книг теоремасы арқылы Дилворт теоремасының дәлелі: ішінара тәртіптен екі жақты график құру және сәйкес келу бойынша тізбектерге бөлу

Комбинаторикадағы бірқатар басқа нәтижелер сияқты, Дилворт теоремасы эквивалентті Кёниг теоремасы қосулы екі жақты граф сәйкес келетін және басқа бірнеше теоремалар, соның ішінде Холлдың неке теоремасы (Фулкерсон 1956 ж ).

Ішінара бұйрық үшін Дилворт теоремасын дәлелдеу S бірге n элементтер, Книг теоремасын қолдана отырып, екі жақты графикті анықтайды G = (U,V,E) қайда U = V = S және қайда (сен,v) - бұл шеті G қашан сен < v жылы S. Кёниг теоремасы бойынша сәйкес келеді М жылы Gжәне шыңдар жиынтығы C жылы G, графиктің әр шетінде кем дегенде бір шыңы болатын етіп C және солай М және C бірдей күшке ие м. Келіңіздер A элементтерінің жиынтығы болуы керек S in кез-келген шыңына сәйкес келмейтіндер C; содан кейін A кем дегенде бар n - м элементтер (мүмкін, егер одан да көп болса C екі бөлімнің екі жағында бірдей элементке сәйкес келетін шыңдардан тұрады) және екі элементі жоқ A бір-бірімен салыстыруға болады. Келіңіздер P қосу арқылы құрылған тізбектер отбасы болыңыз х және ж шеті болған кезде сол тізбекте (х,ж) М; содан кейін P бар n - м тізбектер. Сондықтан, біз антихейнді және бірдей күші бар тізбектерге бөлуді жасадық.

Екі жақты граф үшін Дильворт теоремасынан Кёниг теоремасын дәлелдеу G = (U,V,E), шыңдарында ішінара бұйрық құрайды G онда сен < v дәл қашан сен ішінде U, v ішінде V, және шеті бар E бастап сен дейін v. Дилворттың теоремасы бойынша антитейн бар A және тізбектерге бөлу P екеуінің өлшемдері бірдей. Бірақ ішінара тәртіптегі жалғыз нейтривиалды тізбектер графиктің шеттеріне сәйкес келетін жұп элементтер болып табылады, сондықтан нейтривиалды тізбектер P графикте сәйкестікті қалыптастыру. Толықтыру A ішіндегі төбелік қақпақты құрайды G дәл осы сәйкестік сияқты дәлдікпен.

Екі жақты сәйкестікке қосылу кез-келген ішінара бұйрықтың енін есептеуге мүмкіндік береді көпмүшелік уақыт. Дәлірек айтсақ, n-элементтің енінің ішінара реті к уақытында танылуы мүмкін O(кн2) (Felsner, Raghavan & Spinrad 2003 ж ).

Шексіз ішінара реттелген жиынтықтарға дейін кеңейту

Дилворттың шексіз ішінара реттелген жиындар туралы теоремасы ішінара реттелген жиынның ақырлы ені бар екенін айтады w егер ол бөлуге болатын болса ғана w тізбектер. Мысалы, шексіз ішінара тәртіп P ені бар w, бұл ең көп дегенде ақырлы сан бар екенін білдіреді w кез-келген античайн құрамындағы элементтер. Кез-келген ішкі жиын үшін S туралы P, ішіне ыдырау w тізбектер (егер ол бар болса) а ретінде сипатталуы мүмкін бояу туралы салыстыруға болмайтын график туралы S (элементтері бар график S шыңдар ретінде, әр екі теңдесі жоқ элементтердің арасындағы шеті бар) пайдалану w түстер; салыстыруға болмайтын графиктің тиісті бояуындағы әр түсті класс тізбек болуы керек. Деген болжам бойынша P ені бар wжәне Дилворт теоремасының ақырлы нұсқасы бойынша әрбір ақырғы жиын S туралы P бар w-түстін салыстыруға болмайтын график. Сондықтан Де Брюйн-Эрдес теоремасы, P өзі де бар w-түстін салыстыруға болмайтын график, осылайша қажетті бөлімді тізбектерге бөледі (Харцгейм 2005 ).

Алайда, теорема жай емес, ішінара реттелген жиындарға жайылады, онда жиынтықтың тек түпкілікті емес, ені де шексіз болады. Бұл жағдайда ішінара тәртіпті жабу үшін қажет ең үлкен античайнның мөлшері мен тізбектердің минималды саны бір-бірінен мүлде өзгеше болуы мүмкін. Атап айтқанда, inf әрбір шексіз кардиналды сан үшін еннің шексіз ішінара реттелген жиыны бар 0 ең аз тізбектерге бөлу κ тізбекке ие (Харцгейм 2005 ).

Перлес (1963) шексіз жағдайда Дилворт теоремасының аналогтарын талқылайды.

Дилворт теоремасының қосарлануы (Мирский теоремасы)

Дилворттың теоремасының қосарында, ең үлкен тізбектің мөлшері ішінара тәртіпте (егер шекті болса), бұйрықты бөлуге болатын античайнерлердің ең аз санына тең екендігі айтылады (Мирский 1971 ж ). Мұның дәлелі Дилворт теоремасының өзіне қарағанда әлдеқайда қарапайым: кез келген элемент үшін х, бар тізбектерді қарастырыңыз х олардың ең үлкен элементі ретінде N(х) олардың ішіндегі ең үлкенінің мөлшерін белгілеңіз х- максималды тізбектер. Содан кейін әрбір жиынтық N−1(мен) тең мәндерге ие элементтерден тұрады N, античайн болып табылады, және бұл античейндер ішінара тәртіпті ең үлкен тізбектің өлшеміне тең античайналар қатарына бөледі.

Салыстырмалы графиктердің жетілдірілуі

A салыстыру графигі болып табылады бағытталмаған граф ішінара тәртіптен реттің бір элементіне шың және кез-келген екі салыстырылатын элементтерді біріктіретін шетін құру арқылы пайда болды. Осылайша, а клика салыстырмалы графикте тізбекке сәйкес келеді, ал тәуелсіз жиынтық салыстырмалы графикте антихейнге сәйкес келеді. Кез келген индукцияланған субография салыстырмалы графиктің өзі - бұл ішінара тәртіпті оның элементтерінің жиынтығына шектеуінен пайда болған салыстырмалы график.

Бағытталмаған график мінсіз егер әр индустриялық подграфта хроматикалық сан ең үлкен кликтің өлшеміне тең. Әр салыстырылатын график өте жақсы: бұл тек графикалық-теоретикалық терминдермен жазылған Мирскийдің теоремасы (Berge & Chvátal 1984 ж ). Бойынша тамаша графикалық теорема туралы Ловас (1972), толықтыру кез-келген керемет графиктің өзі де тамаша. Сондықтан кез-келген салыстырмалы графиктің толықтылығы өте жақсы; бұл негізінен тек график-теориялық тұрғыдан келтірілген Дилворттың теоремасы (Berge & Chvátal 1984 ж ). Осылайша, кемелді графиктердің комплементация қасиеті Дилворт теоремасының балама дәлелі бола алады.

Арнайы ішінара тапсырыстардың ені

The Буль торы Bn болып табылады қуат орнатылды туралы n- элементтер жиынтығы X- негізінен {1, 2,…, n} - тапсырыс берген қосу немесе шартты түрде (2[n], ⊆). Спернер теоремасы максималды античайн екенін айтады Bn мөлшері бар

Басқаша айтқанда, теңдесі жоқ кіші топтардың ең үлкен отбасы X ішкі жиынын таңдау арқылы алынады X орташа мөлшері бар. The Любелл-Ямамото-Мешалкин теңсіздігі сонымен қатар қуат жиынтығындағы антихейндерге қатысты және оларды Спернер теоремасын дәлелдеуге қолдануға болады.

Егер біз бүтін сандарды [1, 2] аралығында реттесекn] арқылы бөлінгіштік, ішкі аралық [n + 1, 2n] кардиналмен антихейн түзеді n. Осы ішінара тәртіптің бөлімі n тізбектерге қол жеткізу оңай: әр тақ сан үшін м [1,2n], форма сандарының тізбегін құрыңыз м2мен. Демек, Дилворт теоремасы бойынша бұл ішінара ретті ені тең болады n.

The Эрдис-Секерес теоремасы монотонды секрециялар бойынша Дилворт теоремасын ішінара бұйрықтарға қолдану ретінде түсіндіруге болады тапсырыс өлшемі екі (Стил 1995 ).

«Дөңес өлшемі» antimatroid антиматироидты анықтауға қажетті тізбектердің минималды саны ретінде анықталады және Дилворт теоремасын оның байланысты бөлшектік тәртіптің еніне тең екендігін көрсетуге болады; бұл байланыс дөңес өлшем үшін уақыттың полиномдық алгоритміне әкеледі (Edelman & Saks 1988 ж ).

Әдебиеттер тізімі

Сыртқы сілтемелер