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.
