Uwe Leck and Ian Roberts (01/09/17)

Anders Claesson, August 29, 2017

Math Colloquium

Speaker: Uwe Leck and Ian Roberts, University of Flensburg and Darwin

Title: Extremal problems for finite sets related to antichains

Location: Tg-227 (Tæknigarður, 2. hæð)
Time: Friday 1 September at 13:30


This talk requires little more than mathematical maturity as it relates to problems concerning finite sets. The basic ideas are simple, and the problems are easy to state, but the problems range from simple to very hard.
An antichain (or Sperner family) in the Boolean lattice \(B_n\) is a collection \(A\) of subsets of \([n] = \{1,2,…,n\}\) such that no set in \(A\) is a subset of another. By Sperners famous theorem, the largest possible cardinality of an antichain in \(B_n\) is \({n \choose\lfloor n/2\rfloor}\). Antichains are fundamental in extremal set theory; but also with applications in other areas such as Search Theory.
We will discuss several extremal problems and results involving antichains such as: minimizing the union-closure of uniform antichains of a given size; finding the number of different antichains in \(B_n\); determining the possible cardinalities of maximal antichains; and others.
Some of the problems are solved and some provide tantalising unsolved problems.