Order, lattices, ordered algebraic structures Theorem
On-line antichain partition of a poset of bounded height
Builds on Partial orderAntichainHeight of a poset
Statement
Consider the on-line game in which the points of a partially ordered set are shown to Assigner one at a time. When a point appears, Assigner sees how it compares with the points shown before it. She must at once put it into a class, and she can never move it later. Each class must end up as an antichain.
Fix an integer . Then Assigner has a strategy for this game that works for every poset whose height is at most . This strategy splits into at most antichains.
Remarks
The off-line bound is only antichains, by Mirsky's theorem. The theorem shows that the on-line setting costs a factor of about in the number of classes.
Reading path
To understand this page from the ground up, read these 4 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Antichain concept
- Height of a poset concept
- Partial order concept
- On-line antichain partition of a poset of bounded height statement
Further reading
- Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_kitchensink_online.ptx#L57, source/s_kitchensink_online.ptx:57
About this page
| Tag | JK9V1NZKXQ |
|---|---|
| URI | m2://JK9V1NZKXQ |
| Kind | statement, theorem |
| Writing | W1 stated |
| MSC | 06A07, 05C15 |
| Status | This copy of the site has no build data. Run m2 status JK9V1NZKXQ. |
| About | Antichain, Height of a poset |
| Uses | Partial order, Antichain, Height of a poset |
| 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.