Union-closed sets conjecture

In combinatorial mathematics, the union-closed sets conjecture is an elementary problem, posed by Péter Frankl in 1979 and still open as of 2008. 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, 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.

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 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.

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 [Lo Faro (1994). Both West and Lo Faro cite an unpublished technical report (Roberts 1992) claiming a similar result for families of at most 40 sets.] ,
* families of sets on at most 11 elements [Bošnjak and Marković (2008), improving previous bounds by Morris (2006), Lo Faro (1994) and others.] , and
* families of sets in which the smallest set has one or two elements [Sarvate and Renaud (1989), since rediscovered by several other authors. If a one-element or two-element set "S" exists, some element of "S" belongs to at least half the sets in the family, but the same property does not hold for three-element sets, due to counterexamples of Sarvate, Renaud, and Ronald Graham.] .

History

Péter Frankl 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).

Notes

References

*cite journal
author = Abe, Tetsuya
title = Strong semimodular lattices and Frankl's conjecture
journal = Algebra Universalis
volume = 44
year = 2000
issue = 3–4
pages = 379–382
doi = 10.1007/s000120050195

*cite journal
author = Bošnjak, Ivica; Marković, Peter
title = The 11-element case of Frankl's conjecture
journal = Electronic Journal of Combinatorics
volume = 15 | issue = 1 | year = 2008 | pages = R88 | url = http://www.combinatorics.org/Volume_15/Abstracts/v15i1r88.html

*cite conference
author = Duffus, D.
title = Open problem session
booktitle = Graphs and Order
editor = Rival, I. (Ed.)
publisher = D. Reidel
date = 1985
pages = 525

*cite journal
author = Lo Faro, Giovanni
title = Union-closed sets conjecture: improved bounds
journal = J. Combin. Math. Combin. Comput.
volume = 16
year = 1994
pages = 97–102
id = MathSciNet | id = 1301213

*cite journal
author = Morris, Robert
title = FC-families and improved bounds for Frankl's conjecture
journal = European Journal of Combinatorics
volume = 27
year = 2006
issue = 2
pages = 269–282
id = MathSciNet | id = 2199779
doi = 10.1016/j.ejc.2004.07.012

*cite journal
author = Poonen, Bjorn
title = Union-closed families
journal = Journal of Combinatorial Theory, Series A
volume = 59
year = 1992
issue = 2
pages = 253–268
id = MathSciNet | id = 1149898
doi = 10.1016/0097-3165(92)90068-6

*cite journal
author = Reinhold, Jürgen
title = Frankl's conjecture is true for lower semimodular lattices
journal = Graphs Combin.
volume = 16
year = 2000
issue = 1
pages = 115–116
doi = 10.1007/s003730050008

*cite paper
author = Roberts, I.
title = Tech. Rep. No. 2/92
publisher = School Math. Stat., Curtin Univ. Tech., Perth
date = 1992

*cite journal
author = Sarvate, D. G.; Renaud, J.-C.
title = On the union-closed sets conjecture
journal = Ars Combin.
volume = 27
year = 1989
pages = 149–153
id = MathSciNet | id = 0989460

External links

* [http://www.math.uiuc.edu/~west/openp/unionclos.html Union-Closed Sets Conjecture (1979)] . In " [http://www.math.uiuc.edu/~west/openp/index.html Open Problems - Graph Theory and Combinatorics] , collected by D. B. West.

*