Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

Question

I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):

"More precisely, for any polynomially bounded collection of weight assignments $\{w_i\}$ $i \in [n^c]$ with weight range $[n^{c'}]$, there exists a family $F$ of subsets of $[n]$ such that for all $j \in [n^c]$, there exists two minimal weight subsets with respect to $w_j$.

They claim that this follows from a counting argument that uses the existence of $2^{(2^n)}$ set systems. The article they cite does not contain a proof of this assertion.

Question: What proof are they thinking of? Why is their claim true?

Answer 1

I learned the following argument from Dieter van Melkebeek (but any mistakes are my own). I'm not sure that this is what Arvind and Mukhopadhyay had in mind, because the assumptions are not the same, as I point out after the argument. I am still interested in learning alternative proofs.

The idea will be to start with the collection of all subsets, and iteratively fix it by removing subsets until the conditions are satisfied. This is similar to the deletion method from the probabilistic method.

We will iterate the following algorithm:

F := Powerset([n])
While there is some i in [n^c] such that w_i makes F min unique:
    Update F by removing the element with min w_i weight.  

It suffices to show that this algorithm terminates with a non-empty set $F$.

To wit, note that each time we find such an $i$, the minweight of $F$ under $w_i$ increases by at least $1$. Since the max weight of any set under $w_i$ is $n^{c' + 1}$, this means that for each weight $w_i$, we can update $F$ at most $n^{c' + 1}$ times during the algorithm. Thus, in total $F$ is updated at most $n^{ c + c' + 1}$ times. Since each step removes one set from $F$, this means that $F$ is nonempty at the end of the procedure provided that $2^n > n^{ c + c' + 1}$.

Additionally, at the end of the process $F$ can be culled to size at most $2n^{c}$, by picking two min-weight sets for each $w_i$ $i \in [n^c]$.

Since we delete up to $n^{c + c' + 1}$ sets from $F$, we only need to work with a universe of set systems of size ${2^n \choose n^{c + c' + 1} } = O( 2^{(n^{c + c' + 2})})$. This makes me think that this argument is not the one that uses the fact that there are $2^{2^n}$ set systems.