Namespaces
Variants
Actions

Difference between revisions of "Interval order"

From Encyclopedia of Mathematics
Jump to: navigation, search
(MSC 06A)
(→‎References: Golumbic & Trenk (2004))
Line 21: Line 21:
 
<TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Scott,  P. Suppes,  "Foundational aspects of the theories of measurement"  ''J. Symbolic Logic'' , '''23'''  (1958)  pp. 113–128</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Scott,  P. Suppes,  "Foundational aspects of the theories of measurement"  ''J. Symbolic Logic'' , '''23'''  (1958)  pp. 113–128</TD></TR>
 
<TR><TD valign="top">[a3]</TD> <TD valign="top">  W.T. Trotter,  "Partially ordered sets"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovász (ed.) , ''Handbook of Combinatorics'' , '''I''' , North-Holland  (1995)  pp. 433–480</TD></TR>
 
<TR><TD valign="top">[a3]</TD> <TD valign="top">  W.T. Trotter,  "Partially ordered sets"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovász (ed.) , ''Handbook of Combinatorics'' , '''I''' , North-Holland  (1995)  pp. 433–480</TD></TR>
 +
</table>
 +
 +
<table>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Martin Charles Golumbic, Ann N. Trenk,  ''Tolerance Graphs'', Cambridge Studies in Advanced Mathematics '''89''' Cambridge University Press (2004) ISBN 0-521-82758-2</TD></TR>
 
</table>
 
</table>

Revision as of 21:36, 1 December 2014

2020 Mathematics Subject Classification: Primary: 06A [MSN][ZBL]

interval ordering, interval partially ordered set, interval poset

A partial order on the set $S$ of closed intervals of the real line $\mathbb{R}$, defined by $$ I_1 \le I_2 \Leftrightarrow x \le y\ \text{in}\ \mathbb{R}\ \text{for all}\ x\in I_1,\,y \in I_2\ . $$

Such a partially ordered set (more precisely, one isomorphic to it) is called an interval order.

A linear order, also called a totally ordered set, is an interval order (but an interval order need not be total, of course).

There is the following forbidden sub-poset characterization of interval orders (the Fishburn theorem, [a1]): A poset $P$ is an interval order if and only if $P$ does not contain the disjoint sum $\mathbf{2} + \mathbf{2}$ as a sub-poset (cf. also Disjoint sum of partially ordered sets). Here, $\mathbf{2}$ is the totally ordered set $\{1,2\}$, $1<2$, so that $\mathbf{2} + \mathbf{2} = \{a_1,a_2,b_1,b_2\}$ with $a_1 < a_2$, $b_1 < b_2$ and no other comparable pairs of distinct elements.

A poset is called a semi-order if there is a function $f : P \rightarrow \mathbf{R}$ such that $x < y$ in $P$ if and only if $f(y) > f(x)+1$. Clearly, a semi-order is isomorphic to an interval order with all intervals of length $1$. Here too, a forbidden sub-poset characterization holds (the Scott–Suppes theorem, [a2]): A poset $P$ is a semi-order if and only if it does not contain either $\mathbf{2} + \mathbf{2}$ or $\mathbf{3} + \mathbf{1}$ as a sub-poset.

References

[a1] P.C. Fishburn, "Intransitive indifference with unequal indifference intervals" J. Math. Psychol. , 7 (1970) pp. 144–149
[a2] D. Scott, P. Suppes, "Foundational aspects of the theories of measurement" J. Symbolic Logic , 23 (1958) pp. 113–128
[a3] W.T. Trotter, "Partially ordered sets" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , I , North-Holland (1995) pp. 433–480
[b1] Martin Charles Golumbic, Ann N. Trenk, Tolerance Graphs, Cambridge Studies in Advanced Mathematics 89 Cambridge University Press (2004) ISBN 0-521-82758-2
How to Cite This Entry:
Interval order. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Interval_order&oldid=35292
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article