The union basis of a group of finite sets

32 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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