The width of downsets
2019
Abstract How large an antichain can we find inside a given downset in the Boolean lattice B ( n ) ? Sperner’s theorem asserts that the largest antichain in the whole of B ( n ) has size n ⌊ n ∕ 2 ⌋ ; what happens for general downsets? Our main results are a Dilworth-type decomposition theorem for downsets, and a new proof of a result of Engel and Leck that determines the largest possible antichain size over all downsets of a given size. We also prove some related results, such as determining the maximum size of an antichain inside the downset that we conjecture minimizes this quantity among downsets of a given size.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
0
Citations
NaN
KQI