Order, lattices, ordered algebraic structures Theorem
Minimal integer representation of an interval order
Builds on Interval orderUpper set
Statement
Let be a finite poset on a set that contains no . Let be the family of distinct strict down sets of elements . Let be the family of distinct strict up sets (see upper set). Both families are chains under inclusion. Order the sets of each family and use their positions to give every an interval with integer end points. This is the standard interval order representation of . Then all of these hold.
- The two families have the same size: . Call this number .
- For each with , we have .
- For with and , we have in if and only if .
- The number is the least positive integer such that has an interval representation with all end points in . This representation is unique.
Remarks
Parts 2 and 3 say that the intervals are genuine intervals and that they encode the order of exactly. Part 4 says that this representation uses the fewest possible integer values and that nothing else does as well.
Reading path
To understand this page from the ground up, read these 3 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Interval order concept
- Upper set concept
- Minimal integer representation of an interval order statement
Further reading
- Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_posets_intervalorder_findrep.ptx#L53, source/s_posets_intervalorder_findrep.ptx:53
About this page
| Tag | D20HMAETQV |
|---|---|
| URI | m2://D20HMAETQV |
| Kind | statement, theorem |
| Writing | W1 stated |
| MSC | 06A06 |
| Status | This copy of the site has no build data. Run m2 status D20HMAETQV. |
| About | Interval order |
| Uses | Interval order, Upper set |
| Changed | 4 November 2026 |
Markdown Β· JSON Β· Edit on GitHub
What this page needs for W2
- edge proves in: at least one proof node (0 of 1)
- edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
- explanation L2 (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.