The width of downsets
Autor: | David M. Howard, Dwight Duffus, Imre Leader |
---|---|
Rok vydání: | 2019 |
Předmět: | |
Zdroj: | European Journal of Combinatorics. 79:46-59 |
ISSN: | 0195-6698 |
Popis: | 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. 18 pages, 3 figures |
Databáze: | OpenAIRE |
Externí odkaz: |