Supersaturation in the Boolean Lattice

A.P. Dove, J.R. Griggs, J.R. Kang, J.-S. Sereni

    Research output: Book/ReportReportAcademic

    Abstract

    We prove a “supersaturation-type” extension of both Sperner’s Theorem (1928) and its generalization by Erd˝os (1945) to k-chains. Our result implies that a largest family whose size is x more than the size of a largest k-chain free family and that contains the minimum number of k-chains is the family formed by taking the middle (k ¡1) rows of the Boolean lattice and x elements fromthe kth middle row. We prove our result using the symmetric chain decomposition method of de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (1951).
    Original languageEnglish
    PublisherCentre pour la Communication Scientifique Directe (CNRS), hal-00802000
    Number of pages6
    Publication statusPublished - 2013

    Fingerprint

    Dive into the research topics of 'Supersaturation in the Boolean Lattice'. Together they form a unique fingerprint.

    Cite this