4
$\begingroup$

(This is a refined version of https://cs.stackexchange.com/q/144371)

Let $\Omega$ be a finite set. A Dynkin system on $\Omega$ is a subset of the power set of $\Omega$ containing $\Omega$, which is closed under complements in $\Omega$ and which is closed under union of disjoint sets.

Given any subset $\mathcal E$ of the power set of $\Omega$, there is a unique minimal Dynkin system $\delta(\mathcal E)$, the Dynkin system generated by $\mathcal E$.

I am interested in a good algorithm that determines the elements of $\delta(\mathcal E)\setminus\{\emptyset\}$ which are minimal with respect to inclusion.

For example, given $$ \mathcal E = \{\{1,2,3,4\}, \{1,2,3\}, \{2,3,4\}\} $$ the minimal elements of the generated Dynkin system are $$ \{\{1\}, \{2,3\}, \{4\}\}. $$

Currently, I do not even have a good algorithm to check whether a subset of $\Omega$ is the set of minimal elements of $\delta(\mathcal E)\setminus\{\emptyset\}$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think your example is a bit misleading, because the minimal elements are disjoint. In the case of the Dynkin system $\{\{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,2,3,4\}\}$, do you consider your minimal elements to be these four pairs? $\endgroup$
    – Pierre PC
    Commented Oct 8, 2021 at 8:46
  • $\begingroup$ Yes, the minimal elements (atoms, actually) would be the pairs $\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$. Indeed, any set partition $\mathcal E$ of $\Omega$ generates a Dynkin system such that the minimal elements of $\delta(\mathcal E)\setminus\{\emptyset\}$ are the blocks of $\mathcal E$, but these are the less interesting Dynkin systems. $\endgroup$
    – Martin Rubey
    Commented Oct 8, 2021 at 9:11

0

Reset to default

You must log in to answer this question.