Probabilistic many-to-one matching

Question

Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the remaining edges. Is it true that as $n\rightarrow\infty$, the probability that there exists a matching between $A$ and $B$, such that each vertex in $A$ is matched to exactly $f(n)$ vertices in $B$, approaches $1$?

The case $f(n)=1$ is settled positively by Erdős and Rényi's 1964 paper On Random Matrices. (See also this question.) If $f(n)$ is polynomial in $n$, we can divide $B$ into $f(n)$ groups of $n$ vertices each and perform the matching for each group separately. By the union bound, the probability of failing still vanishes. However, what if $f(n)$ is exponential in $n$? Intuitively it should even be easier to find a matching, but this approach no longer works. Is there a reference for this generalization?

Answer 1

The probability that a single vertex in $B$ has zero neighbours in $A$ is $(1-p)^n > 0$, and these events are independent for distinct elements of $B$. So if $f(n)$ is sufficiently large you expect to have an isolated vertex, which rules out having a matching of the desired form. Thus the failure of the union bound is in a sense a true feature of the problem, and the intuition that a larger $f$ makes things easier is flawed.