Combinatorics Seminar

When: Sunday, December 23, 10am Where: Schreiber 309 Speaker: Benny Sudakov, University of California at Los Angeles Title: 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 in a strong form a conjecture of Erdos and Shelah from 1972. I will also discuss some related results and open problems.

Joint work with Jacob Fox and Choongbum Lee.