"Minimal Cover" in Finite Collection of Sets?

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.
  • #1
WWGD
Science Advisor
Gold Member
7,007
10,465
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:
Physics news on Phys.org
  • #2
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.

Similar threads

A Minimal Covering Set: System of Distinct Representatives
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
935
I Collection of finite unions of half-open intervals form an algebra
    • Topology and Analysis
Replies
3
Views
199
I How to determine if a set is a semiring or a ring?
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
A proof that a union of compact spaces is compact
    • Calculus and Beyond Homework Help
Replies
12
Views
1K
I Two basic results from measure theory -- on volumes of rectangles
    • Topology and Analysis
Replies
2
Views
137
I Direct limit of multiverse models of ZFC
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
MHB Can a finite collection of open discs cover a given set in two dimensions?
    • Math POTW for University Students
Replies
1
Views
1K
MHB Finding a Minimal Vertex Cover & Max Sets for a Graph
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
My proof of the Geometry-Real Analysis theorem
    • Calculus and Beyond Homework Help
Replies
1
Views
654
A Formal axiom systems and the finite/infinite sets
    • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K

Hot Threads

Recent Insights

Back
Top