Math 2.0

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 PP 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 h≥1h \ge 1. Then Assigner has a strategy for this game that works for every poset PP whose height is at most hh. This strategy splits PP into at most (h+12)\binom{h+1}{2} antichains.

Remarks

The off-line bound is only hh antichains, by Mirsky's theorem. The theorem shows that the on-line setting costs a factor of about (h+1)/2(h+1)/2 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
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Antichain concept
  2. Height of a poset concept
  3. Partial order concept
  4. On-line antichain partition of a poset of bounded height statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_kitchensink_online.ptx#L57, source/s_kitchensink_online.ptx:57
About this page
TagJK9V1NZKXQ
URIm2://JK9V1NZKXQ
Kindstatement, theorem
WritingW1 stated
MSC06A07, 05C15
StatusThis copy of the site has no build data. Run m2 status JK9V1NZKXQ.
AboutAntichain, Height of a poset
UsesPartial order, Antichain, Height of a poset
Changed4 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.