# "Minimal Cover" in Finite Collection of Sets?

• WWGD
In summary, the conversation discusses finding the minimal collection of sets whose union is a given set, when the sets are not all pairwise disjoint. The participants suggest the possibility of making the sets pairwise-disjoint or using results related to minimal systems of representatives. An intermediate step is also proposed, where the problem is repeatedly restricted until a certain condition is met. It is also mentioned that for each pair of sets, one is not a subset of the other.
WWGD
Gold Member
Hi All,
Say we have a finite collection ## S_1,...,S_n ## of sets , which are not all pairwise disjoint , and we want
to find the minimal collection of the ## S_j ## whose union is ## \cup S_j ## . Is there
any theorem, result to this effect?

I would imagine that making the ## S_j## pairwise-disjoint would help. Is there some other way?
I think I remember some results about results elated to minimal systems of representatives, maybe would also work?

Last edited:
An interesting problem!
I don't have a full solution but here is an intermediate step:

Without loss of generality, you can assume that ##S_i \subset \cup S_{j\neq i}## for all i. If this would be wrong, you know Si has to be part of the minimal cover, this allows to restrict the problem to the subproblem without that Si and its elements. This step can be repeated until the first condition is true, or the remaining collection of sets is empty.

Also, for each pair of sets Si, Sj, ##S_i \not\subset S_j## otherwise you can remove Si.

## 1. What is a minimal cover in a finite collection of sets?

A minimal cover in a finite collection of sets is a subset of the collection that contains the same elements as the original collection, but with the fewest number of sets possible. This means that no set in the minimal cover can be removed without changing the overall contents of the collection.

## 2. How is a minimal cover different from a minimum cover?

A minimal cover is a subset of a collection of sets that contains the same elements as the original collection, while a minimum cover is the smallest possible number of sets that can cover all the elements in the collection. This means that a minimum cover may not necessarily contain all the sets in the original collection, but it will still cover all the elements.

## 3. What is the significance of finding a minimal cover in a finite collection of sets?

Finding a minimal cover in a finite collection of sets is important because it can help reduce the complexity of the collection and make it easier to work with. It can also help identify redundant or unnecessary sets in the collection, which can save time and resources when working with the collection.

## 4. How is a minimal cover calculated?

A minimal cover is typically calculated using an algorithm, such as the Greedy Algorithm or the Set Cover Algorithm. These algorithms use a step-by-step process to identify and remove redundant sets from the collection, resulting in a minimal cover.

## 5. Can a minimal cover be unique?

Yes, a minimal cover can be unique. However, in some cases, there may be multiple minimal covers for a given collection of sets. This can happen when there are multiple ways to group the sets in the collection without losing any elements. In these cases, any of the minimal covers can be considered valid.

• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Topology and Analysis
Replies
3
Views
673
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
12
Views
2K
• Topology and Analysis
Replies
2
Views
473
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Math POTW for University Students
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
777
• Set Theory, Logic, Probability, Statistics
Replies
10
Views
2K