3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.