 Solution

For fixed $k$-element subsets $U,V$, their rectangle is empty with probability $(1-p{)}^{k^2}$. A union bound over at most $n^{2k}$ choices gives $P(A)\le n^{2k}(1-p{)}^{k^2}$. For a specified vertex and a specified $(n-k)$-subset, the chance of no edges is $(1-p{)}^{n-k}$. There are at most $n\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le n^{k+1}$ choices on each side, givingFor $n\ge 6$, $k=\lceil \sqrt{n}\rceil \le n/2$ and $k^2\ge n$. Hence $P(A\cup B\cup C)<3n^{2k}(1-p{)}^{n/2}$. The logarithm of this bound is $\log 3+2k\log n+(n/2)\log (1-p)$, which tends to $-\infty$ because $\sqrt{n}\log n=o(n)$. Thus the bad-event probability tends to zero.

The printed phrase “almost surely” must mean asymptotically almost surely as $n\to \infty$. At any fixed $n$, the empty graph has positive probability $(1-p{)}^{n^2}$, so the literal probability-one assertion is false.

When no bad event occurs, verify Hall's marriage theorem. If $0<|U|\le k$, each vertex has more than $k$ neighbors because event $B$ is absent, so $|N(U)|\ge |U|$. If $k<|U|\le n-k$, a failure would leave at least $k$ vertices outside $N(U)$, producing a forbidden empty $k$-square. If $|U|>n-k$, every vertex in $Y$ meets $U$ because event $C$ is absent; hence $N(U)=Y$. The empty set also satisfies Hall. Therefore the graph has a perfect matching whenever the three events are absent, proving the random bipartite matching from empty-rectangle exclusion result with probability tending to one.