Mar 8, 3:30pm, Wean 8220

Igor Balla, CMU

Extremal Results for Union-Closed Families

Igor Balla, CMU

Extremal Results for Union-Closed Families

Abstract:

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.