2
$\begingroup$

[Updated question]

A Dynkin System is, provided all sets are finite, a collection of subsets of a universal set closed under complements with the universal set and closed under union of disjoint sets.

In particular, every Dynkin system contains the universal set and the empty set.

Fix a finite set $\Omega$ and let $\mathcal E$ be any set of subsets of $\Omega$. Let $\delta(\mathcal E)$ be the Dynkin system generated by $\mathcal E$. This is the intersection of all Dynkin systems on $\Omega$ that contain $\mathcal E$.

The sets in the Dynkin system $\delta(\mathcal E)$ are partially ordered by inclusion. Its minimal element is the empty set and its maximal element is $\Omega$.

Question: Is there an efficient algorithm to determine the atoms of $\delta(\mathcal E)$, that is, the elements which contain no other set of $\delta(\mathcal E)$ except the empty set?

Note that this set may be much smaller than the full Dynkin system. For example, the Dynkin system generated by $n$ distinct elements is the Boolean algebra of cardinality $2^n$. See below for a further example.

In the previous formulation, kept below for reference, I did not assume that the universal set is in $\mathcal E$. Therefore, the resulting set is not a Dynkin system. However, for my application, I can in fact assume that the universal set is in $\mathcal E$.

[Original question]

A Sperner family is a family $\mathcal F$ of subsets of a finite set in which none of the sets contains another.

Suppose that $\mathcal E$ is any finite set of finite sets. For any two elements $A$ and $B$ of $\mathcal E$ such that $A\subsetneq B$, add $B\setminus A$ to $\mathcal E$. Repeat this process until no new elements are added. Then return the minimal elements of $\mathcal E$ with respect to inclusion (which is a Sperner family).

Question: is there an efficient algorithm to obtain this set? Does this procedure have a name?

My first idea was to proceed as follows:

  • create the poset whose elements are the sets in $\mathcal E$, ordered by containment
  • while there is a covering relation $A\subset B$, delete $B$ from the poset, and add $B\setminus A$.

I implicitly assumed that it would not matter which relation is chosen. Unfortunately, this is wrong. A colleague found the following counterexample: $$ \mathcal E = \{\{1,2,3,4\}, \{1,2\}, \{1,4\}\} $$ The desired output is $$ \{\{1,2\}, \{2,3\}, \{3,4\}, \{1,4\}\}. $$

Following the (incorrect) algorithm above, choosing the relation $\{1,2\}\subset\{1,2,3,4\}$ first, we only obtain $$ \{\{1,2\}, \{3,4\}, \{1,4\}\}. $$

$\endgroup$
8
  • $\begingroup$ It is also possible to create an $O(n+d)$ algorithm, where $d$ is the number of elements from $\mathcal{E}$ that have a common intersection. $\endgroup$
    – nir shahar
    Sep 30 '21 at 14:48
  • $\begingroup$ @InuyashaYagami: what I am currently doing is to create the poset, collect all the covering relations of the minimal elements, replace those, and repeat until there are no relations left. Possibly this is good enough. Its complexity is unclear to me, because it may happen that a replacement creates more relations, but I admit that it doesn't look so bad experimentally. $\endgroup$ Sep 30 '21 at 15:11
  • $\begingroup$ @nirshahar: could you please expand? $\endgroup$ Sep 30 '21 at 15:11
  • $\begingroup$ @MartinRubey Your algorithm always converges since the size of a set is always decreasing. If there are $n$ sets in $\mathcal{E}$, and the ground set has $m$ elements, then the running time of your algorithm is $O(mn) $ X time to find sets $A \subset B$ in $\mathcal{E}$. But this algorithm is inefficient. $\endgroup$ Sep 30 '21 at 17:52
  • $\begingroup$ Thinking back at this, there also needs to be a factor of the amount of values in $\cup\mathcal{E}$ (the union of all sets in $\mathcal{E}$). The simple solution of mapping elements from $\cup\mathcal{E}$ to their respective sets, and applying the operations only between sets that have a common element. This would result in a fairly weird complexity, which we might write as $O(\sum_{x\in \cup\mathcal{E}} d^2_x)$ where $d_x$ is the number of sets that contain $x$. So please disregard my previous comment about a solution in $O(n+d)$ since it doesn't take into account such factors. $\endgroup$
    – nir shahar
    Sep 30 '21 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.