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 (기초과학연구원)

Speaker

Tuan Tran
IBS Discrete Mathematics Group
https://tuaentran.wixsite.com/homepage

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.

Details

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

Venue

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

Organizer

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.