Abstract
A poset P = (X, ≺) has an interval representation if each x ∈ X can be assigned a real interval Ix so that x ≺ y in P if and only if Ix lies completely to the left of Iy. Such orders are called interval orders. Fishburn (1983, 1985) proved that for any positive integer k, an interval order has a representation in which all interval lengths are between 1 and k if and only if the order does not contain (k+2)+1 as an induced poset. In this paper, we give a simple proof of this result using a digraph model.
| Original language | English |
|---|---|
| Pages (from-to) | 893-900 |
| Number of pages | 8 |
| Journal | Involve |
| Volume | 11 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 2018 |
Bibliographical note
Funding Information:MSC2010: 05C62, 06A99. Keywords: interval order, interval graph, semiorder. Boyadzhiyska was supported by a Jerome A. Schiff Fellowship at Wellesley College. supported by a grant from the Simons Foundation #426725.
Publisher Copyright:
© 2018 Mathematical Sciences Publishers.
Keywords
- interval graph
- interval order
- semiorder
ASJC Scopus subject areas
- General Mathematics