The union-closed sets conjecture, also known as Frankl’s conjecture, is an open problem in combinatorics posed by Péter Frankl in 1979.
The conjecture states: For every finite union-closed family of sets, other than the family containing only the empty set, there exists an element that belongs to at least half of the sets in the family.Professor Timothy Gowers has called this "one of the best known open problems in combinatorics" and has said that the conjecture "feels as though it ought to be easy (and as a result has attracted a lot of false proofs over the years).
A good way to understand why it isn't easy is to spend an afternoon trying to prove it.
That clever averaging argument you had in mind doesn't work ..."[1] The family of sets consists of five different sets and is union-closed.
It is easy to show that if a union-closed family contains a singleton
Therefore, without loss of generality, we will assume that all sets in the given union-closed family are finite.
Therefore, in general we cannot ask for an element contained in more than half of the sets of the family: the bound of the conjecture is sharp.
is the universe set, i.e. the union of all members of the system
Firstly, we show that a set system is union-closed if and only if its complement is intersection-closed.
Secondly, we show that if a set system contains an element in at least half the sets, then its complement has an element in at most half.
contains an element in at most half of its sets.
is closed under intersection, and an element that belongs to at least half of the sets of
belongs to at most half of the complement sets.
Thus, an equivalent form of the conjecture (the form in which it was originally stated) is that, for any intersection-closed family of sets that contains more than one set, there exists an element that belongs to at most half of the sets in the family.
Although stated above in terms of families of sets, Frankl's conjecture has also been formulated and studied as a question in lattice theory.
A lattice is a partially ordered set in which for two elements x and y there is a unique greatest element less than or equal to both of them (the meet of x and y) and a unique least element greater than or equal to both of them (the join of x and y).
The family of all subsets of a set S, ordered by set inclusion, forms a lattice in which the meet is represented by the set-theoretic intersection and the join is represented by the set-theoretic union; a lattice formed in this way is called a Boolean lattice.
The lattice-theoretic version of Frankl's conjecture is that in any finite lattice there exists an element x that is not the join of any two smaller elements, and such that the number of elements greater than or equal to x totals at most half the lattice, with equality only if the lattice is a Boolean lattice.
As Abe (2000) shows, this statement about lattices is equivalent to the Frankl conjecture for union-closed sets: each lattice can be translated into a union-closed set family, and each union-closed set family can be translated into a lattice, such that the truth of the Frankl conjecture for the translated object implies the truth of the conjecture for the original object.
This lattice-theoretic version of the conjecture is known to be true for several natural subclasses of lattices[3] but remains open in the general case.
Another equivalent formulation of the union-closed sets conjecture uses graph theory.
In any graph, the "heavy" vertices that appear in more than half of the maximal independent sets must themselves form an independent set.
So, if the graph is non-empty, there always exists at least one non-heavy vertex, a vertex that appears in at most half of the maximal independent sets.
The graph formulation of the union-closed sets conjecture states that every finite non-empty graph contains two adjacent non-heavy vertices.
It is automatically true when the graph contains an odd cycle, because the independent set of all heavy vertices cannot cover all the edges of the cycle.
Therefore, the more interesting case of the conjecture is for bipartite graphs, which have no odd cycles.
Another equivalent formulation of the conjecture is that, in every bipartite graph, there exist two vertices, one on each side of the bipartition, such that each of these two vertices belongs to at most half of the graph's maximal independent sets.
[4] The conjecture has been proven for many special cases of union-closed set families.
The earliest publication of the union-closed version of the conjecture appears to be by Duffus (1985).
A history of the work on the conjecture up to 2013 was published by Bruhn & Schaudt (2015).