"Minimal Cover" in Finite Collection of Sets?

  • Context: Undergrad 
  • Thread starter Thread starter WWGD
  • Start date Start date
  • Tags Tags
    Finite Sets
Click For Summary
SUMMARY

The discussion focuses on finding a minimal collection of sets from a finite collection \( S_1, \ldots, S_n \) whose union equals \( \cup S_j \). A key insight is that if \( S_i \subset \cup S_{j \neq i} \) holds for all \( i \), then \( S_i \) must be included in the minimal cover. Additionally, the condition \( S_i \not\subset S_j \) for each pair of sets \( S_i, S_j \) allows for the removal of redundant sets, streamlining the process of determining the minimal cover.

PREREQUISITES
  • Understanding of set theory and unions
  • Familiarity with minimal systems of representatives
  • Knowledge of pairwise disjoint sets
  • Basic problem-solving skills in combinatorial optimization
NEXT STEPS
  • Research the concept of minimal systems of representatives in combinatorial set theory
  • Study algorithms for finding minimal covers in finite collections of sets
  • Explore techniques for transforming sets into pairwise disjoint sets
  • Investigate the implications of set inclusion on minimal cover problems
USEFUL FOR

Mathematicians, computer scientists, and anyone involved in combinatorial optimization or set theory who seeks to understand minimal covers in finite collections of sets.

WWGD
Science Advisor
Homework Helper
Messages
7,798
Reaction score
13,096
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
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.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 2 ·
Replies
2
Views
4K
  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 12 ·
Replies
12
Views
3K
  • · Replies 12 ·
Replies
12
Views
3K
Replies
1
Views
1K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 8 ·
Replies
8
Views
3K