Loading Events

« All Events

  • This event has passed.

Tuan Tran, Minimum saturated families of sets

January 26 Tuesday @ 4:30 AM - 5:30 PM KST

Room B232, IBS (기초과학연구원)


Tuan Tran
IBS Discrete Mathematics Group

A family $\mathcal 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 $\mathcal 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^n$. It is a simple exercise 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 + \varepsilon)2^n$, for some fixed $\varepsilon > 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^n$. In this talk,  I will present two short proofs. This is joint work with M. Bucic, S. Letzter and B. Sudakov.


January 26 Tuesday
4:30 AM - 5:30 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.