Math 2.0

Order, lattices, ordered algebraic structures Theorem

Builder strategy forcing many antichains in on-line poset partitioning

Builds on Partial orderAntichainHeight of a posetMaximal element

Statement

Two players build a partially ordered set PP in an on-line game. The builder presents the points of PP one at a time, and states how each new point compares with the points shown before. The assigner must put each new point at once into an antichain, and cannot change this later. The antichains together partition PP.

Then for every integer h≥1h \ge 1, the builder has a strategy ShS_h that produces a poset PP of height hh and forces the assigner to do both of the following.

  1. The assigner uses at least (h+12)\binom{h+1}{2} antichains to partition PP.
  2. The assigner uses at least hh different antichains for the set of maximal elements of PP.

Remarks

Off-line, a poset of height hh needs only hh antichains, by Mirsky's theorem. The result shows that an on-line assigner can be forced to use about h2/2h^2/2 antichains.

Reading path

To understand this page from the ground up, read these 5 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. Maximal element concept
  4. Partial order concept
  5. Builder strategy forcing many antichains in on-line poset partitioning statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_kitchensink_online.ptx#L84, source/s_kitchensink_online.ptx:84
About this page
Tag2FC9JFQPBX
URIm2://2FC9JFQPBX
Kindstatement, theorem
WritingW1 stated
MSC06A07
StatusThis copy of the site has no build data. Run m2 status 2FC9JFQPBX.
AboutAntichain, Height of a poset
UsesPartial order, Antichain, Height of a poset, Maximal element
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.