Find $\mathcal{F}$ s.t. for each family $\mathcal{G}$ of $n$ sets each of size $n/2$, there's a $F\in \mathcal{F}$ intersecting each $G\in\mathcal{G}$

Question

Show that given $N=\{1,\ldots, n\}$, there exists a family $\mathcal{F}$ such that $|\mathcal{F}| = n^{10}$, for each $F\in \mathcal{F}$ we have $|F| \leq 10\log n$ and such that for every family $\mathcal{G}$ of $n$ subsets of $N$, each of cardinality $n/2$, there is an $F\in \mathcal{F}$ such that $F$ intersects all members of $\mathcal{G}$. Then find a deterministic polynomial time algorithm that determines such an $\mathcal{F}$.

This is a question from Alon and Spencer from a chapter on derandomization. I am having a hard time even getting started. In general, the chapter is about how we can deterministically find structures we are interested in by first showing that a suitable random structure is expected to have the desired properties. Then we make a sequence of choices that fix part of our structure in such a way that the expectation conditioned on the first choices moves in the right direction. Once all choices are made, the expectation then just counts something, which is then bounded by the bound in the random structure.

So I guess maybe we should let $\mathcal{F}$ consist of random sets of size $10\log n$. Given $F$ of size $10\log n$ selected randomly and $G$ of size $n/2$, we have \begin{equation} \mathbb{P}(F\cap G = \emptyset) = \frac{ \binom{n/2}{10\log n} }{\binom{n}{10\log n}}\sim \frac{ 1 }{2^{10\log n} }. \end{equation} Then, given a family $\mathcal{G}$ as described, we have \begin{equation} \mathbb{P}(\emptyset \notin F\cap \mathcal{G}) \geq 1-\frac{ n }{2^{10\log n} }. \end{equation} This is where I am stuck... I do not see where to get an expectation of something that I can use throughout my construction. Moreover, we cannot take $\mathcal{G}$ to be random, we need to build an $\mathcal{F}$ that works simultaneously for all $\mathcal{G}$. Also, the number of subsets of $N$ of size $n$ with each element of size $n/2$ is exponential in $n$, so I think we should be able to find some alternative sufficient condition on the $\mathcal{F}$ that we can use...

Thanks in advance for any help!

EDIT: So as per Yuval Filmus' answer, indeed the existence part is quite easy. However, it does not really help in the construction of a deterministic poly time algorithm. I think we probably need some estimates on the conditional probabilities that are computable in polytime.

Answer 1

Did you take a look at the hint provided by Alon and Spencer? I didn't work it out too formally, but I think the following roughly works: using, say, the Lubotzky or Margulis explicit construction of expanders, one may check that the preconditions for Corollary 9.2.8 in their book applies, with parameters $d=30$, $\lambda\leq 2\sqrt{30-1}=2\sqrt{29}$, $C$ an arbitrary subset of size $n/2$, and $c=\vert C\vert/n=1/2$. What that result tells you is that the probability a randomly chosen walk of length of length $2.5\log n$ avoids $C$ is at most $2^{-2.5\log n/2}=1/n^{1.25}$. In particular, for any $n$ subsets $C_1,\ldots,C_n$ all with $\vert C_i\vert=n/2$, it follows that there exists some walk of length $2.5\log n$ that intersects all of them simultaneously. The number of such walks is $30^{2.5\log n}n\leq n^{9.6}$. So the algorithm is just to use the explicit expander construction and simply list all such walks (where of course, each vertex is labeled with a unique element of $[n]$), which can evidently be done in polynomial time.

Answer 2

You have shown that the probability that a random set $F$ doesn't intersect an arbitrary $G$ is at most roughly $1/n^{10}$, and so the probability that it doesn't intersect all sets in $\mathcal G$ is at most roughly $1/n^9$. Let's call such a set bad with respect to $\mathcal G$. Hence the probability that all $n^{10}$ sets in $\mathcal F$ are bad with respect to $\mathcal G$ is at most roughly $(1/n^9)^{n^{10}}$. In contrast, the number of choices for $\mathcal{G}$ is only at most $2^{n^2}$.

This is supposed to be the easy part of the exercise. The more interesting part is to come up with an efficient algorithm that constructs $\mathcal F$.