Union-closed sets conjecture

representing a family of union-closed sets.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

representing a family of union-closed sets. Vertices 1 and 2 (highlighted red and blue respectively) are present in over half the edges. The union-closed sets conjecture, also known as Frankl’s conjecture, is an open problem in combinatorics posed by Péter Frankl in 1979.

A family of sets is said to be union-closed if the union of any two sets from the family belongs to the family. The conjecture states: For every finite union-closed family of sets, other than the empty family, there exists an element that belongs to at least half of the sets in the family.

Professor Timothy Gowers has called this "one of the best known open problems in combinatorics" and has said that the conjecture "feels as though it ought to be easy (and as a result has attracted a lot of false proofs over the years). A good way to understand why it isn't easy is to spend an afternoon trying to prove it. That clever averaging argument you had in mind doesn't work ..."

representing a family of union-closed sets. Vertices 1 and 2 (highlighted red and blue respectively) are present in over half the edges.]] The union-closed sets conjecture, also known as Frankl’s conjecture, is an open problem in combinatorics posed by Péter Frankl in 1979.

A family of sets is said to be union-closed if the union of any two sets from the family belongs to the family. The conjecture states: For every finite union-closed family of sets, other than the empty family, there exists an element that belongs to at least half of the sets in the family.

Professor Timothy Gowers has called this "one of the best known open problems in combinatorics" and has said that the conjecture "feels as though it ought to be easy (and as a result has attracted a lot of false proofs over the years). A good way to understand why it isn't easy is to spend an afternoon trying to prove it. That clever averaging argument you had in mind doesn't work ..."

We define the complement of the set system X as X^c := \{U(X) - S : S \in X\} . Let X_1 , X_2 be arbitrary sets in X and so U(X) - X_1 and U(X) - X_2 are both in X^c . Since X is union-closed, X_1 \cup X_2 = X_3 is in X , and therefore the complement of X_3 , U(X) - X_3 is in X^c , the elements in neither X_1 , nor X_2 .

And this is exactly the intersection of the complements of X_1 and X_2 , (U(X)-X_1) \cap (U(X)-X_2) . Therefore, X is union-closed if and only if the complement of X , X^c is intersection closed. Secondly, we show that if a set system contains an element in at least half the sets, then its complement has an element in at most half.

Lemma 2. A set system X contains an element in half of its sets if and only if the complement set system X , X^* contains an element in at most half of its sets. Proof.

Trivial. Therefore, if X is a union-closed family of sets, the family of complement sets to sets in X relative to the universe U(X) is closed under intersection, and an element that belongs to at least half of the sets of X 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. T_x = \{ j \in J(L) : j \le x \}.

The map x \mapsto T_x is injective, because in a finite lattice every element is the join of the join-irreducible elements below it. Thus, if T_x = T_y , then x and y have the same join-irreducible elements below them, and therefore x=y . It follows that the family \mathcal{F}=\{T_x : x\in L\} has cardinality |L| . Moreover, \mathcal{F} is intersection-closed.

Indeed, for any x,y\in L , j\le x\wedge y if and only if j\le x and j\le y , so T_{x\wedge y}=T_x\cap T_y. Assume now that every finite intersection-closed family has an element contained in at most half of its sets. Applying this statement to \mathcal{F} , there exists some j\in J(L) such that j belongs to at most half of the sets T_x . But j\in T_x holds exactly when j\le x . Therefore the number of members of \mathcal{F} containing j is exactly the number of elements of L lying above j, namely |\uparrow j| , where \uparrow j = \{x\in L : j\le x\}.

Hence |\uparrow j|\le \frac {2}. This proves the lattice-theoretic statement. For the converse, let \mathcal{A} be a finite intersection-closed family of sets.

Ordered by inclusion, \mathcal{A} is a finite lattice in which the meet is set intersection and the join of two elements is the least member of \mathcal{A} containing their union. Assume that every finite lattice contains a join-irreducible element j such that |\uparrow j|\le \frac {2}.

Applying this to the lattice L=\mathcal{A} , choose such a join-irreducible element j. Because j is join-irreducible in a finite lattice, it has a unique lower cover, denoted j_* . Choose an element a \in j\setminus j_*.

Such an element exists because j_* \subsetneq j . It is then claimed that every member of \mathcal{A} containing a lies above j. Let A\in\mathcal{A} and suppose a\in A . If j\nsubseteq A , then j\wedge A = j\cap A is a proper subset of j, and hence j\wedge A \le j_*. But a\in j and a\in A , so a\in j\cap A = j\wedge A , which would imply a\in j_* , contrary to the choice of a. Therefore j\subseteq A , that is, j\le A in the lattice order.

So every set in \mathcal{A} containing a belongs to \uparrow j . Conversely, if A\in\uparrow j , then j\subseteq A , and since a\in j , the set A contains a. Thus the sets in \mathcal{A} containing a are exactly the elements of \uparrow j . It follows that the number of members of \mathcal{A} containing a is |\uparrow j| \le \frac {2}. Therefore a belongs to at most half of the sets in \mathcal{A} .

This proves the intersection-closed formulation.

Frankl's union-closed sets conjecture, the Open Problem Garden. Union-Closed Sets Conjecture (1979). In Open Problems – Graph Theory and Combinatorics, collected by D. B. West.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1350313043 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.