Union-closed sets conjecture

<h2 id="example">Example</h2>
The family of sets

∅
        ,
        {
        1
        }
        ,
        {
        1
        ,
        2
        }
        ,
        {
        2
        ,
        3
        ,
        4
        }
        ,
        {
        1
        ,
        2
        ,
        3
        ,
        4
        }
      
    
    {\displaystyle \varnothing ,\{1\},\{1,2\},\{2,3,4\},\{1,2,3,4\}}

consists of five different sets and is union-closed. The element 
 
 
 
 1
 
 
 {\displaystyle 1}
 
 is contained in three of the five sets (and so is the element 
 
 
 
 2
 
 
 {\displaystyle 2}
 
), thus the conjecture holds in this case.

<h2 id="basic-results">Basic results</h2>
It is easy to show that if a union-closed family contains a <a href="/facts/Singleton_(mathematics)/LtNVfujT">singleton</a> 
 
 
 
 {
 a
 }
 
 
 {\displaystyle \{a\}}
 
 (as in the example above), then the element 
 
 
 
 a
 
 
 {\displaystyle a}
 
 must occur in at least half of the sets of the family.
If there is a <a href="/facts/Counterexample/dnThYpHW">counterexample</a> to the conjecture, then there is also a counterexample consisting only of finite sets. Therefore, without loss of generality, we will assume that all sets in the given union-closed family are finite.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
Given a finite non-empty set 
 
 
 
 U
 
 
 {\displaystyle U}
 
, the <a href="/facts/Power_set/FVuf8PDD">power set</a> 
 
 
 
 P
 (
 U
 )
 
 
 {\displaystyle P(U)}
 
 consisting of all <a href="/facts/Subset/SJGERmbA">subsets</a> of 
 
 
 
 U
 
 
 {\displaystyle U}
 
 is union-closed. Each element of 
 
 
 
 U
 
 
 {\displaystyle U}
 
 is contained in exactly half of the subsets of 
 
 
 
 U
 
 
 {\displaystyle U}
 
. Therefore, in general we cannot ask for an element contained in more than half of the sets of the family: the <a href="/facts/Upper_and_lower_bounds/YJje9oC2">bound</a> of the conjecture is sharp.

<h2 id="equivalent-forms">Equivalent forms</h2>
<h3>Intersection formulation</h3>
The union-closed set conjecture is true <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> a set system 
 
 
 
 X
 
 
 {\displaystyle X}
 
 which is intersection-closed contains an element of 
 
 
 
 U
 (
 X
 )
 
 
 {\displaystyle U(X)}
 
 in at most half of the sets of 
 
 
 
 X
 
 
 {\displaystyle X}
 
, where 
 
 
 
 U
 (
 X
 )
 
 
 {\displaystyle U(X)}
 
 is the universe set, i.e. the union of all members of the system 
 
 
 
 X
 
 
 {\displaystyle X}
 
.
The following facts show the equivalence.
Firstly, we show that a set system is union-closed if and only if its complement is intersection-closed.
Lemma 1. If 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a union-closed family of sets with universe 
 
 
 
 U
 (
 X
 )
 
 
 {\displaystyle U(X)}
 
, the family of <a href="/facts/Complement_set/yWUePIYY">complement sets</a> to sets in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is closed under <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a>.
Proof.
We define the complement of the set system 
 
 
 
 X
 
 
 {\displaystyle X}
 
 as 
 
 
 
 
 X
 
 c
 
 
 :=
 {
 U
 (
 X
 )
 −
 S
 :
 S
 ∈
 X
 }
 
 
 {\displaystyle X^{c}:=\{U(X)-S:S\in X\}}
 
. 
Let 
 
 
 
 
 X
 
 1
 
 
 
 
 {\displaystyle X_{1}}
 
, 
 
 
 
 
 X
 
 2
 
 
 
 
 {\displaystyle X_{2}}
 
 be arbitrary sets in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and so 
 
 
 
 U
 (
 X
 )
 −
 
 X
 
 1
 
 
 
 
 {\displaystyle U(X)-X_{1}}
 
 and 
 
 
 
 U
 (
 X
 )
 −
 
 X
 
 2
 
 
 
 
 {\displaystyle U(X)-X_{2}}
 
 are both in 
 
 
 
 
 X
 
 c
 
 
 
 
 {\displaystyle X^{c}}
 
