maths.free › Combinatorics & Graph Theory › 6. Partially Ordered Sets › Interval Orders

Interval Orders

When we discussed , we commented that the algorithmic aspects would be deferred until later in the text. But there is one important class of orders for which the full solution is easy to obtain.

Interval Orders

When we discussed , we commented that the algorithmic aspects would be deferred until later in the text. But there is one important class of orders for which the full solution is easy to obtain.

A poset \(\PXP\) is called an interval order if there exists a function \(I\) assigning to each element \(x\in X\) a closed interval \(I(x)=[a_x,b_x]\) of the real line \(\reals\) so that for all \(x\), \(y\in X\), \(x\lt y\) in \(P\) if and only if \(b_x\lt a_y\) in \(\reals\). We call \(I\) an interval representation of \(\bfP\), or just a representation for short. For brevity, whenever we say that \(I\) is a representation of an interval order \(\PXP\), we will use the alternate notation \([a_x,b_x]\) for the closed interval \(I(x)\). Also, we let \(|I(x)|\) denote the length of the interval, , \(|I(x)|=b_x-a_x\). Returning to the poset \(\bfP_3\), the representation shown in shows that it is an interval order.

Note that end points of intervals used in a representation need not be distinct. In fact, distinct points \(x\) and \(y\) from \(X\) may satisfy \(I(x)=I(y)\). We even allow degenerate intervals, , those of the form \([a,a]\). On the other hand, a representation is said to be distinguishing if all intervals are non-degenerate and all end points are distinct. It is relatively easy to see that every interval order has a distinguishing representation.

As we shall soon see, interval orders can be characterized succinctly in terms of forbidden subposets. Before stating this characterization, we need to introduce a bit more notation. By \(\bfn\) (for \(n\geq 1\) an integer), we mean the chain with \(n\) points. \(\bfn\) chain with \(n\) points More precisely, we take the ground set to be \(\{0,1,\dots,n-1\}\) with \(i \lt j\) in \(\bfn\) if and only if \(i\lt j\) in \(\ints\). If \(\PXP\) and \(\QYQ\) are posets with \(X\) and \(Y\) disjoint, then \(\bfP+\bfQ\) \(\bfP+\bfQ\) disjoint sum of posets is the poset \(\bfR=(X\cup Y,R)\) where the partial order is given by \(z\leq w\) in \(R\) if and only if (a) \(z,w\in X\) and \(z\leq w\) in \(P\) or (b) \(z,w\in Y\) and \(z\leq w\) in \(Q\). Thus, \(\bfn+\bfm\) consists of a chain with \(n\) points and a chain with \(m\) points and no comparabilities between them. In particular, \(\bftwo+\bftwo\) can be viewed as a four-point poset with ground set \(\{a,b,c,d\}\) and \(a\lt b\) and \(c\lt d\) as the only relations (other than those required to make the relation reflexive).

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Practice (3)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Consider the interval representation of an interval order shown below. The intervals depicted as vertical lines are degenerate intervals of the form \([z,z]\). List the elements that are less than \(m\) in this interval order.

  2. Consider the interval representation of an interval order shown below. The intervals depicted as vertical lines are degenerate intervals of the form \([z,z]\). List the elements that are incomparable to \(f\) in this interval order.

  3. Consider the poset whose diagram is shown below. Explain why this poset is not an interval order.

Symbols used here

\int f(x)\,dx,\ \int_a^b
integral
Antiderivative (indefinite) or signed area from a to b (definite).
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Өөрийнхөөг турш

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Бүх зүйл Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs