Reports on Mathematical Logic

No. 42


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