Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Tuesday, March 27, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Wojciech Samotij (Tel Aviv University)
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 that do not contain a chain of sets of an arbitrary length k. The extremal families contain all subsets whose cardinalities belong to an interval of length k–1 centred around 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. Kleitman conjectured that the same is true about chains of an arbitrary length k, for all a and n. We will sketch a proof of this conjecture.
Automatic MiSe System Software Version 1.4803M | admin login