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

Author(s)

Griggs, Jerrold R

Hartmann, Sven

Kalinowski, Thomas

Leck, Uwe

Roberts, Ian T

Publication Date

2021-10

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 m k-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.

Citation

Order, 38(3), p. 441-453

ISSN

1572-9273

0167-8094

Link

https://hdl.handle.net/1959.11/30189

Publisher

Springer Netherlands

Title

Minimum Weight Flat Antichains of Subsets

Type of document

Journal Article

Entity Type

Publication

Author(s)	Griggs, Jerrold R Hartmann, Sven Kalinowski, Thomas Leck, Uwe Roberts, Ian T
Publication Date	2021-10
Abstract	Building on classical theorems of Sperner and Kruskal-Katona, we investigate antichains <i>F</i> in the Boolean lattice <i>Bn</i> of all subsets of [<i>n</i>]:={1,2,…,<i>n</i>}, where <i>F</i> is flat, meaning that it contains sets of at most two consecutive sizes, say <i>F</i>=<i>A</i>∪<i>B</i>, where <i>A</i> contains only <i>k</i>-subsets, while <i>B</i> contains only (<i>k</i> − 1)-subsets. Moreover, we assume <i>A</i> consists of the first <i>m k</i>-subsets in squashed (colexicographic) order, while <i>B</i> consists of all (<i>k</i> − 1)-subsets not contained in the subsets in <i>A</i>. Given reals <i>α</i>,<i>β</i> > 0, we say the weight of <i>F</i> is <i>α</i>⋅\|<i>A</i>\|+<i>β</i>⋅\|<i>B</i>\|. We characterize the minimum weight antichains <i>F</i> for any given <i>n</i>,<i>k</i>,<i>α</i>,<i>β</i>, and we do the same when in addition <i>F</i> is a maximal antichain. We can then derive asymptotic results on both the minimum size and the minimum Lubell function.
Citation	Order, 38(3), p. 441-453
ISSN	1572-9273 0167-8094
Link	https://hdl.handle.net/1959.11/30189
Publisher	Springer Netherlands
Title	Minimum Weight Flat Antichains of Subsets
Type of document	Journal Article
Entity Type	Publication

Minimum Weight Flat Antichains of Subsets

Files: