1

Given a finite group of finite sets $\mathcal{A}$, how to find a smallest group of finite sets $\mathcal{B}$, such that for any finite set $A\in\mathcal{A}$, $A$ can be expressed by the union of some finite sets $B_1,B_2,\cdots,B_n\in\mathcal{B}$?

Obviously, $\mathcal{A}$ itself is an answer, so such a $\mathcal{B}$ exists. Another answer is the group of atoms, (the maximal subgroups of $\mathcal{A}$ such that the intersection of each subgroup is nonempty, and the atoms are just those intersections). I emphasize that $\mathcal{B}\subset \mathcal{A}$ is not necessary. Thus, this problem is different from the topology basis, which requires that the basis elements are open.

My question is, is there a method to get at least one smallest union basis ($\mathcal{B}$) just like one gets bases for vector space? Which mathematical branch does this problem belong to? Thank you.

ljw
  • 21
  • 3
  • 1
    If everything is involving finite stuff, and you're looking for lower/upper bounds on size, then it is almost definitely *not* set theory. – Asaf Karagila May 07 '22 at 08:13

1 Answers1

1

I have found the answer.

L. J. Stockmeyer, The minimal set basis problem is NP-complete, Research Rep., RC5431, IBM, 1975, May

http://scholar.google.com/scholar?hl=en&q=L.+J.+Stockmeyer%2C+The+minimal+set+basis+problem+is+NP-complete%2C+Research+Rep.%2C+RC5431%2C+IBM%2C+1975%2C+May

ljw
  • 21
  • 3
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community May 29 '22 at 16:43