The ACO Seminar (2012-2013)

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.