Union-Closed Sets Conjecture

Let A={A_1,A_2,...,A_n} be a union-closed set, then the union-closed set conjecture states that an element exists which belongs to at least n/2 of the sets in A. Sarvate and Renaud (1989) showed that the conjecture is true if |A_1|<=2, where A_1 is the smallest set in A, or if n<11. They also showed that if the conjecture fails, then |A_1|<|A_n|/2, where A_n is the largest set of A.

These results have since been improved for n up to 18 (Sarvate and Renaud 1990), 24 (Lo Faro 1994a), 27 (Poonen 1992), 32 in (Gao and Yu 1998), and the best known result of 40 (Roberts 1992).

The proof for the case where A has a 2-set can be effected as follows. Write A_1={x,y}, then partition the sets of A into four disjoint families B_0, B_x, B_y, and B_(xy), according to whether their intersection with A_1 is emptyset, {x}, {y}, or {x,y}, respectively. It follows that |B_(xy)|>=|B_0| by taking unions with A_1, where |B| is the cardinal number of B. Now compare |B_x| with |B_y|. If |B_x|>=|B_y|, then |B_x|+|B_xy|>=|B_0|+|B_y|, so x is in at least half the sets of A. Similarly, if |B_x|<=|B_y|, then y is in at least half the sets (Hoey, pers. comm.).

Unfortunately, this method of proof does not extend to |A_1|=3, since Sarvate and Renaud show an example of a union-closed set with A_1={x,y,z} where none of x, y, z is in half the sets. However, in these cases, there are other elements which do appear in half the sets, so this is not a counterexample to the conjecture, but only a limitation to the method of proof given above (Hoey, pers. comm.).

See also

Union-Closed Set

Explore with Wolfram|Alpha


Gao, W. and Yu, H. "Note on the Union-Closed Sets Conjecture." Ars Combin. 49, 280-288, 1998.Lo Faro, G. "A Note on the Union-Closed Sets Conjecture." J. Austral. Math. Soc. Ser. A 57, 230-236, 1994a.Lo Faro, G. "Union-Closed Sets Conjecture: Improved Bounds." J. Combin. Math. Combin. Comput. 16, 97-102, 1994b.Poonen, B. "Union-Closed Families." J. Combin. Theory Ser. A 59, 253-268, 1992.Roberts, I. Tech. Rep. No. 2/92. School Math. Stat., Curtin Univ. Tech., Perth, 1992.Sarvate, D. G. and Renaud, J.-C. "On the Union-Closed Sets Conjecture." Ars Combin. 27, 149-153, 1989.Sarvate, D. G. and Renaud, J.-C. "Improved Bounds for the Union-Closed Sets Conjecture." Ars Combin. 29, 181-185, 1990.West, D. "Union-Closed Sets Conjecture (1979)."

Referenced on Wolfram|Alpha

Union-Closed Sets Conjecture

Cite this as:

Weisstein, Eric W. "Union-Closed Sets Conjecture." From MathWorld--A Wolfram Web Resource.

Subject classifications