## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, October 08, 2019, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: István Tomon

## Partitioning the Boolean lattice into chains of uniform size

The Boolean lattice 2^[n] is the family of subsets of [n]={1,...,n} ordered by inclusion, and a chain in 2^[n] is a family {A_1,...,A_k} such that A_j contains A_i for i < j. By the well known theorem of Sperner (1928), the minimum number of chains 2^[n] can be partitioned into is equal to the number of subsets of [n] of size n/2. However, not much is known about the chain partitions achieving this minimum. Addressing a conjecture of Furedi (1985), we prove that there exists such a chain partition where the sizes of any two chains are within a constant factor, in particular, each chain has size roughly n^1/2. I will talk about how such uniform chain partitions can be used to solve certain extremal and partitioning problems in the Boolean lattice.

Information for students and suggested topics for student talks