Article View

UNION-CLOSED FAMILIES OF SETS AND THE FRANKL CONJECTURE

JOHN L. PFALTZ Department of Computer Science, University of Virginia, United States

Abstract

The “union-closed” conjecture, sometimes attributed to Peter Frankl, dates from 1979. It asserts that in any finite, union-closed family, F, of sets, there is some element x that is a member of at least half the sets in F. It seems simple, but to date no one has been able to either prove or disprove it. In this article we prove it to be true. In the course of this proof we show that even seemingly randomly generated union-closed families of sets have a rich auxiliary structure, and that this structure is determined by the largest sets in F, rather than the smallest sets, often called "atoms". We will show that all union closed families fall into two distinct classes, and that two different proof techniques are needed to prove that the conjecture is indeed true.

Keywords

Set System, Interval, Internal Structure, Co-atom, Bifurcated Structure,