Extremal Union-Closed Set Families

• 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 boolean OR(F is an element of F) F 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.

Subject headings

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Keyword

Family of sets

Union-closed sets

Normal and irreducible families

Publication and Content Type

ref (subject category)

art (subject category)