**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 *2 ^{n}*, 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
*F _{0},F_{x},F_{y},F_{xy}*
by whether the members contain

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 *Q ^{P}* denote the set of order-preserving maps from

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.

**References:**

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