Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 27, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Matija Bucic
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.
Automatic MiSe System Software Version 1.4803M | admin login