Sökning: onr:"swepub:oai:DiVA.org:umu-167631" >
Extremal Union-Clos...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Nyckelord
- Family of sets
- Union-closed sets
- Normal and irreducible families
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas