##
Reports on Mathematical Logic

###
No. 42

Kamil KLOCH

Online dimension of partially ordered sets
A b s t r a c t. We investigate the online dimension of upgrowing partial orders. The problem is treated as a two-person game. One person builds an
order, one point at a time; the other person maintains its online realizer. The value of the game (the number of linear extensions used) is compared
with the offline width of the poset. We prove that the online dimension of width 2 upgrowing orders is exactly 2. In general case we prove a lower
bound of $\left\lfloor 7d/4 \right\rfloor - 2$ for width $d$ upgrowing orders.

Back to Main Menu