ACO The ACO Seminar (2011-2012)

Mar 8, 3:30pm, Wean 8220
Igor Balla, CMU
Extremal Results for Union-Closed Families


A family of sets is union-closed if it contains the union of any two of its elements. Reimer and Czedli investigated the average size of an element of a union-closed family consisting of M subsets of a ground set with N elements. We determine the minimum average size precisely, verifying a conjecture of Czedli, Maroti 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.

Back to the ACO home page