In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$:

For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family of all sets $S$ in $\mathcal{F}$, such that no other set $S'$ in $\mathcal{F}$ is a proper subset of $S$.

I am trying to understand what this operator does. So far, I thought that it could be calculated by the following algorithm:

$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_i$$

By the rest of the proof seems to indicate that actually, one has to remove the superset: $$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_j$$

Which leads me to believe that I did not fully understand the description of the operator. What would be an algorithm to calculate that $\pi(F)$?

  • 2
    $\begingroup$ Writing it this way is confusing (or wrong). $\mathcal F$ is fixed, you aren't changing that. It would be clearer to say that $\pi(\mathcal F)=\mathcal G$ and you apply your algorithm to $\mathcal G$ with $\mathcal G$ initialized to $\mathcal F$. At that point the issue Tassle brings up becomes clear as we're then asking that no set in $\mathcal F$ is contained by a set in $\mathcal G$. Removing $S_i$ from $\mathcal G$ doesn't remove it from $\mathcal F$ so doesn't help at all. $\endgroup$ – Derek Elkins left SE Aug 24 '19 at 23:58

From the definition you gave, the supersets have to be removed, as you want to keep only those sets for which there is no proper subset in $\mathcal{F}$.

For example:

enter image description here

In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.