Browsing by Subject "Graph decomposition"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Symmetric chain decompositions of partially ordered sets
    (2014-07) Zjevik, Ondrej
    A partially ordered set, or poset, is a set of elements and a binary relation which determines an order within elements. Various combinatorial properties of finite and ordered posets have been extensively studied during the last 4 decades. The Sperner property states that the size of the largest subset of pairwise incomparable elements does not exceed the size of the largest level set in an ordered poset. Since a symmetric chain decomposition is a sufficient condition for the Sperner property, we may prove the Sperner property by finding a symmetric chain decomposition for a poset.In this paper we focus on three types of posets: the Boolean algebra, inversion poset and the Young's lattice. An explicit construction for a symmetric chain decomposition is known only for Boolean algebras. No explicit construction has been found for inversion posets and Young's lattices, a symmetric chain decomposition was found only for a small subset of these posets. Using a maximal flow, we introduce an algorithm for finding this decomposition. We present our results and discuss two implementations of this algorithm.