Nov 15, 3:30pm, Wean 8220

Choongbum Lee, MIT

Maximum union-free subfamilies

Choongbum Lee, MIT

Maximum union-free subfamilies

Abstract:

A family of sets is called union-free if there are no three distinct
sets in the family such that the union of two of the sets is equal to
the third set. An old problem of Moser asks: how large of a union-free
subfamily does every family of M sets have? In this talk I will prove
that every family of M sets contains a union-free subfamily of size at
least [\sqrt{4M+1}] - 1 and that this bound is tight for all M. This
solves Moser's problem and proves a conjecture of Erdos and Shelah from
1972. I will also discuss some related results and open problems.

Joint work with Jacob Fox and Benny Sudakov.