The width of downsets

Autor:	David M. Howard, Dwight Duffus, Imre Leader
Rok vydání:	2019
Předmět:	Mathematics::Combinatorics Conjecture Mathematics::General Topology 05A9 Antichain Combinatorics Mathematics::Logic FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Maximum size Combinatorics (math.CO) Decomposition theorem Mathematics
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:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4249f47ff4251ff14bdfa81e50cb8876 https://doi.org/10.1016/j.ejc.2018.11.005 Zobrazit plný text záznamu Full Text from ScienceDirect