University of Cambridge > Talks.cam > Combinatorics Seminar > Minimum saturated families of sets

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Minimum saturated families of sets

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

MRL meeting rooms 1 & 2, Level 4 Institute of Metabolic Sciences, Addenbrooke’s Treatment Centre (ATC) THE OLD COMBINATION ROOM TRINITY COLLEGE, CAMBRIDGE, CB2 1TQ Newnham College Speaker Series

Other talks

Polar Oceans Seminar Talk Talk TBC Online Causal Inference Seminar Organiser Welcome Title to be confirmed Ensemble inequivalence for systems with long-range interactions
 

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