About: Dilworth's theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Dilworth's theorem Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatPerfectGraphs, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FDilworth%27s_theorem

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth. A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.

Attributes	Values
rdf:type	yago:WikicatMathematicalTheorems yago:WikicatTheoremsInCombinatorics yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 yago:VisualCommunication106873252 yago:WikicatPerfectGraphs
rdfs:label	Satz von Dilworth (de) Dilworth's theorem (en) Théorème de Dilworth (fr) 딜워스의 정리 (ko) Теорема Дилуорса (ru) Теорема Ділуорса (uk)
rdfs:comment	Der Satz von Dilworth ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er gilt als einer der fundamentalen Sätze der sogenannten Matching theory. Der Satz geht zurück auf eine Arbeit von Robert Palmer Dilworth aus dem Jahr 1950. Er macht eine grundlegende Aussage über das Zusammenspiel zwischen Ketten und Antiketten in einer Halbordnung. (de) Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth, caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes. (fr) 조합론에서 딜워스의 정리(Dilworth의定理, 영어: Dilworth’s theorem)는 부분 순서 집합의 반사슬의 최대 크기에 대한 정리다. (ko) In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth. A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal. (en) Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество может быть разбито на попарно непересекающихся цепей, где — количество элементов наибольшей антицепи множества (называемое также шириной частично упорядоченного множества). Версия теоремы для бесконечных частично упорядоченных множеств: частично упорядоченное множество имеет конечную ширину тогда и только тогда, когда его можно разбить на цепей, но не меньше. (ru) У математиці, в таких галузях, як теорія порядку та комбінаторика, Теорема Ділуорса характеризує ширину довільної скінченної частково впорядкованої множини у термінах розбиття цього порядку на найменше число ланцюгів. Названа на честь математика . Еквівалентне формулювання Теореми Ділуорса таке, у довільній частково впорядкованій множині, найбільше число елементів у будь-якому антиланцюзі дорівнює найменшому числу ланцюгів у будь-якому розбитті даної множини на ланцюги. (uk)
foaf:depiction
dcterms:subject	Perfect graphs Articles containing proofs Order theory Theorems in combinatorics
Wikipage page ID	749033 (xsd:integer)
Wikipage revision ID	1092446153 (xsd:integer)
Link from a Wikipage to another Wikipage	Power set Boolean lattice Annals of Mathematics Antichain Antimatroid Perfect graphs Aleph-naught Undirected graph De Bruijn–Erdős theorem (graph theory) Independent set (graph theory) Induced subgraph Kőnig's theorem (graph theory) Articles containing proofs Order theory Mathematics Order (journal) Order theory Chromatic number Graph coloring Erdős–Szekeres theorem Clique (graph theory) Combinatorics Comparability graph Complement graph Hall's marriage theorem Perfect graph Proceedings of the American Mathematical Society Theorems in combinatorics American Mathematical Monthly Partially ordered set Partition of a set Discrete Mathematics (journal) Israel Journal of Mathematics Order dimension Bipartite graph Sperner's theorem Polynomial time Inclusion (set theory) Chain (order theory) Lubell–Yamamoto–Meshalkin inequality PlanetMath Perfect graph theorem Disjoint set Divisibility
Link from a Wikipage to an external page	https://books.google.com/books%3Fid=FYV6tGm3NzgC&pg=PA59 http://robertborgersen.info/Presentations/GS-05R-1.pdf http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf https://refubium.fu-berlin.de/handle/fub188/18407 http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf http://www.inf.fu-berlin.de/inst/pubs/tr-b-99-05.abstract.html%7C http://planetmath.org/encyclopedia/DualOfDilworthsTheorem.html https://web.archive.org/web/20070714201213/http:/planetmath.org/encyclopedia/DualOfDilworthsTheorem.html https://web.archive.org/web/20110720134637/http:/www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf
sameAs	Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem Dilworth's theorem
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harv dbt:Harvtxt dbt:Main_article

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 45 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software