New Conjectures for Union-Closed Families

Combinatorics Seminar
Tuesday, April 19, 2016 - 14:05
1 hour (actually 50 minutes)
Skiles 006
University of Washington, Seattle, WA
The Frankl union-closed sets conjecture states that there exists an element present in at least half of the sets forming a union-closed family. We reformulate the conjecture as an optimization problem and present an integer program to model it. The computations done with this program lead to a new conjecture: we claim that the maximum number of sets in a non-empty union-closed family in which each element is present at most a times is independent of the number n of elements spanned by the sets if n is greater or equal to log_2(a)+1. We prove that this is true when n is greater or equal to a. We also discuss the impact that this new conjecture would have on the Frankl conjecture if it turns out to be true. This is joint work with Jonad Pulaj and Dirk Theis.