A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture

A finite set system is union-closed if for every pair of sets in the system their union is also in the system.  Frankl in 1979 conjectured that for any such system there exists an element which is contained in ½ of the sets in that system (the only exception being the family containing just the empty set).  In this talk, I will discuss how a simple insight regarding the contrapositive of Frankl's conjecture eventually led to the discovery of an information theoretic approach on the problem and a proof of the first constant lower bound.

Date

Speakers

Justin Gilmer

Affiliation

Google Brain