Union-closed sets conjecture
Encyclopedia
In combinatorial mathematics, the union-closed sets conjecture is an elementary problem, posed by Péter Frankl
in 1979 and still open. A family of sets
is said to be union-closed if the union of any two sets from the family remains in the family. The conjecture states that for any finite union-closed family of finite sets, other than the family consisting only of the empty set
, there exists an element that belongs to at least 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 (Abe 2000; Poonen 1992; Reinhold 2000) but remains open in the general case.
stated the conjecture, in terms of intersection-closed set families, in 1979, and so the conjecture is usually credited to him and sometimes called the Frankl conjecture. The earliest publication of the union-closed version of the conjecture appears to be by Duffus (1985).
Péter Frankl
----Péter Frankl is a Hungarian mathematician and street performer. Frankl studied Mathematics in University Paris Diderot and has lived in Japan since 1988, where he sometimes appears on NHK. Though not as popular as he once was, he still performs juggling in public spaces around Tokyo...
in 1979 and still open. A family of sets
Family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets...
is said to be union-closed if the union of any two sets from the family remains in the family. The conjecture states that for any finite union-closed family of finite sets, other than the family consisting only of the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, there exists an element that belongs to at least half of the sets in the family.
Equivalent forms
If F is a union-closed family of sets, the family of complement sets to sets in F is closed under intersection, and an element that belongs to at least half of the sets of F 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
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
is a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
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
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
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 (Abe 2000; Poonen 1992; Reinhold 2000) but remains open in the general case.
Families known to satisfy the conjecture
The conjecture has been proven for many special cases of union-closed set families. In particular, it is known to be true for- families of at most 36 sets,
- families of sets such that their union has at most 11 elements, and
- families of sets in which the smallest set has one or two elements.
History
Péter FranklPéter Frankl
----Péter Frankl is a Hungarian mathematician and street performer. Frankl studied Mathematics in University Paris Diderot and has lived in Japan since 1988, where he sometimes appears on NHK. Though not as popular as he once was, he still performs juggling in public spaces around Tokyo...
stated the conjecture, in terms of intersection-closed set families, in 1979, and so the conjecture is usually credited to him and sometimes called the Frankl conjecture. The earliest publication of the union-closed version of the conjecture appears to be by Duffus (1985).
External links
- Frankl's union-closed sets conjecture, the Open Problem Garden.
- Union-Closed Sets Conjecture (1979). In Open Problems - Graph Theory and Combinatorics, collected by D. B. West.