Union-closed sets conjecture

From Wikipedia, the free encyclopedia

In combinatorial mathematics, the union-closed sets conjecture is an elementary problem, still open as of 2006. It concerns a finite set X, and a set family F of subsets of X, such that F is union-closed in the sense that the union of Y and Z in F is also in F. The conjecture states that, apart from the case where F is empty, there must be some x in X that belongs to at least 50% of the sets of F.

An equivalent form of the conjecture is that for any family of subsets of X closed under intersection, there must exist some x in X that belongs to at most 50% of the sets of F. Péter Frankl stated the conjecture in this form, 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).

1 Families known to satisfy the conjecture
2 Lattice formulation
3 Notes
4 References
5 External links

[edit] 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^[1],
families of sets on at most 9 elements^[2], and
families of sets in which the smallest set has one or two elements^[3].

[edit] Lattice formulation

Although stated above in terms of families of sets, Frankl's conjecture has also been formulated and studied as a question in lattice theory. In this formulation, the 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 algebra. 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.

[edit] Notes

^ 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.
^ Morris (2006), improving previous bounds by Lo Faro (1994) and others.
^ 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.

[edit] References

Abe, Tetsuya (2000). "Strong semimodular lattices and Frankl's conjecture". Algebra Universalis 44 (3–4): 379–382. DOI:10.1007/s000120050195.

Duffus, D. (1985). Rival, I. (Ed.) "Open problem session". Graphs and Order, 525, D. Reidel.

Lo Faro, Giovanni (1994). "Union-closed sets conjecture: improved bounds". J. Combin. Math. Combin. Comput. 16: 97–102. MR 1301213.

Morris, Robert (2006). "FC-families and improved bounds for Frankl's conjecture". European Journal of Combinatorics 27 (2): 269–282. DOI:10.1016/j.ejc.2004.07.012. MR 2199779.

Poonen, Bjorn (1992). "Union-closed families". Journal of Combinatorial Theory, Series A 59 (2): 253–268. DOI:10.1016/0097-3165(92)90068-6. MR 1149898.