Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Interval order
Résumé
In mathematics, especially order theory,
the interval order for a collection of intervals on the real line
is the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.
More formally, a countable poset is an interval order if and only if
there exists a bijection from to a set of real intervals,
so ,
such that for any we have
in exactly when .
Such posets may be equivalently
characterized as those with no induced subposet isomorphic to the
pair of two-element chains, in other words as the -free posets
Fully written out, this means that for any two pairs of elements and one must have or .
The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form , is precisely the semiorders.
The complement of the comparability graph of an interval order (, ≤)
is the interval graph .
Interval orders should not be confused with the interval-containment orders, which are the inclusion orders on intervals on the real line (equivalently, the orders of dimension ≤ 2).
An important parameter of partial orders is order dimension: the dimension of a partial order is the least number of linear orders whose intersection is . For interval orders, dimension can be arbitrarily large. And while the problem of determining the dimension of general partial orders is known to be NP-hard, determining the dimension of an interval order remains a problem of unknown computational complexity.
A related parameter is interval dimension, which is defined analogously, but in terms of interval orders instead of linear orders. Thus, the interval dimension of a partially ordered set is the least integer for which there exist interval orders on with exactly when and .
The interval dimension of an order is never greater than its order dimension.
Source officielle
À propos de ce résultat
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.