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.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
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.
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. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.
In order theory, a Hasse diagram (ˈhæsə; ˈhasə) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever covers (that is, whenever , and there is no distinct from and with ). These curves may cross each other but must not touch any vertices other than their endpoints.
We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand) ...
The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...
Recently, Pawlik et al. have shown that triangle-free intersection graphs of line segments in the plane can have arbitrarily large chromatic number. Specifically, they construct triangle-free segment intersection graphs with chromatic number Θ(log log n). ...