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

Anders Claesson, ágúst 29, 2017

Málstofa í stærðfræði

Titill: Extremal problems for finite sets related to antichains

Staðsetning: Tg-227 (Tæknigarður, 2. hæð)
Tími: Föstudagur 1. september kl. 13:30

Ágrip:

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.