On Maximal Layers Of Random Orders

Abstract

In this thesis we investigate the maximal layers of random partial orders. Main contributions are two-fold. In the first half we investigate the expected size of different maximal layers of a random partial order. In particular when the points are in a plane, we give an enumerative formula for the distribution of the size of these maximal sets. Using Monte- Carlo based simulation we extrapolate the results for higher dimensions. In the second part we explore the computational aspect of the problem. To this end we propose a randomized algorithm for computing the maximal layers and analyze its expected runtime. We show that the expected runtime of our proposed algorithm is bounded by o(kn2) when k is fixed and in the worst case by O(kn2). This is the first non-trivial algorithm whose run-time remains polynomial whenever k is bounded by some polynomial in n while remaining subquadratic in n for constant k. We also extend these results to random orders with arbitrary distributions.