Rutgers Discrete Mathematics Seminar

Title: Extremal Results for Union-Closed Families

Speaker: Igor Balla, NYU

Date: Tuesday, September 25, 2012 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


A family of sets is union-closed if it contains the union of any two of its elements. Reimer and Cz edli investigated the average size of an element of a union-closed family consisting of m subsets of [n] = {1,2,...,n}. We determine the minimum average size precisely, verifying a conjecture of Cz edli, Mar oti and Schmidt. As a consequence, the union-closed sets conjecture holds if m >= (2/3)2^n - in this case some element of [n] is in at least half the sets of the family.