TY - JOUR

T1 - Minimum Weight Flat Antichains of Subsets

AU - Griggs, Jerrold R.

AU - Hartmann, Sven

AU - Kalinowski, Thomas

AU - Leck, Uwe

AU - Roberts, Ian T.

PY - 2021/10

Y1 - 2021/10

N2 - 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.

AB - 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.

KW - Antichain

KW - Flat antichain

KW - Kruskal-Katona theorem

KW - Lubell function

KW - Sperner family

UR - http://www.scopus.com/inward/record.url?scp=85099915977&partnerID=8YFLogxK

U2 - 10.1007/s11083-021-09550-x

DO - 10.1007/s11083-021-09550-x

M3 - Article

AN - SCOPUS:85099915977

SN - 0167-8094

VL - 38

SP - 441

EP - 453

JO - Order

JF - Order

IS - 3

ER -