Combinatorics: Wojciech Samotij (TAU) "Subsets of posets minimising the number of chains"

Speaker: Wojciech Samotij, TAU 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\H{o}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 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 fifty years ago.

Date: 

Mon, 17/12/2018 - 11:00 to 13:00

Location: 

Rothberg CS bldg, room B500, Safra campus, Givat Ram