HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatoperatorlemmadoessparsificationexactlyproof

Problem

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

Solution

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:

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$.

Context

StackExchange Computer Science Q#113037, answer score: 4

Revisions (0)

No revisions yet.