. Since 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is union-closed, 
 
 
 
 
 X
 
 1
 
 
 ∪
 
 X
 
 2
 
 
 =
 
 X
 
 3
 
 
 
 
 {\displaystyle X_{1}\cup X_{2}=X_{3}}
 
 is in 
 
 
 
 X
 
 
 {\displaystyle X}
 
, and therefore the complement of 
 
 
 
 
 X
 
 3
 
 
 
 
 {\displaystyle X_{3}}
 
, 
 
 
 
 U
 (
 X
 )
 −
 
 X
 
 3
 
 
 
 
 {\displaystyle U(X)-X_{3}}
 
 is in 
 
 
 
 
 X
 
 c
 
 
 
 
 {\displaystyle X^{c}}
 
, the elements in neither 
 
 
 
 
 X
 
 1
 
 
 
 
 {\displaystyle X_{1}}
 
, nor 
 
 
 
 
 X
 
 2
 
 
 
 
 {\displaystyle X_{2}}
 
.
And this is exactly the intersection of the complements of 
 
 
 
 
 X
 
 1
 
 
 
 
 {\displaystyle X_{1}}
 
 and 
 
 
 
 
 X
 
 2
 
 
 
 
 {\displaystyle X_{2}}
 
, 
 
 
 
 (
 U
 (
 X
 )
 −
 
 X
 
 1
 
 
 )
 ∩
 (
 U
 (
 X
 )
 −
 
 X
 
 2
 
 
 )
 
 
 {\displaystyle (U(X)-X_{1})\cap (U(X)-X_{2})}
 
. Therefore, 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is union-closed if and only if the complement of 
 
 
 
 X
 
 
 {\displaystyle X}
 
