Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth (en), caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes.Dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables et une chaîne est une partie dont les éléments sont deux à deux comparables.

PropertyValue
dbpedia-owl:abstract
  • Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth (en), caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes.Dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables et une chaîne est une partie dont les éléments sont deux à deux comparables. Le théorème de Dilworth établit, pour un ordre fini, l'existence d'une antichaîne A et d'une partition de l'ensemble ordonné en une famille P de chaînes, telles que A et P aient même cardinal. Pour de tels A et P, A est nécessairement une antichaîne de cardinal maximum (puisque toute antichaîne a au plus un élément dans chaque membre de P) et P est nécessairement une partition en chaînes de cardinal minimum (puisque toute partition en chaînes a au moins une chaîne par élément de A). La largeur de l'ordre partiel (i.e. la taille maximum d'une antichaîne) peut donc être redéfinie comme le cardinal commun de A et P, ou comme la taille minimum d'une partition en chaînes.Une généralisation de ce théorème établit qu'un ordre (non nécessairement fini) est de largeur finie w si et seulement s'il peut être partitionné en w chaînes, mais pas moins.
  • 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 (1950).An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. Dilworth's theorem states that there exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A. When this occurs, A must be the largest antichain in the order, for any antichain can have at most one element from each member of P. Similarly, P must be the smallest family of chains into which the order can be partitioned, for any partition into chains must have at least one chain per element of A. The width of the partial order is defined as the common size of A and P.An equivalent way of stating Dilworth's theorem is that, in any finite partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains. A version of the theorem for infinite partially ordered sets states that, in this case, a partially ordered set has finite width w if and only if it may be partitioned into w chains, but not less.
  • Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств. Теорема была доказана американским математиком Робертом Дилуорсом, (1914—1993), главной областью исследований которого была теория решёток.
  • 딜워스의 정리(Dilworth's theorem, -定理)는 그래프 이론, 순서론, 조합적 집합론 등에서 다뤄지는 수학적 정리로, 미국의 수학자 로버트 팔머 딜워스(Robert Palmer Dilworth)가 1950년 논문에서 처음 제시하였다.
  • Der Satz von Dilworth ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er geht zurück auf eine Arbeit von Robert Palmer Dilworth aus dem Jahr 1950 . Der Satz macht eine fundamentale Aussage über das Zusammenspiel zwischen Ketten und Antiketten in einer Halbordnung .
dbpedia-owl:thumbnail
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 6635771 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 14973 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 49 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 110357916 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
prop-fr:année
  • 1999 (xsd:integer)
  • 2004 (xsd:integer)
  • 2005 (xsd:integer)
prop-fr:auteur
  • László Babai
  • Robert D. Borgersen
  • S. Felsner, V. Raghavan et J. Spinrad
prop-fr:lienAuteur
  • László Babai
prop-fr:nomUrl
  • DilworthsLemma
prop-fr:site
prop-fr:titre
  • Dilworth's Lemma
prop-fr:url
prop-fr:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth (en), caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes.Dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables et une chaîne est une partie dont les éléments sont deux à deux comparables.
  • Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств. Теорема была доказана американским математиком Робертом Дилуорсом, (1914—1993), главной областью исследований которого была теория решёток.
  • 딜워스의 정리(Dilworth's theorem, -定理)는 그래프 이론, 순서론, 조합적 집합론 등에서 다뤄지는 수학적 정리로, 미국의 수학자 로버트 팔머 딜워스(Robert Palmer Dilworth)가 1950년 논문에서 처음 제시하였다.
  • Der Satz von Dilworth ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er geht zurück auf eine Arbeit von Robert Palmer Dilworth aus dem Jahr 1950 . Der Satz macht eine fundamentale Aussage über das Zusammenspiel zwischen Ketten und Antiketten in einer Halbordnung .
  • 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 (1950).An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable.
rdfs:label
  • Théorème de Dilworth
  • Dilworth's theorem
  • Satz von Dilworth
  • Теорема Дилуорса
  • 딜워스의 정리
owl:sameAs
http://www.w3.org/ns/prov#wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of