University of Cambridge > > Combinatorics Seminar > Minimum saturated families of sets

Minimum saturated families of sets

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

  • UserMatija Bucic (ETH Zurich)
  • ClockThursday 03 May 2018, 16:00-17:00
  • HouseMR12.

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))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 + ε)2n, 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. This is joint work with S. Letzter, B. Sudakov and T. Tran.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity