•   When: Thursday, September 24, 2015 from 01:00 PM to 03:00 PM
•   Speakers: Indranil Banerjee
•   Location: Nguyen Engineering, Room 3507
•   Export to iCal

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 half 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(kn^2) and in the worst case by O(kn^2). For non-constant k, to the best of our knowledge, this is the first such algorithm for the problem. Furthermore we extend the results for random orders with arbitrary distributions.