# Proof of sparsification lemma: What exactly does the $\pi$ operator do?

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)$$?

• 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. – Derek Elkins Aug 24 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}$$.
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$$.