Online dimension of partially ordered sets

• Autorzy: Kloch K.
• Języki publikacji: EN

Abstrakty

EN

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 oine 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 b7d=4c .. 2 for width d upgrowing orders.

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2007
• Tom: No. 42
• Strony: 101--116
• Opis fizyczny: Bibliogr. 3 poz., rys.

Twórcy

autor

Kloch K.

• Computer Science Department Jagiellonian University ul. Nawojki 11, 30-072 Krakow, Poland,

Bibliografia

• [1] S. Felsner, On-line chain partitions of orders, Theoret. Computer Science 175 (1997), pp. 283-292.
• [2] W. T. Trotter, Combinatorics and Partially Ordered Sets: dimension theory, John Hopkins Press, 1992.
• [3] M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Algebraic Discrete Methods 3 (1982), pp. 351-358.