Lower bounds for randomized algorithms for online chain partitioning

We prove that the randomized competitive ratio of online chain partitioning of posets equals the deterministic competitive ratio.

► We consider performance of randomized algorithms for online chain partitioning of posets.
► We construct a set of partial orders that are hard instances for randomized algorithms.
► We prove that known lower bounds for deterministic algorithms hold for randomized algorithms.