The union-closed sets conjecture, proposed by mathematician Péter Frankl in 1979, asserts that in any finite, non-trivial family of sets closed under unions, there exists at least one element that belongs to at least half of the sets in the family.[1] A family \mathcal{F} of sets is union-closed if, for every pair of sets A, B \in \mathcal{F}, their union A \cup B is also contained in \mathcal{F}.[2] The family is non-trivial if it is not the singleton consisting solely of the empty set \{\emptyset\}.[3]This conjecture, also referred to as Frankl's conjecture, originated from informal discussions in the late 1970s and was first formally documented in print in 1984.[2] It gained widespread attention in the combinatorics community after being popularized by Ron Graham, highlighting its deceptive simplicity and challenging nature.[2] Equivalent formulations exist in terms of lattices or generated families, but the core statement remains unchanged.[1]Despite extensive study, the conjecture remains unsolved as of 2025, though significant partial progress has been made.[4] It has been verified computationally for all union-closed families with up to 50 members.[2] Structural results confirm it for specific cases, such as families arising from lower semimodular lattices, subcubic graphs, or when the largest set has size at most 7.[1] A major breakthrough came in 2022 when Justin Gilmer established the first constant lower bound, proving that some element appears in at least 1/100 of the sets in any such family.[5] Subsequent work has improved this to (3 - \sqrt{5})/2 \approx 0.38.[6] These advances employ techniques from information theory and extremal set theory, yet a full proof eludes researchers, underscoring the conjecture's depth in discrete mathematics.[7]
Fundamentals
Definition of Union-Closed Families
A union-closed family of sets is defined with respect to a finite ground set X, typically denoted as = \{1, 2, \dots, n\} for some positive integer n. The power set of X, denoted $2^X or \mathcal{P}(X), consists of all possible subsets of X, and a family F is a collection of subsets, i.e., F \subseteq 2^X. Such families are assumed to be finite unless otherwise specified.[8]A family F \subseteq 2^X is said to be union-closed if, for every pair of sets A, B \in F, their union A \cup B also belongs to F. This binaryclosure property implies closure under arbitrary finite unions: by induction, the union of any finite number of sets in F remains in F.[8]Standard notation for union-closed families includes |F| for the cardinality (size) of the family and, for each element x \in X, the frequency f(x) = |\{A \in F : x \in A\}|, which counts the number of sets in F containing x.[8]To illustrate, consider the family F = \{\{1\}, \{2\}\} over X = \{1, 2\}. This is not union-closed, since \{1\} \cup \{2\} = \{1, 2\} \notin F. In contrast, the full power set $2^X is always union-closed, as it contains all possible unions of its subsets.[9]
Statement of the Conjecture
The union-closed sets conjecture, first posed by Péter Frankl in 1979, asserts that for any finite non-trivial union-closed family \mathcal{F} \subseteq 2^X where X is a finite set, there exists an element x \in X such that the frequency f_{\mathcal{F}}(x) \geq |\mathcal{F}|/2, where f_{\mathcal{F}}(x) denotes the number of sets in \mathcal{F} containing x, and non-trivial means \mathcal{F} is not the singleton \{\emptyset\}. This frequency condition implies that the maximum over x \in X of f_{\mathcal{F}}(x)/|\mathcal{F}| is at least $1/2, meaning at least one element appears in at least half of the sets in the family.The conjecture holds trivially in certain cases, such as when |\mathcal{F}| = 1, where every element of the single set satisfies the bound since f_{\mathcal{F}}(x) = 1 \geq 1/2. Similarly, if there is a fixed element x \in X contained in every set of \mathcal{F}, then f_{\mathcal{F}}(x) = |\mathcal{F}| \geq |\mathcal{F}|/2.[10]Although no counterexamples have been found despite decades of scrutiny, the conjecture remains unproven in full generality, highlighting its non-trivial nature even for moderately sized families.
Examples and Properties
Illustrative Example
A simple illustrative example of a union-closed family is the collection F = \{\emptyset, \{1\}, \{1,2\}, \{1,2,3\}\} defined over the ground set X = \{1,2,3\}.[11] This family is union-closed because it forms a chain under inclusion, so the union of any two sets is the larger set in the chain, which belongs to F; for instance, \{1\} \cup \{1,2,3\} = \{1,2,3\} \in F.[11] The frequency f(x) of an element x \in X is the number of sets in F containing x: f(1) = 3, f(2) = 2, and f(3) = 1.[11] With |F| = 4, the maximum frequency ratio is $3/4 > 1/2, illustrating how the conjecture holds in this case.[2]Another basic example is the power set $2^X of any finite ground set X with |X| = n \geq 1, which consists of all $2^n subsets of X and is union-closed since the union of any two subsets is itself a subset.[11] In this family, every element x \in X belongs to exactly $2^{n-1} sets, yielding a uniform frequency of $1/2.[11]Union-closed families can be generated by selecting a generating collection of sets (such as singletons) and iteratively adding all unions of existing sets until the family stabilizes under the union operation.[2]
Basic Results
Union-closed families possess several elementary structural properties arising directly from their defining closure under unions. Specifically, such a family \mathcal{F} is closed under arbitrary finite unions: if A_1, A_2, \dots, A_k \in \mathcal{F} for finite k \geq 1, then \bigcup_{i=1}^k A_i \in \mathcal{F}. This follows by induction from the binary union closure, as the union of the first two sets is in \mathcal{F}, and iteratively adjoining the remaining sets preserves membership.[2]Every union-closed family \mathcal{F} is generated by its minimal elements, defined as the sets in \mathcal{F} that cannot be expressed as the (non-trivial) union of two other distinct sets in \mathcal{F}. The family \mathcal{F} then consists precisely of all possible unions of subsets of these minimal elements (where the empty union corresponds to \emptyset if it belongs to \mathcal{F}). If the minimal elements are pairwise disjoint, this generation yields exactly $2^m distinct sets, where m is the number of minimal elements; in general, overlaps may reduce the size below this bound. Consequently, |\mathcal{F}| \leq 2^{|\mathcal{X}|}, where \mathcal{X} is the ground set, with equality achieved for the full power set \mathcal{P}(\mathcal{X}), which is union-closed.[2][12]The inclusion of the empty set \emptyset in a union-closed family \mathcal{F} has a direct impact on element frequencies. The frequency f(x) of an element x \in \mathcal{X} is the number of sets in \mathcal{F} containing x, so \emptyset contributes to |\mathcal{F}| but not to any f(x). Thus, f(x) \leq |\mathcal{F}| - 1 for all x when \emptyset \in \mathcal{F}, and the relative frequency f(x)/|\mathcal{F}| satisfies f(x)/|\mathcal{F}| \leq (|\mathcal{F}| - 1)/|\mathcal{F}| < 1. In this case, \emptyset is the unique overall minimal element, and the rest of \mathcal{F} is generated by non-empty unions of the other minimal elements. This adjustment to frequencies motivates consideration of the empty set in analyses of union-closed families, particularly relative to the conjecture's frequency threshold.[2][12]For families excluding \emptyset, all sets are non-empty, and generation proceeds via non-empty unions of the minimal elements, ensuring every set in \mathcal{F} contains at least one minimal element. The overall size bound |\mathcal{F}| \leq 2^{|\mathcal{X}|} still holds, but the structure emphasizes the role of the minimal generators without the empty union.[2]
Equivalent Formulations
Intersection Formulation
An intersection-closed family of sets \mathcal{F} \subseteq 2^X is a collection such that for all A, B \in \mathcal{F}, the intersection A \cap B \in \mathcal{F}. This property is the natural dual to closure under unions, reflecting the De Morgan duality between union and intersection operations in set theory.[2]The union-closed sets conjecture admits an equivalent formulation in terms of intersection-closed families: In any finite intersection-closed family \mathcal{F} \subseteq 2^X with |\mathcal{F}| \geq 2, there exists an element x \in X that belongs to at most |\mathcal{F}|/2 of the sets in \mathcal{F}. This asserts the existence of a "rare" element in the dual setting, contrasting with the "frequent" element guaranteed by the original conjecture.[2]The equivalence between the two formulations arises from the complement operation on a fixed universe X. If \mathcal{F} is a finite union-closed family on X with \emptyset \notin \mathcal{F}, then the family \mathcal{G} = \{X \setminus A : A \in \mathcal{F}\} is intersection-closed, since (X \setminus A) \cap (X \setminus B) = X \setminus (A \cup B) and A \cup B \in \mathcal{F} implies the intersection belongs to \mathcal{G}. The key duality is that an element x \in X belongs to a set A \in \mathcal{F} if and only if x \notin X \setminus A \in \mathcal{G}. Thus, the frequency f(x) = |\{A \in \mathcal{F} : x \in A\}| in the union-closed family satisfies f(x) = |\mathcal{F}| - g(x), where g(x) = |\{B \in \mathcal{G} : x \in B\}| is the frequency in the intersection-closed family. Therefore, the existence of x with f(x) \geq |\mathcal{F}|/2 in \mathcal{F} is equivalent to the existence of x with g(x) \leq |\mathcal{F}|/2 in \mathcal{G}.[2] This complement duality provides a direct bridge, allowing results in one formulation to transfer to the other via this frequency relation.
Lattice Formulation
The lattice formulation of the union-closed sets conjecture reframes the problem in terms of abstract lattice theory, where union-closed families of sets naturally give rise to join-semilattices under the partial order of inclusion, with the join operation defined by set union. This algebraic perspective generalizes the Boolean lattice of subsets, in which up-sets (principal filters and their unions) are precisely the union-closed families closed under supersets. In the Boolean lattice B_n on n elements, the principal filter generated by a join-irreducible element (a singleton \{x\}) has size exactly |B_n|/2 = 2^{n-1}, illustrating the conjecture's bound with equality for these generators.[13]The precise statement of the conjecture in lattice terms is: Every finite lattice L with |L| \geq 2 contains a join-irreducible element j such that the principal filter \uparrow j = \{ y \in L \mid y \geq j \} satisfies |\uparrow j| \leq |L|/2. A join-irreducible element in a lattice is a non-bottom element that cannot be expressed as the join of two strictly smaller elements. This reformulation is equivalent to the original union-closed sets conjecture.[13][14]The equivalence arises from the correspondence between lattices and set families: given a finite lattice L, one can associate to each element x \in L the set S(x) consisting of the join-irreducible elements z \leq x; the collection \{ S(x) \mid x \in L \} forms an intersection-closed family, and the dual nature of the problem (via complements) links it back to union-closed families. In distributive lattices, which include those generated by joins from a set of atoms (analogous to unions from singletons), this structure aligns directly with the set-theoretic view, where atoms play the role of basic elements.[2]
Graph-Theoretic Formulation
The graph-theoretic formulation of the union-closed sets conjecture reinterprets the problem in terms of bipartite graphs, specifically the incidence graph of the set family. Consider a finite union-closed family \mathcal{F} of subsets of a universe X, with |\mathcal{F}| = n \geq 1. The incidence bipartite graph G of \mathcal{F} has bipartition (X, \mathcal{F}), where there is an edge between an element x \in X and a set A \in \mathcal{F} if and only if x \in A.[15][16]In this graph G, the degree of a vertex x \in X is precisely the frequency of x in \mathcal{F}, that is, the number of sets in \mathcal{F} containing x. The original conjecture thus asserts that the maximum degree among vertices in X is at least n/2. The union-closed property ensures that G satisfies additional structural conditions: for any two vertices A, B \in \mathcal{F} that are non-adjacent (meaning A \not\subseteq B and B \not\subseteq A), their neighborhoods N(A) and N(B) are such that no vertex in X is adjacent to both unless it aligns with the union structure, implying connectivity properties in the complement.[15][16]A more general graph-theoretic reformulation, equivalent to the conjecture, shifts focus to maximal independent sets (also called maximal stable sets) in arbitrary finite bipartite graphs. An independent set in a bipartite graph is a set of vertices with no edges between them. A vertex v is rare if it belongs to at most half of the maximal independent sets of the graph. The reformulated conjecture states that every finite bipartite graph with at least one edge has a rare vertex in each partite set. For the incidence graph G of a union-closed family \mathcal{F}, the maximal independent sets correspond bijectively to the sets in the downward closure or related structures, and a rare vertex on the \mathcal{F}-side equates to an element on the X-side appearing in at least n/2 sets, recovering the original statement.[15][16][17]This bipartite perspective highlights degree conditions tied to the union-closure: the family \mathcal{F} induces a clutter (an antichain of sets under inclusion) in its minimal elements, and the conjecture implies that the maximum degree on the element side exceeds the average, with connectivity in G ensuring no isolated components violate the frequency bound. Alternatively, viewing \mathcal{F} as a poset under inclusion, the width (by Dilworth's theorem) relates to the minimal number of chains covering frequencies, but the core insight remains the degree threshold in the incidence graph.[15][16]
Partial Results
Early Bounds and Structural Theorems
Early efforts to resolve the union-closed sets conjecture yielded important structural insights and weaker quantitative bounds on the maximum frequency of an element in the family.A foundational structural result is due to Poonen, who characterized union-closed families as those generated by unions of a basis subfamily consisting of pairwise incomparable sets, reducing the conjecture to properties of this generating basis.[18] This core subfamily, formed by the minimal elements under inclusion that generate the entire family via unions, allows many proofs and counterexample analyses to focus on smaller generating structures rather than the full family.[18]Lo Faro's theorem provides key properties of minimal counterexamples, assuming the conjecture fails for a family with the smallest number of sets. Specifically, any such minimal counterexample must satisfy separation properties: for the set I of elements common to all maximal sets in the family, each element x \in I is separated by distinct sets in the quotient family, meaning there exist sets A_i such that A_i contains x but A_i \setminus \{x\} does not, and these quotients are unique for different x.[19] Moreover, Lo Faro showed that minimal counterexamples have at least 46 member sets and the universe size satisfies |X| \leq 4|F| - 1, implying the conjecture holds for all families with fewer than 46 sets.[20]Early quantitative bounds emerged from extremal set theory techniques. Knill proved that in any nontrivial union-closed family \mathcal{F} with |\mathcal{F}| = n > 1, there exists an element belonging to at least (n-1)/\log_2 n sets, yielding a proportion of at least roughly $1/\log_2 n.[21] This logarithmic bound was improved by Wójcik, who established a maximum frequency of at least $2.4 n / \log_2 n for sufficiently large n.[2]A notable structural theorem by Brualdi and Yang, in the context of modular lattices, shows that if no element appears in at least half the sets, the family admits a large collection of disjoint pairs of sets whose unions cover the family efficiently, providing insight into potential counterexample structures.[2] These results collectively establish that the conjecture holds in many restricted cases and offer tools for analyzing general families through reduction to cores and separation conditions.
Recent Advances (2022 Onward)
In November 2022, Justin Gilmer, a researcher at Google DeepMind, made the first major breakthrough by establishing a constant lower bound for the conjecture using an information-theoretic approach. Specifically, he proved that in any nonempty union-closed family \mathcal{F} \subseteq 2^{}, there exists an element i \in contained in at least 0.01 fraction of the sets in \mathcal{F}.[5] This result improved upon previous bounds that were only \Omega(1/\log |\mathcal{F}|), providing the first dimension-independent constant and sparking renewed interest in the problem.[5]Gilmer's method relied on the contrapositive, showing via entropy arguments that if no element appears in more than 1% of the sets, then the entropy of the union of two independent samples from the family exceeds that of a single sample, leading to a contradiction under certain probabilistic assumptions.[5] Shortly thereafter, in late 2022, Will Sawin refined this technique by sharpening a key inequality, improving the bound to \frac{3 - \sqrt{5}}{2} \approx 0.382.[6] Further optimizations followed, with Lei Yu deriving dimension-free bounds independent of the ground set size n, achieving approximately 0.382 through numerical evaluation of auxiliary random variables in the entropyframework.[22]Subsequent works in 2023 and 2024 continued these refinements using similar probabilistic and optimization methods. For instance, Stijn Cambie summarized the rapid progress, noting improvements to about 0.38234 via dependent random variables and entropy compression techniques, while also exploring offspring conjectures like variants for intersection-closed families that admit constant bounds.[23] In 2023, Jingbo Liu further improved the bound to approximately 0.38271 using a conditionally independent and identically distributed (IID) coupling approach.[24] Additional contributions included hypergraph Turán-type results for constructing extremal families and AI-assisted explorations of the optimization landscape, though the core conjecture remains open.[23] In 2024, Ryan Alweiss, Brice Huang, and Mark Sellke verified a conjectured inequality from Gilmer's work computationally, rigorously establishing the \frac{3 - \sqrt{5}}{2} bound without numerical hypotheses.[25]These advances highlight the power of information theory and numerical optimization in tackling the problem, shifting focus from logarithmic to near-constant guarantees and suggesting potential paths toward the full 1/2 bound, though significant gaps persist.[23]
History and Context
Origins and Initial Work
The union-closed sets conjecture was formulated by Péter Frankl in late 1979 during a flight from Paris to Montreal, as part of his investigations into traces of finite sets aimed at improving extremal bounds in set theory. This work sought to extend insights from the Erdős–Ko–Rado theorem, which characterizes maximum intersecting families where every pair of sets shares a common element, by exploring analogous structural properties in families closed under unions rather than intersections.The conjecture first appeared in print in 1985, reported by Dwight Duffus in the proceedings published in 1985 of a NATO Advanced Study Institute workshop on graphs and orders held in Banff, Canada, in 1984, and edited by Ivan Rival. Frankl referenced the problem in several of his papers throughout the 1980s, including discussions on union-free set families and extremal problems, but no formal proofs or significant progress toward resolution were attempted during this initial period.Central motivations for the conjecture lay in probing the inherent symmetry and uniformity within union-closed families, where the closure property imposes a lattice-like structure that might guarantee balanced element frequencies. Additionally, Frankl's early considerations hinted at potential applications to coding theory, particularly in analyzing constant-weight codes and error-correcting properties derived from set system symmetries.
Key Milestones and Open Questions
In the 1990s, significant structural insights into potential counterexamples to the conjecture were provided by Giovanni Lo Faro, who proved that any minimal counterexample must contain a set of size at least 9 and established bounds on the sizes of sets within such families. These results, building on earlier work, ruled out small-scale counterexamples and highlighted the conjecture's robustness for families with limited set sizes. Further structural theorems by Lo Faro emphasized the absence of certain configurations, such as isolated small sets, in minimal counterexamples.During the 2000s, progress shifted toward quantitative bounds, with Oliver Knill establishing a lower bound of \Omega(1 / \log_2 |\mathcal{F}|) on the frequency of the most common element in any union-closed family \mathcal{F}, using probabilistic arguments over the family structure.[26] This was refined by Tomasz Wójcik in 1999, who improved the constant factors in similar logarithmic bounds through combinatorial analysis of union operations.[26] These weak bounds, while far from the conjectured 1/2, provided the first non-trivial guarantees and motivated entropy-based approaches in later decades.A major breakthrough occurred in 2022 when Justin Gilmer proved the first constant lower bound, showing that in any non-empty finite union-closed family, some element appears in at least 0.01 (or 1/100) of the sets, employing a novel entropy maximization technique over the poset of the family.[5] This result, stemming from Gilmer's background in machine learning at Google Brain, dramatically strengthened prior logarithmic bounds and sparked renewed interest, with subsequent improvements including a bound of approximately 0.38 by Alweiss, Huang, and Sellke in 2024.[25] Gilmer's method has since been extended to dimension-free settings, yielding bounds independent of the underlying ground set size.[27]Key open questions surrounding the conjecture include whether the 1/2 bound is tight beyond the power set example, where each element appears in exactly half the sets, and if there exist families where the maximum frequency approaches but does not reach 1/2 from below.[28] Variants for infinite union-closed families fail, as observed by Barry Poonen, who constructed counterexamples where no element appears in more than a vanishing proportion of the sets.[2] Other extensions explore alternative closure operations, such as intersection-closed families, and connections to probabilistic or algorithmic settings.The conjecture's difficulty arises from its resemblance to Sperner's theorem on antichains, but with unions generating a distributive lattice rather than intersections preserving independence, making direct extremal methods inapplicable; notably, no counterexamples exist despite extensive searches.[2] This lack of counterexamples, combined with the conjecture's simplicity, underscores its elusiveness, as partial results cover special cases like principal filters but not general families.Current efforts include computational verifications using proof assistants like Isabelle/HOL to check frequent-element properties in complex families, as demonstrated by Marić, Živković, and Vučković.[2] Seminars and talks in 2023, such as those at Rutgers and the IBS Discrete Math Seminar, have explored hypergraph reformulations for potential full proofs, while Gilmer's AI-inspired techniques suggest broader interdisciplinary applications.[29][30]