Теорема Ділворса

У математиці, в таких галузях, як теорія порядку та комбінаторика, Теорема Ділворса характеризує ширину довільної скінченної частково впорядкованої множини у термінах розбиття цього порядку на найменше число ланцюгів. Названа на честь математика Роберта П. Ділворса.

Антиланцюг у частково впорядкованій множині є множина елементів, будь-які два з яких не є порівнювані, і ланцюг є множина елементів, кожні два з яких є порівнювані. Теорема Ділворса стверджує, що існує антиланцюг A, і розбиття даного порядку, що являє собою сімейство P ланцюгів, такі, що число ланцюгів у розбитті дорівнює потужності A. Коли це виконується, A повинен бути найбільшим антиланцюгом у порядку, оскільки будь-який антиланцюг не може мати більше одного елемента від кожного представника P. Аналогічно, P має бути найменшим сімейством ланцюгів, що являє собою розбиття даного порядку, оскільки будь-яке розбиття на ланцюги мусить мати принаймні один ланцюг для кожного елементу з A. Ширина часткового порядку визначається як спільний розмір A та P.

Еквівалентне формулювання Теореми Ділворса таке, у довільній частково впорядкованій множині, найбільше число елементів у будь-якому антиланцюзі дорівнює найменшому числу ланцюгів у будь-якому розбитті даної множини на ланцюги.

Див. також

Джерела

  • Dilworth, Robert P. (1950), A Decomposition Theorem for Partially Ordered Sets, Annals of Mathematics, 51: 161—166, doi:10.2307/1969503.

Посилання

Read other articles:

Distrik di Pakistan

Distrik di PakistanKategoriDivisi administratifLetakUnit administratif di PakistanJumlah wilayah170 (hingga 2023)PendudukTerbanyak: Lahore, Punjab — 11.126.285 (2017)[1]Tersedikit: Awaran, Balochistan — 121.660 (2017)[1]LuasTerluas: Chagai, Balochistan — 44.748 km2 (17.277 sq mi)Tersempit: Karachi Tengah, Sindh — 69 km2 (27 sq mi)PemerintahanAdministrasi DistrikPembagian administratifTehsil, Dewan Persatuan Pakistan Artikel ini adalah bagi...

 

Eaten Alive (album)

1985 studio album by Diana RossEaten AliveStudio album by Diana RossReleasedSeptember 24, 1985 (1985-09-24)Recorded1985Genre R&B pop Length40:25LabelRCAProducer Gibb-Galuten-Richardson Michael Jackson (co.) Diana Ross chronology Swept Away(1984) Eaten Alive(1985) Red Hot Rhythm & Blues(1987) Singles from Eaten Alive Eaten AliveReleased: September 1, 1985 Chain ReactionReleased: November 28, 1985 ExperienceReleased: April 4, 1986 Eaten Alive is the sixteenth stud...

 

Keuskupan Itabuna

Keuskupan ItabunaDioecesis ItabunensisCatedral São José (2015)LokasiNegara BrazilProvinsi gerejawiSão Salvador da BahiaStatistikLuas14.533 km2 (5.611 sq mi)Populasi- Total- Katolik(per 2006)650.000550,000 (84.6%)InformasiRitusRitus LatinPendirian7 November 1978 (45 tahun lalu)KatedralCatedral São JoséKepemimpinan kiniPausFransiskusUskupCzeslaw Stanula, C.Ss.R. Keuskupan Itabuna (Latin: Dioecesis Itabunensiscode: la is deprecated ) adalah sebuah keu...

Kuskus coklat

Kuskus coklat Status konservasi Risiko Rendah (IUCN 3.1)[1] Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Mammalia Ordo: Diprotodontia Famili: Phalangeridae Genus: Phalanger Spesies: P. orientalis Nama binomial Phalanger orientalis(Pallas, 1766) Sebaran kuskus coklat Kuskus coklat atau kuskus timur atau kuskus kelabu atau kuskus putih (Phalanger orientalis) adalah spesies marsupial dari famili Phalangeridae.[2][3][4][5] Kuskus ...

 

Daftar basilika di Yunani

Katedral Basilika Santo Dionisius orang Areopagus, Athena Ini adalah daftar basilika di Yunani. Katolik Daftar basilika Gereja Katolik di Yunani[1]: Katedral Basilika Santo Dionisius orang Areopagus, Athena Lihat juga Gereja Katolik Roma Gereja Katolik di Yunani Daftar katedral di Yunani Daftar basilika Referensi ^ Basilika di seluruh dunia lbsDaftar basilika di EropaNegaraberdaulat Albania Andorra Armenia1 Austria Azerbaijan1 Belanda Belarus Belgia Bosnia dan Herzegovina Britania Ray...

 

The Week (Brisbane)

Queensland, Australia newspaper (1876 - 1934) Front page of first issue, 1 January 1876. The Week was a newspaper published in Brisbane, Queensland, Australia. Its masthead described it as A Journal of Commerce, Farming, Mining & General Information & Amusement.[1] History The newspaper was published from 1 January 1876 to 27 June 1934.[2] Digitisation The newspaper has been digitised as part of the Trove digitised newspaper collection. References ^ Masthead. The Week....

Rip Van Winkle

For other uses, see Rip Van Winkle (disambiguation). 1819 short story by Washington IrvingRip Van WinkleShort story by Washington IrvingDepiction of Rip Van Winkle by John Quidor (1829). Housed at Art Institute of Chicago.Text available at WikisourceLanguageEnglishGenre(s)Short storyPublicationPublished inThe Sketch Book of Geoffrey Crayon, Gent.Publication date1819 Rip Van Winkle (Dutch pronunciation: [ˈrɪp fɑɱ ˈʋɪŋkəl]) is a short story by the American author Washington Irv...

 

