Publikation
On-line version of Rabinovitch theorem for proper intervals
Bartlomiej Bosek; Kamil Kloch; Tomasz Krawczyk; Piotr Micek
In: Discrete Mathematics, Vol. 312, No. 23, Pages 3426-3436, Elsevier, 2012.
Zusammenfassung
We analyze the on-line dimension of semi-orders as a two-person game between Algorithm and Spoiler, in a customary way. The game is played in rounds. Spoiler presents a collection of intervals representing a semi-order, one interval at a time. Algorithm maintains its realizer, i.e., the set of linear extensions intersecting to the semi-order presented so far.
Each time a new interval is presented, Algorithm inserts it into all maintained linear extensions and is not allowed to change the ordering of the previously introduced elements.
Reading carefully the theorem of Rabinovitch on dimension of semi-orders one can prove that Algorithm needs only 3 linear extensions when Spoiler presents intervals of unit length. With the introduction of proper intervals, however, Algorithm can be forced to use one more extension. We prove that the value of the game on proper intervals is exactly 4.