Let $X$ and $Y$ be disjoint sets of $n \geqslant 6$ vertices each. Let $G$ be a bipartite graph formed by adding edges between $X$ and $Y$ randomly and independently with probability $p=1 / 100$. Let $e(U, V)$ be the number of edges of $G$ between the subsets $U \subset X$ and $V \subset Y$. Let $k=\left\lceil n^{1 / 2}\right\rceil$. Consider three events $\mathcal{A}, \mathcal{B}$ and $\mathcal{C}$, as follows.

$$\begin{array}{ll} \mathcal{A}: & \text { there exist } U \subset X, V \subset Y \text { with }|U|=|V|=k \text { and } e(U, V)=0 \\ \mathcal{B}: & \text { there exist } x \in X, W \subset Y \text { with }|W|=n-k \text { and } e(\{x\}, W)=0 \\ \mathcal{C}: & \text { there exist } Z \subset X, y \in Y \text { with }|Z|=n-k \text { and } e(Z,\{y\})=0 \end{array}$$

Show that $\operatorname{Pr}(\mathcal{A}) \leqslant n^{2 k}(1-p)^{k^{2}}$ and $\operatorname{Pr}(\mathcal{B} \cup \mathcal{C}) \leqslant 2 n^{k+1}(1-p)^{n-k}$. Hence show that $\operatorname{Pr}(\mathcal{A} \cup \mathcal{B} \cup \mathcal{C})<3 n^{2 k}(1-p)^{n / 2}$ and so show that, almost surely, none of $\mathcal{A}, \mathcal{B}$ or $\mathcal{C}$ occur. Deduce that, almost surely, $G$ has a matching from $X$ to $Y$.