The Saturation Spectrum for Antichains of Subsets

Jerrold R. Griggs, Thomas Kalinowski, Uwe Leck, Ian T. Roberts, Michael Schmitz

    Research output: Contribution to journalArticlepeer-review

    3 Citations (Scopus)
    32 Downloads (Pure)

    Abstract

    Extending a classical theorem of Sperner, we characterize the integers m such that there exists a maximal antichain of size m in the Boolean lattice Bn, that is, the power set of [n] : = { 1 , 2 , … , n} , ordered by inclusion. As an important ingredient in the proof, we initiate the study of an extension of the Kruskal-Katona theorem which is of independent interest. For given positive integers t and k, we ask which integers s have the property that there exists a family F of k-sets with | F| = t such that the shadow of F has size s, where the shadow of F is the collection of (k − 1)-sets that are contained in at least one member of F. We provide a complete answer for t≤ k+ 1. Moreover, we prove that the largest integer which is not the shadow size of any family of k-sets is 2k3/2+84k5/4+O(k).

    Original languageEnglish
    Pages (from-to)537-574
    Number of pages38
    JournalOrder
    Volume40
    Issue number3
    Early online date10 Feb 2023
    DOIs
    Publication statusPublished - Oct 2023

    Bibliographical note

    Funding Information:
    The research of Jerrold Griggs is supported in part by grant #282896 from the Simons Foundation.

    Publisher Copyright:
    © 2023, The Author(s), under exclusive licence to Springer Nature B.V.

    Fingerprint

    Dive into the research topics of 'The Saturation Spectrum for Antichains of Subsets'. Together they form a unique fingerprint.

    Cite this