## 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, February 27, 2018, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Matija Bucic

## Minimum saturated families of sets

A family F of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to F while preserving this property. More than 40 years ago, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least (1 - 2-(s-1))2n. It is easy to show that every s-saturated family has size at least 2n-1, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2 + ε)2 n, for some fixed ε > 0, seems difficult. We prove such a result, showing that every s-saturated family of subsets of [n] has size at least (1 - 1/s)2n. We have two different proofs of this result. The first makes use of the concept of disjoint occurrence and is based on a correlation inequality, which strengthens the famous van den Berg, Kesten, Reimer inequality and was first observed by Talagrand. The second one is a direct, algebraic approach. I will present the second proof as we believe it has more potential to be useful, for further improvements.

Information for students and suggested topics for student talks