A Problem about a theorem proved by Razborov in 1990

Question

Consider the family of all pairs $(A,B)$ of disjoint k-element subsets of $\left\lbrace 1, 2, ..., n \right\rbrace$. We say that a set $Y$ separates the pair $(A,B)$ if $A \subset Y, B \cap Y= \emptyset$. Razborov proved that there exists $l=2k 4^k \ln n$ sets such that every pair $(A,B)$ is separated by at least one of them.

Now I shall show you what I did. We pick $l$ subsets of $\left\lbrace 1, 2, ..., n \right\rbrace$ randomly and independently, each with probability $2^{-n}$. Then the probability that none of these $l$ sets separates a given pair $(A,B)$, denoted by p,

$$p=\prod_{i=1}^l Pr((A \nsubseteq Y) \land (B \cap Y \ne \emptyset)) \le \prod_{i=1}^l (1-2^{-2k})=(1-2^{-2k})^l<1, \forall l $$

So with positive probability, at least one of $l$ sets we choose separates $(A,B)$. That means $\exists$ a family $\cal{F}$ of $l$ sets s.t. at least one of them separates $(A,B)$. This comes to be a contradiction because no limit on $l$ at all. This is obviously wrong, but I don't know where I made a mistake. Could you please help me?

Answer 1

First, we have $\binom{n}{k}\binom{n-k}{k}=\frac{n(n-1)\cdots(n-2k+1)}{k!k!}$ pairs. I want to choose the sets $Y_i$ with following rules, $i=1,2,...,l$. Any number in $[n]$ is selected to form $Y_i$ with possibility of $\frac{1}{2}$ independently. Let $Y=\{Y_1,Y_2,...,Y_l\}$. Fix $(A,B)$. The possibility that $Y_1$ can seperate $(A,B)$, which means $A \subset Y_1$ and $B \cap Y_1= \varnothing$, is $\frac{1}{2^{2k}}$, so the possibility that $Y_1$ cannot seperate $(A,B)$ is $1-\frac{1}{2^{2k}}$. Therefore, for any $i\in[l]$, the possibility that $Y_i$ cannot seperate $(A,B)$ is $(1-\frac{1}{2^{2k}})^l$. Because we have $\frac{n(n-1)\cdots(n-2k+1)}{k!k!}$ pairs, so $$\begin{aligned} (1-\frac{1}{2^{2k}})^l\cdot\frac{n(n-1)\cdots(n-2k+1)}{k!k!}&<(1-\frac{1}{2^{2k}})^l\cdot n(n-1)\cdots(n-2k+1)\\ &<(1-\frac{1}{2^{2k}})^l\cdot n^{2k} \\ &=n^{2k\cdot4^k\ln(1-\frac{1}{4^k})+2k} \\ &<n^{2k\cdot4^k(-\frac{1}{4^k})+2k}=1 \end{aligned}.$$ Let $X_{(A,B)}$ be the event that $(A,B)$ cannot be seperated by any element in $Y$ and $X$ be the event that there is at least one pair cannot be seperated by any element in $Y$. So, $P(X)=P(\bigcup_{A\neq B\in\binom{[n]}{k}}X_{(A,B)})\leqslant \sum_{A\neq B\in\binom{[n]}{k}}^{}P(X_{(A,B)})=(1-\frac{1}{2^{2k}})^l\cdot\frac{n(n-1)\cdots(n-2k+1)}{k!k!}<1$, which means that $P(X^C)>0$.

Answer 2

The probabilistic strategy is this; you compute the expected number of "bad" pairs which are not separated by your random family. If the expected number of bad pairs is less than one, then you can conclude that there must exists a particular random choice where there are zero bad pairs, meaning all pairs are separated.

As you noted, the probability a particular pair is bad is $(1-4^{-k})^\ell$. Since there are $\binom{n}k\binom {n-k}k$ pairs, the expected number of bad pairs is $$ \binom nk\binom{n-k}k(1-4^{-k})^\ell $$

Using the crude upper bound $\binom nk \binom{n-k}k\le n^{2k}$, and the inequality $$ (1-4^{-k})= [(1-4^{-k})^{4^k}]^{4^{-k}}\le \exp(-4^{-k}), $$ the expected number of bad pairs is at most $$ n^{2k}\cdot \exp(-\ell \cdot 4^{-k}) $$ In order for this quantity to be less than one, it suffices to have $\ell \ge 2k\cdot 4^k\cdot \log n$.