Noam Ta-Shma, an Israeli high school student (and son of Amnon), recently posted a new proof of the isolation lemma. The MVV proof is not particularly complicated but it does require feeling very comfortable with independent random variables. Ta-Shma's proof is a more straight-forward combinatorial argument.

Suppose you have a set system over a universe of n elements. Give each element i, a weight w

_{i}uniformly chosen between 1 and m. The weight of a set is the sum of the weights of the elements of that set. Ta-Shma shows that there is a unique minimum weighted set with probability at least (1-1/m)

^{n}, which beats out the bound of (1-n/m) given by MVV.

Here is a sketch of his proof: Suppose all the w

_{i}'s had weights between 2 and m. Let S be the lexicographically minimal weight set given these weights. Consider the function φ(w), defined on weights with all the w

_{i}at least 2, as the following:

- φ(w)
_{i}= w_{i}-1 if i is in S - φ(w)
_{i}= w_{i}if i is not in S

Note that S is the unique minimal set now in the weights φ(w)

_{i}. Moreover φ is 1-1 for we can recover w from φ(w) by taking the unique minimal weight set in φ(w) and adding one to the weight of each element in that set.
So we have the probability that random weights yield a unique minimum set is at least

|range(φ)|/m

^{n}= |domain(φ)|/m^{n}= (m-1)^{n}/m^{n}= (1-1/m)^{n}.
Read all the details in Ta-Shma's paper.

Typoe: MVV is 1-n/m and not 1-m/n.

ReplyDeleteThanks. Fixed.

DeleteTa-Shma is the Newton of our times.

ReplyDelete