Extremal Union-Closed Set Families

Guantao Chen, Hein van der Holst, Alexandr Kostochka, Nana Li

Research output: Contribution to journalArticlepeer-review


A family of finite sets is called union-closed if it contains the union of any two sets in it. The Union-Closed Sets Conjecture of Frankl from 1979 states that each union-closed family contains an element that belongs to at least half of the members of the family. In this paper, we study structural properties of union-closed families. It is known that under the inclusion relation, every union-closed family forms a lattice. We call two union-closed families isomorphic if their corresponding lattices are isomorphic. Let F be a union-closed family and ⋃ F FF be the universe of F. Among all union-closed families isomorphic to F, we develop an algorithm to find one with a maximum universe, and an algorithm to find one with a minimum universe. We also study properties of these two extremal union-closed families in connection with the Union-Closed Set Conjecture. More specifically, a lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained.

Original languageEnglish (US)
Pages (from-to)1495-1502
Number of pages8
JournalGraphs and Combinatorics
Issue number6
StatePublished - Nov 1 2019


  • Family of sets
  • Normal and irreducible families
  • Union-closed sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Extremal Union-Closed Set Families'. Together they form a unique fingerprint.

Cite this