In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.
This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order.
first studied order dimension; for a more detailed treatment of this subject than provided here, see .
The dimension of a poset P is the least integer t for which there exists a family
of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions. That is,
An alternative definition of order dimension is the minimal number of total orders such that P embeds into their product with componentwise ordering i.e. if and only if for all i (, ).
A family of linear orders on X is called a realizer of a poset P = (X,
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Dans la branche des mathématiques de la théorie des ordres, une extension linéaire d'un ordre partiel est un ordre total (ou ordre linéaire) qui est compatible avec l'ordre partiel. Un exemple classique est l'ordre lexicographique des ensembles totalement ordonnés qui est une extension linéaire de leur ordre produit. Étant donnés des ordres partiels quelconques ≤ et ≤* sur un ensemble X, ≤* est une extension linéaire de ≤ si et seulement si (1) ≤* est un ordre total et (2) pour tout x et y dans X, si , alors .
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. first studied order dimension; for a more detailed treatment of this subject than provided here, see . The dimension of a poset P is the least integer t for which there exists a family of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions.
Dans la théorie des graphes, un graphe de comparabilité est un graphe non orienté qui relie les paires d'éléments qui sont comparables les uns aux autres dans un ordre partiel donné. On les trouve aussi sous le nom de transitively orientable graphs, partially orderable graphs, et containment graphs. Les graphes de comparabilité sont des graphes parfaits. Les cographes sont des graphes de comparabilité Les graphes qui sont de comparabilité et dont le complémentaire est aussi de comparabilité sont exactement les graphes de permutations.
Couvre les relations, les séquences et les posets, en mettant l'accent sur des propriétés telles que l'antisymétrie et la transitivité, et introduit des progressions arithmétiques et géométriques.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a