Rudolf Molleker

German tennis player Rudolf MollekerMolleker at the 2019 French Open QualifyingCountry (sports) GermanyResidenceOranienburg, GermanyBorn (2000-10-26) 26 October 2000 (age 23)Sievierodonetsk, UkraineHeight1.85 m (6 ft 1 in)Turned pro2017PlaysRight-handed (two-handed backhand)CoachBenjamin ThielePrize money$536,333SinglesCareer record4–11 (26.7% at ATP Tour level)Career titles0Highest rankingNo. 146 (29 July 2019)Current rankingNo. 1...

 

William Raborn

United States Navy admiral William Raborn7th Director of Central IntelligenceIn officeApril 28, 1965 – June 30, 1966PresidentLyndon JohnsonDeputyRichard HelmsPreceded byJohn McConeSucceeded byRichard Helms Personal detailsBornWilliam Francis Raborn, Jr.(1905-06-08)June 8, 1905Decatur, Texas, U.S.DiedMarch 6, 1990(1990-03-06) (aged 84)McLean, Virginia, U.S.EducationUnited States Naval Academy (BS)Military serviceAllegiance United StatesBranch/service United States Nav...

Человек прямоходящий

† Человек прямоходящий Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапсиды�...

 

Saint Francis Xavier Cathedral (Green Bay, Wisconsin)

This article is about St. Francis Xavier Cathedral of Green Bay. For other uses, see St. Francis Xavier Cathedral (disambiguation). Church in Wisconsin, United StatesSaint Francis Xavier CathedralAerial viewLocation in Wisconsin44°30′41″N 88°00′42″W / 44.5114°N 88.0116°W / 44.5114; -88.0116LocationSouth Monroe AvenueGreen Bay, WisconsinCountryUnited StatesDenominationRoman CatholicWebsitewww.sfxcathedralgb.comHistoryStatusCathedralFounded1851DedicationNovem...

 

Views on masturbation in the Church of Jesus Christ of Latter-day Saints

Mormon views on sexual self-stimulation See also: Religious views on masturbation, Sexuality and Mormonism, and Law of chastity On many occasions spanning over a century, leaders of the Church of Jesus Christ of Latter-day Saints (LDS Church) have taught that adherents should not masturbate as part of obedience to the code of conduct known as the law of chastity.[1]: 94–109 [2][3] This denomination within Mormonism places great emphasis on the sexual ...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

High-occupancy vehicle lane

Restricted traffic lane HOV and HOV Lane redirect here. For the song by Nicki Minaj, see Pink Friday: Roman Reloaded. For other uses, see HOV (disambiguation). This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (January 2023) (Learn how and w...

 

Living for Love

For other uses, see Living for Love (disambiguation). 2014 single by MadonnaLiving for LoveSingle by Madonnafrom the album Rebel Heart ReleasedDecember 20, 2014 (2014-12-20)Recorded2014Genre EDM diva house disco electropop Length3:38LabelInterscopeSongwriter(s) Madonna Ciccone Thomas Wesley Pentz Maureen McDonald Toby Gad Ariel Rechtshaid Producer(s) Madonna Diplo Ariel Rechtshaid Madonna singles chronology Turn Up the Radio (2012) Living for Love (2014) Ghosttown (2015) Music ...

Cunicoli di Claudio

Cunicoli di ClaudioImbocchi del cunicolo MaggioreCiviltàromana EpocaI secolo - VI secolo LocalizzazioneStato Italia ComuneAvezzano, Capistrello AmministrazioneEnteSoprintendenza Archeologia, Belle Arti e PaesaggioConsorzio di bonifica Liri-Garigliano Sito webportalecultura.egov.regione.abruzzo.it/abruzzocultura/loadcard.do?id_card=114880&force=1&theme=aritnew Mappa di localizzazione Modifica dati su Wikidata · ManualeCoordinate: 41°59′18.7″N 13°26′00.2″E ...

 

Heribert Blens

German politician Heribert BlensCandidate poster of Heribert Blens for the Bundestag elections 1998Member of the BundestagIn office29 March 1983 – 17 October 2002 Personal detailsBorn (1936-02-19) 19 February 1936 (age 88)Köln, West Germany(now Germany)Political partyCDU Heribert Blens (19 February 1936, Cologne, West Germany) is a German politician of the Christian Democratic Union (CDU) and former member of the German Bundestag.[1] Life Blens became a member of the ...

 

نادي أبردين

نادي أبردين أف سي الشعار الاسم الكامل نادي أبردين إف سي اللقب السادة، الانيقون، الأغنام الاسم المختصر أبردين تأسس عام 14 أبريل 1903 (منذ 121 سنة) الملعب ملعب بيتودري(السعة: 20,897) البلد المملكة المتحدة  الدوري الدوري الاسكتلندي الممتاز 2019-20 الرابع الإدارة رئيس دايف كورماك المد...

Template talk:Acids and bases

This template does not require a rating on Wikipedia's content assessment scale.It is of interest to the following WikiProjects:Chemistry This template is within the scope of WikiProject Chemistry, a collaborative effort to improve the coverage of chemistry on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ChemistryWikipedia:WikiProject ChemistryTemplate:WikiProject ChemistryChemistry articles This tem...

 

Tell Basta

Pour les articles homonymes, voir Basta. Tell Basta Ville d'Égypte antique Noms Nom égyptien ancien Per Bastet Nom grec Boubastis Administration Pays Égypte Région Basse-Égypte Nome 18e : Nome supérieur de l'Enfant royal (jmt) Démographie Gentilé boubastite Géographie Coordonnées 30° 34′ 00″ nord, 31° 31′ 00″ est Localisation Géolocalisation sur la carte : Égypte Tell Basta Géolocalisation sur la carte : Égypte Tell Basta m...