Minimum saturated families of sets

Add to your list(s) Download to your calendar using vCal

• Matija Bucic (ETH Zurich)
• Thursday 03 May 2018, 16:00-17:00
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

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))2ⁿ. It is easy to show that every s-saturated family has size at least 2^n-1, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2 + ε)2ⁿ, 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)2ⁿ. This is joint work with S. Letzter, B. Sudakov and T. Tran.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.