On-line version of Rabinovitch theorem for proper intervals

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 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.