Subsets of posets minimising the number of chains
Open Access
- 1 October 2018
- journal article
- research article
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 371 (10) , 7259-7274
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.
Keywords
All Related Versions
Funding Information
- Israel Science Foundation (1147/14)