Minimum Weight Flat Antichains of Subsets
2021
Building on classical theorems of Sperner and Kruskal-Katona, we investigate antichains $\mathcal {F}$
in the Boolean lattice Bn of all subsets of $[n]:=\{1,2,\dots ,n\}$
, where $\mathcal {F}$
is flat, meaning that it contains sets of at most two consecutive sizes, say $\mathcal {F}=\mathcal {A}\cup {\mathscr{B}}$
, where $\mathcal {A}$
contains only k-subsets, while ${\mathscr{B}}$
contains only (k − 1)-subsets. Moreover, we assume $\mathcal {A}$
consists of the first m k-subsets in squashed (colexicographic) order, while ${\mathscr{B}}$
consists of all (k − 1)-subsets not contained in the subsets in $\mathcal {A}$
. Given reals α, β > 0, we say the weight of $\mathcal {F}$
is $\alpha \cdot |\mathcal {A}|+\beta \cdot |{\mathscr{B}}|$
. We characterize the minimum weight antichains $\mathcal {F}$
for any given n,k,α,β, and we do the same when in addition $\mathcal {F}$
is a maximal antichain. We can then derive asymptotic results on both the minimum size and the minimum Lubell function.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
20
References
2
Citations
NaN
KQI