Stefan Felsner -Technische Universität Berlin

Chain Partitions of Orders

Abstract: Dilworth's chain decomposition theorem from 1948 is a classical example of a min-max theorem in combinatorics. With this talk we show that until today this theorem remains a driving force in order theory.

We review the original motivation of that let Dilworth to his theorem and show some proofs. We proceed with algorithmic questions including a discussion of the on-line version. Among the extensions of Dilworth theorem the most notable is known as Greene-Kleitman theory. We present the main results of this theory and survey some variations and extensions.

Colloquium - 16:00

Christian Bey -Otto-von-Guericke-Universität Magdeburg

Polynomial LYM inequalities

Abstract: The LYM inequality from extremal set theory says that given a collection F of subsets of an n-element set such that no member of F contains another, then the proportions of i element sets that lie in the given collection added up for i from 0 to n is at most 1. We show that this inequality can be sharpened by adding further higher degree monomials in these proportions with prescribed positive coefficients such that the resulting sum still does not exceed 1.

Applications of this polynomial LYM inequality are given, as well as generalizations to other partially ordered sets.