Minimum Weight Flat Antichains of Subsets

Jerrold R. Griggs, Sven Hartmann, Thomas Kalinowski, Uwe Leck, Ian T. Roberts

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Building on classical theorems of Sperner and Kruskal-Katona, we investigate antichains F in the Boolean lattice Bn of all subsets of [n] : = { 1 , 2 , … , n} , where F is flat, meaning that it contains sets of at most two consecutive sizes, say F= A∪ B, where A contains only k-subsets, while B contains only (k − 1)-subsets. Moreover, we assume A consists of the first mk-subsets in squashed (colexicographic) order, while B consists of all (k − 1)-subsets not contained in the subsets in A. Given reals α, β > 0, we say the weight of F is α⋅ | A| + β⋅ | B|. We characterize the minimum weight antichains F for any given n,k,α,β, and we do the same when in addition F is a maximal antichain. We can then derive asymptotic results on both the minimum size and the minimum Lubell function.

    Original languageEnglish
    Pages (from-to)1-13
    Number of pages13
    JournalOrder
    DOIs
    Publication statusE-pub ahead of print - 25 Jan 2021

    Fingerprint

    Dive into the research topics of 'Minimum Weight Flat Antichains of Subsets'. Together they form a unique fingerprint.

    Cite this