Union-Closed Sets Conjecture (1979)

Originator(s): Peter Frankl

Definitions: A family of sets is union-closed if the union of every two members of the family also belongs to the family. A family is non-trivial if it includes a member other than the empty set.

Conjecture/Question: If F is a finite non-trivial union-closed family of finite sets, then some element appears in at least half the members of F.

Background/motivation: The conjecture is stated in [Du], but there must be earlier appearances; Frankl states the dual version for intersections in [Fr] with the date of 1979. There are several equivalent phrasings. The lattice version is intermediate in the transformation between the original conjecture and the generator version.
Generator version: If F is a non-trivial union-closed family containing the empty set, then some generator of F is contained in at most half the members of F. (Here the generators of F are the members of F not expressible as unions of other members.
Lattice version: Every nontrivial finite lattice L has a join-irreducible element that is at or below at most half the elements of L.

Comments/Partial results: Let n be the total number of elements appearing in members of the family F, and let m=|F|. The conjecture is trivial for families with singletons and families where the average size of the members is at least n/2. It has gradually been proved for larger and larger families, for m up to 11 in [SR1], up to 18 in [SR2], up to 24 in [L1], up to 27 in [P], up to 32 in [GY], and up to 40 in [Ro]. Poonen [P] proved it when the largest set in F has size at most 7. Gao and Yu [GY] proved it when m is close to 2n, using counting methods and results from extremal set theory.

Many researchers have rediscovered the early result of Sarvate and Renaud [SR1] that the conjecture holds for families containing doubletons (also when the largest member is at most twice as big as the smallest). If F has a 2-set {x,y}, then partition F into four subfamilies F0,Fx,Fy,Fxy by whether the members contain x and/or y. Note that |Fxy| >= |F0|. Now x or y appears in at least half of F, depending on which of Fx and Fy is bigger. This method does not extend when the smallest set has three elements, since Sarvate and Renaud [SR2] provided such an example where none of those three elements appears in at least half of F (also found independently by R. Graham). Nevertheless, Poonen [P] gives other conditions where a subfamily is guaranteed to have element in at least half of F.

Knill [K2] proved the conjecture for union-closed families such that every element appears in at most two generators. He proved this by proving the generator version for families generated by 2-element sets. For such a family F, the generators are the edges of a graph, and the sets in F are the vertex subsets inducing subgraphs without isolated vertices.

Dohmen [Do] studied potential counterexamples to Frankl's conjecture using the inclusion-exclusion principle. Duffus and Sands [DS] formulated an inequality that, if true for all finite lattices, would imply the conjecture. Johnson and Vaughan [JV] proved the conjecture for various families. El-Zahar [E] proved a special case of an equivalent conjecture for hypergraphs. Renaud and Fitina [RF] related the problem to a sequence defined recursively by Conway. Other related results appear in [Re], [V], and [W].

One approach is to study properties of a smallest counterexample (minimizing m). Lo Faro [L2] proved that a minimal counterexample has a member of size at least 9, and Roberts [Ro] proved that it has no member of size more than (m+1)/4. Norton and Sarvate [NS] proved that for a minimal counterexample there are at least three elements that appear in exactly (m-1)/2 members of F.

Knill suggested a more general lattice problem. Given posets P,Q, let QP denote the set of order-preserving maps from P to Q, The P-density of x in L is the fraction |UP| / |LP|, where U is the set of elements less than or equal to x in L. A lattice L has the P-density property if it has a join-irreducible element whose P-density is at most 1/p, where p is the number of antichains (or dual ideals). Given a poset P, Knill asked which lattices have the P-density property. When P is the poset consisting of one element (it has two antichains), this reduces to the lattice version of Frankl's conjecture. Knill studied the P-density property in his thesis [K1], proving the following statement and others: for every modular lattice L and every poset P, the lattice L has the P-density property.

It should be noted that we have mentioned only results through 2002. A much more recent survey on the conjecture was given by Bruhn and Schaudt [BS] in 2013, mentioning more than 50 papers and several websites devoted to it, about 20 of which are more recent than those mentioned here.

[BS] Bruhn, H.; Schaudt, O The journey of the union-closed sets conjecture. http://arxiv.org/abs/1309.3297 .
[Do] Dohmen, K. A new perspective on the union-closed sets conjecture. Ars Combin. 58 (2001), 183--185.
[Du] Duffus, D. [open problem] in Graphs and Order, I.~Rival, ed. (D. Reidel, 1985), page 525.
[DS] Duffus, D.; Sands, B. An inequality for the sizes of prime filters of finite distributive lattices. Discrete Math. 201 (1999), 89--99.
[E] El-Zahar, M. H. A graph-theoretic version of the union-closed sets conjecture. J. Graph Theory 26 (1997), no. 3, 155--163.
[Fr] Frankl, P. in Extremal Set Systems, Chapter 24 of the Handbook of Combinatorics (MIT Press & North-Holland, 1995), page 1296.
[GY] Gao, W.; Yu, H. Note on the union-closed sets conjecture. Ars Combin. 49 (1998), 280--288.
[JV] Johnson, R. T.; Vaughan, T. P. On union-closed families, I. J. Combin. Theory Ser. A 84 (1998), 242--249, and J. Combin. Theory Ser. A 85 (1999), 112--119.
[K1] Knill, E. Generalized degrees and densities for families of sets. Ph.D. thesis (U. Colorado - Boulder [1991]).
[K2] Knill, E. Graph-generated union-closed families of sets, preprint.
[L1] Lo Faro, G. A note on the union-closed sets conjecture. J. Austral. Math. Soc. Ser. A 57 (1994), 230--236.
[L2] Lo Faro, G. Union-closed sets conjecture: improved bounds. J. Combin. Math. Combin. Comput. 16 (1994), 97--102.
[NS] Norton, R. M.; Sarvate, D. G. A note of the union-closed sets conjecture. J. Austral. Math. Soc. Ser. A 55 (1993), 411--413.
[P] Poonen, B. Union-closed families. J. Combin. Theory Ser. A 59 (1992), 253--268.
[Re] Renaud, J.-C. Is the union-closed sets conjecture the best possible? J. Austral. Math. Soc. Ser. A 51 (1991), 276--283.
[RF] Renaud, J.-C.; Fitina, L. F. On union-closed sets and Conway's sequence. Bull. Austral. Math. Soc. 47 (1993), 321--332.
[Ro] Roberts, I. Tech. Rep. No. 2/92, School Math. Stat., Curtin Univ. Tech., Perth, 1992.
[SR1] Sarvate, D. G.; Renaud, J.-C. On the union-closed sets conjecture. Ars Combin. 27 (1989), 149--153.
[SR2] Sarvate, D. G.; Renaud, J.-C. Improved bounds for the union-closed sets conjecture. Ars Combin. 29 (1990), 181--185.
[V] Vaughan, T. P. Families implying the Frankl conjecture. European J. Combin. 23 (2002), 851--860.
[W] Wójcik, P. Density of union-closed families. Discrete Math. 105 (1992), 259--267.

Index Page Glossary