New proof of the Isolation Lemma

Let $E$ be a fixed set of $|E|=n$ elements, and $\f$ be a family of subsets of $E$. An $m$-weighting (or just a weighting) is an assignment $x:E\to [m]=\{1,\ldots,m\}$ of integer weights to the elements in $E$. The weight of a subset $S\subseteq E$ is then the total number $x(S)=\sum_{e\in S}x(e)$ of its elements. Let $\Min{\f}{x}$ denote the family of sets in $\f$ receiving the smallest weight under $x$. A weighting $x$ is isolating, if $|\Min{\f}{x}|=1$, i.e. if the minimum weight is achieved on a unique set in $\f$. A random $m$-weighting is a uniformly distributed weighting $x:E\to [m]$, with each weight-sequence taken independently with probability $m^{-n}$.

Isolation Lemma (minimization): For every family $\f\subseteq 2^{E}$, and a random $m$-weighting $x$, we have \[ \prob{|\Min{\f}{x}|=1}\geq \left(1-\frac{1}{m}\right)^n\geq 1-\frac{n}{m}. \]

The latter inequality here follows from the Bernoulli inequality $(1+a)^n\geq 1+na$ valid for any natural number $n\geq 1$ and any real number $a\geq -1$. That the probability is at least $1-n/m$ was proved by K. Mulmuley, U.Vazirani, and V.Vazirani (1987); see Lemma 11.5 in the 2nd edition, or Lemma 12.5 in the 1st edition.

By a different argument, Noam Ta-Shma (2015) obtained a stronger estimate $(1-1/m)^n$, which makes sense even when $m < n$.

Proof: We can assume w.l.o.g. that $\f$ is an anti-chain, i.e. that no set in $\f$ is a proper subset of another set in $\f$: the larger sets can be removed without affecting $|\Min{\f}{x}|$.

Let $X$ be the set of all $|X|=m^n$ weightings $x:E\to[m]$, and $Y$ the set of $|Y|=(m-1)^n$ weightings $y:E\to \{2,3,\ldots,m\}$. Define a mapping $\phi:Y\ni y\mapsto x_y\in X$ as follows: given a weighting $y\in Y$, fix an arbitrary set $S_y\in\Min{\f}{y}$, and define the weighting $x=x_y$ to be \[ x(e)=\begin{cases} y(e)-1 & \mbox{if $e\in S_y$,}\\ y(e) & \mbox{otherwise.} \end{cases} \] We claim that:

If $y\in Y$ and $x=x_y$, then $|\Min{\f}{x}|=1$.
$\phi$ is one-to-one on $Y$.

Together this already gives \[ \prob{|\Min{\f}{x}|=1}\overset{(1)}{\geq} \frac{|\phi(Y)|}{|X|} \overset{(2)}{=} \frac{|Y|}{|X|} =\left(1-\frac{1}{m}\right)^n\,. \] We are left with proving the claims. To see Claim 1, take a weighting $y\in Y$, and let $x=x_y$ be the corresponding weighting in $X$. Notice that for all $S\in\f$, $x(S)=y(S)-|S\cap S_y|$. Thus, for all $S\in\f$, $S\neq S_y$, we have \[ x(S_y)=y(S_y)-|S_y| \leq y(S)-|S_y| < y(S)-|S\cap S_y|=x(S)\,, \] where the first inequality holds because $S_y\in\Min{\f}{y}$, i.e. $S_y$ gives minimal weight under $y$, and the second inequality because the set $S_y$ is not contained in other set in $\f$ and therefore $|S\cap S_y|<|S_y|$. The second claim follows from the first one. If $y\in Y$ then, by Claim 1, there is a unique set $S_y\in\f$ achieving the minimum value under $x=x_y$. If we take $x_y$ and increment the weight it gives to $S_y$, we recover the weighting $y$. Thus, $x_y$ determines $y$. $\Box$

Of course, a similar argument yields the isolation lemma for the maximization problem. Let $\Max{\f}{x}$ denote the family of sets in $\f$ receiving the largest weight under $x$.

Isolation Lemma (maximization): For every family $\f\subseteq 2^{E}$, and a random $m$-weighting $x$, we have \[ \prob{|\Max{\f}{x}|=1}\geq \left(1-\frac{1}{m}\right)^n\geq 1-\frac{n}{m}. \]

The proof is almost the same, but let's do it.

Proof: As before, we can assume w.l.o.g. that $\f$ is an anti-chain, i.e. that no set in $\f$ is a proper subset of another set in $\f$: the smaller sets can be removed without affecting $|\Max{\f}{x}|$.

Let $X$ be the set of all $|X|=m^n$ weightings $x:E\to[m]$, and $Y$ the set of $|Y|=(m-1)^n$ weightings $y:E\to \{1,\ldots,m-1\}$. Define a mapping $\phi: Y\ni y\mapsto x_y\in X$ as follows: given a weighting $y\in Y$, fix an arbitrary set $S_y\in\Max{\f}{y}$, and define the weighting $x=x_y$ to be \[ x(e)=\begin{cases} y(e)+1 & \mbox{if $e\in S_y$,}\\ y(e) & \mbox{otherwise.} \end{cases} \] We claim that:

If $y\in Y$ and $x=x_y$, then $|\Max{\f}{x}|=1$.
$\phi$ is one-to-one on $Y$.

Together this already gives \[ \prob{|\Max{\f}{x}|=1}\geq \frac{|\phi(Y)|}{|X|} = \frac{|Y|}{|X|} =\left(1-\frac{1}{m}\right)^n\,. \] We again are only left with proving the claims. To see Claim (i), take a weighting $y\in Y$, and let $x=x_y$ be the corresponding weighting in $X$. Notice that for all $S\in\f$, $x(S)=y(S)+|S\cap S_y|$. Thus, for all $S\in\f$, $S\neq S_y$, we have \[ x(S_y)=y(S_y)+|S_y| \geq y(S)+|S_y| > y(S)+|S\cap S_y|=x(S)\,, \] where the first inequality holds because $S_y\in\Max{\f}{y}$, i.e. $S_y$ gives maximal weight under $y$, and the second inequality because the set $S_y$ is not contained in other set in $\f$ and therefore $|S_y|> |S\cap S_y|$. The second claim follows from the first one. If $y\in Y$ then, by Claim (i), there is a unique set $S_y\in\f$ achieving the maximum value under $x=x_y$. If we take $x_y$ and decrement the weight it gives to $S_y$, we recover the weighting $y$. Thus, $x_y$ determines $y$. $\Box$

S. Jukna, May 8, 2015