Minimum Weight Flat Antichains of Subsets

DOI10.1007/S11083-021-09550-XMaRDI QIDQ6285036arXivFDO

Authors J. Griggs, Sven Hartmann, Thomas Kalinowski, Uwe Leck, Ian T. Roberts

Publication date 31 March 2017

Published in arXiv

Full work available at URL https://doi.org/10.1007/S11083-021-09550-X

Mathematics Subject Classification ID

Extremal set theory (05D05)

arXiv classification

cs.DMmath.CO

Abstract: Building on classical theorems of Sperner and Kruskal-Katona, we investigate antichains $mathcalF$ in the Boolean lattice $B_n$ of all subsets of $[n]:=1,2,dots,n$, where $mathcalF$ is flat, meaning that it contains sets of at most two consecutive sizes, say $mathcalF=mathcalAcupmathcalB$, where $mathcalA$ contains only $k$-subsets, while $mathcalB$ contains only $(k-1)$-subsets. Moreover, we assume $mathcalA$ consists of the first $m$ $k$-subsets in squashed (colexicographic) order, while $mathcalB$ consists of all $(k-1)$-subsets not contained in the subsets in $mathcalA$. Given reals $$, we say the weight of $mathcalF$ is $$. We characterize the minimum weight antichains $mathcalF$ for any given $$, and we do the same when in addition $mathcalF$ is a maximal antichain. We can then derive asymptotic results on both the minimum size and the minimum Lubell function.

This page was built for publication: Minimum Weight Flat Antichains of Subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6285036)