Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Subsets of posets minimising the number of chains


Author: Wojciech Samotij
Journal: Trans. Amer. Math. Soc. 371 (2019), 7259-7274
MSC (2010): Primary 05D99, 06A07; Secondary 05D40
DOI: https://doi.org/10.1090/tran/7601
Published electronically: October 18, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A well-known theorem of Sperner describes the largest collections of subsets of an $ n$-element set, none of which contain another set from the collection. Generalising this result, Erdős characterised the largest families of subsets of an $ n$-element set that do not contain a chain of sets $ A_1 \subset \cdots \subset A_k$ of an arbitrary length $ k$. The extremal families contain all subsets whose cardinalities belong to an interval of length $ k-1$ centred at $ n/2$. In a far-reaching extension of Sperner's theorem, Kleitman determined the smallest number of chains of length $ 2$ that have to appear in a collection of a given number $ a$ of subsets of an $ n$-element set. For every $ a$, this minimum is achieved by the collection comprising $ a$ sets whose cardinalities are as close to $ n/2+1/4$ as possible. We show that the same is true about chains of an arbitrary length $ k$, for all $ a$ and $ n$, confirming the prediction Kleitman made $ 50$ years ago. We also characterise all families of $ a$ subsets with the smallest number of chains of length $ k$ for all $ a$ for which this smallest number is positive. Our argument is inspired by an elegant probabilistic lemma from a recent paper of Noel, Scott, and Sudakov, which in turn can be traced back to Lubell's proof of Sperner's theorem.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05D99, 06A07, 05D40

Retrieve articles in all journals with MSC (2010): 05D99, 06A07, 05D40


Additional Information

Wojciech Samotij
Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801, Israel
Email: samotij@post.tau.ac.il

DOI: https://doi.org/10.1090/tran/7601
Received by editor(s): November 27, 2017
Received by editor(s) in revised form: March 3, 2018
Published electronically: October 18, 2018
Additional Notes: Research was supported in part by Israel Science Foundation grant 1147/14.
Article copyright: © Copyright 2018 American Mathematical Society