pith. machine review for the scientific record. sign in

arxiv: 1710.05714 · v2 · submitted 2017-10-16 · 🧮 math.CO

Recognition: unknown

The Width of Downsets

Authors on Pith no claims yet
classification 🧮 math.CO
keywords downsetssizeantichaingivendownsetinsidelargestlattice
0
0 comments X
read the original abstract

How large an antichain can we find inside a given downset in the lattice of subsets of [n]? Sperner's theorem asserts that the largest antichain in the whole lattice has size the binomial coefficient C(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.