Prevalent and shy sets: Difference between revisions
en>R'n'B m Fix links to disambiguation page Infinite |
en>SepIHw m The order of "quantifiers" fixed |
||
| Line 1: | Line 1: | ||
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, ''I''<sub>1</sub>, being considered less than another, ''I''<sub>2</sub>, if ''I''<sub>1</sub> is completely to the left of ''I''<sub>2</sub>. | |||
More formally, a [[poset]] <math>P = (X, \leq)</math> is an interval order if and only if | |||
there exists a bijection from <math>X</math> to a set of real intervals, | |||
so <math> x_i \mapsto (\ell_i, r_i) </math>, | |||
such that for any <math>x_i, x_j \in X</math> we have | |||
<math> x_i < x_j </math> in <math>P</math> exactly when <math> r_i < \ell_j </math>. | |||
An interval order defined by [[unit interval]]s is a [[semiorder]]. | |||
The [[complement graph|complement]] of the [[comparability graph]] of an interval order (<math>X</math>, ≤) | |||
is the [[interval graph]] <math>(X, \cap)</math>. | |||
Interval orders should not be confused with the interval-containment orders, which are the [[containment order]]s on intervals on the real line (equivalently, the orders of [[order dimension|dimension]] ≤ 2). | |||
== Interval dimension == | |||
The interval dimension of a [[partial order]] can be defined as the minimal number of interval order extensions realizing this order, in a similar way to the definition of the [[order dimension]] which uses [[linear extension]]s. The interval dimension of an order is always less than its [[order dimension]],<ref>http://page.math.tu-berlin.de/~felsner/Paper/Idim-dim.pdf p.2</ref> but interval orders with high dimensions are known to exist. While the problem of determining the [[order dimension]] of general partial orders is known to be [[NP-complete]], the complexity of determining the [[order dimension]] of an interval order is unknown.<ref>http://page.math.tu-berlin.de/~felsner/Paper/diss.pdf, p.47</ref> | |||
==References== | |||
*{{cite book | last = Fishburn | first = Peter | title = Interval Orders and Interval Graphs: A Study of Partially Ordered Sets | publisher = John Wiley | year = 1985}} | |||
*[[Gunther Schmidt]], 2010. ''Relational Mathematics''. Cambridge University Press, ISBN 978-0-521-76268-7. | |||
<references /> | |||
[[Category:Order theory]] | |||
Latest revision as of 03:08, 27 December 2012
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 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 .
An interval order defined by unit intervals is a semiorder.
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 containment orders on intervals on the real line (equivalently, the orders of dimension ≤ 2).
Interval dimension
The interval dimension of a partial order can be defined as the minimal number of interval order extensions realizing this order, in a similar way to the definition of the order dimension which uses linear extensions. The interval dimension of an order is always less than its order dimension,[1] but interval orders with high dimensions are known to exist. While the problem of determining the order dimension of general partial orders is known to be NP-complete, the complexity of determining the order dimension of an interval order is unknown.[2]
References
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.