Union-closed sets conjecture

In combinatorics, the union-closed sets conjecture is an elementary problem, posed by Péter Frankl in 1979 and still open. A family of sets is said to be union-closed if the union of any two sets from the family remains in the family. The conjecture states:

For every finite union-closed family of finite sets, other than the family containing only the empty set, there exists an element that belongs to at least half of the sets in the family.

Unsolved problem in mathematics:
If any two sets in some finite family of sets have a union that also belongs to the family, must some element belong to at least half of the sets in the family?
(more unsolved problems in mathematics)

Equivalent forms

If F is a union-closed family of sets, the family of complement sets to sets in F is closed under intersection, and an element that belongs to at least half of the sets of F 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.

Although stated above in terms of families of sets, Frankl's conjecture has also been formulated and studied as a question in lattice theory. A lattice is a partially ordered set in which for two elements x and y there is a unique greatest element less than or equal to both of them (the meet of x and y) and a unique least element greater than or equal to both of them (the join 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 set-theoretic intersection and the join is represented by the set-theoretic union; a lattice formed in this way is called a Boolean lattice. 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[1] but remains open in the general case.

Another equivalent formulation of the union-closed sets conjecture uses graph theory. In an undirected graph, an independent set is a set of vertices no two of which are adjacent to each other; an independent set is maximal 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 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 odd cycle, 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 bipartite graphs, 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 chordal bipartite graphs, bipartite series-parallel graphs, and bipartite graphs of maximum degree three.[2]

Families known to satisfy the conjecture

The conjecture has been proven for many special cases of union-closed set families. In particular, it is known to be true for

  • families of at most 46 sets.[3]
  • families of sets whose union has at most 11 elements.[4]
  • families of sets in which the smallest set has one or two elements.[5]
  • families of at least subsets of an -element set, for some constant .[6]

History

Péter Frankl stated the conjecture, in terms of intersection-closed set families, in 1979, and so the conjecture is usually credited to him and sometimes called the Frankl conjecture. The earliest publication of the union-closed version of the conjecture appears to be by Duffus (1985).

Notes
  1. Abe (2000); Poonen (1992); Reinhold (2000)
  2. Bruhn et al. (2015).
  3. Roberts & Simpson (2010).
  4. Bošnjak & Marković (2008), improving previous bounds by Morris (2006), Lo Faro (1994) and others.
  5. 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.
  6. Karpas (2017).
gollark: It's a Rust library for parallel iterators.
gollark: I mean, the matcher isn't parallel because it needs to know about previously bound bindings, but the reduction-rule-applier is.
gollark: Much. Ish. Kind of.
gollark: It was trivial via rayon and the fact that subexpressions don't depend on each other.
gollark: (although that only becomes obvious when it gets stuck in horrible infinite loops due to misprogrammed rules)

References
  • Abe, Tetsuya (2000). "Strong semimodular lattices and Frankl's conjecture". Algebra Universalis. 44 (3–4): 379–382. doi:10.1007/s000120050195.CS1 maint: ref=harv (link)
  • Bošnjak, Ivica; Marković, Peter (2008). "The 11-element case of Frankl's conjecture". Electronic Journal of Combinatorics. 15 (1): R88.CS1 maint: ref=harv (link)
  • 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.CS1 maint: ref=harv (link)
  • Duffus, D. (1985). Rival, I. (ed.). Open problem session. Graphs and Order. D. Reidel. p. 525.CS1 maint: ref=harv (link)
  • Karpas, Ilan (2017). "Two Results on Union-Closed Families". arXiv:1708.01434. Bibcode:2017arXiv170801434K. Cite journal requires |journal= (help)CS1 maint: ref=harv (link)
  • Lo Faro, Giovanni (1994). "Union-closed sets conjecture: improved bounds". J. Combin. Math. Combin. Comput. 16: 97–102. MR 1301213.CS1 maint: ref=harv (link)
  • Morris, Robert (2006). "FC-families and improved bounds for Frankl's conjecture". European Journal of Combinatorics. 27 (2): 269–282. arXiv:math/0702348. doi:10.1016/j.ejc.2004.07.012. MR 2199779.CS1 maint: ref=harv (link)
  • Poonen, Bjorn (1992). "Union-closed families". Journal of Combinatorial Theory. Series A. 59 (2): 253–268. doi:10.1016/0097-3165(92)90068-6. MR 1149898.CS1 maint: ref=harv (link)
  • Reinhold, Jürgen (2000). "Frankl's conjecture is true for lower semimodular lattices". Graphs and Combinatorics. 16 (1): 115–116. doi:10.1007/s003730050008.CS1 maint: ref=harv (link)
  • Roberts, Ian; Simpson, Jamie (2010). "A note on the union-closed sets conjecture" (PDF). Australas. J. Combin. 47: 265–267.CS1 maint: ref=harv (link)
  • Sarvate, D. G.; Renaud, J.-C. (1989). "On the union-closed sets conjecture". Ars Combin. 27: 149–153. MR 0989460.CS1 maint: ref=harv (link)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.