In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, especially order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

,
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₁, being considered less than another, I₂, if I₁ is completely to the left of I₂.
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 interval

Unit interval

In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

s is a semiorder

Semiorder

In order theory, a branch of mathematics, a semiorder is a type of ordering that may be determined for a set of items with numerical scores by declaring two items to be incomparable when their scores are within some threshold of each other and otherwise using the numerical comparison of their scores...

.

The complement

Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

 of the comparability graph

Comparability graph

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

 of an interval order (, ≤)
is the interval graph

Interval graph

In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...

.