Derandomize this algorithm? Given an $n$-vertex set $V$ and some bipartite graphs $G_1,\dots, G_k$ on $V$. Assume $G_i$ has parts $S_i, T_i$.
A claim says that if each vertex $v\in V$ is in at least $\log_2 n$ bipartite graphs of $G_1,\dots, G_k$, then it is possible to choose either $S_i$ or $T_i$ (but not both) from each $G_i$ so that their union is $V$.
I am thinking about how to prove this claim in a deterministic way.
It can be done by the following randomized algorithm: for each $i$ we take $S_i$ (or $T_i$) with probability 1/2. Then a vertex $v$ is not covered has probability $(1/2)^{\log_2n}$ (which is less than $1/n$ if we round it up). So with probability less than 1, there is a vertex not covered. So with some choices, all vertices are covered.
 A: There are some standard ways to de-randomize algorithms like this one that come from expected value calculations.
We will go through $G_1, G_2, \dots, G_k$ one at a time to make a decision for them. To guide our decisions, let's give every vertex $v\in V$ a "danger level" $\ell(v)$, which, partway through the algorithm, will be equal to

*

*$0$, if $v$ has been covered by a part we choose from one of the bipartite graphs.

*$2^{-d}$, if there are $d$ remaining bipartite graphs containing $v$.

We will always act to choose the option which minimizes the "total danger level" $\sum_{v \in V} \ell(v)$.
Suppose we are choosing between $S_i$ and $T_i$ for graph $G_i$. Choosing $S_i$ will decrease the total danger level by $\sum_{v \in S_i} \ell(v)$, because those danger levels will be set to $0$; however, it will increase the total danger level by $\sum_{v \in T_i} \ell(v)$, because those danger levels will double. (Each one will go from $2^{-d}$ to $2^{-(d-1)}$ for some $d$.) The net change is by $(\sum_{v \in T_i} \ell(v)) - (\sum_{v \in S_i} \ell(v))$. Similarly, choosing $T_i$ will change the total danger level by $(\sum_{v \in S_i} \ell(v)) - (\sum_{v \in T_i} \ell(v))$.
These are negatives of each other. So choose $S_i$ if $\sum_{v \in S_i} \ell(v) > \sum_{v \in T_i} \ell(v)$, and $T_i$ otherwise; this guarantees that the total danger level does not increase.
Initially, the total danger level is less than $1$, because $\ell(v) < 2^{-\log_2 n} = \frac1n$ for each $v \in V$. So at the end, the total danger level is less than $1$.
However, at the end of this process, each vertex $v \in V$ has a danger level of $0$ if it has been covered and $1$ if it has not been covered. Since the total danger level is less than $1$, all vertices must be covered.
