Combinatorics Seminar

When: Sunday, October 14, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, Tel Aviv University
Title: Subsets of posets minimising the number of chains

Abstract:

A well-known theorem of Sperner describes the largest collections of subsets of an $n$-element set none of which contains 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 \dotsc \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 two that have to appear in a collection of a given number $a$ of subsets. 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 fifty years ago.