, 
 
 
 
 
 X
 
 c
 
 
 
 
 {\displaystyle 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
 
 
 {\displaystyle X}
 
 contains an element in half of its sets if and only if the complement set system 
 
 
 
 X
 
 
 {\displaystyle X}
 
, 
 
 
 
 
 X
 
 ∗
 
 
 
 
 {\displaystyle X^{*}}
 
 contains an element in at most half of its sets.
Proof. Trivial.
Therefore, if 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a union-closed family of sets, the family of complement sets to sets in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 relative to the universe 
 
 
 
 U
 (
 X
 )
 
 
 {\displaystyle U(X)}
 
 is closed under intersection, and an element that belongs to at least half of the sets of 
 
 
 
 X
 
 
 {\displaystyle 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.

<h3>Lattice formulation</h3>
Although stated above in terms of families of sets, Frankl's conjecture has also been formulated and studied as a question in <a href="/facts/Lattice_theory/5ak6ufky">lattice theory</a>. A <a href="/facts/Lattice_(order)/5ak6ufky">lattice</a> is a <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> in which for two elements x and y there is a unique greatest element less than or equal to both of them (the <a href="/facts/Meet_and_join/cYcLhRIR">meet</a> of x and y) and a unique least element greater than or equal to both of them (the <a href="/facts/Meet_and_join/cYcLhRIR">join</a> of x and y). The family of all subsets of a set S, ordered by set inclusion, forms a lattice in which the meet is represented by the <a href="/facts/Set-theoretic/1ptfsvUP">set-theoretic</a> intersection and the join is represented by the set-theoretic union; a lattice formed in this way is called a <a href="/facts/Boolean_algebra_(structure)/cHbo65jm">Boolean lattice</a>.
The lattice-theoretic version of Frankl's conjecture is that in any finite lattice there exists an element x that is not the join of any two smaller elements, and such that the number of elements greater than or equal to x totals at most half the lattice, with equality only if the lattice is a Boolean lattice. As Abe (2000) shows, this statement about lattices is equivalent to the Frankl conjecture for union-closed sets: each lattice can be translated into a union-closed set family, and each union-closed set family can be translated into a lattice, such that the truth of the Frankl conjecture for the translated object implies the truth of the conjecture for the original object. This lattice-theoretic version of the conjecture is known to be true for several natural subclasses of lattices<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> but remains open in the general case.

<h3>Graph-theoretic formulation</h3>
Another equivalent formulation of the union-closed sets conjecture uses <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>. In an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a>, an <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">Independent set</a> is a set of vertices no two of which are adjacent to each other; an independent set is <a href="/facts/Maximal_independent_set/eB4NQsny">maximal</a> if it is not a subset of a larger independent set. In any graph, the "heavy" vertices that appear in more than half of the maximal independent sets must themselves form an independent set. So, if the graph is non-empty, there always exists at least one non-heavy vertex, a vertex that appears in at most half of the maximal independent sets. The graph formulation of the union-closed sets conjecture states that every finite non-empty graph contains two adjacent non-heavy vertices. It is automatically true when the graph contains an <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd</a> <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle</a>, because the independent set of all heavy vertices cannot cover all the edges of the cycle. Therefore, the more interesting case of the conjecture is for <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a>, which have no odd cycles. Another equivalent formulation of the conjecture is that, in every bipartite graph, there exist two vertices, one on each side of the bipartition, such that each of these two vertices belongs to at most half of the graph's maximal independent sets. This conjecture is known to hold for <a href="/facts/Chordal_bipartite_graph/cQYSheFr">chordal bipartite graphs</a>, bipartite <a href="/facts/Series%25E2%2580%2593parallel_graph/XdfWgomL">series–parallel graphs</a>, and bipartite graphs of maximum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> three.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="partial-results">Partial results</h2>
The conjecture has been proven for many special cases of union-closed set families. In particular, it is known to be true for

<ul><li>families of at most 46 sets,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>families of sets whose union has at most 12 elements,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>families of sets in which the smallest set has one or two elements,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li>families of at least 
 
 
 
 (
 
 
 
 1
 2
 
 
 
 −
 ε
 )
 
 2
 
 n
 
 
 
 
 {\displaystyle ({\tfrac {1}{2}}-\varepsilon )2^{n}}
 
 subsets of an 
 
 
 
 n
 
 
 {\displaystyle n}
 
-element set, for some constant 
 
 
 
 ε
 >
 0
 
 
 {\displaystyle \varepsilon >0}
 
, according to an unpublished preprint.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>families of sets with short chain no more than 3 or long chain no less than 
 
 
 
 n
 −
 1
 
 
 {\displaystyle n-1}
 
.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li></ul>
Additionally, for every union-closed family, other than the family containing only the empty set, there exists an element that belongs to at least a fraction of 0.38234 of the sets in the family.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="history">History</h2>
<a href="/facts/P%25C3%25A9ter_Frankl/GpakDRMh">Péter Frankl</a> stated the conjecture in terms of intersection-closed set families in 1979, and so the conjecture is usually credited to him and is sometimes referred to as the Frankl conjecture. The earliest publication of the union-closed version of the conjecture appears to be by Duffus (1985). A history of the work on the conjecture up to 2013 was published by Bruhn & Schaudt (2015).

<h2 id="notes">Notes</h2>

<ul><li>Abe, Tetsuya (2000). "Strong semimodular lattices and Frankl's conjecture". Algebra Universalis. 44 (3–4): 379–382. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs000120050195">10.1007/s000120050195</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:120741780">120741780</a>.</li>
<li>Vuckovic, Bojan; Zivkovic, Miodrag (2017). <a href="https://ipsitransactions.org/journals/papers/tir/2017jan/p9.pdf">"The 12-Element Case of Frankl's Conjecture"</a> (PDF). IPSI BGD Transactions on Internet Research. 13 (1): 65.</li>
<li>Bošnjak, Ivica; Marković, Peter (2008). <a href="http://www.combinatorics.org/Volume_15/Abstracts/v15i1r88.html">"The 11-element case of Frankl's conjecture"</a>. <a href="/facts/Electronic_Journal_of_Combinatorics/lHJkJW01">Electronic Journal of Combinatorics</a>. 15 (1): R88. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.37236%2F812">10.37236/812</a>.</li>
<li>Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne (2015). "The graph formulation of the union-closed sets conjecture". <a href="/facts/European_Journal_of_Combinatorics/a6jNXFuH">European Journal of Combinatorics</a>. 43: 210–219. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1212.4175">1212.4175</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2014.08.030">10.1016/j.ejc.2014.08.030</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=3266293">3266293</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2373192">2373192</a>.</li>
<li>Bruhn, Henning; Schaudt, Oliver (2015-11-01). <a href="https://doi.org/10.1007/s00373-014-1515-0">"The Journey of the Union-Closed Sets Conjecture"</a>. Graphs and Combinatorics. 31 (6): 2043–2074. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1309.3297">1309.3297</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00373-014-1515-0">10.1007/s00373-014-1515-0</a>.</li>
<li><a href="/facts/Dwight_Duffus/HScwYNC0">Duffus, D.</a> (1985). <a href="/facts/Ivan_Rival/adGRLxnU">Rival, I.</a> (ed.). Open problem session. Graphs and Order. D. Reidel. p. 525.</li>
<li>Karpas, Ilan (2017). "Two Results on Union-Closed Families". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1708.01434">1708.01434</a> [<a href="https://arxiv.org/archive/math.CO">math.CO</a>].</li>
<li>Tian, Chenxiao (2021). "Union-closed Sets Conjecture Holds for Height H(𝓕)≤ 𝟑 and H(𝓕)≥ 𝐧 - 𝟏". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2112.06659">2112.06659</a> [<a href="https://arxiv.org/archive/math.CO">math.CO</a>].</li>
<li>Lo Faro, Giovanni (1994). "Union-closed sets conjecture: improved bounds". J. Combin. Math. Combin. Comput. 16: 97–102. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1301213">1301213</a>.</li>
<li><a href="/facts/Robert_Morris_(mathematician)/gDosa5Pp">Morris, Robert</a> (2006). "FC-families and improved bounds for Frankl's conjecture". <a href="/facts/European_Journal_of_Combinatorics/a6jNXFuH">European Journal of Combinatorics</a>. 27 (2): 269–282. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/0702348">math/0702348</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2004.07.012">10.1016/j.ejc.2004.07.012</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2199779">2199779</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17633023">17633023</a>.</li>
<li><a href="/facts/Bjorn_Poonen/H9o7mHkf">Poonen, Bjorn</a> (1992). <a href="https://doi.org/10.1016%2F0097-3165%2892%2990068-6">"Union-closed families"</a>. <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>. Series A. 59 (2): 253–268. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0097-3165%2892%2990068-6">10.1016/0097-3165(92)90068-6</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1149898">1149898</a>.</li>
<li>Reinhold, Jürgen (2000). "Frankl's conjecture is true for lower semimodular lattices". <a href="/facts/Graphs_and_Combinatorics/kQJQ9uUy">Graphs and Combinatorics</a>. 16 (1): 115–116. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs003730050008">10.1007/s003730050008</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12660895">12660895</a>.</li>
<li>Roberts, Ian; Simpson, Jamie (2010). <a href="http://ajc.maths.uq.edu.au/pdf/47/ajc_v47_p265.pdf">"A note on the union-closed sets conjecture"</a> (PDF). Australas. J. Combin. 47: 265–267.</li>
<li>Sarvate, D. G.; Renaud, J.-C. (1989). "On the union-closed sets conjecture". Ars Combin. 27: 149–153. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0989460">0989460</a>.</li>
<li>Yu, Lei (2023). <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10217025">"Dimension-free bounds for the union-closed sets conjecture"</a>. Entropy. 25 (5): 767. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2212.00658">2212.00658</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2023Entrp..25..767Y">2023Entrp..25..767Y</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.3390%2Fe25050767">10.3390/e25050767</a>. <a href="/facts/PMC_(identifier)/dX1zMt71">PMC</a> <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10217025">10217025</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/37238522">37238522</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://garden.irmacs.sfu.ca/?q=op/frankls_union_closed_sets_conjecture">Frankl's union-closed sets conjecture</a>, the Open Problem Garden.</li>
<li><a href="http://www.math.uiuc.edu/~west/openp/unionclos.html">Union-Closed Sets Conjecture (1979)</a>. In <a href="http://www.math.uiuc.edu/~west/openp/index.html">Open Problems – Graph Theory and Combinatorics</a>, collected by D. B. West.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Timothy Gowers, Tweet on 17 November 2022 <a href="https://twitter.com/wtgowers/status/1593157232543207424" target="_blank">https://twitter.com/wtgowers/status/1593157232543207424</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bruhn & Schaudt (2015). - Bruhn, Henning; Schaudt, Oliver (2015-11-01). "The Journey of the Union-Closed Sets Conjecture". Graphs and Combinatorics. 31 (6): 2043–2074. arXiv:1309.3297. doi:10.1007/s00373-014-1515-0. <a href="https://doi.org/10.1007/s00373-014-1515-0" target="_blank">https://doi.org/10.1007/s00373-014-1515-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Abe (2000); Poonen (1992); Reinhold (2000). - Abe, Tetsuya (2000). "Strong semimodular lattices and Frankl's conjecture". Algebra Universalis. 44 (3–4): 379–382. doi:10.1007/s000120050195. S2CID 120741780. <a href="https://doi.org/10.1007%2Fs000120050195" target="_blank">https://doi.org/10.1007%2Fs000120050195</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bruhn et al. (2015). - Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne (2015). "The graph formulation of the union-closed sets conjecture". European Journal of Combinatorics. 43: 210–219. arXiv:1212.4175. doi:10.1016/j.ejc.2014.08.030. MR 3266293. S2CID 2373192. <a href="https://arxiv.org/abs/1212.4175" target="_blank">https://arxiv.org/abs/1212.4175</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Roberts & Simpson (2010). - Roberts, Ian; Simpson, Jamie (2010). "A note on the union-closed sets conjecture" (PDF). Australas. J. Combin. 47: 265–267. <a href="http://ajc.maths.uq.edu.au/pdf/47/ajc_v47_p265.pdf" target="_blank">http://ajc.maths.uq.edu.au/pdf/47/ajc_v47_p265.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Vuckovic & Zivkovic (2017), improving previous bounds by Bošnjak & Marković (2008), Morris (2006), Lo Faro (1994) and others. - Vuckovic, Bojan; Zivkovic, Miodrag (2017). "The 12-Element Case of Frankl's Conjecture" (PDF). IPSI BGD Transactions on Internet Research. 13 (1): 65. <a href="https://ipsitransactions.org/journals/papers/tir/2017jan/p9.pdf" target="_blank">https://ipsitransactions.org/journals/papers/tir/2017jan/p9.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Sarvate & Renaud (1989), since rediscovered by several other authors. If a one-element or two-element set S exists, some element of S belongs to at least half the sets in the family, but the same property does not hold for three-element sets, due to counterexamples of Sarvate, Renaud, and Ronald Graham. - Sarvate, D. G.; Renaud, J.-C. (1989). "On the union-closed sets conjecture". Ars Combin. 27: 149–153. MR 0989460. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0989460" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0989460</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Karpas (2017). - Karpas, Ilan (2017). "Two Results on Union-Closed Families". arXiv:1708.01434 [math.CO]. <a href="https://arxiv.org/abs/1708.01434" target="_blank">https://arxiv.org/abs/1708.01434</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Tian (2021). - Tian, Chenxiao (2021). "Union-closed Sets Conjecture Holds for Height H(𝓕)≤ 𝟑 and H(𝓕)≥ 𝐧 - 𝟏". arXiv:2112.06659 [math.CO]. <a href="https://arxiv.org/abs/2112.06659" target="_blank">https://arxiv.org/abs/2112.06659</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Yu (2023). - Yu, Lei (2023). "Dimension-free bounds for the union-closed sets conjecture". Entropy. 25 (5): 767. arXiv:2212.00658. Bibcode:2023Entrp..25..767Y. doi:10.3390/e25050767. PMC 10217025. PMID 37238522. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10217025" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10217025</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Union-closed sets conjecture open-in-new

Union-closed sets conjecture