We are currently learning derandomization, which aims to transfer a probabilistic proof into a deterministic algorithm. My problem is as follows.
Given $n$, constructs in time polynomial in $n$, a family $\mathcal{F}\subset 2^{[n]}$ of $n^{10}$ subsets, where each $F\in\mathcal{F}$ contains at most $10\log n$ elements satisfying:
For every family $\mathcal{G}$ of $n$ subsets, each of cardinality $n/2$, there is an $F\in\mathcal{F}$ that intersects all such $n$ subsets.
I found the following theorem could be useful: (corollary 9.2.8 of 'probabilistic method' by N. Alon and Spencer)
Let $G=(V,E)$ be an $n$-vertex, $d$-regular graph with the second largest eigenvalue at most $\lambda.$ If $C\subset V$ contains $cn$ vertices and
$$(1-c)d+c\lambda\leq\frac{d}{\sqrt{2}},$$
then for every $l$, the probability that a randomly chosen walk of length $l$ in $G$ avoids $C$ is at most $2^{-l/2}.$
If we take $l=10\log n$ and $c=1/2$ and $G=K_n$, then the condition is satisfied. And the probability that a random walk avoids $C$ is $\leq2^{-l/2}=n^{-5}.$ Even $\mathcal{F}$ contains $n$ such $C$'s, the possibility that a walk intersects all of them is at least $1-n^{-4}>0.$
My questions are:
- How to transform the above argument into finding a possible walk for a given $\mathcal{G}$
- How to find $n^{10}$ such walks that works for all possible $\mathcal{G}$?
